|
||||
File indexing completed on 2025-01-18 09:27:15
0001 // Copyright 2018 The Abseil Authors. 0002 // 0003 // Licensed under the Apache License, Version 2.0 (the "License"); 0004 // you may not use this file except in compliance with the License. 0005 // You may obtain a copy of the License at 0006 // 0007 // https://www.apache.org/licenses/LICENSE-2.0 0008 // 0009 // Unless required by applicable law or agreed to in writing, software 0010 // distributed under the License is distributed on an "AS IS" BASIS, 0011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 0012 // See the License for the specific language governing permissions and 0013 // limitations under the License. 0014 // 0015 // ----------------------------------------------------------------------------- 0016 // File: node_hash_map.h 0017 // ----------------------------------------------------------------------------- 0018 // 0019 // An `absl::node_hash_map<K, V>` is an unordered associative container of 0020 // unique keys and associated values designed to be a more efficient replacement 0021 // for `std::unordered_map`. Like `unordered_map`, search, insertion, and 0022 // deletion of map elements can be done as an `O(1)` operation. However, 0023 // `node_hash_map` (and other unordered associative containers known as the 0024 // collection of Abseil "Swiss tables") contain other optimizations that result 0025 // in both memory and computation advantages. 0026 // 0027 // In most cases, your default choice for a hash map should be a map of type 0028 // `flat_hash_map`. However, if you need pointer stability and cannot store 0029 // a `flat_hash_map` with `unique_ptr` elements, a `node_hash_map` may be a 0030 // valid alternative. As well, if you are migrating your code from using 0031 // `std::unordered_map`, a `node_hash_map` provides a more straightforward 0032 // migration, because it guarantees pointer stability. Consider migrating to 0033 // `node_hash_map` and perhaps converting to a more efficient `flat_hash_map` 0034 // upon further review. 0035 // 0036 // `node_hash_map` is not exception-safe. 0037 0038 #ifndef ABSL_CONTAINER_NODE_HASH_MAP_H_ 0039 #define ABSL_CONTAINER_NODE_HASH_MAP_H_ 0040 0041 #include <cstddef> 0042 #include <memory> 0043 #include <type_traits> 0044 #include <utility> 0045 0046 #include "absl/algorithm/container.h" 0047 #include "absl/base/attributes.h" 0048 #include "absl/container/hash_container_defaults.h" 0049 #include "absl/container/internal/container_memory.h" 0050 #include "absl/container/internal/node_slot_policy.h" 0051 #include "absl/container/internal/raw_hash_map.h" // IWYU pragma: export 0052 #include "absl/memory/memory.h" 0053 #include "absl/meta/type_traits.h" 0054 0055 namespace absl { 0056 ABSL_NAMESPACE_BEGIN 0057 namespace container_internal { 0058 template <class Key, class Value> 0059 class NodeHashMapPolicy; 0060 } // namespace container_internal 0061 0062 // ----------------------------------------------------------------------------- 0063 // absl::node_hash_map 0064 // ----------------------------------------------------------------------------- 0065 // 0066 // An `absl::node_hash_map<K, V>` is an unordered associative container which 0067 // has been optimized for both speed and memory footprint in most common use 0068 // cases. Its interface is similar to that of `std::unordered_map<K, V>` with 0069 // the following notable differences: 0070 // 0071 // * Supports heterogeneous lookup, through `find()`, `operator[]()` and 0072 // `insert()`, provided that the map is provided a compatible heterogeneous 0073 // hashing function and equality operator. See below for details. 0074 // * Contains a `capacity()` member function indicating the number of element 0075 // slots (open, deleted, and empty) within the hash map. 0076 // * Returns `void` from the `erase(iterator)` overload. 0077 // 0078 // By default, `node_hash_map` uses the `absl::Hash` hashing framework. 0079 // All fundamental and Abseil types that support the `absl::Hash` framework have 0080 // a compatible equality operator for comparing insertions into `node_hash_map`. 0081 // If your type is not yet supported by the `absl::Hash` framework, see 0082 // absl/hash/hash.h for information on extending Abseil hashing to user-defined 0083 // types. 0084 // 0085 // Using `absl::node_hash_map` at interface boundaries in dynamically loaded 0086 // libraries (e.g. .dll, .so) is unsupported due to way `absl::Hash` values may 0087 // be randomized across dynamically loaded libraries. 0088 // 0089 // To achieve heterogeneous lookup for custom types either `Hash` and `Eq` type 0090 // parameters can be used or `T` should have public inner types 0091 // `absl_container_hash` and (optionally) `absl_container_eq`. In either case, 0092 // `typename Hash::is_transparent` and `typename Eq::is_transparent` should be 0093 // well-formed. Both types are basically functors: 0094 // * `Hash` should support `size_t operator()(U val) const` that returns a hash 0095 // for the given `val`. 0096 // * `Eq` should support `bool operator()(U lhs, V rhs) const` that returns true 0097 // if `lhs` is equal to `rhs`. 0098 // 0099 // In most cases `T` needs only to provide the `absl_container_hash`. In this 0100 // case `std::equal_to<void>` will be used instead of `eq` part. 0101 // 0102 // Example: 0103 // 0104 // // Create a node hash map of three strings (that map to strings) 0105 // absl::node_hash_map<std::string, std::string> ducks = 0106 // {{"a", "huey"}, {"b", "dewey"}, {"c", "louie"}}; 0107 // 0108 // // Insert a new element into the node hash map 0109 // ducks.insert({"d", "donald"}}; 0110 // 0111 // // Force a rehash of the node hash map 0112 // ducks.rehash(0); 0113 // 0114 // // Find the element with the key "b" 0115 // std::string search_key = "b"; 0116 // auto result = ducks.find(search_key); 0117 // if (result != ducks.end()) { 0118 // std::cout << "Result: " << result->second << std::endl; 0119 // } 0120 template <class Key, class Value, class Hash = DefaultHashContainerHash<Key>, 0121 class Eq = DefaultHashContainerEq<Key>, 0122 class Alloc = std::allocator<std::pair<const Key, Value>>> 0123 class ABSL_INTERNAL_ATTRIBUTE_OWNER node_hash_map 0124 : public absl::container_internal::raw_hash_map< 0125 absl::container_internal::NodeHashMapPolicy<Key, Value>, Hash, Eq, 0126 Alloc> { 0127 using Base = typename node_hash_map::raw_hash_map; 0128 0129 public: 0130 // Constructors and Assignment Operators 0131 // 0132 // A node_hash_map supports the same overload set as `std::unordered_map` 0133 // for construction and assignment: 0134 // 0135 // * Default constructor 0136 // 0137 // // No allocation for the table's elements is made. 0138 // absl::node_hash_map<int, std::string> map1; 0139 // 0140 // * Initializer List constructor 0141 // 0142 // absl::node_hash_map<int, std::string> map2 = 0143 // {{1, "huey"}, {2, "dewey"}, {3, "louie"},}; 0144 // 0145 // * Copy constructor 0146 // 0147 // absl::node_hash_map<int, std::string> map3(map2); 0148 // 0149 // * Copy assignment operator 0150 // 0151 // // Hash functor and Comparator are copied as well 0152 // absl::node_hash_map<int, std::string> map4; 0153 // map4 = map3; 0154 // 0155 // * Move constructor 0156 // 0157 // // Move is guaranteed efficient 0158 // absl::node_hash_map<int, std::string> map5(std::move(map4)); 0159 // 0160 // * Move assignment operator 0161 // 0162 // // May be efficient if allocators are compatible 0163 // absl::node_hash_map<int, std::string> map6; 0164 // map6 = std::move(map5); 0165 // 0166 // * Range constructor 0167 // 0168 // std::vector<std::pair<int, std::string>> v = {{1, "a"}, {2, "b"}}; 0169 // absl::node_hash_map<int, std::string> map7(v.begin(), v.end()); 0170 node_hash_map() {} 0171 using Base::Base; 0172 0173 // node_hash_map::begin() 0174 // 0175 // Returns an iterator to the beginning of the `node_hash_map`. 0176 using Base::begin; 0177 0178 // node_hash_map::cbegin() 0179 // 0180 // Returns a const iterator to the beginning of the `node_hash_map`. 0181 using Base::cbegin; 0182 0183 // node_hash_map::cend() 0184 // 0185 // Returns a const iterator to the end of the `node_hash_map`. 0186 using Base::cend; 0187 0188 // node_hash_map::end() 0189 // 0190 // Returns an iterator to the end of the `node_hash_map`. 0191 using Base::end; 0192 0193 // node_hash_map::capacity() 0194 // 0195 // Returns the number of element slots (assigned, deleted, and empty) 0196 // available within the `node_hash_map`. 0197 // 0198 // NOTE: this member function is particular to `absl::node_hash_map` and is 0199 // not provided in the `std::unordered_map` API. 0200 using Base::capacity; 0201 0202 // node_hash_map::empty() 0203 // 0204 // Returns whether or not the `node_hash_map` is empty. 0205 using Base::empty; 0206 0207 // node_hash_map::max_size() 0208 // 0209 // Returns the largest theoretical possible number of elements within a 0210 // `node_hash_map` under current memory constraints. This value can be thought 0211 // of as the largest value of `std::distance(begin(), end())` for a 0212 // `node_hash_map<K, V>`. 0213 using Base::max_size; 0214 0215 // node_hash_map::size() 0216 // 0217 // Returns the number of elements currently within the `node_hash_map`. 0218 using Base::size; 0219 0220 // node_hash_map::clear() 0221 // 0222 // Removes all elements from the `node_hash_map`. Invalidates any references, 0223 // pointers, or iterators referring to contained elements. 0224 // 0225 // NOTE: this operation may shrink the underlying buffer. To avoid shrinking 0226 // the underlying buffer call `erase(begin(), end())`. 0227 using Base::clear; 0228 0229 // node_hash_map::erase() 0230 // 0231 // Erases elements within the `node_hash_map`. Erasing does not trigger a 0232 // rehash. Overloads are listed below. 0233 // 0234 // void erase(const_iterator pos): 0235 // 0236 // Erases the element at `position` of the `node_hash_map`, returning 0237 // `void`. 0238 // 0239 // NOTE: this return behavior is different than that of STL containers in 0240 // general and `std::unordered_map` in particular. 0241 // 0242 // iterator erase(const_iterator first, const_iterator last): 0243 // 0244 // Erases the elements in the open interval [`first`, `last`), returning an 0245 // iterator pointing to `last`. The special case of calling 0246 // `erase(begin(), end())` resets the reserved growth such that if 0247 // `reserve(N)` has previously been called and there has been no intervening 0248 // call to `clear()`, then after calling `erase(begin(), end())`, it is safe 0249 // to assume that inserting N elements will not cause a rehash. 0250 // 0251 // size_type erase(const key_type& key): 0252 // 0253 // Erases the element with the matching key, if it exists, returning the 0254 // number of elements erased (0 or 1). 0255 using Base::erase; 0256 0257 // node_hash_map::insert() 0258 // 0259 // Inserts an element of the specified value into the `node_hash_map`, 0260 // returning an iterator pointing to the newly inserted element, provided that 0261 // an element with the given key does not already exist. If rehashing occurs 0262 // due to the insertion, all iterators are invalidated. Overloads are listed 0263 // below. 0264 // 0265 // std::pair<iterator,bool> insert(const init_type& value): 0266 // 0267 // Inserts a value into the `node_hash_map`. Returns a pair consisting of an 0268 // iterator to the inserted element (or to the element that prevented the 0269 // insertion) and a `bool` denoting whether the insertion took place. 0270 // 0271 // std::pair<iterator,bool> insert(T&& value): 0272 // std::pair<iterator,bool> insert(init_type&& value): 0273 // 0274 // Inserts a moveable value into the `node_hash_map`. Returns a `std::pair` 0275 // consisting of an iterator to the inserted element (or to the element that 0276 // prevented the insertion) and a `bool` denoting whether the insertion took 0277 // place. 0278 // 0279 // iterator insert(const_iterator hint, const init_type& value): 0280 // iterator insert(const_iterator hint, T&& value): 0281 // iterator insert(const_iterator hint, init_type&& value); 0282 // 0283 // Inserts a value, using the position of `hint` as a non-binding suggestion 0284 // for where to begin the insertion search. Returns an iterator to the 0285 // inserted element, or to the existing element that prevented the 0286 // insertion. 0287 // 0288 // void insert(InputIterator first, InputIterator last): 0289 // 0290 // Inserts a range of values [`first`, `last`). 0291 // 0292 // NOTE: Although the STL does not specify which element may be inserted if 0293 // multiple keys compare equivalently, for `node_hash_map` we guarantee the 0294 // first match is inserted. 0295 // 0296 // void insert(std::initializer_list<init_type> ilist): 0297 // 0298 // Inserts the elements within the initializer list `ilist`. 0299 // 0300 // NOTE: Although the STL does not specify which element may be inserted if 0301 // multiple keys compare equivalently within the initializer list, for 0302 // `node_hash_map` we guarantee the first match is inserted. 0303 using Base::insert; 0304 0305 // node_hash_map::insert_or_assign() 0306 // 0307 // Inserts an element of the specified value into the `node_hash_map` provided 0308 // that a value with the given key does not already exist, or replaces it with 0309 // the element value if a key for that value already exists, returning an 0310 // iterator pointing to the newly inserted element. If rehashing occurs due to 0311 // the insertion, all iterators are invalidated. Overloads are listed 0312 // below. 0313 // 0314 // std::pair<iterator, bool> insert_or_assign(const init_type& k, T&& obj): 0315 // std::pair<iterator, bool> insert_or_assign(init_type&& k, T&& obj): 0316 // 0317 // Inserts/Assigns (or moves) the element of the specified key into the 0318 // `node_hash_map`. 0319 // 0320 // iterator insert_or_assign(const_iterator hint, 0321 // const init_type& k, T&& obj): 0322 // iterator insert_or_assign(const_iterator hint, init_type&& k, T&& obj): 0323 // 0324 // Inserts/Assigns (or moves) the element of the specified key into the 0325 // `node_hash_map` using the position of `hint` as a non-binding suggestion 0326 // for where to begin the insertion search. 0327 using Base::insert_or_assign; 0328 0329 // node_hash_map::emplace() 0330 // 0331 // Inserts an element of the specified value by constructing it in-place 0332 // within the `node_hash_map`, provided that no element with the given key 0333 // already exists. 0334 // 0335 // The element may be constructed even if there already is an element with the 0336 // key in the container, in which case the newly constructed element will be 0337 // destroyed immediately. Prefer `try_emplace()` unless your key is not 0338 // copyable or moveable. 0339 // 0340 // If rehashing occurs due to the insertion, all iterators are invalidated. 0341 using Base::emplace; 0342 0343 // node_hash_map::emplace_hint() 0344 // 0345 // Inserts an element of the specified value by constructing it in-place 0346 // within the `node_hash_map`, using the position of `hint` as a non-binding 0347 // suggestion for where to begin the insertion search, and only inserts 0348 // provided that no element with the given key already exists. 0349 // 0350 // The element may be constructed even if there already is an element with the 0351 // key in the container, in which case the newly constructed element will be 0352 // destroyed immediately. Prefer `try_emplace()` unless your key is not 0353 // copyable or moveable. 0354 // 0355 // If rehashing occurs due to the insertion, all iterators are invalidated. 0356 using Base::emplace_hint; 0357 0358 // node_hash_map::try_emplace() 0359 // 0360 // Inserts an element of the specified value by constructing it in-place 0361 // within the `node_hash_map`, provided that no element with the given key 0362 // already exists. Unlike `emplace()`, if an element with the given key 0363 // already exists, we guarantee that no element is constructed. 0364 // 0365 // If rehashing occurs due to the insertion, all iterators are invalidated. 0366 // Overloads are listed below. 0367 // 0368 // std::pair<iterator, bool> try_emplace(const key_type& k, Args&&... args): 0369 // std::pair<iterator, bool> try_emplace(key_type&& k, Args&&... args): 0370 // 0371 // Inserts (via copy or move) the element of the specified key into the 0372 // `node_hash_map`. 0373 // 0374 // iterator try_emplace(const_iterator hint, 0375 // const key_type& k, Args&&... args): 0376 // iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args): 0377 // 0378 // Inserts (via copy or move) the element of the specified key into the 0379 // `node_hash_map` using the position of `hint` as a non-binding suggestion 0380 // for where to begin the insertion search. 0381 // 0382 // All `try_emplace()` overloads make the same guarantees regarding rvalue 0383 // arguments as `std::unordered_map::try_emplace()`, namely that these 0384 // functions will not move from rvalue arguments if insertions do not happen. 0385 using Base::try_emplace; 0386 0387 // node_hash_map::extract() 0388 // 0389 // Extracts the indicated element, erasing it in the process, and returns it 0390 // as a C++17-compatible node handle. Overloads are listed below. 0391 // 0392 // node_type extract(const_iterator position): 0393 // 0394 // Extracts the key,value pair of the element at the indicated position and 0395 // returns a node handle owning that extracted data. 0396 // 0397 // node_type extract(const key_type& x): 0398 // 0399 // Extracts the key,value pair of the element with a key matching the passed 0400 // key value and returns a node handle owning that extracted data. If the 0401 // `node_hash_map` does not contain an element with a matching key, this 0402 // function returns an empty node handle. 0403 // 0404 // NOTE: when compiled in an earlier version of C++ than C++17, 0405 // `node_type::key()` returns a const reference to the key instead of a 0406 // mutable reference. We cannot safely return a mutable reference without 0407 // std::launder (which is not available before C++17). 0408 using Base::extract; 0409 0410 // node_hash_map::merge() 0411 // 0412 // Extracts elements from a given `source` node hash map into this 0413 // `node_hash_map`. If the destination `node_hash_map` already contains an 0414 // element with an equivalent key, that element is not extracted. 0415 using Base::merge; 0416 0417 // node_hash_map::swap(node_hash_map& other) 0418 // 0419 // Exchanges the contents of this `node_hash_map` with those of the `other` 0420 // node hash map, avoiding invocation of any move, copy, or swap operations on 0421 // individual elements. 0422 // 0423 // All iterators and references on the `node_hash_map` remain valid, excepting 0424 // for the past-the-end iterator, which is invalidated. 0425 // 0426 // `swap()` requires that the node hash map's hashing and key equivalence 0427 // functions be Swappable, and are exchanged using unqualified calls to 0428 // non-member `swap()`. If the map's allocator has 0429 // `std::allocator_traits<allocator_type>::propagate_on_container_swap::value` 0430 // set to `true`, the allocators are also exchanged using an unqualified call 0431 // to non-member `swap()`; otherwise, the allocators are not swapped. 0432 using Base::swap; 0433 0434 // node_hash_map::rehash(count) 0435 // 0436 // Rehashes the `node_hash_map`, setting the number of slots to be at least 0437 // the passed value. If the new number of slots increases the load factor more 0438 // than the current maximum load factor 0439 // (`count` < `size()` / `max_load_factor()`), then the new number of slots 0440 // will be at least `size()` / `max_load_factor()`. 0441 // 0442 // To force a rehash, pass rehash(0). 0443 using Base::rehash; 0444 0445 // node_hash_map::reserve(count) 0446 // 0447 // Sets the number of slots in the `node_hash_map` to the number needed to 0448 // accommodate at least `count` total elements without exceeding the current 0449 // maximum load factor, and may rehash the container if needed. 0450 using Base::reserve; 0451 0452 // node_hash_map::at() 0453 // 0454 // Returns a reference to the mapped value of the element with key equivalent 0455 // to the passed key. 0456 using Base::at; 0457 0458 // node_hash_map::contains() 0459 // 0460 // Determines whether an element with a key comparing equal to the given `key` 0461 // exists within the `node_hash_map`, returning `true` if so or `false` 0462 // otherwise. 0463 using Base::contains; 0464 0465 // node_hash_map::count(const Key& key) const 0466 // 0467 // Returns the number of elements with a key comparing equal to the given 0468 // `key` within the `node_hash_map`. note that this function will return 0469 // either `1` or `0` since duplicate keys are not allowed within a 0470 // `node_hash_map`. 0471 using Base::count; 0472 0473 // node_hash_map::equal_range() 0474 // 0475 // Returns a closed range [first, last], defined by a `std::pair` of two 0476 // iterators, containing all elements with the passed key in the 0477 // `node_hash_map`. 0478 using Base::equal_range; 0479 0480 // node_hash_map::find() 0481 // 0482 // Finds an element with the passed `key` within the `node_hash_map`. 0483 using Base::find; 0484 0485 // node_hash_map::operator[]() 0486 // 0487 // Returns a reference to the value mapped to the passed key within the 0488 // `node_hash_map`, performing an `insert()` if the key does not already 0489 // exist. If an insertion occurs and results in a rehashing of the container, 0490 // all iterators are invalidated. Otherwise iterators are not affected and 0491 // references are not invalidated. Overloads are listed below. 0492 // 0493 // T& operator[](const Key& key): 0494 // 0495 // Inserts an init_type object constructed in-place if the element with the 0496 // given key does not exist. 0497 // 0498 // T& operator[](Key&& key): 0499 // 0500 // Inserts an init_type object constructed in-place provided that an element 0501 // with the given key does not exist. 0502 using Base::operator[]; 0503 0504 // node_hash_map::bucket_count() 0505 // 0506 // Returns the number of "buckets" within the `node_hash_map`. 0507 using Base::bucket_count; 0508 0509 // node_hash_map::load_factor() 0510 // 0511 // Returns the current load factor of the `node_hash_map` (the average number 0512 // of slots occupied with a value within the hash map). 0513 using Base::load_factor; 0514 0515 // node_hash_map::max_load_factor() 0516 // 0517 // Manages the maximum load factor of the `node_hash_map`. Overloads are 0518 // listed below. 0519 // 0520 // float node_hash_map::max_load_factor() 0521 // 0522 // Returns the current maximum load factor of the `node_hash_map`. 0523 // 0524 // void node_hash_map::max_load_factor(float ml) 0525 // 0526 // Sets the maximum load factor of the `node_hash_map` to the passed value. 0527 // 0528 // NOTE: This overload is provided only for API compatibility with the STL; 0529 // `node_hash_map` will ignore any set load factor and manage its rehashing 0530 // internally as an implementation detail. 0531 using Base::max_load_factor; 0532 0533 // node_hash_map::get_allocator() 0534 // 0535 // Returns the allocator function associated with this `node_hash_map`. 0536 using Base::get_allocator; 0537 0538 // node_hash_map::hash_function() 0539 // 0540 // Returns the hashing function used to hash the keys within this 0541 // `node_hash_map`. 0542 using Base::hash_function; 0543 0544 // node_hash_map::key_eq() 0545 // 0546 // Returns the function used for comparing keys equality. 0547 using Base::key_eq; 0548 }; 0549 0550 // erase_if(node_hash_map<>, Pred) 0551 // 0552 // Erases all elements that satisfy the predicate `pred` from the container `c`. 0553 // Returns the number of erased elements. 0554 template <typename K, typename V, typename H, typename E, typename A, 0555 typename Predicate> 0556 typename node_hash_map<K, V, H, E, A>::size_type erase_if( 0557 node_hash_map<K, V, H, E, A>& c, Predicate pred) { 0558 return container_internal::EraseIf(pred, &c); 0559 } 0560 0561 namespace container_internal { 0562 0563 // c_for_each_fast(node_hash_map<>, Function) 0564 // 0565 // Container-based version of the <algorithm> `std::for_each()` function to 0566 // apply a function to a container's elements. 0567 // There is no guarantees on the order of the function calls. 0568 // Erasure and/or insertion of elements in the function is not allowed. 0569 template <typename K, typename V, typename H, typename E, typename A, 0570 typename Function> 0571 decay_t<Function> c_for_each_fast(const node_hash_map<K, V, H, E, A>& c, 0572 Function&& f) { 0573 container_internal::ForEach(f, &c); 0574 return f; 0575 } 0576 template <typename K, typename V, typename H, typename E, typename A, 0577 typename Function> 0578 decay_t<Function> c_for_each_fast(node_hash_map<K, V, H, E, A>& c, 0579 Function&& f) { 0580 container_internal::ForEach(f, &c); 0581 return f; 0582 } 0583 template <typename K, typename V, typename H, typename E, typename A, 0584 typename Function> 0585 decay_t<Function> c_for_each_fast(node_hash_map<K, V, H, E, A>&& c, 0586 Function&& f) { 0587 container_internal::ForEach(f, &c); 0588 return f; 0589 } 0590 0591 } // namespace container_internal 0592 0593 namespace container_internal { 0594 0595 template <class Key, class Value> 0596 class NodeHashMapPolicy 0597 : public absl::container_internal::node_slot_policy< 0598 std::pair<const Key, Value>&, NodeHashMapPolicy<Key, Value>> { 0599 using value_type = std::pair<const Key, Value>; 0600 0601 public: 0602 using key_type = Key; 0603 using mapped_type = Value; 0604 using init_type = std::pair</*non const*/ key_type, mapped_type>; 0605 0606 template <class Allocator, class... Args> 0607 static value_type* new_element(Allocator* alloc, Args&&... args) { 0608 using PairAlloc = typename absl::allocator_traits< 0609 Allocator>::template rebind_alloc<value_type>; 0610 PairAlloc pair_alloc(*alloc); 0611 value_type* res = 0612 absl::allocator_traits<PairAlloc>::allocate(pair_alloc, 1); 0613 absl::allocator_traits<PairAlloc>::construct(pair_alloc, res, 0614 std::forward<Args>(args)...); 0615 return res; 0616 } 0617 0618 template <class Allocator> 0619 static void delete_element(Allocator* alloc, value_type* pair) { 0620 using PairAlloc = typename absl::allocator_traits< 0621 Allocator>::template rebind_alloc<value_type>; 0622 PairAlloc pair_alloc(*alloc); 0623 absl::allocator_traits<PairAlloc>::destroy(pair_alloc, pair); 0624 absl::allocator_traits<PairAlloc>::deallocate(pair_alloc, pair, 1); 0625 } 0626 0627 template <class F, class... Args> 0628 static decltype(absl::container_internal::DecomposePair( 0629 std::declval<F>(), std::declval<Args>()...)) 0630 apply(F&& f, Args&&... args) { 0631 return absl::container_internal::DecomposePair(std::forward<F>(f), 0632 std::forward<Args>(args)...); 0633 } 0634 0635 static size_t element_space_used(const value_type*) { 0636 return sizeof(value_type); 0637 } 0638 0639 static Value& value(value_type* elem) { return elem->second; } 0640 static const Value& value(const value_type* elem) { return elem->second; } 0641 0642 template <class Hash> 0643 static constexpr HashSlotFn get_hash_slot_fn() { 0644 return memory_internal::IsLayoutCompatible<Key, Value>::value 0645 ? &TypeErasedDerefAndApplyToSlotFn<Hash, Key> 0646 : nullptr; 0647 } 0648 }; 0649 } // namespace container_internal 0650 0651 namespace container_algorithm_internal { 0652 0653 // Specialization of trait in absl/algorithm/container.h 0654 template <class Key, class T, class Hash, class KeyEqual, class Allocator> 0655 struct IsUnorderedContainer< 0656 absl::node_hash_map<Key, T, Hash, KeyEqual, Allocator>> : std::true_type {}; 0657 0658 } // namespace container_algorithm_internal 0659 0660 ABSL_NAMESPACE_END 0661 } // namespace absl 0662 0663 #endif // ABSL_CONTAINER_NODE_HASH_MAP_H_
[ Source navigation ] | [ Diff markup ] | [ Identifier search ] | [ general search ] |
This page was automatically generated by the 2.3.7 LXR engine. The LXR team |