IOSS 2.0

robin_map.h
Go to the documentation of this file.
1 /**
2 * MIT License
3 *
4 * Copyright (c) 2017 Tessil
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a copy
7 * of this software and associated documentation files (the "Software"), to deal
8 * in the Software without restriction, including without limitation the rights
9 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the Software is
11 * furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included in all
14 * copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 * SOFTWARE.
23 */
24 #ifndef TSL_ROBIN_MAP_H
25 #define TSL_ROBIN_MAP_H
26
27 #include "robin_hash.h"
28 #include <cstddef>
29 #include <functional>
30 #include <initializer_list>
31 #include <memory>
32 #include <type_traits>
33 #include <utility>
34
35 namespace tsl {
36
37 /**
38 * Implementation of a hash map using open-adressing and the robin hood hashing algorithm with
39 * backward shift deletion.
40 *
41 * For operations modifying the hash map (insert, erase, rehash, ...), the strong exception
42 * guarantee is only guaranteed when the expression `std::is_nothrow_swappable<std::pair<Key,
43 * T>>\:\:value && std::is_nothrow_move_constructible<std::pair<Key, T>>\:\:value` is true,
44 * otherwise if an exception is thrown during the swap or the move, the hash map may end up in a
45 * undefined state. Per the standard a `Key` or `T` with a noexcept copy constructor and no move
46 * constructor also satisfies the `std::is_nothrow_move_constructible<std::pair<Key, T>>\:\:value`
47 * criterion (and will thus guarantee the strong exception for the map).
48 *
49 * When `StoreHash` is true, 32 bits of the hash are stored alongside the values. It can improve
50 * the performance during lookups if the `KeyEqual` function takes time (if it engenders a
51 * cache-miss for example) as we then compare the stored hashes before comparing the keys. When
52 * `tsl::rh::power_of_two_growth_policy` is used as `GrowthPolicy`, it may also speed-up the
53 * rehash process as we can avoid to recalculate the hash. When it is detected that storing the
54 * hash will not incur any memory penality due to alignement (i.e.
55 * `sizeof(tsl::detail_robin_hash::bucket_entry<ValueType, true>) ==
56 * sizeof(tsl::detail_robin_hash::bucket_entry<ValueType, false>)`) and
57 * `tsl::rh::power_of_two_growth_policy` is used, the hash will be stored even if `StoreHash` is
58 * false so that we can speed-up the rehash (but it will not be used on lookups unless `StoreHash`
59 * is true).
60 *
61 * `GrowthPolicy` defines how the map grows and consequently how a hash value is mapped to a
62 * bucket. By default the map uses `tsl::rh::power_of_two_growth_policy`. This policy keeps the
63 * number of buckets to a power of two and uses a mask to map the hash to a bucket instead of the
64 * slow modulo. Other growth policies are available and you may define your own growth policy,
65 * check `tsl::rh::power_of_two_growth_policy` for the interface.
66 *
67 * If the destructor of `Key` or `T` throws an exception, the behaviour of the class is undefined.
68 *
69 * Iterators invalidation:
70 * - clear, operator=, reserve, rehash: always invalidate the iterators.
71 * - insert, emplace, emplace_hint, operator[]: if there is an effective insert, invalidate the
72 * iterators.
73 * - erase: always invalidate the iterators.
74 */
75 template <class Key, class T, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>,
76 class Allocator = std::allocator<std::pair<Key, T>>, bool StoreHash = false,
77 class GrowthPolicy = tsl::rh::power_of_two_growth_policy<2>>
78 class robin_map
79 {
80 private:
81 template <typename U> using has_is_transparent = tsl::detail_robin_hash::has_is_transparent<U>;
82
83 class KeySelect
84 {
85 public:
86 using key_type = Key;
87
88 const key_type &operator()(const std::pair<Key, T> &key_value) const noexcept
89 {
90 return key_value.first;
91 }
92
93 key_type &operator()(std::pair<Key, T> &key_value) noexcept { return key_value.first; }
94 };
95
96 class ValueSelect
97 {
98 public:
99 using value_type = T;
100
101 const value_type &operator()(const std::pair<Key, T> &key_value) const noexcept
102 {
103 return key_value.second;
104 }
105
106 value_type &operator()(std::pair<Key, T> &key_value) noexcept { return key_value.second; }
107 };
108
109 using ht = detail_robin_hash::robin_hash<std::pair<Key, T>, KeySelect, ValueSelect, Hash,
110 KeyEqual, Allocator, StoreHash, GrowthPolicy>;
111
112 public:
113 using key_type = typename ht::key_type;
114 using mapped_type = T;
115 using value_type = typename ht::value_type;
116 using size_type = typename ht::size_type;
117 using difference_type = typename ht::difference_type;
118 using hasher = typename ht::hasher;
119 using key_equal = typename ht::key_equal;
120 using allocator_type = typename ht::allocator_type;
121 using reference = typename ht::reference;
122 using const_reference = typename ht::const_reference;
123 using pointer = typename ht::pointer;
124 using const_pointer = typename ht::const_pointer;
125 using iterator = typename ht::iterator;
126 using const_iterator = typename ht::const_iterator;
127
128 public:
129 /*
130 * Constructors
131 */
132 robin_map() : robin_map(ht::DEFAULT_INIT_BUCKETS_SIZE) {}
133
134 explicit robin_map(size_type bucket_count, const Hash &hash = Hash(),
135 const KeyEqual &equal = KeyEqual(), const Allocator &alloc = Allocator())
136 : m_ht(bucket_count, hash, equal, alloc)
137 {
138 }
139
140 robin_map(size_type bucket_count, const Allocator &alloc)
141 : robin_map(bucket_count, Hash(), KeyEqual(), alloc)
142 {
143 }
144
145 robin_map(size_type bucket_count, const Hash &hash, const Allocator &alloc)
146 : robin_map(bucket_count, hash, KeyEqual(), alloc)
147 {
148 }
149
150 explicit robin_map(const Allocator &alloc) : robin_map(ht::DEFAULT_INIT_BUCKETS_SIZE, alloc) {}
151
152 template <class InputIt>
153 robin_map(InputIt first, InputIt last, size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE,
154 const Hash &hash = Hash(), const KeyEqual &equal = KeyEqual(),
155 const Allocator &alloc = Allocator())
156 : robin_map(bucket_count, hash, equal, alloc)
157 {
158 insert(first, last);
159 }
160
161 template <class InputIt>
162 robin_map(InputIt first, InputIt last, size_type bucket_count, const Allocator &alloc)
163 : robin_map(first, last, bucket_count, Hash(), KeyEqual(), alloc)
164 {
165 }
166
167 template <class InputIt>
168 robin_map(InputIt first, InputIt last, size_type bucket_count, const Hash &hash,
169 const Allocator &alloc)
170 : robin_map(first, last, bucket_count, hash, KeyEqual(), alloc)
171 {
172 }
173
174 robin_map(std::initializer_list<value_type> init,
175 size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE, const Hash &hash = Hash(),
176 const KeyEqual &equal = KeyEqual(), const Allocator &alloc = Allocator())
177 : robin_map(init.begin(), init.end(), bucket_count, hash, equal, alloc)
178 {
179 }
180
181 robin_map(std::initializer_list<value_type> init, size_type bucket_count,
182 const Allocator &alloc)
183 : robin_map(init.begin(), init.end(), bucket_count, Hash(), KeyEqual(), alloc)
184 {
185 }
186
187 robin_map(std::initializer_list<value_type> init, size_type bucket_count, const Hash &hash,
188 const Allocator &alloc)
189 : robin_map(init.begin(), init.end(), bucket_count, hash, KeyEqual(), alloc)
190 {
191 }
192
193 robin_map &operator=(std::initializer_list<value_type> ilist)
194 {
195 m_ht.clear();
196
197 m_ht.reserve(ilist.size());
198 m_ht.insert(ilist.begin(), ilist.end());
199
200 return *this;
201 }
202
203 allocator_type get_allocator() const { return m_ht.get_allocator(); }
204
205 /*
206 * Iterators
207 */
208 iterator begin() noexcept { return m_ht.begin(); }
209 const_iterator begin() const noexcept { return m_ht.begin(); }
210 const_iterator cbegin() const noexcept { return m_ht.cbegin(); }
211
212 iterator end() noexcept { return m_ht.end(); }
213 const_iterator end() const noexcept { return m_ht.end(); }
214 const_iterator cend() const noexcept { return m_ht.cend(); }
215
216 /*
217 * Capacity
218 */
219 bool empty() const noexcept { return m_ht.empty(); }
220 size_type size() const noexcept { return m_ht.size(); }
221 size_type max_size() const noexcept { return m_ht.max_size(); }
222
223 /*
224 * Modifiers
225 */
226 void clear() noexcept { m_ht.clear(); }
227
228 std::pair<iterator, bool> insert(const value_type &value) { return m_ht.insert(value); }
229
230 template <class P, typename std::enable_if<std::is_constructible<value_type, P &&>::value>::type
231 * = nullptr>
232 std::pair<iterator, bool> insert(P &&value)
233 {
234 return m_ht.emplace(std::forward<P>(value));
235 }
236
237 std::pair<iterator, bool> insert(value_type &&value) { return m_ht.insert(std::move(value)); }
238
239 iterator insert(const_iterator hint, const value_type &value)
240 {
241 return m_ht.insert_hint(hint, value);
242 }
243
244 template <class P, typename std::enable_if<std::is_constructible<value_type, P &&>::value>::type
245 * = nullptr>
246 iterator insert(const_iterator hint, P &&value)
247 {
248 return m_ht.emplace_hint(hint, std::forward<P>(value));
249 }
250
251 iterator insert(const_iterator hint, value_type &&value)
252 {
253 return m_ht.insert_hint(hint, std::move(value));
254 }
255
256 template <class InputIt> void insert(InputIt first, InputIt last) { m_ht.insert(first, last); }
257
258 void insert(std::initializer_list<value_type> ilist)
259 {
260 m_ht.insert(ilist.begin(), ilist.end());
261 }
262
263 template <class M> std::pair<iterator, bool> insert_or_assign(const key_type &k, M &&obj)
264 {
265 return m_ht.insert_or_assign(k, std::forward<M>(obj));
266 }
267
268 template <class M> std::pair<iterator, bool> insert_or_assign(key_type &&k, M &&obj)
269 {
270 return m_ht.insert_or_assign(std::move(k), std::forward<M>(obj));
271 }
272
273 template <class M> iterator insert_or_assign(const_iterator hint, const key_type &k, M &&obj)
274 {
275 return m_ht.insert_or_assign(hint, k, std::forward<M>(obj));
276 }
277
278 template <class M> iterator insert_or_assign(const_iterator hint, key_type &&k, M &&obj)
279 {
280 return m_ht.insert_or_assign(hint, std::move(k), std::forward<M>(obj));
281 }
282
283 /**
284 * Due to the way elements are stored, emplace will need to move or copy the key-value once.
285 * The method is equivalent to insert(value_type(std::forward<Args>(args)...));
286 *
287 * Mainly here for compatibility with the std::unordered_map interface.
288 */
289 template <class... Args> std::pair<iterator, bool> emplace(Args &&... args)
290 {
291 return m_ht.emplace(std::forward<Args>(args)...);
292 }
293
294 /**
295 * Due to the way elements are stored, emplace_hint will need to move or copy the key-value
296 * once. The method is equivalent to insert(hint, value_type(std::forward<Args>(args)...));
297 *
298 * Mainly here for compatibility with the std::unordered_map interface.
299 */
300 template <class... Args> iterator emplace_hint(const_iterator hint, Args &&... args)
301 {
302 return m_ht.emplace_hint(hint, std::forward<Args>(args)...);
303 }
304
305 template <class... Args>
306 std::pair<iterator, bool> try_emplace(const key_type &k, Args &&... args)
307 {
308 return m_ht.try_emplace(k, std::forward<Args>(args)...);
309 }
310
311 template <class... Args> std::pair<iterator, bool> try_emplace(key_type &&k, Args &&... args)
312 {
313 return m_ht.try_emplace(std::move(k), std::forward<Args>(args)...);
314 }
315
316 template <class... Args>
317 iterator try_emplace(const_iterator hint, const key_type &k, Args &&... args)
318 {
319 return m_ht.try_emplace_hint(hint, k, std::forward<Args>(args)...);
320 }
321
322 template <class... Args>
323 iterator try_emplace(const_iterator hint, key_type &&k, Args &&... args)
324 {
325 return m_ht.try_emplace_hint(hint, std::move(k), std::forward<Args>(args)...);
326 }
327
328 iterator erase(iterator pos) { return m_ht.erase(pos); }
329 iterator erase(const_iterator pos) { return m_ht.erase(pos); }
330 iterator erase(const_iterator first, const_iterator last) { return m_ht.erase(first, last); }
331 size_type erase(const key_type &key) { return m_ht.erase(key); }
332
333 /**
334 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
335 * the same as hash_function()(key). Usefull to speed-up the lookup to the value if you already
336 * have the hash.
337 */
338 size_type erase(const key_type &key, std::size_t precalculated_hash)
339 {
340 return m_ht.erase(key, precalculated_hash);
341 }
342
343 /**
344 * This overload only participates in the overload resolution if the typedef
345 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
346 */
347 template <class K, class KE = KeyEqual,
348 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
349 size_type erase(const K &key)
350 {
351 return m_ht.erase(key);
352 }
353
354 /**
355 * @copydoc erase(const K& key)
356 *
357 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
358 * the same as hash_function()(key). Usefull to speed-up the lookup to the value if you already
359 * have the hash.
360 */
361 template <class K, class KE = KeyEqual,
362 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
363 size_type erase(const K &key, std::size_t precalculated_hash)
364 {
365 return m_ht.erase(key, precalculated_hash);
366 }
367
368 void swap(robin_map &other) { other.m_ht.swap(m_ht); }
369
370 /*
371 * Lookup
372 */
373 T &at(const Key &key) { return m_ht.at(key); }
374
375 /**
376 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
377 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
378 * hash.
379 */
380 T &at(const Key &key, std::size_t precalculated_hash)
381 {
382 return m_ht.at(key, precalculated_hash);
383 }
384
385 const T &at(const Key &key) const { return m_ht.at(key); }
386
387 /**
388 * @copydoc at(const Key& key, std::size_t precalculated_hash)
389 */
390 const T &at(const Key &key, std::size_t precalculated_hash) const
391 {
392 return m_ht.at(key, precalculated_hash);
393 }
394
395 /**
396 * This overload only participates in the overload resolution if the typedef
397 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
398 */
399 template <class K, class KE = KeyEqual,
400 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
401 T &at(const K &key)
402 {
403 return m_ht.at(key);
404 }
405
406 /**
407 * @copydoc at(const K& key)
408 *
409 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
410 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
411 * hash.
412 */
413 template <class K, class KE = KeyEqual,
414 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
415 T &at(const K &key, std::size_t precalculated_hash)
416 {
417 return m_ht.at(key, precalculated_hash);
418 }
419
420 /**
421 * @copydoc at(const K& key)
422 */
423 template <class K, class KE = KeyEqual,
424 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
425 const T &at(const K &key) const
426 {
427 return m_ht.at(key);
428 }
429
430 /**
431 * @copydoc at(const K& key, std::size_t precalculated_hash)
432 */
433 template <class K, class KE = KeyEqual,
434 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
435 const T &at(const K &key, std::size_t precalculated_hash) const
436 {
437 return m_ht.at(key, precalculated_hash);
438 }
439
440 T &operator[](const Key &key) { return m_ht[key]; }
441 T &operator[](Key &&key) { return m_ht[std::move(key)]; }
442
443 size_type count(const Key &key) const { return m_ht.count(key); }
444
445 /**
446 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
447 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
448 * hash.
449 */
450 size_type count(const Key &key, std::size_t precalculated_hash) const
451 {
452 return m_ht.count(key, precalculated_hash);
453 }
454
455 /**
456 * This overload only participates in the overload resolution if the typedef
457 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
458 */
459 template <class K, class KE = KeyEqual,
460 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
461 size_type count(const K &key) const
462 {
463 return m_ht.count(key);
464 }
465
466 /**
467 * @copydoc count(const K& key) const
468 *
469 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
470 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
471 * hash.
472 */
473 template <class K, class KE = KeyEqual,
474 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
475 size_type count(const K &key, std::size_t precalculated_hash) const
476 {
477 return m_ht.count(key, precalculated_hash);
478 }
479
480 iterator find(const Key &key) { return m_ht.find(key); }
481
482 /**
483 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
484 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
485 * hash.
486 */
487 iterator find(const Key &key, std::size_t precalculated_hash)
488 {
489 return m_ht.find(key, precalculated_hash);
490 }
491
492 const_iterator find(const Key &key) const { return m_ht.find(key); }
493
494 /**
495 * @copydoc find(const Key& key, std::size_t precalculated_hash)
496 */
497 const_iterator find(const Key &key, std::size_t precalculated_hash) const
498 {
499 return m_ht.find(key, precalculated_hash);
500 }
501
502 /**
503 * This overload only participates in the overload resolution if the typedef
504 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
505 */
506 template <class K, class KE = KeyEqual,
507 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
508 iterator find(const K &key)
509 {
510 return m_ht.find(key);
511 }
512
513 /**
514 * @copydoc find(const K& key)
515 *
516 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
517 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
518 * hash.
519 */
520 template <class K, class KE = KeyEqual,
521 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
522 iterator find(const K &key, std::size_t precalculated_hash)
523 {
524 return m_ht.find(key, precalculated_hash);
525 }
526
527 /**
528 * @copydoc find(const K& key)
529 */
530 template <class K, class KE = KeyEqual,
531 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
532 const_iterator find(const K &key) const
533 {
534 return m_ht.find(key);
535 }
536
537 /**
538 * @copydoc find(const K& key)
539 *
540 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
541 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
542 * hash.
543 */
544 template <class K, class KE = KeyEqual,
545 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
546 const_iterator find(const K &key, std::size_t precalculated_hash) const
547 {
548 return m_ht.find(key, precalculated_hash);
549 }
550
551 std::pair<iterator, iterator> equal_range(const Key &key) { return m_ht.equal_range(key); }
552
553 /**
554 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
555 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
556 * hash.
557 */
558 std::pair<iterator, iterator> equal_range(const Key &key, std::size_t precalculated_hash)
559 {
560 return m_ht.equal_range(key, precalculated_hash);
561 }
562
563 std::pair<const_iterator, const_iterator> equal_range(const Key &key) const
564 {
565 return m_ht.equal_range(key);
566 }
567
568 /**
569 * @copydoc equal_range(const Key& key, std::size_t precalculated_hash)
570 */
571 std::pair<const_iterator, const_iterator> equal_range(const Key & key,
572 std::size_t precalculated_hash) const
573 {
574 return m_ht.equal_range(key, precalculated_hash);
575 }
576
577 /**
578 * This overload only participates in the overload resolution if the typedef
579 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
580 */
581 template <class K, class KE = KeyEqual,
582 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
583 std::pair<iterator, iterator> equal_range(const K &key)
584 {
585 return m_ht.equal_range(key);
586 }
587
588 /**
589 * @copydoc equal_range(const K& key)
590 *
591 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
592 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
593 * hash.
594 */
595 template <class K, class KE = KeyEqual,
596 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
597 std::pair<iterator, iterator> equal_range(const K &key, std::size_t precalculated_hash)
598 {
599 return m_ht.equal_range(key, precalculated_hash);
600 }
601
602 /**
603 * @copydoc equal_range(const K& key)
604 */
605 template <class K, class KE = KeyEqual,
606 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
607 std::pair<const_iterator, const_iterator> equal_range(const K &key) const
608 {
609 return m_ht.equal_range(key);
610 }
611
612 /**
613 * @copydoc equal_range(const K& key, std::size_t precalculated_hash)
614 */
615 template <class K, class KE = KeyEqual,
616 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
617 std::pair<const_iterator, const_iterator> equal_range(const K & key,
618 std::size_t precalculated_hash) const
619 {
620 return m_ht.equal_range(key, precalculated_hash);
621 }
622
623 /*
624 * Bucket interface
625 */
626 size_type bucket_count() const { return m_ht.bucket_count(); }
627 size_type max_bucket_count() const { return m_ht.max_bucket_count(); }
628
629 /*
630 * Hash policy
631 */
632 float load_factor() const { return m_ht.load_factor(); }
633
634 float min_load_factor() const { return m_ht.min_load_factor(); }
635 float max_load_factor() const { return m_ht.max_load_factor(); }
636
637 /**
638 * Set the `min_load_factor` to `ml`. When the `load_factor` of the map goes
639 * below `min_load_factor` after some erase operations, the map will be
640 * shrunk when an insertion occurs. The erase method itself never shrinks
641 * the map.
642 *
643 * The default value of `min_load_factor` is 0.0f, the map never shrinks by default.
644 */
645 void min_load_factor(float ml) { m_ht.min_load_factor(ml); }
646 void max_load_factor(float ml) { m_ht.max_load_factor(ml); }
647
648 void rehash(size_type count) { m_ht.rehash(count); }
649 void reserve(size_type count) { m_ht.reserve(count); }
650
651 /*
652 * Observers
653 */
654 hasher hash_function() const { return m_ht.hash_function(); }
655 key_equal key_eq() const { return m_ht.key_eq(); }
656
657 /*
658 * Other
659 */
660
661 /**
662 * Convert a const_iterator to an iterator.
663 */
664 iterator mutable_iterator(const_iterator pos) { return m_ht.mutable_iterator(pos); }
665
666 friend bool operator==(const robin_map &lhs, const robin_map &rhs)
667 {
668 if (lhs.size() != rhs.size()) {
669 return false;
670 }
671
672 for (const auto &element_lhs : lhs) {
673 const auto it_element_rhs = rhs.find(element_lhs.first);
674 if (it_element_rhs == rhs.cend() || element_lhs.second != it_element_rhs->second) {
675 return false;
676 }
677 }
678
679 return true;
680 }
681
682 friend bool operator!=(const robin_map &lhs, const robin_map &rhs)
683 {
684 return !operator==(lhs, rhs);
685 }
686
687 friend void swap(robin_map &lhs, robin_map &rhs) { lhs.swap(rhs); }
688
689 private:
690 ht m_ht;
691 };
692
693 /**
694 * Same as `tsl::robin_map<Key, T, Hash, KeyEqual, Allocator, StoreHash,
695 * tsl::rh::prime_growth_policy>`.
696 */
697 template <class Key, class T, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>,
698 class Allocator = std::allocator<std::pair<Key, T>>, bool StoreHash = false>
699 using robin_pg_map =
700 robin_map<Key, T, Hash, KeyEqual, Allocator, StoreHash, tsl::rh::prime_growth_policy>;
701
702 } // end namespace tsl
703
704 #endif
tsl::detail_robin_hash::robin_hash::equal_range
std::pair< iterator, iterator > equal_range(const K &key)
Definition: robin_hash.h:936
tsl::robin_map::robin_map
robin_map(size_type bucket_count, const Hash &hash=Hash(), const KeyEqual &equal=KeyEqual(), const Allocator &alloc=Allocator())
Definition: robin_map.h:134
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::reference
value_type & reference
Definition: robin_hash.h:329
tsl::robin_map::max_bucket_count
size_type max_bucket_count() const
Definition: robin_map.h:627
tsl::detail_robin_hash::robin_hash::end
iterator end() noexcept
Definition: robin_hash.h:637
tsl::robin_map::key_equal
typename ht::key_equal key_equal
Definition: robin_map.h:119
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::size_type
std::size_t size_type
Definition: robin_hash.h:324
tsl::robin_map::end
iterator end() noexcept
Definition: robin_map.h:212
tsl::robin_map::min_load_factor
float min_load_factor() const
Definition: robin_map.h:634
tsl::robin_map::ValueSelect::value_type
T value_type
Definition: robin_map.h:99
tsl::robin_map::hash_function
hasher hash_function() const
Definition: robin_map.h:654
tsl::detail_robin_hash::robin_hash::bucket_count
size_type bucket_count() const
Definition: robin_hash.h:962
tsl::robin_map::const_reference
typename ht::const_reference const_reference
Definition: robin_map.h:122
tsl::robin_map::find
iterator find(const K &key, std::size_t precalculated_hash)
Definition: robin_map.h:522
tsl::detail_robin_hash::robin_hash::max_bucket_count
size_type max_bucket_count() const
Definition: robin_hash.h:964
tsl::robin_map::KeySelect
Definition: robin_map.h:83
tsl::robin_map::at
const T & at(const K &key, std::size_t precalculated_hash) const
Definition: robin_map.h:435
tsl::detail_robin_hash::robin_hash::try_emplace
std::pair< iterator, bool > try_emplace(K &&key, Args &&... args)
Definition: robin_hash.h:730
tsl::robin_map::insert
std::pair< iterator, bool > insert(P &&value)
Definition: robin_map.h:232
tsl::robin_map::operator[]
T & operator[](const Key &key)
Definition: robin_map.h:440
tsl::robin_map::find
iterator find(const Key &key, std::size_t precalculated_hash)
Definition: robin_map.h:487
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::const_reference
const value_type & const_reference
Definition: robin_hash.h:330
tsl::robin_map::at
T & at(const K &key)
Definition: robin_map.h:401
tsl::detail_robin_hash::robin_hash::insert
std::pair< iterator, bool > insert(P &&value)
Definition: robin_hash.h:665
tsl::robin_map::at
const T & at(const K &key) const
Definition: robin_map.h:425
tsl::detail_robin_hash::robin_hash::load_factor
float load_factor() const
Definition: robin_hash.h:972
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::key_type
typename KeySelect::key_type key_type
Definition: robin_hash.h:322
tsl::robin_map::erase
size_type erase(const K &key, std::size_t precalculated_hash)
Definition: robin_map.h:363
tsl::robin_map::operator!=
friend bool operator!=(const robin_map &lhs, const robin_map &rhs)
Definition: robin_map.h:682
tsl
Definition: hopscotch_growth_policy.h:37
tsl::robin_map::erase
iterator erase(const_iterator first, const_iterator last)
Definition: robin_map.h:330
tsl::robin_map::find
const_iterator find(const Key &key) const
Definition: robin_map.h:492
tsl::robin_map::insert
std::pair< iterator, bool > insert(const value_type &value)
Definition: robin_map.h:228
tsl::robin_map::insert
void insert(InputIt first, InputIt last)
Definition: robin_map.h:256
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::value_type
std::pair< Key, T > value_type
Definition: robin_hash.h:323
tsl::robin_map::find
const_iterator find(const K &key, std::size_t precalculated_hash) const
Definition: robin_map.h:546
tsl::detail_robin_hash::robin_hash::insert_hint
iterator insert_hint(const_iterator hint, P &&value)
Definition: robin_hash.h:670
tsl::robin_map::key_type
typename ht::key_type key_type
Definition: robin_map.h:113
tsl::robin_map::begin
iterator begin() noexcept
Definition: robin_map.h:208
tsl::detail_robin_hash::robin_hash::begin
iterator begin() noexcept
Definition: robin_hash.h:615
tsl::robin_map::begin
const_iterator begin() const noexcept
Definition: robin_map.h:209
tsl::robin_map::equal_range
std::pair< iterator, iterator > equal_range(const Key &key, std::size_t precalculated_hash)
Definition: robin_map.h:558
tsl::robin_map::max_load_factor
void max_load_factor(float ml)
Definition: robin_map.h:646
tsl::detail_robin_hash::robin_hash::count
size_type count(const K &key) const
Definition: robin_hash.h:907
tsl::robin_map::swap
void swap(robin_map &other)
Definition: robin_map.h:368
tsl::detail_robin_hash::robin_hash::clear
void clear() noexcept
Definition: robin_hash.h:655
tsl::robin_map::end
const_iterator end() const noexcept
Definition: robin_map.h:213
tsl::robin_map::hasher
typename ht::hasher hasher
Definition: robin_map.h:118
tsl::robin_map::insert
iterator insert(const_iterator hint, value_type &&value)
Definition: robin_map.h:251
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::const_pointer
const value_type * const_pointer
Definition: robin_hash.h:332
tsl::robin_map::mapped_type
T mapped_type
Definition: robin_map.h:114
robin_hash.h
tsl::robin_map::count
size_type count(const K &key) const
Definition: robin_map.h:461
tsl::robin_map::empty
bool empty() const noexcept
Definition: robin_map.h:219
tsl::robin_map::bucket_count
size_type bucket_count() const
Definition: robin_map.h:626
tsl::detail_robin_hash::robin_hash::erase
iterator erase(iterator pos)
Definition: robin_hash.h:751
tsl::detail_robin_hash::robin_hash::cbegin
const_iterator cbegin() const noexcept
Definition: robin_hash.h:627
tsl::detail_robin_hash::robin_hash::size
size_type size() const noexcept
Definition: robin_hash.h:648
tsl::robin_map::equal_range
std::pair< iterator, iterator > equal_range(const Key &key)
Definition: robin_map.h:551
tsl::robin_map::ValueSelect
Definition: robin_map.h:96
tsl::robin_map::allocator_type
typename ht::allocator_type allocator_type
Definition: robin_map.h:120
tsl::robin_map::operator[]
T & operator[](Key &&key)
Definition: robin_map.h:441
tsl::robin_map
Definition: robin_map.h:78
tsl::robin_map::max_size
size_type max_size() const noexcept
Definition: robin_map.h:221
tsl::robin_map::at
const T & at(const Key &key, std::size_t precalculated_hash) const
Definition: robin_map.h:390
tsl::robin_map::try_emplace
iterator try_emplace(const_iterator hint, const key_type &k, Args &&... args)
Definition: robin_map.h:317
tsl::detail_robin_hash::robin_hash::cend
const_iterator cend() const noexcept
Definition: robin_hash.h:641
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::key_equal
KeyEqual key_equal
Definition: robin_hash.h:327
tsl::robin_map::insert_or_assign
std::pair< iterator, bool > insert_or_assign(const key_type &k, M &&obj)
Definition: robin_map.h:263
tsl::robin_map::KeySelect::key_type
Key key_type
Definition: robin_map.h:86
tsl::detail_robin_hash::robin_hash::insert_or_assign
std::pair< iterator, bool > insert_or_assign(K &&key, M &&obj)
Definition: robin_hash.h:697
tsl::robin_map::KeySelect::operator()
key_type & operator()(std::pair< Key, T > &key_value) noexcept
Definition: robin_map.h:93
tsl::robin_map::value_type
typename ht::value_type value_type
Definition: robin_map.h:115
tsl::robin_map::count
size_type count(const K &key, std::size_t precalculated_hash) const
Definition: robin_map.h:475
tsl::robin_map::operator=
robin_map & operator=(std::initializer_list< value_type > ilist)
Definition: robin_map.h:193
tsl::robin_map::try_emplace
std::pair< iterator, bool > try_emplace(const key_type &k, Args &&... args)
Definition: robin_map.h:306
tsl::detail_robin_hash::robin_hash::mutable_iterator
iterator mutable_iterator(const_iterator pos)
Definition: robin_hash.h:1019
tsl::robin_map::insert_or_assign
iterator insert_or_assign(const_iterator hint, const key_type &k, M &&obj)
Definition: robin_map.h:273
tsl::robin_map::key_eq
key_equal key_eq() const
Definition: robin_map.h:655
tsl::robin_map::min_load_factor
void min_load_factor(float ml)
Definition: robin_map.h:645
tsl::robin_map::const_pointer
typename ht::const_pointer const_pointer
Definition: robin_map.h:124
tsl::robin_map::rehash
void rehash(size_type count)
Definition: robin_map.h:648
tsl::robin_map::robin_map
robin_map(size_type bucket_count, const Allocator &alloc)
Definition: robin_map.h:140
tsl::detail_robin_hash::robin_hash::emplace_hint
iterator emplace_hint(const_iterator hint, Args &&... args)
Definition: robin_hash.h:724
tsl::robin_map::robin_map
robin_map()
Definition: robin_map.h:132
tsl::robin_map::try_emplace
std::pair< iterator, bool > try_emplace(key_type &&k, Args &&... args)
Definition: robin_map.h:311
tsl::robin_map::at
T & at(const Key &key, std::size_t precalculated_hash)
Definition: robin_map.h:380
tsl::robin_map::erase
size_type erase(const K &key)
Definition: robin_map.h:349
tsl::robin_map::insert
iterator insert(const_iterator hint, P &&value)
Definition: robin_map.h:246
tsl::detail_robin_hash::robin_hash::max_size
size_type max_size() const noexcept
Definition: robin_hash.h:650
tsl::robin_map::equal_range
std::pair< iterator, iterator > equal_range(const K &key, std::size_t precalculated_hash)
Definition: robin_map.h:597
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::const_iterator
robin_iterator< true > const_iterator
Definition: robin_hash.h:334
tsl::robin_map::load_factor
float load_factor() const
Definition: robin_map.h:632
tsl::detail_robin_hash::robin_hash::swap
void swap(robin_hash &other)
Definition: robin_hash.h:844
tsl::robin_map::erase
iterator erase(const_iterator pos)
Definition: robin_map.h:329
tsl::robin_map::equal_range
std::pair< const_iterator, const_iterator > equal_range(const K &key) const
Definition: robin_map.h:607
tsl::robin_map::find
const_iterator find(const K &key) const
Definition: robin_map.h:532
tsl::robin_map::robin_map
robin_map(std::initializer_list< value_type > init, size_type bucket_count, const Allocator &alloc)
Definition: robin_map.h:181
tsl::robin_map::at
const T & at(const Key &key) const
Definition: robin_map.h:385
tsl::robin_map::find
const_iterator find(const Key &key, std::size_t precalculated_hash) const
Definition: robin_map.h:497
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::allocator_type
Allocator allocator_type
Definition: robin_hash.h:328
tsl::robin_map::robin_map
robin_map(InputIt first, InputIt last, size_type bucket_count=ht::DEFAULT_INIT_BUCKETS_SIZE, const Hash &hash=Hash(), const KeyEqual &equal=KeyEqual(), const Allocator &alloc=Allocator())
Definition: robin_map.h:153
tsl::robin_map::equal_range
std::pair< const_iterator, const_iterator > equal_range(const Key &key, std::size_t precalculated_hash) const
Definition: robin_map.h:571
tsl::robin_map::pointer
typename ht::pointer pointer
Definition: robin_map.h:123
tsl::detail_robin_hash::robin_hash::at
U::value_type & at(const K &key)
Definition: robin_hash.h:867
tsl::robin_map::m_ht
ht m_ht
Definition: robin_map.h:690
tsl::robin_map::at
T & at(const Key &key)
Definition: robin_map.h:373
tsl::robin_map::get_allocator
allocator_type get_allocator() const
Definition: robin_map.h:203
tsl::detail_robin_hash::robin_hash::find
iterator find(const K &key)
Definition: robin_hash.h:919
tsl::robin_map::find
iterator find(const Key &key)
Definition: robin_map.h:480
tsl::robin_map::robin_map
robin_map(std::initializer_list< value_type > init, size_type bucket_count=ht::DEFAULT_INIT_BUCKETS_SIZE, const Hash &hash=Hash(), const KeyEqual &equal=KeyEqual(), const Allocator &alloc=Allocator())
Definition: robin_map.h:174
tsl::detail_robin_hash::has_is_transparent
Definition: robin_hash.h:52
tsl::robin_map::robin_map
robin_map(InputIt first, InputIt last, size_type bucket_count, const Hash &hash, const Allocator &alloc)
Definition: robin_map.h:168
tsl::robin_map::insert_or_assign
std::pair< iterator, bool > insert_or_assign(key_type &&k, M &&obj)
Definition: robin_map.h:268
tsl::robin_map::find
iterator find(const K &key)
Definition: robin_map.h:508
tsl::robin_map::reserve
void reserve(size_type count)
Definition: robin_map.h:649
tsl::robin_map::cbegin
const_iterator cbegin() const noexcept
Definition: robin_map.h:210
tsl::robin_map::reference
typename ht::reference reference
Definition: robin_map.h:121
tsl::detail_robin_hash::robin_hash::key_eq
key_equal key_eq() const
Definition: robin_hash.h:1014
tsl::robin_map::iterator
typename ht::iterator iterator
Definition: robin_map.h:125
tsl::robin_map::operator==
friend bool operator==(const robin_map &lhs, const robin_map &rhs)
Definition: robin_map.h:666
tsl::robin_map::count
size_type count(const Key &key) const
Definition: robin_map.h:443
tsl::robin_map::at
T & at(const K &key, std::size_t precalculated_hash)
Definition: robin_map.h:415
tsl::robin_map::difference_type
typename ht::difference_type difference_type
Definition: robin_map.h:117
tsl::robin_map::emplace_hint
iterator emplace_hint(const_iterator hint, Args &&... args)
Definition: robin_map.h:300
tsl::robin_map::ValueSelect::operator()
value_type & operator()(std::pair< Key, T > &key_value) noexcept
Definition: robin_map.h:106
tsl::robin_map::count
size_type count(const Key &key, std::size_t precalculated_hash) const
Definition: robin_map.h:450
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::DEFAULT_INIT_BUCKETS_SIZE
static const size_type DEFAULT_INIT_BUCKETS_SIZE
Definition: robin_hash.h:1282
tsl::robin_map::robin_map
robin_map(std::initializer_list< value_type > init, size_type bucket_count, const Hash &hash, const Allocator &alloc)
Definition: robin_map.h:187
tsl::robin_map::equal_range
std::pair< iterator, iterator > equal_range(const K &key)
Definition: robin_map.h:583
tsl::robin_map::ValueSelect::operator()
const value_type & operator()(const std::pair< Key, T > &key_value) const noexcept
Definition: robin_map.h:101
tsl::robin_map::insert
void insert(std::initializer_list< value_type > ilist)
Definition: robin_map.h:258
anonymous_namespace{Ioss_SmartAssert.C}::init
struct anonymous_namespace{Ioss_SmartAssert.C}::assert_initializer init
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::hasher
Hash hasher
Definition: robin_hash.h:326
tsl::robin_map::robin_map
robin_map(const Allocator &alloc)
Definition: robin_map.h:150
tsl::robin_map::clear
void clear() noexcept
Definition: robin_map.h:226
tsl::robin_map::ht
detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy > ht
Definition: robin_map.h:110
tsl::detail_robin_hash::robin_hash::hash_function
hasher hash_function() const
Definition: robin_hash.h:1012
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::iterator
robin_iterator< false > iterator
Definition: robin_hash.h:333
tsl::detail_robin_hash::robin_hash::emplace
std::pair< iterator, bool > emplace(Args &&... args)
Definition: robin_hash.h:719
tsl::detail_robin_hash::robin_hash
Definition: robin_hash.h:308
tsl::robin_map::robin_map
robin_map(InputIt first, InputIt last, size_type bucket_count, const Allocator &alloc)
Definition: robin_map.h:162
tsl::robin_map::insert
iterator insert(const_iterator hint, const value_type &value)
Definition: robin_map.h:239
tsl::robin_map::size_type
typename ht::size_type size_type
Definition: robin_map.h:116
tsl::robin_map::swap
friend void swap(robin_map &lhs, robin_map &rhs)
Definition: robin_map.h:687
tsl::robin_map::size
size_type size() const noexcept
Definition: robin_map.h:220
tsl::robin_map::erase
size_type erase(const key_type &key)
Definition: robin_map.h:331
tsl::robin_map::equal_range
std::pair< const_iterator, const_iterator > equal_range(const K &key, std::size_t precalculated_hash) const
Definition: robin_map.h:617
tsl::detail_robin_hash::robin_hash::try_emplace_hint
iterator try_emplace_hint(const_iterator hint, K &&key, Args &&... args)
Definition: robin_hash.h:738
tsl::robin_map::insert
std::pair< iterator, bool > insert(value_type &&value)
Definition: robin_map.h:237
tsl::robin_map::erase
iterator erase(iterator pos)
Definition: robin_map.h:328
tsl::robin_map::insert_or_assign
iterator insert_or_assign(const_iterator hint, key_type &&k, M &&obj)
Definition: robin_map.h:278
tsl::robin_map::robin_map
robin_map(size_type bucket_count, const Hash &hash, const Allocator &alloc)
Definition: robin_map.h:145
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::difference_type
std::ptrdiff_t difference_type
Definition: robin_hash.h:325
tsl::detail_robin_hash::robin_hash::max_load_factor
float max_load_factor() const
Definition: robin_hash.h:983
tsl::detail_robin_hash::robin_hash::reserve
void reserve(size_type my_count)
Definition: robin_hash.h:1004
tsl::detail_robin_hash::robin_hash::min_load_factor
float min_load_factor() const
Definition: robin_hash.h:981
tsl::detail_robin_hash::robin_hash::empty
bool empty() const noexcept
Definition: robin_hash.h:646
tsl::robin_map::max_load_factor
float max_load_factor() const
Definition: robin_map.h:635
tsl::robin_map::cend
const_iterator cend() const noexcept
Definition: robin_map.h:214
tsl::robin_map::KeySelect::operator()
const key_type & operator()(const std::pair< Key, T > &key_value) const noexcept
Definition: robin_map.h:88
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::pointer
value_type * pointer
Definition: robin_hash.h:331
tsl::robin_map::mutable_iterator
iterator mutable_iterator(const_iterator pos)
Definition: robin_map.h:664
tsl::robin_map::erase
size_type erase(const key_type &key, std::size_t precalculated_hash)
Definition: robin_map.h:338
tsl::detail_robin_hash::robin_hash::get_allocator
allocator_type get_allocator() const
Definition: robin_hash.h:610
tsl::robin_map::try_emplace
iterator try_emplace(const_iterator hint, key_type &&k, Args &&... args)
Definition: robin_map.h:323
tsl::detail_robin_hash::robin_hash::rehash
void rehash(size_type my_count)
Definition: robin_hash.h:998
tsl::robin_map::emplace
std::pair< iterator, bool > emplace(Args &&... args)
Definition: robin_map.h:289
tsl::robin_map::equal_range
std::pair< const_iterator, const_iterator > equal_range(const Key &key) const
Definition: robin_map.h:563
tsl::robin_map::const_iterator
typename ht::const_iterator const_iterator
Definition: robin_map.h:126