1 // Copyright 2018 The Abseil Authors. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #ifndef ABSL_CONTAINER_INTERNAL_RAW_HASH_MAP_H_ 16 #define ABSL_CONTAINER_INTERNAL_RAW_HASH_MAP_H_ 17 18 #include <tuple> 19 #include <type_traits> 20 #include <utility> 21 22 #include "absl/base/internal/throw_delegate.h" 23 #include "absl/container/internal/container_memory.h" 24 #include "absl/container/internal/raw_hash_set.h" // IWYU pragma: export 25 26 namespace absl { 27 ABSL_NAMESPACE_BEGIN 28 namespace container_internal { 29 30 template <class Policy, class Hash, class Eq, class Alloc> 31 class raw_hash_map : public raw_hash_set<Policy, Hash, Eq, Alloc> { 32 // P is Policy. It's passed as a template argument to support maps that have 33 // incomplete types as values, as in unordered_map<K, IncompleteType>. 34 // MappedReference<> may be a non-reference type. 35 template <class P> 36 using MappedReference = decltype(P::value( 37 std::addressof(std::declval<typename raw_hash_map::reference>()))); 38 39 // MappedConstReference<> may be a non-reference type. 40 template <class P> 41 using MappedConstReference = decltype(P::value( 42 std::addressof(std::declval<typename raw_hash_map::const_reference>()))); 43 44 using KeyArgImpl = 45 KeyArg<IsTransparent<Eq>::value && IsTransparent<Hash>::value>; 46 47 public: 48 using key_type = typename Policy::key_type; 49 using mapped_type = typename Policy::mapped_type; 50 template <class K> 51 using key_arg = typename KeyArgImpl::template type<K, key_type>; 52 53 static_assert(!std::is_reference<key_type>::value, ""); 54 55 // TODO(b/187807849): Evaluate whether to support reference mapped_type and 56 // remove this assertion if/when it is supported. 57 static_assert(!std::is_reference<mapped_type>::value, ""); 58 59 using iterator = typename raw_hash_map::raw_hash_set::iterator; 60 using const_iterator = typename raw_hash_map::raw_hash_set::const_iterator; 61 raw_hash_map()62 raw_hash_map() {} 63 using raw_hash_map::raw_hash_set::raw_hash_set; 64 65 // The last two template parameters ensure that both arguments are rvalues 66 // (lvalue arguments are handled by the overloads below). This is necessary 67 // for supporting bitfield arguments. 68 // 69 // union { int n : 1; }; 70 // flat_hash_map<int, int> m; 71 // m.insert_or_assign(n, n); 72 template <class K = key_type, class V = mapped_type, K* = nullptr, 73 V* = nullptr> insert_or_assign(key_arg<K> && k,V && v)74 std::pair<iterator, bool> insert_or_assign(key_arg<K>&& k, V&& v) 75 ABSL_ATTRIBUTE_LIFETIME_BOUND { 76 return insert_or_assign_impl(std::forward<K>(k), std::forward<V>(v)); 77 } 78 79 template <class K = key_type, class V = mapped_type, K* = nullptr> insert_or_assign(key_arg<K> && k,const V & v)80 std::pair<iterator, bool> insert_or_assign(key_arg<K>&& k, const V& v) 81 ABSL_ATTRIBUTE_LIFETIME_BOUND { 82 return insert_or_assign_impl(std::forward<K>(k), v); 83 } 84 85 template <class K = key_type, class V = mapped_type, V* = nullptr> insert_or_assign(const key_arg<K> & k,V && v)86 std::pair<iterator, bool> insert_or_assign(const key_arg<K>& k, V&& v) 87 ABSL_ATTRIBUTE_LIFETIME_BOUND { 88 return insert_or_assign_impl(k, std::forward<V>(v)); 89 } 90 91 template <class K = key_type, class V = mapped_type> insert_or_assign(const key_arg<K> & k,const V & v)92 std::pair<iterator, bool> insert_or_assign(const key_arg<K>& k, const V& v) 93 ABSL_ATTRIBUTE_LIFETIME_BOUND { 94 return insert_or_assign_impl(k, v); 95 } 96 97 template <class K = key_type, class V = mapped_type, K* = nullptr, 98 V* = nullptr> insert_or_assign(const_iterator,key_arg<K> && k,V && v)99 iterator insert_or_assign(const_iterator, key_arg<K>&& k, 100 V&& v) ABSL_ATTRIBUTE_LIFETIME_BOUND { 101 return insert_or_assign(std::forward<K>(k), std::forward<V>(v)).first; 102 } 103 104 template <class K = key_type, class V = mapped_type, K* = nullptr> insert_or_assign(const_iterator,key_arg<K> && k,const V & v)105 iterator insert_or_assign(const_iterator, key_arg<K>&& k, 106 const V& v) ABSL_ATTRIBUTE_LIFETIME_BOUND { 107 return insert_or_assign(std::forward<K>(k), v).first; 108 } 109 110 template <class K = key_type, class V = mapped_type, V* = nullptr> insert_or_assign(const_iterator,const key_arg<K> & k,V && v)111 iterator insert_or_assign(const_iterator, const key_arg<K>& k, 112 V&& v) ABSL_ATTRIBUTE_LIFETIME_BOUND { 113 return insert_or_assign(k, std::forward<V>(v)).first; 114 } 115 116 template <class K = key_type, class V = mapped_type> insert_or_assign(const_iterator,const key_arg<K> & k,const V & v)117 iterator insert_or_assign(const_iterator, const key_arg<K>& k, 118 const V& v) ABSL_ATTRIBUTE_LIFETIME_BOUND { 119 return insert_or_assign(k, v).first; 120 } 121 122 // All `try_emplace()` overloads make the same guarantees regarding rvalue 123 // arguments as `std::unordered_map::try_emplace()`, namely that these 124 // functions will not move from rvalue arguments if insertions do not happen. 125 template <class K = key_type, class... Args, 126 typename std::enable_if< 127 !std::is_convertible<K, const_iterator>::value, int>::type = 0, 128 K* = nullptr> try_emplace(key_arg<K> && k,Args &&...args)129 std::pair<iterator, bool> try_emplace(key_arg<K>&& k, Args&&... args) 130 ABSL_ATTRIBUTE_LIFETIME_BOUND { 131 return try_emplace_impl(std::forward<K>(k), std::forward<Args>(args)...); 132 } 133 134 template <class K = key_type, class... Args, 135 typename std::enable_if< 136 !std::is_convertible<K, const_iterator>::value, int>::type = 0> try_emplace(const key_arg<K> & k,Args &&...args)137 std::pair<iterator, bool> try_emplace(const key_arg<K>& k, Args&&... args) 138 ABSL_ATTRIBUTE_LIFETIME_BOUND { 139 return try_emplace_impl(k, std::forward<Args>(args)...); 140 } 141 142 template <class K = key_type, class... Args, K* = nullptr> try_emplace(const_iterator,key_arg<K> && k,Args &&...args)143 iterator try_emplace(const_iterator, key_arg<K>&& k, 144 Args&&... args) ABSL_ATTRIBUTE_LIFETIME_BOUND { 145 return try_emplace(std::forward<K>(k), std::forward<Args>(args)...).first; 146 } 147 148 template <class K = key_type, class... Args> try_emplace(const_iterator,const key_arg<K> & k,Args &&...args)149 iterator try_emplace(const_iterator, const key_arg<K>& k, 150 Args&&... args) ABSL_ATTRIBUTE_LIFETIME_BOUND { 151 return try_emplace(k, std::forward<Args>(args)...).first; 152 } 153 154 template <class K = key_type, class P = Policy> at(const key_arg<K> & key)155 MappedReference<P> at(const key_arg<K>& key) ABSL_ATTRIBUTE_LIFETIME_BOUND { 156 auto it = this->find(key); 157 if (it == this->end()) { 158 base_internal::ThrowStdOutOfRange( 159 "absl::container_internal::raw_hash_map<>::at"); 160 } 161 return Policy::value(&*it); 162 } 163 164 template <class K = key_type, class P = Policy> at(const key_arg<K> & key)165 MappedConstReference<P> at(const key_arg<K>& key) const 166 ABSL_ATTRIBUTE_LIFETIME_BOUND { 167 auto it = this->find(key); 168 if (it == this->end()) { 169 base_internal::ThrowStdOutOfRange( 170 "absl::container_internal::raw_hash_map<>::at"); 171 } 172 return Policy::value(&*it); 173 } 174 175 template <class K = key_type, class P = Policy, K* = nullptr> 176 MappedReference<P> operator[](key_arg<K>&& key) 177 ABSL_ATTRIBUTE_LIFETIME_BOUND { 178 return Policy::value(&*try_emplace(std::forward<K>(key)).first); 179 } 180 181 template <class K = key_type, class P = Policy> 182 MappedReference<P> operator[](const key_arg<K>& key) 183 ABSL_ATTRIBUTE_LIFETIME_BOUND { 184 return Policy::value(&*try_emplace(key).first); 185 } 186 187 private: 188 template <class K, class V> insert_or_assign_impl(K && k,V && v)189 std::pair<iterator, bool> insert_or_assign_impl(K&& k, V&& v) 190 ABSL_ATTRIBUTE_LIFETIME_BOUND { 191 auto res = this->find_or_prepare_insert(k); 192 if (res.second) 193 this->emplace_at(res.first, std::forward<K>(k), std::forward<V>(v)); 194 else 195 Policy::value(&*this->iterator_at(res.first)) = std::forward<V>(v); 196 return {this->iterator_at(res.first), res.second}; 197 } 198 199 template <class K = key_type, class... Args> try_emplace_impl(K && k,Args &&...args)200 std::pair<iterator, bool> try_emplace_impl(K&& k, Args&&... args) 201 ABSL_ATTRIBUTE_LIFETIME_BOUND { 202 auto res = this->find_or_prepare_insert(k); 203 if (res.second) 204 this->emplace_at(res.first, std::piecewise_construct, 205 std::forward_as_tuple(std::forward<K>(k)), 206 std::forward_as_tuple(std::forward<Args>(args)...)); 207 return {this->iterator_at(res.first), res.second}; 208 } 209 }; 210 211 } // namespace container_internal 212 ABSL_NAMESPACE_END 213 } // namespace absl 214 215 #endif // ABSL_CONTAINER_INTERNAL_RAW_HASH_MAP_H_ 216