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
43 * `std::is_nothrow_swappable<std::pair<Key,T>>::value &&
44 * std::is_nothrow_move_constructible<std::pair<Key, T>>::value` is true, otherwise if an
45 * exception is thrown during the swap or the move, the hash map may end up in a undefined state.
46 * Per the standard a `Key` or `T` with a noexcept copy constructor and no move constructor also
47 * satisfies the `std::is_nothrow_move_constructible<std::pair<Key, T>>::value` criterion (and
48 * will thus guarantee the strong exception for the map).
49 *
50 * When `StoreHash` is true, 32 bits of the hash are stored alongside the values. It can improve
51 * the performance during lookups if the `KeyEqual` function takes time (if it engenders a
52 * cache-miss for example) as we then compare the stored hashes before comparing the keys. When
53 * `tsl::rh::power_of_two_growth_policy` is used as `GrowthPolicy`, it may also speed-up the
54 * rehash process as we can avoid to recalculate the hash. When it is detected that storing the
55 * hash will not incur any memory penality due to alignement (i.e.
56 * `sizeof(tsl::detail_robin_hash::bucket_entry<ValueType, true>) ==
57 * sizeof(tsl::detail_robin_hash::bucket_entry<ValueType, false>)`) and
58 * `tsl::rh::power_of_two_growth_policy` is used, the hash will be stored even if `StoreHash` is
59 * false so that we can speed-up the rehash (but it will not be used on lookups unless `StoreHash`
60 * is true).
61 *
62 * `GrowthPolicy` defines how the map grows and consequently how a hash value is mapped to a
63 * bucket. By default the map uses `tsl::rh::power_of_two_growth_policy`. This policy keeps the
64 * number of buckets to a power of two and uses a mask to map the hash to a bucket instead of the
65 * slow modulo. Other growth policies are available and you may define your own growth policy,
66 * check `tsl::rh::power_of_two_growth_policy` for the interface.
67 *
68 * If the destructor of `Key` or `T` throws an exception, the behaviour of the class is undefined.
69 *
70 * Iterators invalidation:
71 * - clear, operator=, reserve, rehash: always invalidate the iterators.
72 * - insert, emplace, emplace_hint, operator[]: if there is an effective insert, invalidate the
73 * iterators.
74 * - erase: always invalidate the iterators.
75 */
76 template <class Key, class T, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>,
77 class Allocator = std::allocator<std::pair<Key, T>>, bool StoreHash = false,
78 class GrowthPolicy = tsl::rh::power_of_two_growth_policy<2>>
79 class robin_map
80 {
81 private:
82 template <typename U> using has_is_transparent = tsl::detail_robin_hash::has_is_transparent<U>;
83
84 class KeySelect
85 {
86 public:
87 using key_type = Key;
88
89 const key_type &operator()(const std::pair<Key, T> &key_value) const noexcept
90 {
91 return key_value.first;
92 }
93
94 key_type &operator()(std::pair<Key, T> &key_value) noexcept { return key_value.first; }
95 };
96
97 class ValueSelect
98 {
99 public:
100 using value_type = T;
101
102 const value_type &operator()(const std::pair<Key, T> &key_value) const noexcept
103 {
104 return key_value.second;
105 }
106
107 value_type &operator()(std::pair<Key, T> &key_value) noexcept { return key_value.second; }
108 };
109
110 using ht = detail_robin_hash::robin_hash<std::pair<Key, T>, KeySelect, ValueSelect, Hash,
111 KeyEqual, Allocator, StoreHash, GrowthPolicy>;
112
113 public:
114 using key_type = typename ht::key_type;
115 using mapped_type = T;
116 using value_type = typename ht::value_type;
117 using size_type = typename ht::size_type;
118 using difference_type = typename ht::difference_type;
119 using hasher = typename ht::hasher;
120 using key_equal = typename ht::key_equal;
121 using allocator_type = typename ht::allocator_type;
122 using reference = typename ht::reference;
123 using const_reference = typename ht::const_reference;
124 using pointer = typename ht::pointer;
125 using const_pointer = typename ht::const_pointer;
126 using iterator = typename ht::iterator;
127 using const_iterator = typename ht::const_iterator;
128
129 public:
130 /*
131 * Constructors
132 */
133 robin_map() : robin_map(ht::DEFAULT_INIT_BUCKETS_SIZE) {}
134
135 explicit robin_map(size_type bucket_count, const Hash &hash = Hash(),
136 const KeyEqual &equal = KeyEqual(), const Allocator &alloc = Allocator())
137 : m_ht(bucket_count, hash, equal, alloc, ht::DEFAULT_MAX_LOAD_FACTOR)
138 {
139 }
140
141 robin_map(size_type bucket_count, const Allocator &alloc)
142 : robin_map(bucket_count, Hash(), KeyEqual(), alloc)
143 {
144 }
145
146 robin_map(size_type bucket_count, const Hash &hash, const Allocator &alloc)
147 : robin_map(bucket_count, hash, KeyEqual(), alloc)
148 {
149 }
150
151 explicit robin_map(const Allocator &alloc) : robin_map(ht::DEFAULT_INIT_BUCKETS_SIZE, alloc) {}
152
153 template <class InputIt>
154 robin_map(InputIt first, InputIt last, size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE,
155 const Hash &hash = Hash(), const KeyEqual &equal = KeyEqual(),
156 const Allocator &alloc = Allocator())
157 : robin_map(bucket_count, hash, equal, alloc)
158 {
159 insert(first, last);
160 }
161
162 template <class InputIt>
163 robin_map(InputIt first, InputIt last, size_type bucket_count, const Allocator &alloc)
164 : robin_map(first, last, bucket_count, Hash(), KeyEqual(), alloc)
165 {
166 }
167
168 template <class InputIt>
169 robin_map(InputIt first, InputIt last, size_type bucket_count, const Hash &hash,
170 const Allocator &alloc)
171 : robin_map(first, last, bucket_count, hash, KeyEqual(), alloc)
172 {
173 }
174
175 robin_map(std::initializer_list<value_type> init,
176 size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE, const Hash &hash = Hash(),
177 const KeyEqual &equal = KeyEqual(), const Allocator &alloc = Allocator())
178 : robin_map(init.begin(), init.end(), bucket_count, hash, equal, alloc)
179 {
180 }
181
182 robin_map(std::initializer_list<value_type> init, size_type bucket_count,
183 const Allocator &alloc)
184 : robin_map(init.begin(), init.end(), bucket_count, Hash(), KeyEqual(), alloc)
185 {
186 }
187
188 robin_map(std::initializer_list<value_type> init, size_type bucket_count, const Hash &hash,
189 const Allocator &alloc)
190 : robin_map(init.begin(), init.end(), bucket_count, hash, KeyEqual(), alloc)
191 {
192 }
193
194 robin_map &operator=(std::initializer_list<value_type> ilist)
195 {
196 m_ht.clear();
197
198 m_ht.reserve(ilist.size());
199 m_ht.insert(ilist.begin(), ilist.end());
200
201 return *this;
202 }
203
204 allocator_type get_allocator() const { return m_ht.get_allocator(); }
205
206 /*
207 * Iterators
208 */
209 iterator begin() noexcept { return m_ht.begin(); }
210 const_iterator begin() const noexcept { return m_ht.begin(); }
211 const_iterator cbegin() const noexcept { return m_ht.cbegin(); }
212
213 iterator end() noexcept { return m_ht.end(); }
214 const_iterator end() const noexcept { return m_ht.end(); }
215 const_iterator cend() const noexcept { return m_ht.cend(); }
216
217 /*
218 * Capacity
219 */
220 bool empty() const noexcept { return m_ht.empty(); }
221 size_type size() const noexcept { return m_ht.size(); }
222 size_type max_size() const noexcept { return m_ht.max_size(); }
223
224 /*
225 * Modifiers
226 */
227 void clear() noexcept { m_ht.clear(); }
228
229 std::pair<iterator, bool> insert(const value_type &value) { return m_ht.insert(value); }
230
231 template <class P, typename std::enable_if<std::is_constructible<value_type, P &&>::value>::type
232 * = nullptr>
233 std::pair<iterator, bool> insert(P &&value)
234 {
235 return m_ht.emplace(std::forward<P>(value));
236 }
237
238 std::pair<iterator, bool> insert(value_type &&value) { return m_ht.insert(std::move(value)); }
239
240 iterator insert(const_iterator hint, const value_type &value)
241 {
242 return m_ht.insert(hint, value);
243 }
244
245 template <class P, typename std::enable_if<std::is_constructible<value_type, P &&>::value>::type
246 * = nullptr>
247 iterator insert(const_iterator hint, P &&value)
248 {
249 return m_ht.emplace_hint(hint, std::forward<P>(value));
250 }
251
252 iterator insert(const_iterator hint, value_type &&value)
253 {
254 return m_ht.insert(hint, std::move(value));
255 }
256
257 template <class InputIt> void insert(InputIt first, InputIt last) { m_ht.insert(first, last); }
258
259 void insert(std::initializer_list<value_type> ilist)
260 {
261 m_ht.insert(ilist.begin(), ilist.end());
262 }
263
264 template <class M> std::pair<iterator, bool> insert_or_assign(const key_type &k, M &&obj)
265 {
266 return m_ht.insert_or_assign(k, std::forward<M>(obj));
267 }
268
269 template <class M> std::pair<iterator, bool> insert_or_assign(key_type &&k, M &&obj)
270 {
271 return m_ht.insert_or_assign(std::move(k), std::forward<M>(obj));
272 }
273
274 template <class M> iterator insert_or_assign(const_iterator hint, const key_type &k, M &&obj)
275 {
276 return m_ht.insert_or_assign(hint, k, std::forward<M>(obj));
277 }
278
279 template <class M> iterator insert_or_assign(const_iterator hint, key_type &&k, M &&obj)
280 {
281 return m_ht.insert_or_assign(hint, std::move(k), std::forward<M>(obj));
282 }
283
284 /**
285 * Due to the way elements are stored, emplace will need to move or copy the key-value once.
286 * The method is equivalent to insert(value_type(std::forward<Args>(args)...));
287 *
288 * Mainly here for compatibility with the std::unordered_map interface.
289 */
290 template <class... Args> std::pair<iterator, bool> emplace(Args &&... args)
291 {
292 return m_ht.emplace(std::forward<Args>(args)...);
293 }
294
295 /**
296 * Due to the way elements are stored, emplace_hint will need to move or copy the key-value
297 * once. The method is equivalent to insert(hint, value_type(std::forward<Args>(args)...));
298 *
299 * Mainly here for compatibility with the std::unordered_map interface.
300 */
301 template <class... Args> iterator emplace_hint(const_iterator hint, Args &&... args)
302 {
303 return m_ht.emplace_hint(hint, std::forward<Args>(args)...);
304 }
305
306 template <class... Args>
307 std::pair<iterator, bool> try_emplace(const key_type &k, Args &&... args)
308 {
309 return m_ht.try_emplace(k, std::forward<Args>(args)...);
310 }
311
312 template <class... Args> std::pair<iterator, bool> try_emplace(key_type &&k, Args &&... args)
313 {
314 return m_ht.try_emplace(std::move(k), std::forward<Args>(args)...);
315 }
316
317 template <class... Args>
318 iterator try_emplace(const_iterator hint, const key_type &k, Args &&... args)
319 {
320 return m_ht.try_emplace(hint, k, std::forward<Args>(args)...);
321 }
322
323 template <class... Args>
324 iterator try_emplace(const_iterator hint, key_type &&k, Args &&... args)
325 {
326 return m_ht.try_emplace(hint, std::move(k), std::forward<Args>(args)...);
327 }
328
329 iterator erase(iterator pos) { return m_ht.erase(pos); }
330 iterator erase(const_iterator pos) { return m_ht.erase(pos); }
331 iterator erase(const_iterator first, const_iterator last) { return m_ht.erase(first, last); }
332 size_type erase(const key_type &key) { return m_ht.erase(key); }
333
334 /**
335 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
336 * the same as hash_function()(key). Usefull to speed-up the lookup to the value if you already
337 * have the hash.
338 */
339 size_type erase(const key_type &key, std::size_t precalculated_hash)
340 {
341 return m_ht.erase(key, precalculated_hash);
342 }
343
344 /**
345 * This overload only participates in the overload resolution if the typedef
346 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
347 */
348 template <class K, class KE = KeyEqual,
349 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
350 size_type erase(const K &key)
351 {
352 return m_ht.erase(key);
353 }
354
355 /**
356 * @copydoc erase(const K& key)
357 *
358 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
359 * the same as hash_function()(key). Usefull to speed-up the lookup to the value if you already
360 * have the hash.
361 */
362 template <class K, class KE = KeyEqual,
363 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
364 size_type erase(const K &key, std::size_t precalculated_hash)
365 {
366 return m_ht.erase(key, precalculated_hash);
367 }
368
369 void swap(robin_map &other) { other.m_ht.swap(m_ht); }
370
371 /*
372 * Lookup
373 */
374 T &at(const Key &key) { return m_ht.at(key); }
375
376 /**
377 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
378 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
379 * hash.
380 */
381 T &at(const Key &key, std::size_t precalculated_hash)
382 {
383 return m_ht.at(key, precalculated_hash);
384 }
385
386 const T &at(const Key &key) const { return m_ht.at(key); }
387
388 /**
389 * @copydoc at(const Key& key, std::size_t precalculated_hash)
390 */
391 const T &at(const Key &key, std::size_t precalculated_hash) const
392 {
393 return m_ht.at(key, precalculated_hash);
394 }
395
396 /**
397 * This overload only participates in the overload resolution if the typedef
398 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
399 */
400 template <class K, class KE = KeyEqual,
401 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
402 T &at(const K &key)
403 {
404 return m_ht.at(key);
405 }
406
407 /**
408 * @copydoc at(const K& key)
409 *
410 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
411 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
412 * hash.
413 */
414 template <class K, class KE = KeyEqual,
415 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
416 T &at(const K &key, std::size_t precalculated_hash)
417 {
418 return m_ht.at(key, precalculated_hash);
419 }
420
421 /**
422 * @copydoc at(const K& key)
423 */
424 template <class K, class KE = KeyEqual,
425 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
426 const T &at(const K &key) const
427 {
428 return m_ht.at(key);
429 }
430
431 /**
432 * @copydoc at(const K& key, std::size_t precalculated_hash)
433 */
434 template <class K, class KE = KeyEqual,
435 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
436 const T &at(const K &key, std::size_t precalculated_hash) const
437 {
438 return m_ht.at(key, precalculated_hash);
439 }
440
441 T &operator[](const Key &key) { return m_ht[key]; }
442 T &operator[](Key &&key) { return m_ht[std::move(key)]; }
443
444 size_type count(const Key &key) const { return m_ht.count(key); }
445
446 /**
447 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
448 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
449 * hash.
450 */
451 size_type count(const Key &key, std::size_t precalculated_hash) const
452 {
453 return m_ht.count(key, precalculated_hash);
454 }
455
456 /**
457 * This overload only participates in the overload resolution if the typedef
458 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
459 */
460 template <class K, class KE = KeyEqual,
461 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
462 size_type count(const K &key) const
463 {
464 return m_ht.count(key);
465 }
466
467 /**
468 * @copydoc count(const K& key) const
469 *
470 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
471 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
472 * hash.
473 */
474 template <class K, class KE = KeyEqual,
475 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
476 size_type count(const K &key, std::size_t precalculated_hash) const
477 {
478 return m_ht.count(key, precalculated_hash);
479 }
480
481 iterator find(const Key &key) { return m_ht.find(key); }
482
483 /**
484 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
485 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
486 * hash.
487 */
488 iterator find(const Key &key, std::size_t precalculated_hash)
489 {
490 return m_ht.find(key, precalculated_hash);
491 }
492
493 const_iterator find(const Key &key) const { return m_ht.find(key); }
494
495 /**
496 * @copydoc find(const Key& key, std::size_t precalculated_hash)
497 */
498 const_iterator find(const Key &key, std::size_t precalculated_hash) const
499 {
500 return m_ht.find(key, precalculated_hash);
501 }
502
503 /**
504 * This overload only participates in the overload resolution if the typedef
505 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
506 */
507 template <class K, class KE = KeyEqual,
508 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
509 iterator find(const K &key)
510 {
511 return m_ht.find(key);
512 }
513
514 /**
515 * @copydoc find(const K& key)
516 *
517 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
518 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
519 * hash.
520 */
521 template <class K, class KE = KeyEqual,
522 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
523 iterator find(const K &key, std::size_t precalculated_hash)
524 {
525 return m_ht.find(key, precalculated_hash);
526 }
527
528 /**
529 * @copydoc find(const K& key)
530 */
531 template <class K, class KE = KeyEqual,
532 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
533 const_iterator find(const K &key) const
534 {
535 return m_ht.find(key);
536 }
537
538 /**
539 * @copydoc find(const K& key)
540 *
541 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
542 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
543 * hash.
544 */
545 template <class K, class KE = KeyEqual,
546 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
547 const_iterator find(const K &key, std::size_t precalculated_hash) const
548 {
549 return m_ht.find(key, precalculated_hash);
550 }
551
552 std::pair<iterator, iterator> equal_range(const Key &key) { return m_ht.equal_range(key); }
553
554 /**
555 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
556 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
557 * hash.
558 */
559 std::pair<iterator, iterator> equal_range(const Key &key, std::size_t precalculated_hash)
560 {
561 return m_ht.equal_range(key, precalculated_hash);
562 }
563
564 std::pair<const_iterator, const_iterator> equal_range(const Key &key) const
565 {
566 return m_ht.equal_range(key);
567 }
568
569 /**
570 * @copydoc equal_range(const Key& key, std::size_t precalculated_hash)
571 */
572 std::pair<const_iterator, const_iterator> equal_range(const Key & key,
573 std::size_t precalculated_hash) const
574 {
575 return m_ht.equal_range(key, precalculated_hash);
576 }
577
578 /**
579 * This overload only participates in the overload resolution if the typedef
580 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
581 */
582 template <class K, class KE = KeyEqual,
583 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
584 std::pair<iterator, iterator> equal_range(const K &key)
585 {
586 return m_ht.equal_range(key);
587 }
588
589 /**
590 * @copydoc equal_range(const K& key)
591 *
592 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
593 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
594 * hash.
595 */
596 template <class K, class KE = KeyEqual,
597 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
598 std::pair<iterator, iterator> equal_range(const K &key, std::size_t precalculated_hash)
599 {
600 return m_ht.equal_range(key, precalculated_hash);
601 }
602
603 /**
604 * @copydoc equal_range(const K& key)
605 */
606 template <class K, class KE = KeyEqual,
607 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
608 std::pair<const_iterator, const_iterator> equal_range(const K &key) const
609 {
610 return m_ht.equal_range(key);
611 }
612
613 /**
614 * @copydoc equal_range(const K& key, std::size_t precalculated_hash)
615 */
616 template <class K, class KE = KeyEqual,
617 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
618 std::pair<const_iterator, const_iterator> equal_range(const K & key,
619 std::size_t precalculated_hash) const
620 {
621 return m_ht.equal_range(key, precalculated_hash);
622 }
623
624 /*
625 * Bucket interface
626 */
627 size_type bucket_count() const { return m_ht.bucket_count(); }
628 size_type max_bucket_count() const { return m_ht.max_bucket_count(); }
629
630 /*
631 * Hash policy
632 */
633 float load_factor() const { return m_ht.load_factor(); }
634 float max_load_factor() const { return m_ht.max_load_factor(); }
635 void max_load_factor(float ml) { m_ht.max_load_factor(ml); }
636
637 void rehash(size_type count_) { m_ht.rehash(count_); }
638 void reserve(size_type count_) { m_ht.reserve(count_); }
639
640 /*
641 * Observers
642 */
643 hasher hash_function() const { return m_ht.hash_function(); }
644 key_equal key_eq() const { return m_ht.key_eq(); }
645
646 /*
647 * Other
648 */
649
650 /**
651 * Convert a const_iterator to an iterator.
652 */
653 iterator mutable_iterator(const_iterator pos) { return m_ht.mutable_iterator(pos); }
654
655 friend bool operator==(const robin_map &lhs, const robin_map &rhs)
656 {
657 if (lhs.size() != rhs.size()) {
658 return false;
659 }
660
661 for (const auto &element_lhs : lhs) {
662 const auto it_element_rhs = rhs.find(element_lhs.first);
663 if (it_element_rhs == rhs.cend() || element_lhs.second != it_element_rhs->second) {
664 return false;
665 }
666 }
667
668 return true;
669 }
670
671 friend bool operator!=(const robin_map &lhs, const robin_map &rhs)
672 {
673 return !operator==(lhs, rhs);
674 }
675
676 friend void swap(robin_map &lhs, robin_map &rhs) { lhs.swap(rhs); }
677
678 private:
679 ht m_ht;
680 };
681
682 /**
683 * Same as `tsl::robin_map<Key, T, Hash, KeyEqual, Allocator, StoreHash,
684 * tsl::rh::prime_growth_policy>`.
685 */
686 template <class Key, class T, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>,
687 class Allocator = std::allocator<std::pair<Key, T>>, bool StoreHash = false>
688 using robin_pg_map =
689 robin_map<Key, T, Hash, KeyEqual, Allocator, StoreHash, tsl::rh::prime_growth_policy>;
690
691 } // end namespace tsl
692
693 #endif
tsl::detail_robin_hash::robin_hash::equal_range
std::pair< iterator, iterator > equal_range(const K &key)
Definition: robin_hash.h:886
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:135
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:323
tsl::robin_map::max_bucket_count
size_type max_bucket_count() const
Definition: robin_map.h:628
tsl::detail_robin_hash::robin_hash::end
iterator end() noexcept
Definition: robin_hash.h:593
tsl::robin_map::key_equal
typename ht::key_equal key_equal
Definition: robin_map.h:120
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:318
tsl::robin_map::end
iterator end() noexcept
Definition: robin_map.h:213
tsl::robin_map::ValueSelect::value_type
T value_type
Definition: robin_map.h:100
tsl::robin_map::hash_function
hasher hash_function() const
Definition: robin_map.h:643
tsl::detail_robin_hash::robin_hash::bucket_count
size_type bucket_count() const
Definition: robin_hash.h:912
tsl::robin_map::const_reference
typename ht::const_reference const_reference
Definition: robin_map.h:123
tsl::robin_map::find
iterator find(const K &key, std::size_t precalculated_hash)
Definition: robin_map.h:523
tsl::detail_robin_hash::robin_hash::max_bucket_count
size_type max_bucket_count() const
Definition: robin_hash.h:914
tsl::robin_map::KeySelect
Definition: robin_map.h:84
tsl::robin_map::at
const T & at(const K &key, std::size_t precalculated_hash) const
Definition: robin_map.h:436
tsl::detail_robin_hash::robin_hash::try_emplace
std::pair< iterator, bool > try_emplace(K &&key, Args &&... args)
Definition: robin_hash.h:686
tsl::robin_map::insert
std::pair< iterator, bool > insert(P &&value)
Definition: robin_map.h:233
tsl::robin_map::operator[]
T & operator[](const Key &key)
Definition: robin_map.h:441
tsl::robin_map::find
iterator find(const Key &key, std::size_t precalculated_hash)
Definition: robin_map.h:488
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:324
tsl::robin_map::at
T & at(const K &key)
Definition: robin_map.h:402
tsl::detail_robin_hash::robin_hash::insert
std::pair< iterator, bool > insert(P &&value)
Definition: robin_hash.h:621
tsl::robin_map::at
const T & at(const K &key) const
Definition: robin_map.h:426
tsl::detail_robin_hash::robin_hash::load_factor
float load_factor() const
Definition: robin_hash.h:922
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:316
tsl::robin_map::erase
size_type erase(const K &key, std::size_t precalculated_hash)
Definition: robin_map.h:364
tsl::robin_map::operator!=
friend bool operator!=(const robin_map &lhs, const robin_map &rhs)
Definition: robin_map.h:671
tsl
Definition: hopscotch_growth_policy.h:37
tsl::robin_map::erase
iterator erase(const_iterator first, const_iterator last)
Definition: robin_map.h:331
tsl::robin_map::find
const_iterator find(const Key &key) const
Definition: robin_map.h:493
tsl::robin_map::insert
std::pair< iterator, bool > insert(const value_type &value)
Definition: robin_map.h:229
tsl::robin_map::insert
void insert(InputIt first, InputIt last)
Definition: robin_map.h:257
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:317
tsl::robin_map::find
const_iterator find(const K &key, std::size_t precalculated_hash) const
Definition: robin_map.h:547
tsl::robin_map::key_type
typename ht::key_type key_type
Definition: robin_map.h:114
tsl::robin_map::begin
iterator begin() noexcept
Definition: robin_map.h:209
tsl::detail_robin_hash::robin_hash::begin
iterator begin() noexcept
Definition: robin_hash.h:571
tsl::robin_map::begin
const_iterator begin() const noexcept
Definition: robin_map.h:210
tsl::robin_map::equal_range
std::pair< iterator, iterator > equal_range(const Key &key, std::size_t precalculated_hash)
Definition: robin_map.h:559
tsl::robin_map::max_load_factor
void max_load_factor(float ml)
Definition: robin_map.h:635
tsl::detail_robin_hash::robin_hash::count
size_type count(const K &key) const
Definition: robin_hash.h:857
tsl::robin_map::swap
void swap(robin_map &other)
Definition: robin_map.h:369
tsl::detail_robin_hash::robin_hash::clear
void clear() noexcept
Definition: robin_hash.h:611
tsl::robin_map::end
const_iterator end() const noexcept
Definition: robin_map.h:214
tsl::robin_map::hasher
typename ht::hasher hasher
Definition: robin_map.h:119
tsl::robin_map::insert
iterator insert(const_iterator hint, value_type &&value)
Definition: robin_map.h:252
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:326
tsl::robin_map::mapped_type
T mapped_type
Definition: robin_map.h:115
robin_hash.h
tsl::robin_map::count
size_type count(const K &key) const
Definition: robin_map.h:462
tsl::robin_map::empty
bool empty() const noexcept
Definition: robin_map.h:220
tsl::robin_map::bucket_count
size_type bucket_count() const
Definition: robin_map.h:627
tsl::detail_robin_hash::robin_hash::erase
iterator erase(iterator pos)
Definition: robin_hash.h:707
tsl::detail_robin_hash::robin_hash::cbegin
const_iterator cbegin() const noexcept
Definition: robin_hash.h:583
tsl::detail_robin_hash::robin_hash::size
size_type size() const noexcept
Definition: robin_hash.h:604
tsl::robin_map::equal_range
std::pair< iterator, iterator > equal_range(const Key &key)
Definition: robin_map.h:552
tsl::robin_map::ValueSelect
Definition: robin_map.h:97
tsl::robin_map::allocator_type
typename ht::allocator_type allocator_type
Definition: robin_map.h:121
tsl::robin_map::operator[]
T & operator[](Key &&key)
Definition: robin_map.h:442
tsl::robin_map
Definition: robin_map.h:79
tsl::robin_map::max_size
size_type max_size() const noexcept
Definition: robin_map.h:222
tsl::robin_map::at
const T & at(const Key &key, std::size_t precalculated_hash) const
Definition: robin_map.h:391
tsl::robin_map::try_emplace
iterator try_emplace(const_iterator hint, const key_type &k, Args &&... args)
Definition: robin_map.h:318
tsl::detail_robin_hash::robin_hash::cend
const_iterator cend() const noexcept
Definition: robin_hash.h:597
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:321
tsl::robin_map::insert_or_assign
std::pair< iterator, bool > insert_or_assign(const key_type &k, M &&obj)
Definition: robin_map.h:264
tsl::robin_map::KeySelect::key_type
Key key_type
Definition: robin_map.h:87
tsl::detail_robin_hash::robin_hash::insert_or_assign
std::pair< iterator, bool > insert_or_assign(K &&key, M &&obj)
Definition: robin_hash.h:653
tsl::robin_map::KeySelect::operator()
key_type & operator()(std::pair< Key, T > &key_value) noexcept
Definition: robin_map.h:94
tsl::robin_map::value_type
typename ht::value_type value_type
Definition: robin_map.h:116
tsl::robin_map::count
size_type count(const K &key, std::size_t precalculated_hash) const
Definition: robin_map.h:476
tsl::robin_map::operator=
robin_map & operator=(std::initializer_list< value_type > ilist)
Definition: robin_map.h:194
tsl::robin_map::try_emplace
std::pair< iterator, bool > try_emplace(const key_type &k, Args &&... args)
Definition: robin_map.h:307
tsl::detail_robin_hash::robin_hash::mutable_iterator
iterator mutable_iterator(const_iterator pos)
Definition: robin_hash.h:960
tsl::robin_map::insert_or_assign
iterator insert_or_assign(const_iterator hint, const key_type &k, M &&obj)
Definition: robin_map.h:274
tsl::robin_map::key_eq
key_equal key_eq() const
Definition: robin_map.h:644
tsl::robin_map::const_pointer
typename ht::const_pointer const_pointer
Definition: robin_map.h:125
tsl::robin_map::robin_map
robin_map(size_type bucket_count, const Allocator &alloc)
Definition: robin_map.h:141
tsl::detail_robin_hash::robin_hash::emplace_hint
iterator emplace_hint(const_iterator hint, Args &&... args)
Definition: robin_hash.h:680
tsl::robin_map::robin_map
robin_map()
Definition: robin_map.h:133
tsl::robin_map::try_emplace
std::pair< iterator, bool > try_emplace(key_type &&k, Args &&... args)
Definition: robin_map.h:312
tsl::robin_map::at
T & at(const Key &key, std::size_t precalculated_hash)
Definition: robin_map.h:381
tsl::robin_map::erase
size_type erase(const K &key)
Definition: robin_map.h:350
tsl::robin_map::insert
iterator insert(const_iterator hint, P &&value)
Definition: robin_map.h:247
tsl::detail_robin_hash::robin_hash::max_size
size_type max_size() const noexcept
Definition: robin_hash.h:606
tsl::robin_map::equal_range
std::pair< iterator, iterator > equal_range(const K &key, std::size_t precalculated_hash)
Definition: robin_map.h:598
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:328
tsl::robin_map::load_factor
float load_factor() const
Definition: robin_map.h:633
tsl::detail_robin_hash::robin_hash::swap
void swap(robin_hash &other)
Definition: robin_hash.h:796
tsl::robin_map::erase
iterator erase(const_iterator pos)
Definition: robin_map.h:330
tsl::robin_map::equal_range
std::pair< const_iterator, const_iterator > equal_range(const K &key) const
Definition: robin_map.h:608
tsl::robin_map::find
const_iterator find(const K &key) const
Definition: robin_map.h:533
tsl::robin_map::robin_map
robin_map(std::initializer_list< value_type > init, size_type bucket_count, const Allocator &alloc)
Definition: robin_map.h:182
tsl::robin_map::at
const T & at(const Key &key) const
Definition: robin_map.h:386
tsl::robin_map::find
const_iterator find(const Key &key, std::size_t precalculated_hash) const
Definition: robin_map.h:498
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:322
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:154
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:572
tsl::robin_map::pointer
typename ht::pointer pointer
Definition: robin_map.h:124
tsl::detail_robin_hash::robin_hash::at
U::value_type & at(const K &key)
Definition: robin_hash.h:817
tsl::robin_map::m_ht
ht m_ht
Definition: robin_map.h:679
tsl::robin_map::at
T & at(const Key &key)
Definition: robin_map.h:374
tsl::robin_map::get_allocator
allocator_type get_allocator() const
Definition: robin_map.h:204
tsl::detail_robin_hash::robin_hash::find
iterator find(const K &key)
Definition: robin_hash.h:869
tsl::robin_map::find
iterator find(const Key &key)
Definition: robin_map.h:481
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:175
tsl::detail_robin_hash::has_is_transparent
Definition: robin_hash.h:52
tsl::detail_robin_hash::robin_hash::rehash
void rehash(size_type count_)
Definition: robin_hash.h:939
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:169
tsl::robin_map::insert_or_assign
std::pair< iterator, bool > insert_or_assign(key_type &&k, M &&obj)
Definition: robin_map.h:269
tsl::robin_map::find
iterator find(const K &key)
Definition: robin_map.h:509
tsl::robin_map::cbegin
const_iterator cbegin() const noexcept
Definition: robin_map.h:211
tsl::robin_map::reference
typename ht::reference reference
Definition: robin_map.h:122
tsl::detail_robin_hash::robin_hash::key_eq
key_equal key_eq() const
Definition: robin_hash.h:955
tsl::robin_map::iterator
typename ht::iterator iterator
Definition: robin_map.h:126
tsl::robin_map::operator==
friend bool operator==(const robin_map &lhs, const robin_map &rhs)
Definition: robin_map.h:655
tsl::robin_map::count
size_type count(const Key &key) const
Definition: robin_map.h:444
tsl::robin_map::at
T & at(const K &key, std::size_t precalculated_hash)
Definition: robin_map.h:416
tsl::robin_map::difference_type
typename ht::difference_type difference_type
Definition: robin_map.h:118
tsl::robin_map::emplace_hint
iterator emplace_hint(const_iterator hint, Args &&... args)
Definition: robin_map.h:301
tsl::robin_map::ValueSelect::operator()
value_type & operator()(std::pair< Key, T > &key_value) noexcept
Definition: robin_map.h:107
tsl::robin_map::count
size_type count(const Key &key, std::size_t precalculated_hash) const
Definition: robin_map.h:451
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:1204
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:188
tsl::robin_map::equal_range
std::pair< iterator, iterator > equal_range(const K &key)
Definition: robin_map.h:584
tsl::robin_map::ValueSelect::operator()
const value_type & operator()(const std::pair< Key, T > &key_value) const noexcept
Definition: robin_map.h:102
tsl::robin_map::insert
void insert(std::initializer_list< value_type > ilist)
Definition: robin_map.h:259
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:320
tsl::robin_map::robin_map
robin_map(const Allocator &alloc)
Definition: robin_map.h:151
tsl::detail_robin_hash::robin_hash::reserve
void reserve(size_type count_)
Definition: robin_hash.h:945
tsl::robin_map::clear
void clear() noexcept
Definition: robin_map.h:227
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:111
tsl::detail_robin_hash::robin_hash::hash_function
hasher hash_function() const
Definition: robin_hash.h:953
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:327
tsl::detail_robin_hash::robin_hash::emplace
std::pair< iterator, bool > emplace(Args &&... args)
Definition: robin_hash.h:675
tsl::detail_robin_hash::robin_hash
Definition: robin_hash.h:302
tsl::robin_map::robin_map
robin_map(InputIt first, InputIt last, size_type bucket_count, const Allocator &alloc)
Definition: robin_map.h:163
tsl::robin_map::insert
iterator insert(const_iterator hint, const value_type &value)
Definition: robin_map.h:240
tsl::robin_map::size_type
typename ht::size_type size_type
Definition: robin_map.h:117
tsl::robin_map::swap
friend void swap(robin_map &lhs, robin_map &rhs)
Definition: robin_map.h:676
tsl::robin_map::size
size_type size() const noexcept
Definition: robin_map.h:221
tsl::robin_map::reserve
void reserve(size_type count_)
Definition: robin_map.h:638
tsl::robin_map::erase
size_type erase(const key_type &key)
Definition: robin_map.h:332
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:618
tsl::robin_map::insert
std::pair< iterator, bool > insert(value_type &&value)
Definition: robin_map.h:238
tsl::robin_map::erase
iterator erase(iterator pos)
Definition: robin_map.h:329
tsl::robin_map::insert_or_assign
iterator insert_or_assign(const_iterator hint, key_type &&k, M &&obj)
Definition: robin_map.h:279
tsl::robin_map::rehash
void rehash(size_type count_)
Definition: robin_map.h:637
tsl::robin_map::robin_map
robin_map(size_type bucket_count, const Hash &hash, const Allocator &alloc)
Definition: robin_map.h:146
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:319
tsl::detail_robin_hash::robin_hash::max_load_factor
float max_load_factor() const
Definition: robin_hash.h:931
tsl::detail_robin_hash::robin_hash::empty
bool empty() const noexcept
Definition: robin_hash.h:602
tsl::robin_map::max_load_factor
float max_load_factor() const
Definition: robin_map.h:634
tsl::robin_map::cend
const_iterator cend() const noexcept
Definition: robin_map.h:215
tsl::robin_map::KeySelect::operator()
const key_type & operator()(const std::pair< Key, T > &key_value) const noexcept
Definition: robin_map.h:89
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:325
tsl::robin_map::mutable_iterator
iterator mutable_iterator(const_iterator pos)
Definition: robin_map.h:653
tsl::robin_map::erase
size_type erase(const key_type &key, std::size_t precalculated_hash)
Definition: robin_map.h:339
tsl::detail_robin_hash::robin_hash::get_allocator
allocator_type get_allocator() const
Definition: robin_hash.h:566
tsl::robin_map::try_emplace
iterator try_emplace(const_iterator hint, key_type &&k, Args &&... args)
Definition: robin_map.h:324
tsl::robin_map::emplace
std::pair< iterator, bool > emplace(Args &&... args)
Definition: robin_map.h:290
tsl::robin_map::equal_range
std::pair< const_iterator, const_iterator > equal_range(const Key &key) const
Definition: robin_map.h:564
tsl::robin_map::const_iterator
typename ht::const_iterator const_iterator
Definition: robin_map.h:127