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