IOSS 2.0

bhopscotch_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_BHOPSCOTCH_MAP_H
25 #define TSL_BHOPSCOTCH_MAP_H
26
27 #include "hopscotch_hash.h"
28 #include <algorithm>
29 #include <cstddef>
30 #include <functional>
31 #include <initializer_list>
32 #include <map>
33 #include <memory>
34 #include <type_traits>
35 #include <utility>
36
37 namespace tsl {
38
39 /**
40 * Similar to tsl::hopscotch_map but instead of using a list for overflowing elements it uses
41 * a binary search tree. It thus needs an additional template parameter Compare. Compare should
42 * be arithmetically coherent with KeyEqual.
43 *
44 * The binary search tree allows the map to have a worst-case scenario of O(log n) for search
45 * and delete, even if the hash function maps all the elements to the same bucket.
46 * For insert, the amortized worst case is O(log n), but the worst case is O(n) in case of rehash.
47 *
48 * This makes the map resistant to DoS attacks (but doesn't preclude you to have a good hash
49 * function, as an element in the bucket array is faster to retrieve than in the tree).
50 *
51 * @copydoc hopscotch_map
52 */
53 template <class Key, class T, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>,
54 class Compare = std::less<Key>,
55 class Allocator = std::allocator<std::pair<const Key, T>>,
56 unsigned int NeighborhoodSize = 62, bool StoreHash = false,
57 class GrowthPolicy = tsl::hh::power_of_two_growth_policy<2>>
58 class bhopscotch_map
59 {
60 private:
61 template <typename U>
62 using has_is_transparent = tsl::detail_hopscotch_hash::has_is_transparent<U>;
63
64 class KeySelect
65 {
66 public:
67 using key_type = Key;
68
69 const key_type &operator()(const std::pair<const Key, T> &key_value) const
70 {
71 return key_value.first;
72 }
73
74 const key_type &operator()(std::pair<const Key, T> &key_value) { return key_value.first; }
75 };
76
77 class ValueSelect
78 {
79 public:
80 using value_type = T;
81
82 const value_type &operator()(const std::pair<const Key, T> &key_value) const
83 {
84 return key_value.second;
85 }
86
87 value_type &operator()(std::pair<Key, T> &key_value) { return key_value.second; }
88 };
89
90 // TODO Not optimal as we have to use std::pair<const Key, T> as ValueType which forbid
91 // us to move the key in the bucket array, we have to use copy. Optimize.
92 using overflow_container_type = std::map<Key, T, Compare, Allocator>;
93 using ht =
94 detail_hopscotch_hash::hopscotch_hash<std::pair<const Key, T>, KeySelect, ValueSelect, Hash,
95 KeyEqual, Allocator, NeighborhoodSize, StoreHash,
96 GrowthPolicy, overflow_container_type>;
97
98 public:
99 using key_type = typename ht::key_type;
100 using mapped_type = T;
101 using value_type = typename ht::value_type;
102 using size_type = typename ht::size_type;
103 using difference_type = typename ht::difference_type;
104 using hasher = typename ht::hasher;
105 using key_equal = typename ht::key_equal;
106 using key_compare = Compare;
107 using allocator_type = typename ht::allocator_type;
108 using reference = typename ht::reference;
109 using const_reference = typename ht::const_reference;
110 using pointer = typename ht::pointer;
111 using const_pointer = typename ht::const_pointer;
112 using iterator = typename ht::iterator;
113 using const_iterator = typename ht::const_iterator;
114
115 /*
116 * Constructors
117 */
118 bhopscotch_map() : bhopscotch_map(ht::DEFAULT_INIT_BUCKETS_SIZE) {}
119
120 explicit bhopscotch_map(size_type bucket_count, const Hash &hash = Hash(),
121 const KeyEqual & equal = KeyEqual(),
122 const Allocator &alloc = Allocator(), const Compare &comp = Compare())
123 : m_ht(bucket_count, hash, equal, alloc, ht::DEFAULT_MAX_LOAD_FACTOR, comp)
124 {
125 }
126
127 bhopscotch_map(size_type bucket_count, const Allocator &alloc)
128 : bhopscotch_map(bucket_count, Hash(), KeyEqual(), alloc)
129 {
130 }
131
132 bhopscotch_map(size_type bucket_count, const Hash &hash, const Allocator &alloc)
133 : bhopscotch_map(bucket_count, hash, KeyEqual(), alloc)
134 {
135 }
136
137 explicit bhopscotch_map(const Allocator &alloc)
138 : bhopscotch_map(ht::DEFAULT_INIT_BUCKETS_SIZE, alloc)
139 {
140 }
141
142 template <class InputIt>
143 bhopscotch_map(InputIt first, InputIt last,
144 size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE,
145 const Hash &hash = Hash(), const KeyEqual &equal = KeyEqual(),
146 const Allocator &alloc = Allocator())
147 : bhopscotch_map(bucket_count, hash, equal, alloc)
148 {
149 insert(first, last);
150 }
151
152 template <class InputIt>
153 bhopscotch_map(InputIt first, InputIt last, size_type bucket_count, const Allocator &alloc)
154 : bhopscotch_map(first, last, bucket_count, Hash(), KeyEqual(), alloc)
155 {
156 }
157
158 template <class InputIt>
159 bhopscotch_map(InputIt first, InputIt last, size_type bucket_count, const Hash &hash,
160 const Allocator &alloc)
161 : bhopscotch_map(first, last, bucket_count, hash, KeyEqual(), alloc)
162 {
163 }
164
165 bhopscotch_map(std::initializer_list<value_type> init,
166 size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE,
167 const Hash &hash = Hash(), const KeyEqual &equal = KeyEqual(),
168 const Allocator &alloc = Allocator())
169 : bhopscotch_map(init.begin(), init.end(), bucket_count, hash, equal, alloc)
170 {
171 }
172
173 bhopscotch_map(std::initializer_list<value_type> init, size_type bucket_count,
174 const Allocator &alloc)
175 : bhopscotch_map(init.begin(), init.end(), bucket_count, Hash(), KeyEqual(), alloc)
176 {
177 }
178
179 bhopscotch_map(std::initializer_list<value_type> init, size_type bucket_count, const Hash &hash,
180 const Allocator &alloc)
181 : bhopscotch_map(init.begin(), init.end(), bucket_count, hash, KeyEqual(), alloc)
182 {
183 }
184
185 bhopscotch_map &operator=(std::initializer_list<value_type> ilist)
186 {
187 m_ht.clear();
188
189 m_ht.reserve(ilist.size());
190 m_ht.insert(ilist.begin(), ilist.end());
191
192 return *this;
193 }
194
195 allocator_type get_allocator() const { return m_ht.get_allocator(); }
196
197 /*
198 * Iterators
199 */
200 iterator begin() noexcept { return m_ht.begin(); }
201 const_iterator begin() const noexcept { return m_ht.begin(); }
202 const_iterator cbegin() const noexcept { return m_ht.cbegin(); }
203
204 iterator end() noexcept { return m_ht.end(); }
205 const_iterator end() const noexcept { return m_ht.end(); }
206 const_iterator cend() const noexcept { return m_ht.cend(); }
207
208 /*
209 * Capacity
210 */
211 bool empty() const noexcept { return m_ht.empty(); }
212 size_type size() const noexcept { return m_ht.size(); }
213 size_type max_size() const noexcept { return m_ht.max_size(); }
214
215 /*
216 * Modifiers
217 */
218 void clear() noexcept { m_ht.clear(); }
219
220 std::pair<iterator, bool> insert(const value_type &value) { return m_ht.insert(value); }
221
222 template <class P, typename std::enable_if<std::is_constructible<value_type, P &&>::value>::type
223 * = nullptr>
224 std::pair<iterator, bool> insert(P &&value)
225 {
226 return m_ht.insert(std::forward<P>(value));
227 }
228
229 std::pair<iterator, bool> insert(value_type &&value) { return m_ht.insert(std::move(value)); }
230
231 iterator insert(const_iterator hint, const value_type &value)
232 {
233 return m_ht.insert(hint, value);
234 }
235
236 template <class P, typename std::enable_if<std::is_constructible<value_type, P &&>::value>::type
237 * = nullptr>
238 iterator insert(const_iterator hint, P &&value)
239 {
240 return m_ht.insert(hint, std::forward<P>(value));
241 }
242
243 iterator insert(const_iterator hint, value_type &&value)
244 {
245 return m_ht.insert(hint, std::move(value));
246 }
247
248 template <class InputIt> void insert(InputIt first, InputIt last) { m_ht.insert(first, last); }
249
250 void insert(std::initializer_list<value_type> ilist)
251 {
252 m_ht.insert(ilist.begin(), ilist.end());
253 }
254
255 template <class M> std::pair<iterator, bool> insert_or_assign(const key_type &k, M &&obj)
256 {
257 return m_ht.insert_or_assign(k, std::forward<M>(obj));
258 }
259
260 template <class M> std::pair<iterator, bool> insert_or_assign(key_type &&k, M &&obj)
261 {
262 return m_ht.insert_or_assign(std::move(k), std::forward<M>(obj));
263 }
264
265 template <class M> iterator insert_or_assign(const_iterator hint, const key_type &k, M &&obj)
266 {
267 return m_ht.insert_or_assign(hint, k, std::forward<M>(obj));
268 }
269
270 template <class M> iterator insert_or_assign(const_iterator hint, key_type &&k, M &&obj)
271 {
272 return m_ht.insert_or_assign(hint, std::move(k), std::forward<M>(obj));
273 }
274
275 /**
276 * Due to the way elements are stored, emplace will need to move or copy the key-value once.
277 * The method is equivalent to insert(value_type(std::forward<Args>(args)...));
278 *
279 * Mainly here for compatibility with the std::unordered_map interface.
280 */
281 template <class... Args> std::pair<iterator, bool> emplace(Args &&... args)
282 {
283 return m_ht.emplace(std::forward<Args>(args)...);
284 }
285
286 /**
287 * Due to the way elements are stored, emplace_hint will need to move or copy the key-value
288 * once. The method is equivalent to insert(hint, value_type(std::forward<Args>(args)...));
289 *
290 * Mainly here for compatibility with the std::unordered_map interface.
291 */
292 template <class... Args> iterator emplace_hint(const_iterator hint, Args &&... args)
293 {
294 return m_ht.emplace_hint(hint, std::forward<Args>(args)...);
295 }
296
297 template <class... Args>
298 std::pair<iterator, bool> try_emplace(const key_type &k, Args &&... args)
299 {
300 return m_ht.try_emplace(k, std::forward<Args>(args)...);
301 }
302
303 template <class... Args> std::pair<iterator, bool> try_emplace(key_type &&k, Args &&... args)
304 {
305 return m_ht.try_emplace(std::move(k), std::forward<Args>(args)...);
306 }
307
308 template <class... Args>
309 iterator try_emplace(const_iterator hint, const key_type &k, Args &&... args)
310 {
311 return m_ht.try_emplace(hint, k, std::forward<Args>(args)...);
312 }
313
314 template <class... Args>
315 iterator try_emplace(const_iterator hint, key_type &&k, Args &&... args)
316 {
317 return m_ht.try_emplace(hint, std::move(k), std::forward<Args>(args)...);
318 }
319
320 iterator erase(iterator pos) { return m_ht.erase(pos); }
321 iterator erase(const_iterator pos) { return m_ht.erase(pos); }
322 iterator erase(const_iterator first, const_iterator last) { return m_ht.erase(first, last); }
323 size_type erase(const key_type &key) { return m_ht.erase(key); }
324
325 /**
326 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
327 * the same as hash_function()(key). Usefull to speed-up the lookup to the value if you already
328 * have the hash.
329 */
330 size_type erase(const key_type &key, std::size_t precalculated_hash)
331 {
332 return m_ht.erase(key, precalculated_hash);
333 }
334
335 /**
336 * This overload only participates in the overload resolution if the typedef
337 * KeyEqual::is_transparent and Compare::is_transparent exist. If so, K must be hashable and
338 * comparable to Key.
339 */
340 template <class K, class KE = KeyEqual, class CP = Compare,
341 typename std::enable_if<has_is_transparent<KE>::value &&
342 has_is_transparent<CP>::value>::type * = nullptr>
343 size_type erase(const K &key)
344 {
345 return m_ht.erase(key);
346 }
347
348 /**
349 * @copydoc erase(const K& key)
350 *
351 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
352 * the same as hash_function()(key). Usefull to speed-up the lookup to the value if you already
353 * have the hash.
354 */
355 template <class K, class KE = KeyEqual, class CP = Compare,
356 typename std::enable_if<has_is_transparent<KE>::value &&
357 has_is_transparent<CP>::value>::type * = nullptr>
358 size_type erase(const K &key, std::size_t precalculated_hash)
359 {
360 return m_ht.erase(key, precalculated_hash);
361 }
362
363 void swap(bhopscotch_map &other) { other.m_ht.swap(m_ht); }
364
365 /*
366 * Lookup
367 */
368 T &at(const Key &key) { return m_ht.at(key); }
369
370 /**
371 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
372 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
373 * hash.
374 */
375 T &at(const Key &key, std::size_t precalculated_hash)
376 {
377 return m_ht.at(key, precalculated_hash);
378 }
379
380 const T &at(const Key &key) const { return m_ht.at(key); }
381
382 /**
383 * @copydoc at(const Key& key, std::size_t precalculated_hash)
384 */
385 const T &at(const Key &key, std::size_t precalculated_hash) const
386 {
387 return m_ht.at(key, precalculated_hash);
388 }
389
390 /**
391 * This overload only participates in the overload resolution if the typedef
392 * KeyEqual::is_transparent and Compare::is_transparent exist. If so, K must be hashable and
393 * comparable to Key.
394 */
395 template <class K, class KE = KeyEqual, class CP = Compare,
396 typename std::enable_if<has_is_transparent<KE>::value &&
397 has_is_transparent<CP>::value>::type * = nullptr>
398 T &at(const K &key)
399 {
400 return m_ht.at(key);
401 }
402
403 /**
404 * @copydoc at(const K& key)
405 *
406 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
407 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
408 * hash.
409 */
410 template <class K, class KE = KeyEqual, class CP = Compare,
411 typename std::enable_if<has_is_transparent<KE>::value &&
412 has_is_transparent<CP>::value>::type * = nullptr>
413 T &at(const K &key, std::size_t precalculated_hash)
414 {
415 return m_ht.at(key, precalculated_hash);
416 }
417
418 /**
419 * @copydoc at(const K& key)
420 */
421 template <class K, class KE = KeyEqual, class CP = Compare,
422 typename std::enable_if<has_is_transparent<KE>::value &&
423 has_is_transparent<CP>::value>::type * = nullptr>
424 const T &at(const K &key) const
425 {
426 return m_ht.at(key);
427 }
428
429 /**
430 * @copydoc at(const K& key, std::size_t precalculated_hash)
431 */
432 template <class K, class KE = KeyEqual, class CP = Compare,
433 typename std::enable_if<has_is_transparent<KE>::value &&
434 has_is_transparent<CP>::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 and Compare::is_transparent exist. If so, K must be hashable and
458 * comparable to Key.
459 */
460 template <class K, class KE = KeyEqual, class CP = Compare,
461 typename std::enable_if<has_is_transparent<KE>::value &&
462 has_is_transparent<CP>::value>::type * = nullptr>
463 size_type count(const K &key) const
464 {
465 return m_ht.count(key);
466 }
467
468 /**
469 * @copydoc count(const K& key) const
470 *
471 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
472 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
473 * hash.
474 */
475 template <class K, class KE = KeyEqual, class CP = Compare,
476 typename std::enable_if<has_is_transparent<KE>::value &&
477 has_is_transparent<CP>::value>::type * = nullptr>
478 size_type count(const K &key, std::size_t precalculated_hash) const
479 {
480 return m_ht.count(key, precalculated_hash);
481 }
482
483 iterator find(const Key &key) { return m_ht.find(key); }
484
485 /**
486 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
487 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
488 * hash.
489 */
490 iterator find(const Key &key, std::size_t precalculated_hash)
491 {
492 return m_ht.find(key, precalculated_hash);
493 }
494
495 const_iterator find(const Key &key) const { return m_ht.find(key); }
496
497 /**
498 * @copydoc find(const Key& key, std::size_t precalculated_hash)
499 */
500 const_iterator find(const Key &key, std::size_t precalculated_hash) const
501 {
502 return m_ht.find(key, precalculated_hash);
503 }
504
505 /**
506 * This overload only participates in the overload resolution if the typedef
507 * KeyEqual::is_transparent and Compare::is_transparent exist. If so, K must be hashable and
508 * comparable to Key.
509 */
510 template <class K, class KE = KeyEqual, class CP = Compare,
511 typename std::enable_if<has_is_transparent<KE>::value &&
512 has_is_transparent<CP>::value>::type * = nullptr>
513 iterator find(const K &key)
514 {
515 return m_ht.find(key);
516 }
517
518 /**
519 * @copydoc find(const K& key)
520 *
521 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
522 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
523 * hash.
524 */
525 template <class K, class KE = KeyEqual, class CP = Compare,
526 typename std::enable_if<has_is_transparent<KE>::value &&
527 has_is_transparent<CP>::value>::type * = nullptr>
528 iterator find(const K &key, std::size_t precalculated_hash)
529 {
530 return m_ht.find(key, precalculated_hash);
531 }
532
533 /**
534 * @copydoc find(const K& key)
535 */
536 template <class K, class KE = KeyEqual, class CP = Compare,
537 typename std::enable_if<has_is_transparent<KE>::value &&
538 has_is_transparent<CP>::value>::type * = nullptr>
539 const_iterator find(const K &key) const
540 {
541 return m_ht.find(key);
542 }
543
544 /**
545 * @copydoc find(const K& key, std::size_t precalculated_hash)
546 */
547 template <class K, class KE = KeyEqual, class CP = Compare,
548 typename std::enable_if<has_is_transparent<KE>::value &&
549 has_is_transparent<CP>::value>::type * = nullptr>
550 const_iterator find(const K &key, std::size_t precalculated_hash) const
551 {
552 return m_ht.find(key, precalculated_hash);
553 }
554
555 bool contains(const Key &key) const { return m_ht.contains(key); }
556
557 /**
558 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
559 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
560 * hash.
561 */
562 bool contains(const Key &key, std::size_t precalculated_hash) const
563 {
564 return m_ht.contains(key, precalculated_hash);
565 }
566
567 /**
568 * This overload only participates in the overload resolution if the typedef
569 * KeyEqual::is_transparent exists. If so, K must be hashable and comparable to Key.
570 */
571 template <class K, class KE = KeyEqual,
572 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
573 bool contains(const K &key) const
574 {
575 return m_ht.contains(key);
576 }
577
578 /**
579 * @copydoc contains(const K& key) const
580 *
581 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
582 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
583 * hash.
584 */
585 template <class K, class KE = KeyEqual,
586 typename std::enable_if<has_is_transparent<KE>::value>::type * = nullptr>
587 bool contains(const K &key, std::size_t precalculated_hash) const
588 {
589 return m_ht.contains(key, precalculated_hash);
590 }
591
592 std::pair<iterator, iterator> equal_range(const Key &key) { return m_ht.equal_range(key); }
593
594 /**
595 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
596 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
597 * hash.
598 */
599 std::pair<iterator, iterator> equal_range(const Key &key, std::size_t precalculated_hash)
600 {
601 return m_ht.equal_range(key, precalculated_hash);
602 }
603
604 std::pair<const_iterator, const_iterator> equal_range(const Key &key) const
605 {
606 return m_ht.equal_range(key);
607 }
608
609 /**
610 * @copydoc equal_range(const Key& key, std::size_t precalculated_hash)
611 */
612 std::pair<const_iterator, const_iterator> equal_range(const Key & key,
613 std::size_t precalculated_hash) const
614 {
615 return m_ht.equal_range(key, precalculated_hash);
616 }
617
618 /**
619 * This overload only participates in the overload resolution if the typedef
620 * KeyEqual::is_transparent and Compare::is_transparent exist. If so, K must be hashable and
621 * comparable to Key.
622 */
623 template <class K, class KE = KeyEqual, class CP = Compare,
624 typename std::enable_if<has_is_transparent<KE>::value &&
625 has_is_transparent<CP>::value>::type * = nullptr>
626 std::pair<iterator, iterator> equal_range(const K &key)
627 {
628 return m_ht.equal_range(key);
629 }
630
631 /**
632 * @copydoc equal_range(const K& key)
633 *
634 * Use the hash value 'precalculated_hash' instead of hashing the key. The hash value should be
635 * the same as hash_function()(key). Usefull to speed-up the lookup if you already have the
636 * hash.
637 */
638 template <class K, class KE = KeyEqual, class CP = Compare,
639 typename std::enable_if<has_is_transparent<KE>::value &&
640 has_is_transparent<CP>::value>::type * = nullptr>
641 std::pair<iterator, iterator> equal_range(const K &key, std::size_t precalculated_hash)
642 {
643 return m_ht.equal_range(key, precalculated_hash);
644 }
645
646 /**
647 * @copydoc equal_range(const K& key)
648 */
649 template <class K, class KE = KeyEqual, class CP = Compare,
650 typename std::enable_if<has_is_transparent<KE>::value &&
651 has_is_transparent<CP>::value>::type * = nullptr>
652 std::pair<const_iterator, const_iterator> equal_range(const K &key) const
653 {
654 return m_ht.equal_range(key);
655 }
656
657 /**
658 * @copydoc equal_range(const K& key, std::size_t precalculated_hash)
659 */
660 template <class K, class KE = KeyEqual, class CP = Compare,
661 typename std::enable_if<has_is_transparent<KE>::value &&
662 has_is_transparent<CP>::value>::type * = nullptr>
663 std::pair<const_iterator, const_iterator> equal_range(const K & key,
664 std::size_t precalculated_hash) const
665 {
666 return m_ht.equal_range(key, precalculated_hash);
667 }
668
669 /*
670 * Bucket interface
671 */
672 size_type bucket_count() const { return m_ht.bucket_count(); }
673 size_type max_bucket_count() const { return m_ht.max_bucket_count(); }
674
675 /*
676 * Hash policy
677 */
678 float load_factor() const { return m_ht.load_factor(); }
679 float max_load_factor() const { return m_ht.max_load_factor(); }
680 void max_load_factor(float ml) { m_ht.max_load_factor(ml); }
681
682 void rehash(size_type count_) { m_ht.rehash(count_); }
683 void reserve(size_type count_) { m_ht.reserve(count_); }
684
685 /*
686 * Observers
687 */
688 hasher hash_function() const { return m_ht.hash_function(); }
689 key_equal key_eq() const { return m_ht.key_eq(); }
690 key_compare key_comp() const { return m_ht.key_comp(); }
691
692 /*
693 * Other
694 */
695
696 /**
697 * Convert a const_iterator to an iterator.
698 */
699 iterator mutable_iterator(const_iterator pos) { return m_ht.mutable_iterator(pos); }
700
701 size_type overflow_size() const noexcept { return m_ht.overflow_size(); }
702
703 friend bool operator==(const bhopscotch_map &lhs, const bhopscotch_map &rhs)
704 {
705 if (lhs.size() != rhs.size()) {
706 return false;
707 }
708
709 for (const auto &element_lhs : lhs) {
710 const auto it_element_rhs = rhs.find(element_lhs.first);
711 if (it_element_rhs == rhs.cend() || element_lhs.second != it_element_rhs->second) {
712 return false;
713 }
714 }
715
716 return true;
717 }
718
719 friend bool operator!=(const bhopscotch_map &lhs, const bhopscotch_map &rhs)
720 {
721 return !operator==(lhs, rhs);
722 }
723
724 friend void swap(bhopscotch_map &lhs, bhopscotch_map &rhs) { lhs.swap(rhs); }
725
726 private:
727 ht m_ht;
728 };
729
730 /**
731 * Same as `tsl::bhopscotch_map<Key, T, Hash, KeyEqual, Compare, Allocator, NeighborhoodSize,
732 * StoreHash, tsl::hh::prime_growth_policy>`.
733 */
734 template <class Key, class T, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>,
735 class Compare = std::less<Key>,
736 class Allocator = std::allocator<std::pair<const Key, T>>,
737 unsigned int NeighborhoodSize = 62, bool StoreHash = false>
738 using bhopscotch_pg_map =
739 bhopscotch_map<Key, T, Hash, KeyEqual, Compare, Allocator, NeighborhoodSize, StoreHash,
740 tsl::hh::prime_growth_policy>;
741
742 } // end namespace tsl
743
744 #endif
tsl::bhopscotch_map::erase
size_type erase(const K &key, std::size_t precalculated_hash)
Definition: bhopscotch_map.h:358
tsl::bhopscotch_map::end
const_iterator end() const noexcept
Definition: bhopscotch_map.h:205
tsl::detail_hopscotch_hash::hopscotch_hash::equal_range
std::pair< iterator, iterator > equal_range(const K &key)
Definition: hopscotch_hash.h:1087
tsl::detail_hopscotch_hash::hopscotch_hash::max_load_factor
float max_load_factor() const
Definition: hopscotch_hash.h:1147
tsl
Definition: bhopscotch_map.h:37
tsl::bhopscotch_map::at
const T & at(const K &key) const
Definition: bhopscotch_map.h:424
tsl::bhopscotch_map::begin
const_iterator begin() const noexcept
Definition: bhopscotch_map.h:201
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::bhopscotch_map::insert
iterator insert(const_iterator hint, const value_type &value)
Definition: bhopscotch_map.h:231
tsl::bhopscotch_map::size_type
typename ht::size_type size_type
Definition: bhopscotch_map.h:102
tsl::bhopscotch_map::insert
iterator insert(const_iterator hint, P &&value)
Definition: bhopscotch_map.h:238
tsl::bhopscotch_map::operator==
friend bool operator==(const bhopscotch_map &lhs, const bhopscotch_map &rhs)
Definition: bhopscotch_map.h:703
tsl::bhopscotch_map::pointer
typename ht::pointer pointer
Definition: bhopscotch_map.h:110
tsl::bhopscotch_map::equal_range
std::pair< const_iterator, const_iterator > equal_range(const Key &key, std::size_t precalculated_hash) const
Definition: bhopscotch_map.h:612
tsl::detail_hopscotch_hash::hopscotch_hash< std::pair< const Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::reference
value_type & reference
Definition: hopscotch_hash.h:440
tsl::bhopscotch_map::equal_range
std::pair< const_iterator, const_iterator > equal_range(const K &key) const
Definition: bhopscotch_map.h:652
tsl::bhopscotch_map::erase
iterator erase(const_iterator pos)
Definition: bhopscotch_map.h:321
tsl::bhopscotch_map::contains
bool contains(const Key &key, std::size_t precalculated_hash) const
Definition: bhopscotch_map.h:562
tsl::bhopscotch_map::value_type
typename ht::value_type value_type
Definition: bhopscotch_map.h:101
tsl::bhopscotch_map::erase
iterator erase(const_iterator first, const_iterator last)
Definition: bhopscotch_map.h:322
tsl::bhopscotch_map::mutable_iterator
iterator mutable_iterator(const_iterator pos)
Definition: bhopscotch_map.h:699
tsl::bhopscotch_map::at
T & at(const K &key, std::size_t precalculated_hash)
Definition: bhopscotch_map.h:413
tsl::bhopscotch_map::allocator_type
typename ht::allocator_type allocator_type
Definition: bhopscotch_map.h:107
tsl::bhopscotch_map::hash_function
hasher hash_function() const
Definition: bhopscotch_map.h:688
tsl::bhopscotch_map::equal_range
std::pair< iterator, iterator > equal_range(const Key &key, std::size_t precalculated_hash)
Definition: bhopscotch_map.h:599
tsl::bhopscotch_map::find
iterator find(const Key &key)
Definition: bhopscotch_map.h:483
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::detail_hopscotch_hash::hopscotch_hash::rehash
void rehash(size_type count_)
Definition: hopscotch_hash.h:1156
tsl::detail_hopscotch_hash::hopscotch_hash< std::pair< const Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::allocator_type
Allocator allocator_type
Definition: hopscotch_hash.h:439
tsl::bhopscotch_map::at
const T & at(const Key &key) const
Definition: bhopscotch_map.h:380
anonymous_namespace{Ioss_SmartAssert.C}::init
struct anonymous_namespace{Ioss_SmartAssert.C}::assert_initializer init
tsl::bhopscotch_map::at
T & at(const K &key)
Definition: bhopscotch_map.h:398
tsl::bhopscotch_map::find
iterator find(const K &key, std::size_t precalculated_hash)
Definition: bhopscotch_map.h:528
tsl::bhopscotch_map::KeySelect
Definition: bhopscotch_map.h:64
tsl::detail_hopscotch_hash::hopscotch_hash::get_allocator
allocator_type get_allocator() const
Definition: hopscotch_hash.h:724
tsl::detail_hopscotch_hash::hopscotch_hash< std::pair< const 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< const Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::hasher
Hash hasher
Definition: hopscotch_hash.h:437
tsl::bhopscotch_map::overflow_container_type
std::map< Key, T, Compare, Allocator > overflow_container_type
Definition: bhopscotch_map.h:92
tsl::bhopscotch_map::begin
iterator begin() noexcept
Definition: bhopscotch_map.h:200
tsl::bhopscotch_map::key_comp
key_compare key_comp() const
Definition: bhopscotch_map.h:690
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::bhopscotch_map::size
size_type size() const noexcept
Definition: bhopscotch_map.h:212
tsl::detail_hopscotch_hash::hopscotch_hash< std::pair< const 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::bhopscotch_map::const_pointer
typename ht::const_pointer const_pointer
Definition: bhopscotch_map.h:111
tsl::bhopscotch_map::erase
size_type erase(const K &key)
Definition: bhopscotch_map.h:343
tsl::bhopscotch_map::erase
size_type erase(const key_type &key)
Definition: bhopscotch_map.h:323
tsl::bhopscotch_map::find
const_iterator find(const Key &key, std::size_t precalculated_hash) const
Definition: bhopscotch_map.h:500
tsl::bhopscotch_map::erase
size_type erase(const key_type &key, std::size_t precalculated_hash)
Definition: bhopscotch_map.h:330
tsl::bhopscotch_map::equal_range
std::pair< const_iterator, const_iterator > equal_range(const Key &key) const
Definition: bhopscotch_map.h:604
tsl::bhopscotch_map::insert_or_assign
iterator insert_or_assign(const_iterator hint, key_type &&k, M &&obj)
Definition: bhopscotch_map.h:270
tsl::bhopscotch_map::bhopscotch_map
bhopscotch_map(std::initializer_list< value_type > init, size_type bucket_count, const Allocator &alloc)
Definition: bhopscotch_map.h:173
tsl::bhopscotch_map::difference_type
typename ht::difference_type difference_type
Definition: bhopscotch_map.h:103
tsl::detail_hopscotch_hash::hopscotch_hash::hash_function
hasher hash_function() const
Definition: hopscotch_hash.h:1170
tsl::detail_hopscotch_hash::hopscotch_hash::load_factor
float load_factor() const
Definition: hopscotch_hash.h:1138
tsl::bhopscotch_map::count
size_type count(const Key &key, std::size_t precalculated_hash) const
Definition: bhopscotch_map.h:450
tsl::bhopscotch_map::operator!=
friend bool operator!=(const bhopscotch_map &lhs, const bhopscotch_map &rhs)
Definition: bhopscotch_map.h:719
tsl::detail_hopscotch_hash::hopscotch_hash::emplace
std::pair< iterator, bool > emplace(Args &&... args)
Definition: hopscotch_hash.h:876
tsl::bhopscotch_map::count
size_type count(const Key &key) const
Definition: bhopscotch_map.h:443
tsl::bhopscotch_map::operator[]
T & operator[](Key &&key)
Definition: bhopscotch_map.h:441
tsl::bhopscotch_map::const_iterator
typename ht::const_iterator const_iterator
Definition: bhopscotch_map.h:113
tsl::detail_hopscotch_hash::hopscotch_hash< std::pair< const 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< const 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::bhopscotch_map::insert
iterator insert(const_iterator hint, value_type &&value)
Definition: bhopscotch_map.h:243
tsl::bhopscotch_map::insert
std::pair< iterator, bool > insert(value_type &&value)
Definition: bhopscotch_map.h:229
tsl::detail_hopscotch_hash::hopscotch_hash::key_comp
U::key_compare key_comp() const
Definition: hopscotch_hash.h:1196
tsl::detail_hopscotch_hash::hopscotch_hash::max_size
size_type max_size() const noexcept
Definition: hopscotch_hash.h:771
tsl::bhopscotch_map::equal_range
std::pair< iterator, iterator > equal_range(const K &key)
Definition: bhopscotch_map.h:626
tsl::detail_hopscotch_hash::hopscotch_hash< std::pair< const Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::value_type
std::pair< const Key, T > value_type
Definition: hopscotch_hash.h:434
tsl::bhopscotch_map::insert_or_assign
std::pair< iterator, bool > insert_or_assign(key_type &&k, M &&obj)
Definition: bhopscotch_map.h:260
tsl::bhopscotch_map::ValueSelect::operator()
const value_type & operator()(const std::pair< const Key, T > &key_value) const
Definition: bhopscotch_map.h:82
tsl::bhopscotch_map::swap
void swap(bhopscotch_map &other)
Definition: bhopscotch_map.h:363
tsl::bhopscotch_map::equal_range
std::pair< const_iterator, const_iterator > equal_range(const K &key, std::size_t precalculated_hash) const
Definition: bhopscotch_map.h:663
tsl::bhopscotch_map::mapped_type
T mapped_type
Definition: bhopscotch_map.h:100
tsl::bhopscotch_map::find
iterator find(const K &key)
Definition: bhopscotch_map.h:513
tsl::bhopscotch_map::bhopscotch_map
bhopscotch_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: bhopscotch_map.h:143
tsl::bhopscotch_map::bhopscotch_map
bhopscotch_map()
Definition: bhopscotch_map.h:118
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::bhopscotch_map::find
iterator find(const Key &key, std::size_t precalculated_hash)
Definition: bhopscotch_map.h:490
tsl::bhopscotch_map::contains
bool contains(const K &key, std::size_t precalculated_hash) const
Definition: bhopscotch_map.h:587
tsl::detail_hopscotch_hash::hopscotch_hash< std::pair< const Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::key_equal
KeyEqual key_equal
Definition: hopscotch_hash.h:438
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< const 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::bhopscotch_map::find
const_iterator find(const Key &key) const
Definition: bhopscotch_map.h:495
tsl::bhopscotch_map::empty
bool empty() const noexcept
Definition: bhopscotch_map.h:211
tsl::bhopscotch_map::bucket_count
size_type bucket_count() const
Definition: bhopscotch_map.h:672
tsl::detail_hopscotch_hash::hopscotch_hash< std::pair< const 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::bhopscotch_map::insert
void insert(InputIt first, InputIt last)
Definition: bhopscotch_map.h:248
tsl::detail_hopscotch_hash::hopscotch_hash::begin
iterator begin() noexcept
Definition: hopscotch_hash.h:729
tsl::bhopscotch_map::max_bucket_count
size_type max_bucket_count() const
Definition: bhopscotch_map.h:673
tsl::bhopscotch_map::bhopscotch_map
bhopscotch_map(std::initializer_list< value_type > init, size_type bucket_count, const Hash &hash, const Allocator &alloc)
Definition: bhopscotch_map.h:179
tsl::bhopscotch_map::key_compare
Compare key_compare
Definition: bhopscotch_map.h:106
tsl::bhopscotch_map::key_eq
key_equal key_eq() const
Definition: bhopscotch_map.h:689
tsl::bhopscotch_map::bhopscotch_map
bhopscotch_map(size_type bucket_count, const Hash &hash, const Allocator &alloc)
Definition: bhopscotch_map.h:132
tsl::bhopscotch_map::insert_or_assign
iterator insert_or_assign(const_iterator hint, const key_type &k, M &&obj)
Definition: bhopscotch_map.h:265
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::bhopscotch_map::insert
void insert(std::initializer_list< value_type > ilist)
Definition: bhopscotch_map.h:250
tsl::detail_hopscotch_hash::hopscotch_hash::find
iterator find(const K &key)
Definition: hopscotch_hash.h:1063
tsl::bhopscotch_map::bhopscotch_map
bhopscotch_map(size_type bucket_count, const Allocator &alloc)
Definition: bhopscotch_map.h:127
tsl::bhopscotch_map::count
size_type count(const K &key) const
Definition: bhopscotch_map.h:463
tsl::bhopscotch_map::insert_or_assign
std::pair< iterator, bool > insert_or_assign(const key_type &k, M &&obj)
Definition: bhopscotch_map.h:255
tsl::detail_hopscotch_hash::hopscotch_hash< std::pair< const 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::bhopscotch_map::cbegin
const_iterator cbegin() const noexcept
Definition: bhopscotch_map.h:202
tsl::detail_hopscotch_hash::hopscotch_hash< std::pair< const Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::pointer
value_type * pointer
Definition: hopscotch_hash.h:442
tsl::bhopscotch_map::insert
std::pair< iterator, bool > insert(const value_type &value)
Definition: bhopscotch_map.h:220
tsl::bhopscotch_map::ValueSelect::operator()
value_type & operator()(std::pair< Key, T > &key_value)
Definition: bhopscotch_map.h:87
tsl::detail_hopscotch_hash::hopscotch_hash::emplace_hint
iterator emplace_hint(const_iterator hint, Args &&... args)
Definition: hopscotch_hash.h:881
tsl::bhopscotch_map::cend
const_iterator cend() const noexcept
Definition: bhopscotch_map.h:206
tsl::detail_hopscotch_hash::hopscotch_hash::cbegin
const_iterator cbegin() const noexcept
Definition: hopscotch_hash.h:741
tsl::bhopscotch_map::KeySelect::operator()
const key_type & operator()(const std::pair< const Key, T > &key_value) const
Definition: bhopscotch_map.h:69
tsl::detail_hopscotch_hash::hopscotch_hash::key_eq
key_equal key_eq() const
Definition: hopscotch_hash.h:1172
tsl::bhopscotch_map::m_ht
ht m_ht
Definition: bhopscotch_map.h:727
tsl::bhopscotch_map::load_factor
float load_factor() const
Definition: bhopscotch_map.h:678
tsl::detail_hopscotch_hash::has_is_transparent
Definition: hopscotch_hash.h:69
tsl::bhopscotch_map::reference
typename ht::reference reference
Definition: bhopscotch_map.h:108
tsl::bhopscotch_map::try_emplace
iterator try_emplace(const_iterator hint, const key_type &k, Args &&... args)
Definition: bhopscotch_map.h:309
tsl::bhopscotch_map::hasher
typename ht::hasher hasher
Definition: bhopscotch_map.h:104
tsl::detail_hopscotch_hash::hopscotch_hash< std::pair< const Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >::iterator
hopscotch_iterator< false > iterator
Definition: hopscotch_hash.h:444
tsl::bhopscotch_map::ValueSelect
Definition: bhopscotch_map.h:77
tsl::bhopscotch_map::KeySelect::operator()
const key_type & operator()(std::pair< const Key, T > &key_value)
Definition: bhopscotch_map.h:74
tsl::bhopscotch_map::find
const_iterator find(const K &key) const
Definition: bhopscotch_map.h:539
tsl::bhopscotch_map::end
iterator end() noexcept
Definition: bhopscotch_map.h:204
tsl::bhopscotch_map::find
const_iterator find(const K &key, std::size_t precalculated_hash) const
Definition: bhopscotch_map.h:550
tsl::bhopscotch_map::count
size_type count(const K &key, std::size_t precalculated_hash) const
Definition: bhopscotch_map.h:478
tsl::detail_hopscotch_hash::hopscotch_hash::swap
void swap(hopscotch_hash &other)
Definition: hopscotch_hash.h:980
tsl::bhopscotch_map::clear
void clear() noexcept
Definition: bhopscotch_map.h:218
tsl::detail_hopscotch_hash::hopscotch_hash::empty
bool empty() const noexcept
Definition: hopscotch_hash.h:767
tsl::bhopscotch_map::try_emplace
std::pair< iterator, bool > try_emplace(key_type &&k, Args &&... args)
Definition: bhopscotch_map.h:303
tsl::bhopscotch_map::try_emplace
iterator try_emplace(const_iterator hint, key_type &&k, Args &&... args)
Definition: bhopscotch_map.h:315
tsl::bhopscotch_map::swap
friend void swap(bhopscotch_map &lhs, bhopscotch_map &rhs)
Definition: bhopscotch_map.h:724
tsl::bhopscotch_map::KeySelect::key_type
Key key_type
Definition: bhopscotch_map.h:67
tsl::detail_hopscotch_hash::hopscotch_hash::count
size_type count(const K &key) const
Definition: hopscotch_hash.h:1056
tsl::bhopscotch_map::equal_range
std::pair< iterator, iterator > equal_range(const Key &key)
Definition: bhopscotch_map.h:592
tsl::bhopscotch_map
Definition: bhopscotch_map.h:58
tsl::bhopscotch_map::max_load_factor
float max_load_factor() const
Definition: bhopscotch_map.h:679
tsl::bhopscotch_map::bhopscotch_map
bhopscotch_map(InputIt first, InputIt last, size_type bucket_count, const Allocator &alloc)
Definition: bhopscotch_map.h:153
tsl::bhopscotch_map::ValueSelect::value_type
T value_type
Definition: bhopscotch_map.h:80
tsl::bhopscotch_map::bhopscotch_map
bhopscotch_map(const Allocator &alloc)
Definition: bhopscotch_map.h:137
tsl::detail_hopscotch_hash::hopscotch_hash< std::pair< const Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, NeighborhoodSize, StoreHash, GrowthPolicy, overflow_container_type >
tsl::bhopscotch_map::bhopscotch_map
bhopscotch_map(size_type bucket_count, const Hash &hash=Hash(), const KeyEqual &equal=KeyEqual(), const Allocator &alloc=Allocator(), const Compare &comp=Compare())
Definition: bhopscotch_map.h:120
tsl::bhopscotch_map::contains
bool contains(const Key &key) const
Definition: bhopscotch_map.h:555
tsl::bhopscotch_map::at
const T & at(const Key &key, std::size_t precalculated_hash) const
Definition: bhopscotch_map.h:385
tsl::bhopscotch_map::at
T & at(const Key &key)
Definition: bhopscotch_map.h:368
tsl::bhopscotch_map::emplace_hint
iterator emplace_hint(const_iterator hint, Args &&... args)
Definition: bhopscotch_map.h:292
tsl::detail_hopscotch_hash::hopscotch_hash::cend
const_iterator cend() const noexcept
Definition: hopscotch_hash.h:758
tsl::bhopscotch_map::rehash
void rehash(size_type count_)
Definition: bhopscotch_map.h:682
tsl::detail_hopscotch_hash::hopscotch_hash::max_bucket_count
size_type max_bucket_count() const
Definition: hopscotch_hash.h:1128
tsl::detail_hopscotch_hash::hopscotch_hash::at
U::value_type & at(const K &key)
Definition: hopscotch_hash.h:1001
tsl::bhopscotch_map::erase
iterator erase(iterator pos)
Definition: bhopscotch_map.h:320
tsl::bhopscotch_map::operator[]
T & operator[](const Key &key)
Definition: bhopscotch_map.h:440
hopscotch_hash.h
tsl::bhopscotch_map::iterator
typename ht::iterator iterator
Definition: bhopscotch_map.h:112
tsl::bhopscotch_map::max_size
size_type max_size() const noexcept
Definition: bhopscotch_map.h:213
tsl::bhopscotch_map::key_type
typename ht::key_type key_type
Definition: bhopscotch_map.h:99
tsl::bhopscotch_map::get_allocator
allocator_type get_allocator() const
Definition: bhopscotch_map.h:195
tsl::bhopscotch_map::operator=
bhopscotch_map & operator=(std::initializer_list< value_type > ilist)
Definition: bhopscotch_map.h:185
tsl::bhopscotch_map::emplace
std::pair< iterator, bool > emplace(Args &&... args)
Definition: bhopscotch_map.h:281
tsl::bhopscotch_map::key_equal
typename ht::key_equal key_equal
Definition: bhopscotch_map.h:105
tsl::bhopscotch_map::insert
std::pair< iterator, bool > insert(P &&value)
Definition: bhopscotch_map.h:224
tsl::bhopscotch_map::at
T & at(const Key &key, std::size_t precalculated_hash)
Definition: bhopscotch_map.h:375
tsl::bhopscotch_map::contains
bool contains(const K &key) const
Definition: bhopscotch_map.h:573
tsl::bhopscotch_map::max_load_factor
void max_load_factor(float ml)
Definition: bhopscotch_map.h:680
tsl::bhopscotch_map::at
const T & at(const K &key, std::size_t precalculated_hash) const
Definition: bhopscotch_map.h:435
tsl::bhopscotch_map::reserve
void reserve(size_type count_)
Definition: bhopscotch_map.h:683
tsl::bhopscotch_map::bhopscotch_map
bhopscotch_map(InputIt first, InputIt last, size_type bucket_count, const Hash &hash, const Allocator &alloc)
Definition: bhopscotch_map.h:159
tsl::bhopscotch_map::overflow_size
size_type overflow_size() const noexcept
Definition: bhopscotch_map.h:701
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::bhopscotch_map::const_reference
typename ht::const_reference const_reference
Definition: bhopscotch_map.h:109
tsl::bhopscotch_map::bhopscotch_map
bhopscotch_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: bhopscotch_map.h:165
tsl::bhopscotch_map::try_emplace
std::pair< iterator, bool > try_emplace(const key_type &k, Args &&... args)
Definition: bhopscotch_map.h:298
tsl::hh::prime_growth_policy
Definition: hopscotch_growth_policy.h:250
tsl::bhopscotch_map::equal_range
std::pair< iterator, iterator > equal_range(const K &key, std::size_t precalculated_hash)
Definition: bhopscotch_map.h:641