IOSS 2.0

hopscotch_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_HOPSCOTCH_MAP_H
25 #define TSL_HOPSCOTCH_MAP_H
26
27 #include "hopscotch_hash.h"
28 #include <algorithm>
29 #include <cstddef>
30 #include <functional>
31 #include <initializer_list>
32 #include <list>
33 #include <memory>
34 #include <type_traits>
35 #include <utility>
36
37 namespace tsl {
38
39 /**
40 * Implementation of a hash map using the hopscotch hashing algorithm.
41 *
42 * The Key and the value T must be either nothrow move-constructible, copy-constuctible or both.
43 *
44 * The size of the neighborhood (NeighborhoodSize) must be > 0 and <= 62 if StoreHash is false.
45 * When StoreHash is true, 32-bits of the hash will be stored alongside the neighborhood limiting
46 * the NeighborhoodSize to <= 30. There is no memory usage difference between
47 * 'NeighborhoodSize 62; StoreHash false' and 'NeighborhoodSize 30; StoreHash true'.
48 *
49 * Storing the hash may improve performance on insert during the rehash process if the hash takes
50 * time to compute. It may also improve read performance if the KeyEqual function takes time (or
51 * incurs a cache-miss). If used with simple Hash and KeyEqual it may slow things down.
52 *
53 * StoreHash can only be set if the GrowthPolicy is set to tsl::power_of_two_growth_policy.
54 *
55 * GrowthPolicy defines how the map grows and consequently how a hash value is mapped to a bucket.
56 * By default the map uses tsl::power_of_two_growth_policy. This policy keeps the number of
57 * buckets to a power of two and uses a mask to map the hash to a bucket instead of the slow
58 * modulo. You may define your own growth policy, check tsl::power_of_two_growth_policy for the
59 * interface.
60 *
61 * If the destructors of Key or T throw an exception, behaviour of the class is undefined.
62 *
63 * Iterators invalidation:
64 * - clear, operator=, reserve, rehash: always invalidate the iterators.
65 * - insert, emplace, emplace_hint, operator[]: if there is an effective insert, invalidate the
66 * iterators if a displacement is needed to resolve a collision (which mean that most of the time,
67 * insert will invalidate the iterators). Or if there is a rehash.
68 * - erase: iterator on the erased element is the only one which become invalid.
69 */
70 template <class Key, class T, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>,
71 class Allocator = std::allocator<std::pair<Key, T>>, unsigned int NeighborhoodSize = 62,
72 bool StoreHash = false, class GrowthPolicy = tsl::hh::power_of_two_growth_policy<2>>
73 class hopscotch_map
74 {
75 private:
76 template <typename U>
77 using has_is_transparent = tsl::detail_hopscotch_hash::has_is_transparent<U>;
78
79 class KeySelect
80 {
81 public:
82 using key_type = Key;
83
84 const key_type &operator()(const std::pair<Key, T> &key_value) const
85 {
86 return key_value.first;
87 }
88
89 key_type &operator()(std::pair<Key, T> &key_value) { return key_value.first; }
90 };
91
92 class ValueSelect
93 {
94 public:
95 using value_type = T;
96
97 const value_type &operator()(const std::pair<Key, T> &key_value) const
98 {
99 return key_value.second;
100 }
101
102 value_type &operator()(std::pair<Key, T> &key_value) { return key_value.second; }
103 };
104
105 using overflow_container_type = std::list<std::pair<Key, T>, Allocator>;
106 using ht =
107 detail_hopscotch_hash::hopscotch_hash<std::pair<Key, T>, KeySelect, ValueSelect, Hash,
108 KeyEqual, Allocator, NeighborhoodSize, StoreHash,
109 GrowthPolicy, overflow_container_type>;
110
111 public:
112 using key_type = typename ht::key_type;
113 using mapped_type = T;
114 using value_type = typename ht::value_type;
115 using size_type = typename ht::size_type;
116 using difference_type = typename ht::difference_type;
117 using hasher = typename ht::hasher;
118 using key_equal = typename ht::key_equal;
119 using allocator_type = typename ht::allocator_type;
120 using reference = typename ht::reference;
121 using const_reference = typename ht::const_reference;
122 using pointer = typename ht::pointer;
123 using const_pointer = typename ht::const_pointer;
124 using iterator = typename ht::iterator;
125 using const_iterator = typename ht::const_iterator;
126
127 /*
128 * Constructors
129 */
130 hopscotch_map() : hopscotch_map(ht::DEFAULT_INIT_BUCKETS_SIZE) {}
131
132 explicit hopscotch_map(size_type bucket_count, const Hash &hash = Hash(),
133 const KeyEqual &equal = KeyEqual(), const Allocator &alloc = Allocator())
134 : m_ht(bucket_count, hash, equal, alloc, ht::DEFAULT_MAX_LOAD_FACTOR)
135 {
136 }
137
138 hopscotch_map(size_type bucket_count, const Allocator &alloc)
139 : hopscotch_map(bucket_count, Hash(), KeyEqual(), alloc)
140 {
141 }
142
143 hopscotch_map(size_type bucket_count, const Hash &hash, const Allocator &alloc)
144 : hopscotch_map(bucket_count, hash, KeyEqual(), alloc)
145 {
146 }
147
148 explicit hopscotch_map(const Allocator &alloc)
149 : hopscotch_map(ht::DEFAULT_INIT_BUCKETS_SIZE, alloc)
150 {
151 }
152
153 template <class InputIt>
154 hopscotch_map(InputIt first, InputIt last,
155 size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE, const Hash &hash = Hash(),
156 const KeyEqual &equal = KeyEqual(), const Allocator &alloc = Allocator())
157 : hopscotch_map(bucket_count, hash, equal, alloc)
158 {
159 insert(first, last);
160 }
161
162 template <class InputIt>
163 hopscotch_map(InputIt first, InputIt last, size_type bucket_count, const Allocator &alloc)
164 : hopscotch_map(first, last, bucket_count, Hash(), KeyEqual(), alloc)
165 {
166 }
167
168 template <class InputIt>
169 hopscotch_map(InputIt first, InputIt last, size_type bucket_count, const Hash &hash,
170 const Allocator &alloc)
171 : hopscotch_map(first, last, bucket_count, hash, KeyEqual(), alloc)
172 {
173 }
174
175 hopscotch_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 : hopscotch_map(init.begin(), init.end(), bucket_count, hash, equal, alloc)
179 {
180 }
181
182 hopscotch_map(std::initializer_list<value_type> init, size_type bucket_count,
183 const Allocator &alloc)
184 : hopscotch_map(init.begin(), init.end(), bucket_count, Hash(), KeyEqual(), alloc)
185 {
186 }
187
188 hopscotch_map(std::initializer_list<value_type> init, size_type bucket_count, const Hash &hash,
189 const Allocator &alloc)
190 : hopscotch_map(init.begin(), init.end(), bucket_count, hash, KeyEqual(), alloc)
191 {
192 }
193
194 hopscotch_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.insert(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.insert(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(hopscotch_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 bool contains(const Key &key) const { return m_ht.contains(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 bool contains(const Key &key, std::size_t precalculated_hash) const
560 {
561 return m_ht.contains(key, precalculated_hash);
562 }
563
564 /**
565 * This overload only participates in the overload resolution if the typedef
566 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
567 */
568 template <class K, class KE = KeyEqual,
569 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
570 bool contains(const K &key) const
571 {
572 return m_ht.contains(key);
573 }
574
575 /**
576 * @copydoc contains(const K& key) const
577 *
578 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
579 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
580 * hash.
581 */
582 template <class K, class KE = KeyEqual,
583 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
584 bool contains(const K &key, std::size_t precalculated_hash) const
585 {
586 return m_ht.contains(key, precalculated_hash);
587 }
588
589 std::pair<iterator, iterator> equal_range(const Key &key) { return m_ht.equal_range(key); }
590
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 std::pair<iterator, iterator> equal_range(const Key &key, std::size_t precalculated_hash)
597 {
598 return m_ht.equal_range(key, precalculated_hash);
599 }
600
601 std::pair<const_iterator, const_iterator> equal_range(const Key &key) const
602 {
603 return m_ht.equal_range(key);
604 }
605
606 /**
607 * @copydoc equal_range(const Key& key, std::size_t precalculated_hash)
608 */
609 std::pair<const_iterator, const_iterator> equal_range(const Key & key,
610 std::size_t precalculated_hash) const
611 {
612 return m_ht.equal_range(key, precalculated_hash);
613 }
614
615 /**
616 * This overload only participates in the overload resolution if the typedef
617 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
618 */
619 template <class K, class KE = KeyEqual,
620 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
621 std::pair<iterator, iterator> equal_range(const K &key)
622 {
623 return m_ht.equal_range(key);
624 }
625
626 /**
627 * @copydoc equal_range(const K& key)
628 *
629 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
630 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
631 * hash.
632 */
633 template <class K, class KE = KeyEqual,
634 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
635 std::pair<iterator, iterator> equal_range(const K &key, std::size_t precalculated_hash)
636 {
637 return m_ht.equal_range(key, precalculated_hash);
638 }
639
640 /**
641 * @copydoc equal_range(const K& key)
642 */
643 template <class K, class KE = KeyEqual,
644 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
645 std::pair<const_iterator, const_iterator> equal_range(const K &key) const
646 {
647 return m_ht.equal_range(key);
648 }
649
650 /**
651 * @copydoc equal_range(const K& key, std::size_t precalculated_hash)
652 */
653 template <class K, class KE = KeyEqual,
654 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
655 std::pair<const_iterator, const_iterator> equal_range(const K & key,
656 std::size_t precalculated_hash) const
657 {
658 return m_ht.equal_range(key, precalculated_hash);
659 }
660
661 /*
662 * Bucket interface
663 */
664 size_type bucket_count() const { return m_ht.bucket_count(); }
665 size_type max_bucket_count() const { return m_ht.max_bucket_count(); }
666
667 /*
668 * Hash policy
669 */
670 float load_factor() const { return m_ht.load_factor(); }
671 float max_load_factor() const { return m_ht.max_load_factor(); }
672 void max_load_factor(float ml) { m_ht.max_load_factor(ml); }
673
674 void rehash(size_type count_) { m_ht.rehash(count_); }
675 void reserve(size_type count_) { m_ht.reserve(count_); }
676
677 /*
678 * Observers
679 */
680 hasher hash_function() const { return m_ht.hash_function(); }
681 key_equal key_eq() const { return m_ht.key_eq(); }
682
683 /*
684 * Other
685 */
686
687 /**
688 * Convert a const_iterator to an iterator.
689 */
690 iterator mutable_iterator(const_iterator pos) { return m_ht.mutable_iterator(pos); }
691
692 size_type overflow_size() const noexcept { return m_ht.overflow_size(); }
693
694 friend bool operator==(const hopscotch_map &lhs, const hopscotch_map &rhs)
695 {
696 if (lhs.size() != rhs.size()) {
697 return false;
698 }
699
700 for (const auto &element_lhs : lhs) {
701 const auto it_element_rhs = rhs.find(element_lhs.first);
702 if (it_element_rhs == rhs.cend() || element_lhs.second != it_element_rhs->second) {
703 return false;
704 }
705 }
706
707 return true;
708 }
709
710 friend bool operator!=(const hopscotch_map &lhs, const hopscotch_map &rhs)
711 {
712 return !operator==(lhs, rhs);
713 }
714
715 friend void swap(hopscotch_map &lhs, hopscotch_map &rhs) { lhs.swap(rhs); }
716
717 private:
718 ht m_ht;
719 };
720
721 /**
722 * Same as `tsl::hopscotch_map<Key, T, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash,
723 * tsl::hh::prime_growth_policy>`.
724 */
725 template <class Key, class T, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>,
726 class Allocator = std::allocator<std::pair<Key, T>>, unsigned int NeighborhoodSize = 62,
727 bool StoreHash = false>
728 using hopscotch_pg_map = hopscotch_map<Key, T, Hash, KeyEqual, Allocator, NeighborhoodSize,
729 StoreHash, tsl::hh::prime_growth_policy>;
730
731 } // end namespace tsl
732
733 #endif
tsl::detail_hopscotch_hash::hopscotch_hash::equal_range
std::pair< iterator, iterator > equal_range(const K &key)
Definition: hopscotch_hash.h:1087
tsl::hopscotch_map::ValueSelect::operator()
value_type & operator()(std::pair< Key, T > &key_value)
Definition: hopscotch_map.h:102
tsl::detail_hopscotch_hash::hopscotch_hash::max_load_factor
float max_load_factor() const
Definition: hopscotch_hash.h:1147
tsl::hopscotch_map::at
T & at(const K &key)
Definition: hopscotch_map.h:402
tsl::hopscotch_map::cend
const_iterator cend() const noexcept
Definition: hopscotch_map.h:215
tsl::hopscotch_map::insert
iterator insert(const_iterator hint, P &&value)
Definition: hopscotch_map.h:247
tsl
Definition: bhopscotch_map.h:37
tsl::hopscotch_map::max_size
size_type max_size() const noexcept
Definition: hopscotch_map.h:222
tsl::hopscotch_map::max_load_factor
void max_load_factor(float ml)
Definition: hopscotch_map.h:672
tsl::hopscotch_map::overflow_container_type
std::list< std::pair< Key, T >, Allocator > overflow_container_type
Definition: hopscotch_map.h:105
tsl::hopscotch_map::KeySelect
Definition: hopscotch_map.h:79
tsl::detail_hopscotch_hash::hopscotch_hash::try_emplace
std::pair< iterator, bool > try_emplace(const key_type &k, Args &&... args)
Definition: hopscotch_hash.h:887
tsl::hopscotch_map::ValueSelect::value_type
T value_type
Definition: hopscotch_map.h:95
tsl::hopscotch_map::find
const_iterator find(const K &key, std::size_t precalculated_hash) const
Definition: hopscotch_map.h:547
tsl::hopscotch_map::equal_range
std::pair< const_iterator, const_iterator > equal_range(const K &key, std::size_t precalculated_hash) const
Definition: hopscotch_map.h:655
tsl::hopscotch_map::max_bucket_count
size_type max_bucket_count() const
Definition: hopscotch_map.h:665
tsl::hopscotch_map::try_emplace
iterator try_emplace(const_iterator hint, const key_type &k, Args &&... args)
Definition: hopscotch_map.h:318
tsl::hopscotch_map::hopscotch_map
hopscotch_map(size_type bucket_count, const Allocator &alloc)
Definition: hopscotch_map.h:138
tsl::hopscotch_map::operator==
friend bool operator==(const hopscotch_map &lhs, const hopscotch_map &rhs)
Definition: hopscotch_map.h:694
tsl::detail_hopscotch_hash::hopscotch_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::reference
value_type & reference
Definition: hopscotch_hash.h:440
tsl::hopscotch_map::at
T & at(const K &key, std::size_t precalculated_hash)
Definition: hopscotch_map.h:416
tsl::hopscotch_map::end
iterator end() noexcept
Definition: hopscotch_map.h:213
tsl::hopscotch_map::hasher
typename ht::hasher hasher
Definition: hopscotch_map.h:117
tsl::hopscotch_map::at
const T & at(const K &key) const
Definition: hopscotch_map.h:426
tsl::hopscotch_map::mutable_iterator
iterator mutable_iterator(const_iterator pos)
Definition: hopscotch_map.h:690
tsl::hopscotch_map::hopscotch_map
hopscotch_map(InputIt first, InputIt last, size_type bucket_count, const Allocator &alloc)
Definition: hopscotch_map.h:163
tsl::hopscotch_map::allocator_type
typename ht::allocator_type allocator_type
Definition: hopscotch_map.h:119
tsl::detail_hopscotch_hash::hopscotch_hash::insert
std::pair< iterator, bool > insert(const value_type &value)
Definition: hopscotch_hash.h:786
tsl::detail_hopscotch_hash::hopscotch_hash::clear
void clear() noexcept
Definition: hopscotch_hash.h:776
tsl::hopscotch_map::equal_range
std::pair< const_iterator, const_iterator > equal_range(const Key &key) const
Definition: hopscotch_map.h:601
tsl::detail_hopscotch_hash::hopscotch_hash::rehash
void rehash(size_type count_)
Definition: hopscotch_hash.h:1156
tsl::detail_hopscotch_hash::hopscotch_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::allocator_type
Allocator allocator_type
Definition: hopscotch_hash.h:439
anonymous_namespace{Ioss_SmartAssert.C}::init
struct anonymous_namespace{Ioss_SmartAssert.C}::assert_initializer init
tsl::hopscotch_map::equal_range
std::pair< const_iterator, const_iterator > equal_range(const K &key) const
Definition: hopscotch_map.h:645
tsl::hopscotch_map::contains
bool contains(const Key &key, std::size_t precalculated_hash) const
Definition: hopscotch_map.h:559
tsl::hopscotch_map::const_reference
typename ht::const_reference const_reference
Definition: hopscotch_map.h:121
tsl::hopscotch_map::insert_or_assign
iterator insert_or_assign(const_iterator hint, key_type &&k, M &&obj)
Definition: hopscotch_map.h:279
tsl::hopscotch_map::count
size_type count(const Key &key) const
Definition: hopscotch_map.h:444
tsl::hopscotch_map::begin
const_iterator begin() const noexcept
Definition: hopscotch_map.h:210
tsl::hopscotch_map::contains
bool contains(const Key &key) const
Definition: hopscotch_map.h:552
tsl::hopscotch_map::key_type
typename ht::key_type key_type
Definition: hopscotch_map.h:112
tsl::detail_hopscotch_hash::hopscotch_hash::get_allocator
allocator_type get_allocator() const
Definition: hopscotch_hash.h:724
tsl::hopscotch_map::rehash
void rehash(size_type count_)
Definition: hopscotch_map.h:674
tsl::detail_hopscotch_hash::hopscotch_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::const_reference
const value_type & const_reference
Definition: hopscotch_hash.h:441
tsl::detail_hopscotch_hash::hopscotch_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::hasher
Hash hasher
Definition: hopscotch_hash.h:437
tsl::hopscotch_map::erase
iterator erase(const_iterator pos)
Definition: hopscotch_map.h:330
tsl::detail_hopscotch_hash::hopscotch_hash::overflow_size
size_type overflow_size() const noexcept
Definition: hopscotch_hash.h:1192
tsl::detail_hopscotch_hash::hopscotch_hash::contains
bool contains(const K &key) const
Definition: hopscotch_hash.h:1080
tsl::hopscotch_map::at
const T & at(const Key &key, std::size_t precalculated_hash) const
Definition: hopscotch_map.h:391
tsl::detail_hopscotch_hash::hopscotch_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::key_type
typename KeySelect::key_type key_type
Definition: hopscotch_hash.h:433
tsl::hopscotch_map::empty
bool empty() const noexcept
Definition: hopscotch_map.h:220
tsl::hopscotch_map::erase
size_type erase(const K &key)
Definition: hopscotch_map.h:350
tsl::hopscotch_map::size
size_type size() const noexcept
Definition: hopscotch_map.h:221
tsl::hopscotch_map::const_pointer
typename ht::const_pointer const_pointer
Definition: hopscotch_map.h:123
tsl::hopscotch_map::erase
size_type erase(const key_type &key, std::size_t precalculated_hash)
Definition: hopscotch_map.h:339
tsl::hopscotch_map::difference_type
typename ht::difference_type difference_type
Definition: hopscotch_map.h:116
tsl::hopscotch_map::size_type
typename ht::size_type size_type
Definition: hopscotch_map.h:115
tsl::detail_hopscotch_hash::hopscotch_hash::hash_function
hasher hash_function() const
Definition: hopscotch_hash.h:1170
tsl::hopscotch_map::reference
typename ht::reference reference
Definition: hopscotch_map.h:120
tsl::hopscotch_map::emplace_hint
iterator emplace_hint(const_iterator hint, Args &&... args)
Definition: hopscotch_map.h:301
tsl::detail_hopscotch_hash::hopscotch_hash::load_factor
float load_factor() const
Definition: hopscotch_hash.h:1138
tsl::hopscotch_map::find
iterator find(const Key &key, std::size_t precalculated_hash)
Definition: hopscotch_map.h:488
tsl::hopscotch_map::hopscotch_map
hopscotch_map(std::initializer_list< value_type > init, size_type bucket_count, const Allocator &alloc)
Definition: hopscotch_map.h:182
tsl::hopscotch_map::operator[]
T & operator[](const Key &key)
Definition: hopscotch_map.h:441
tsl::detail_hopscotch_hash::hopscotch_hash::emplace
std::pair< iterator, bool > emplace(Args &&... args)
Definition: hopscotch_hash.h:876
tsl::detail_hopscotch_hash::hopscotch_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::difference_type
std::ptrdiff_t difference_type
Definition: hopscotch_hash.h:436
tsl::detail_hopscotch_hash::hopscotch_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::DEFAULT_INIT_BUCKETS_SIZE
static const size_type DEFAULT_INIT_BUCKETS_SIZE
Definition: hopscotch_hash.h:1763
tsl::hopscotch_map::insert
void insert(InputIt first, InputIt last)
Definition: hopscotch_map.h:257
tsl::hopscotch_map::iterator
typename ht::iterator iterator
Definition: hopscotch_map.h:124
tsl::hopscotch_map::hopscotch_map
hopscotch_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: hopscotch_map.h:154
tsl::hopscotch_map::equal_range
std::pair< iterator, iterator > equal_range(const Key &key, std::size_t precalculated_hash)
Definition: hopscotch_map.h:596
tsl::detail_hopscotch_hash::hopscotch_hash::max_size
size_type max_size() const noexcept
Definition: hopscotch_hash.h:771
tsl::hopscotch_map::insert
void insert(std::initializer_list< value_type > ilist)
Definition: hopscotch_map.h:259
tsl::hopscotch_map::insert
std::pair< iterator, bool > insert(value_type &&value)
Definition: hopscotch_map.h:238
tsl::detail_hopscotch_hash::hopscotch_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::value_type
std::pair< Key, T > value_type
Definition: hopscotch_hash.h:434
tsl::hopscotch_map::hopscotch_map
hopscotch_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: hopscotch_map.h:175
tsl::hopscotch_map::find
iterator find(const K &key)
Definition: hopscotch_map.h:509
tsl::hopscotch_map::find
const_iterator find(const K &key) const
Definition: hopscotch_map.h:533
tsl::hopscotch_map::hopscotch_map
hopscotch_map()
Definition: hopscotch_map.h:130
tsl::hopscotch_map::KeySelect::operator()
key_type & operator()(std::pair< Key, T > &key_value)
Definition: hopscotch_map.h:89
tsl::hopscotch_map::get_allocator
allocator_type get_allocator() const
Definition: hopscotch_map.h:204
tsl::detail_hopscotch_hash::hopscotch_hash::end
iterator end() noexcept
Definition: hopscotch_hash.h:751
tsl::detail_hopscotch_hash::hopscotch_hash::size
size_type size() const noexcept
Definition: hopscotch_hash.h:769
tsl::hopscotch_map::at
const T & at(const Key &key) const
Definition: hopscotch_map.h:386
tsl::hopscotch_map::find
iterator find(const K &key, std::size_t precalculated_hash)
Definition: hopscotch_map.h:523
tsl::hopscotch_map::equal_range
std::pair< const_iterator, const_iterator > equal_range(const Key &key, std::size_t precalculated_hash) const
Definition: hopscotch_map.h:609
tsl::hopscotch_map::key_equal
typename ht::key_equal key_equal
Definition: hopscotch_map.h:118
tsl::hopscotch_map::swap
void swap(hopscotch_map &other)
Definition: hopscotch_map.h:369
tsl::detail_hopscotch_hash::hopscotch_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::key_equal
KeyEqual key_equal
Definition: hopscotch_hash.h:438
tsl::hopscotch_map::hash_function
hasher hash_function() const
Definition: hopscotch_map.h:680
tsl::detail_hopscotch_hash::hopscotch_hash::reserve
void reserve(size_type count_)
Definition: hopscotch_hash.h:1162
tsl::detail_hopscotch_hash::hopscotch_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::size_type
std::size_t size_type
Definition: hopscotch_hash.h:435
tsl::hopscotch_map::try_emplace
iterator try_emplace(const_iterator hint, key_type &&k, Args &&... args)
Definition: hopscotch_map.h:324
tsl::hopscotch_map::cbegin
const_iterator cbegin() const noexcept
Definition: hopscotch_map.h:211
tsl::hopscotch_map::insert
std::pair< iterator, bool > insert(const value_type &value)
Definition: hopscotch_map.h:229
tsl::hopscotch_map::insert_or_assign
std::pair< iterator, bool > insert_or_assign(const key_type &k, M &&obj)
Definition: hopscotch_map.h:264
tsl::hopscotch_map::equal_range
std::pair< iterator, iterator > equal_range(const K &key)
Definition: hopscotch_map.h:621
tsl::detail_hopscotch_hash::hopscotch_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::const_iterator
hopscotch_iterator< true > const_iterator
Definition: hopscotch_hash.h:445
tsl::hopscotch_map::mapped_type
T mapped_type
Definition: hopscotch_map.h:113
tsl::hopscotch_map::contains
bool contains(const K &key, std::size_t precalculated_hash) const
Definition: hopscotch_map.h:584
tsl::detail_hopscotch_hash::hopscotch_hash::begin
iterator begin() noexcept
Definition: hopscotch_hash.h:729
tsl::hopscotch_map::const_iterator
typename ht::const_iterator const_iterator
Definition: hopscotch_map.h:125
tsl::hopscotch_map::value_type
typename ht::value_type value_type
Definition: hopscotch_map.h:114
tsl::hopscotch_map::swap
friend void swap(hopscotch_map &lhs, hopscotch_map &rhs)
Definition: hopscotch_map.h:715
tsl::detail_hopscotch_hash::hopscotch_hash::insert_or_assign
std::pair< iterator, bool > insert_or_assign(const key_type &k, M &&obj)
Definition: hopscotch_hash.h:842
tsl::detail_hopscotch_hash::hopscotch_hash::erase
iterator erase(iterator pos)
Definition: hopscotch_hash.h:921
tsl::hopscotch_map::equal_range
std::pair< iterator, iterator > equal_range(const Key &key)
Definition: hopscotch_map.h:589
tsl::detail_hopscotch_hash::hopscotch_hash::find
iterator find(const K &key)
Definition: hopscotch_hash.h:1063
tsl::detail_hopscotch_hash::hopscotch_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::const_pointer
const value_type * const_pointer
Definition: hopscotch_hash.h:443
tsl::hopscotch_map::count
size_type count(const Key &key, std::size_t precalculated_hash) const
Definition: hopscotch_map.h:451
tsl::detail_hopscotch_hash::hopscotch_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::pointer
value_type * pointer
Definition: hopscotch_hash.h:442
tsl::hopscotch_map::contains
bool contains(const K &key) const
Definition: hopscotch_map.h:570
tsl::detail_hopscotch_hash::hopscotch_hash::emplace_hint
iterator emplace_hint(const_iterator hint, Args &&... args)
Definition: hopscotch_hash.h:881
tsl::detail_hopscotch_hash::hopscotch_hash::cbegin
const_iterator cbegin() const noexcept
Definition: hopscotch_hash.h:741
tsl::detail_hopscotch_hash::hopscotch_hash::key_eq
key_equal key_eq() const
Definition: hopscotch_hash.h:1172
tsl::hopscotch_map::overflow_size
size_type overflow_size() const noexcept
Definition: hopscotch_map.h:692
tsl::hopscotch_map::hopscotch_map
hopscotch_map(const Allocator &alloc)
Definition: hopscotch_map.h:148
tsl::detail_hopscotch_hash::has_is_transparent
Definition: hopscotch_hash.h:69
tsl::hopscotch_map::count
size_type count(const K &key) const
Definition: hopscotch_map.h:462
tsl::hopscotch_map::m_ht
ht m_ht
Definition: hopscotch_map.h:718
tsl::hopscotch_map::hopscotch_map
hopscotch_map(size_type bucket_count, const Hash &hash, const Allocator &alloc)
Definition: hopscotch_map.h:143
tsl::hopscotch_map::reserve
void reserve(size_type count_)
Definition: hopscotch_map.h:675
tsl::hopscotch_map::equal_range
std::pair< iterator, iterator > equal_range(const K &key, std::size_t precalculated_hash)
Definition: hopscotch_map.h:635
tsl::hopscotch_map::operator=
hopscotch_map & operator=(std::initializer_list< value_type > ilist)
Definition: hopscotch_map.h:194
tsl::detail_hopscotch_hash::hopscotch_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::iterator
hopscotch_iterator< false > iterator
Definition: hopscotch_hash.h:444
tsl::hopscotch_map::hopscotch_map
hopscotch_map(InputIt first, InputIt last, size_type bucket_count, const Hash &hash, const Allocator &alloc)
Definition: hopscotch_map.h:169
tsl::hopscotch_map::max_load_factor
float max_load_factor() const
Definition: hopscotch_map.h:671
tsl::hopscotch_map::hopscotch_map
hopscotch_map(size_type bucket_count, const Hash &hash=Hash(), const KeyEqual &equal=KeyEqual(), const Allocator &alloc=Allocator())
Definition: hopscotch_map.h:132
tsl::detail_hopscotch_hash::hopscotch_hash::swap
void swap(hopscotch_hash &other)
Definition: hopscotch_hash.h:980
tsl::hopscotch_map::insert
std::pair< iterator, bool > insert(P &&value)
Definition: hopscotch_map.h:233
tsl::hopscotch_map::pointer
typename ht::pointer pointer
Definition: hopscotch_map.h:122
tsl::hopscotch_map::count
size_type count(const K &key, std::size_t precalculated_hash) const
Definition: hopscotch_map.h:476
tsl::detail_hopscotch_hash::hopscotch_hash::empty
bool empty() const noexcept
Definition: hopscotch_hash.h:767
tsl::hopscotch_map::key_eq
key_equal key_eq() const
Definition: hopscotch_map.h:681
tsl::detail_hopscotch_hash::hopscotch_hash::count
size_type count(const K &key) const
Definition: hopscotch_hash.h:1056
tsl::hopscotch_map::operator!=
friend bool operator!=(const hopscotch_map &lhs, const hopscotch_map &rhs)
Definition: hopscotch_map.h:710
tsl::hopscotch_map::ValueSelect
Definition: hopscotch_map.h:92
tsl::detail_hopscotch_hash::hopscotch_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >
tsl::hopscotch_map::operator[]
T & operator[](Key &&key)
Definition: hopscotch_map.h:442
tsl::hopscotch_map::begin
iterator begin() noexcept
Definition: hopscotch_map.h:209
tsl::hopscotch_map::load_factor
float load_factor() const
Definition: hopscotch_map.h:670
tsl::hopscotch_map::KeySelect::key_type
Key key_type
Definition: hopscotch_map.h:82
tsl::hopscotch_map
Definition: hopscotch_map.h:73
tsl::hopscotch_map::find
iterator find(const Key &key)
Definition: hopscotch_map.h:481
tsl::detail_hopscotch_hash::hopscotch_hash::cend
const_iterator cend() const noexcept
Definition: hopscotch_hash.h:758
tsl::hopscotch_map::at
const T & at(const K &key, std::size_t precalculated_hash) const
Definition: hopscotch_map.h:436
tsl::hopscotch_map::end
const_iterator end() const noexcept
Definition: hopscotch_map.h:214
tsl::detail_hopscotch_hash::hopscotch_hash::max_bucket_count
size_type max_bucket_count() const
Definition: hopscotch_hash.h:1128
tsl::hopscotch_map::insert
iterator insert(const_iterator hint, const value_type &value)
Definition: hopscotch_map.h:240
tsl::detail_hopscotch_hash::hopscotch_hash::at
U::value_type & at(const K &key)
Definition: hopscotch_hash.h:1001
tsl::hopscotch_map::erase
size_type erase(const key_type &key)
Definition: hopscotch_map.h:332
tsl::hopscotch_map::find
const_iterator find(const Key &key, std::size_t precalculated_hash) const
Definition: hopscotch_map.h:498
hopscotch_hash.h
tsl::hopscotch_map::bucket_count
size_type bucket_count() const
Definition: hopscotch_map.h:664
tsl::hopscotch_map::try_emplace
std::pair< iterator, bool > try_emplace(key_type &&k, Args &&... args)
Definition: hopscotch_map.h:312
tsl::hopscotch_map::insert_or_assign
iterator insert_or_assign(const_iterator hint, const key_type &k, M &&obj)
Definition: hopscotch_map.h:274
tsl::hopscotch_map::insert_or_assign
std::pair< iterator, bool > insert_or_assign(key_type &&k, M &&obj)
Definition: hopscotch_map.h:269
tsl::hopscotch_map::erase
iterator erase(iterator pos)
Definition: hopscotch_map.h:329
tsl::hopscotch_map::erase
iterator erase(const_iterator first, const_iterator last)
Definition: hopscotch_map.h:331
tsl::hopscotch_map::ValueSelect::operator()
const value_type & operator()(const std::pair< Key, T > &key_value) const
Definition: hopscotch_map.h:97
tsl::hopscotch_map::KeySelect::operator()
const key_type & operator()(const std::pair< Key, T > &key_value) const
Definition: hopscotch_map.h:84
tsl::hopscotch_map::at
T & at(const Key &key, std::size_t precalculated_hash)
Definition: hopscotch_map.h:381
tsl::hopscotch_map::find
const_iterator find(const Key &key) const
Definition: hopscotch_map.h:493
tsl::hopscotch_map::hopscotch_map
hopscotch_map(std::initializer_list< value_type > init, size_type bucket_count, const Hash &hash, const Allocator &alloc)
Definition: hopscotch_map.h:188
tsl::hopscotch_map::try_emplace
std::pair< iterator, bool > try_emplace(const key_type &k, Args &&... args)
Definition: hopscotch_map.h:307
tsl::hopscotch_map::insert
iterator insert(const_iterator hint, value_type &&value)
Definition: hopscotch_map.h:252
tsl::hopscotch_map::emplace
std::pair< iterator, bool > emplace(Args &&... args)
Definition: hopscotch_map.h:290
tsl::hopscotch_map::clear
void clear() noexcept
Definition: hopscotch_map.h:227
tsl::detail_hopscotch_hash::hopscotch_hash::bucket_count
size_type bucket_count() const
Definition: hopscotch_hash.h:1114
tsl::detail_hopscotch_hash::hopscotch_hash::mutable_iterator
iterator mutable_iterator(const_iterator pos)
Definition: hopscotch_hash.h:1177
tsl::hopscotch_map::at
T & at(const Key &key)
Definition: hopscotch_map.h:374
tsl::hopscotch_map::erase
size_type erase(const K &key, std::size_t precalculated_hash)
Definition: hopscotch_map.h:364
tsl::hh::prime_growth_policy
Definition: hopscotch_growth_policy.h:250