EnTT 3.12.0
Loading...
Searching...
No Matches
dense_map.hpp
1#ifndef ENTT_CONTAINER_DENSE_MAP_HPP
2#define ENTT_CONTAINER_DENSE_MAP_HPP
3
4#include <cmath>
5#include <cstddef>
6#include <functional>
7#include <iterator>
8#include <limits>
9#include <memory>
10#include <tuple>
11#include <type_traits>
12#include <utility>
13#include <vector>
14#include "../config/config.h"
15#include "../core/compressed_pair.hpp"
16#include "../core/iterator.hpp"
17#include "../core/memory.hpp"
18#include "../core/type_traits.hpp"
19#include "fwd.hpp"
20
21namespace entt {
22
28namespace internal {
29
30template<typename Key, typename Type>
31struct dense_map_node final {
32 using value_type = std::pair<Key, Type>;
33
34 template<typename... Args>
35 dense_map_node(const std::size_t pos, Args &&...args)
36 : next{pos},
37 element{std::forward<Args>(args)...} {}
38
39 template<typename Allocator, typename... Args>
40 dense_map_node(std::allocator_arg_t, const Allocator &allocator, const std::size_t pos, Args &&...args)
41 : next{pos},
42 element{entt::make_obj_using_allocator<value_type>(allocator, std::forward<Args>(args)...)} {}
43
44 template<typename Allocator>
45 dense_map_node(std::allocator_arg_t, const Allocator &allocator, const dense_map_node &other)
46 : next{other.next},
47 element{entt::make_obj_using_allocator<value_type>(allocator, other.element)} {}
48
49 template<typename Allocator>
50 dense_map_node(std::allocator_arg_t, const Allocator &allocator, dense_map_node &&other)
51 : next{other.next},
52 element{entt::make_obj_using_allocator<value_type>(allocator, std::move(other.element))} {}
53
54 std::size_t next;
55 value_type element;
56};
57
58template<typename It>
59class dense_map_iterator final {
60 template<typename>
61 friend class dense_map_iterator;
62
63 using first_type = decltype(std::as_const(std::declval<It>()->element.first));
64 using second_type = decltype((std::declval<It>()->element.second));
65
66public:
67 using value_type = std::pair<first_type, second_type>;
69 using reference = value_type;
70 using difference_type = std::ptrdiff_t;
71 using iterator_category = std::input_iterator_tag;
72
73 constexpr dense_map_iterator() noexcept
74 : it{} {}
75
76 constexpr dense_map_iterator(const It iter) noexcept
77 : it{iter} {}
78
79 template<typename Other, typename = std::enable_if_t<!std::is_same_v<It, Other> && std::is_constructible_v<It, Other>>>
80 constexpr dense_map_iterator(const dense_map_iterator<Other> &other) noexcept
81 : it{other.it} {}
82
83 constexpr dense_map_iterator &operator++() noexcept {
84 return ++it, *this;
85 }
86
87 constexpr dense_map_iterator operator++(int) noexcept {
88 dense_map_iterator orig = *this;
89 return ++(*this), orig;
90 }
91
92 constexpr dense_map_iterator &operator--() noexcept {
93 return --it, *this;
94 }
95
96 constexpr dense_map_iterator operator--(int) noexcept {
97 dense_map_iterator orig = *this;
98 return operator--(), orig;
99 }
100
101 constexpr dense_map_iterator &operator+=(const difference_type value) noexcept {
102 it += value;
103 return *this;
104 }
105
106 constexpr dense_map_iterator operator+(const difference_type value) const noexcept {
107 dense_map_iterator copy = *this;
108 return (copy += value);
109 }
110
111 constexpr dense_map_iterator &operator-=(const difference_type value) noexcept {
112 return (*this += -value);
113 }
114
115 constexpr dense_map_iterator operator-(const difference_type value) const noexcept {
116 return (*this + -value);
117 }
118
119 [[nodiscard]] constexpr reference operator[](const difference_type value) const noexcept {
120 return {it[value].element.first, it[value].element.second};
121 }
122
123 [[nodiscard]] constexpr pointer operator->() const noexcept {
124 return operator*();
125 }
126
127 [[nodiscard]] constexpr reference operator*() const noexcept {
128 return {it->element.first, it->element.second};
129 }
130
131 template<typename Lhs, typename Rhs>
132 friend constexpr std::ptrdiff_t operator-(const dense_map_iterator<Lhs> &, const dense_map_iterator<Rhs> &) noexcept;
133
134 template<typename Lhs, typename Rhs>
135 friend constexpr bool operator==(const dense_map_iterator<Lhs> &, const dense_map_iterator<Rhs> &) noexcept;
136
137 template<typename Lhs, typename Rhs>
138 friend constexpr bool operator<(const dense_map_iterator<Lhs> &, const dense_map_iterator<Rhs> &) noexcept;
139
140private:
141 It it;
142};
143
144template<typename Lhs, typename Rhs>
145[[nodiscard]] constexpr std::ptrdiff_t operator-(const dense_map_iterator<Lhs> &lhs, const dense_map_iterator<Rhs> &rhs) noexcept {
146 return lhs.it - rhs.it;
147}
148
149template<typename Lhs, typename Rhs>
150[[nodiscard]] constexpr bool operator==(const dense_map_iterator<Lhs> &lhs, const dense_map_iterator<Rhs> &rhs) noexcept {
151 return lhs.it == rhs.it;
152}
153
154template<typename Lhs, typename Rhs>
155[[nodiscard]] constexpr bool operator!=(const dense_map_iterator<Lhs> &lhs, const dense_map_iterator<Rhs> &rhs) noexcept {
156 return !(lhs == rhs);
157}
158
159template<typename Lhs, typename Rhs>
160[[nodiscard]] constexpr bool operator<(const dense_map_iterator<Lhs> &lhs, const dense_map_iterator<Rhs> &rhs) noexcept {
161 return lhs.it < rhs.it;
162}
163
164template<typename Lhs, typename Rhs>
165[[nodiscard]] constexpr bool operator>(const dense_map_iterator<Lhs> &lhs, const dense_map_iterator<Rhs> &rhs) noexcept {
166 return rhs < lhs;
167}
168
169template<typename Lhs, typename Rhs>
170[[nodiscard]] constexpr bool operator<=(const dense_map_iterator<Lhs> &lhs, const dense_map_iterator<Rhs> &rhs) noexcept {
171 return !(lhs > rhs);
172}
173
174template<typename Lhs, typename Rhs>
175[[nodiscard]] constexpr bool operator>=(const dense_map_iterator<Lhs> &lhs, const dense_map_iterator<Rhs> &rhs) noexcept {
176 return !(lhs < rhs);
177}
178
179template<typename It>
180class dense_map_local_iterator final {
181 template<typename>
182 friend class dense_map_local_iterator;
183
184 using first_type = decltype(std::as_const(std::declval<It>()->element.first));
185 using second_type = decltype((std::declval<It>()->element.second));
186
187public:
188 using value_type = std::pair<first_type, second_type>;
190 using reference = value_type;
191 using difference_type = std::ptrdiff_t;
192 using iterator_category = std::input_iterator_tag;
193
194 constexpr dense_map_local_iterator() noexcept
195 : it{},
196 offset{} {}
197
198 constexpr dense_map_local_iterator(It iter, const std::size_t pos) noexcept
199 : it{iter},
200 offset{pos} {}
201
202 template<typename Other, typename = std::enable_if_t<!std::is_same_v<It, Other> && std::is_constructible_v<It, Other>>>
203 constexpr dense_map_local_iterator(const dense_map_local_iterator<Other> &other) noexcept
204 : it{other.it},
205 offset{other.offset} {}
206
207 constexpr dense_map_local_iterator &operator++() noexcept {
208 return offset = it[offset].next, *this;
209 }
210
211 constexpr dense_map_local_iterator operator++(int) noexcept {
212 dense_map_local_iterator orig = *this;
213 return ++(*this), orig;
214 }
215
216 [[nodiscard]] constexpr pointer operator->() const noexcept {
217 return operator*();
218 }
219
220 [[nodiscard]] constexpr reference operator*() const noexcept {
221 return {it[offset].element.first, it[offset].element.second};
222 }
223
224 [[nodiscard]] constexpr std::size_t index() const noexcept {
225 return offset;
226 }
227
228private:
229 It it;
230 std::size_t offset;
231};
232
233template<typename Lhs, typename Rhs>
234[[nodiscard]] constexpr bool operator==(const dense_map_local_iterator<Lhs> &lhs, const dense_map_local_iterator<Rhs> &rhs) noexcept {
235 return lhs.index() == rhs.index();
236}
237
238template<typename Lhs, typename Rhs>
239[[nodiscard]] constexpr bool operator!=(const dense_map_local_iterator<Lhs> &lhs, const dense_map_local_iterator<Rhs> &rhs) noexcept {
240 return !(lhs == rhs);
241}
242
243} // namespace internal
244
263template<typename Key, typename Type, typename Hash, typename KeyEqual, typename Allocator>
265 static constexpr float default_threshold = 0.875f;
266 static constexpr std::size_t minimum_capacity = 8u;
267
268 using node_type = internal::dense_map_node<Key, Type>;
269 using alloc_traits = std::allocator_traits<Allocator>;
270 static_assert(std::is_same_v<typename alloc_traits::value_type, std::pair<const Key, Type>>, "Invalid value type");
271 using sparse_container_type = std::vector<std::size_t, typename alloc_traits::template rebind_alloc<std::size_t>>;
272 using packed_container_type = std::vector<node_type, typename alloc_traits::template rebind_alloc<node_type>>;
273
274 template<typename Other>
275 [[nodiscard]] std::size_t key_to_bucket(const Other &key) const noexcept {
276 return fast_mod(static_cast<size_type>(sparse.second()(key)), bucket_count());
277 }
278
279 template<typename Other>
280 [[nodiscard]] auto constrained_find(const Other &key, std::size_t bucket) {
281 for(auto it = begin(bucket), last = end(bucket); it != last; ++it) {
282 if(packed.second()(it->first, key)) {
283 return begin() + static_cast<typename iterator::difference_type>(it.index());
284 }
285 }
286
287 return end();
288 }
289
290 template<typename Other>
291 [[nodiscard]] auto constrained_find(const Other &key, std::size_t bucket) const {
292 for(auto it = cbegin(bucket), last = cend(bucket); it != last; ++it) {
293 if(packed.second()(it->first, key)) {
294 return cbegin() + static_cast<typename iterator::difference_type>(it.index());
295 }
296 }
297
298 return cend();
299 }
300
301 template<typename Other, typename... Args>
302 [[nodiscard]] auto insert_or_do_nothing(Other &&key, Args &&...args) {
303 const auto index = key_to_bucket(key);
304
305 if(auto it = constrained_find(key, index); it != end()) {
306 return std::make_pair(it, false);
307 }
308
309 packed.first().emplace_back(sparse.first()[index], std::piecewise_construct, std::forward_as_tuple(std::forward<Other>(key)), std::forward_as_tuple(std::forward<Args>(args)...));
310 sparse.first()[index] = packed.first().size() - 1u;
311 rehash_if_required();
312
313 return std::make_pair(--end(), true);
314 }
315
316 template<typename Other, typename Arg>
317 [[nodiscard]] auto insert_or_overwrite(Other &&key, Arg &&value) {
318 const auto index = key_to_bucket(key);
319
320 if(auto it = constrained_find(key, index); it != end()) {
321 it->second = std::forward<Arg>(value);
322 return std::make_pair(it, false);
323 }
324
325 packed.first().emplace_back(sparse.first()[index], std::forward<Other>(key), std::forward<Arg>(value));
326 sparse.first()[index] = packed.first().size() - 1u;
327 rehash_if_required();
328
329 return std::make_pair(--end(), true);
330 }
331
332 void move_and_pop(const std::size_t pos) {
333 if(const auto last = size() - 1u; pos != last) {
334 size_type *curr = sparse.first().data() + key_to_bucket(packed.first().back().element.first);
335 packed.first()[pos] = std::move(packed.first().back());
336 for(; *curr != last; curr = &packed.first()[*curr].next) {}
337 *curr = pos;
338 }
339
340 packed.first().pop_back();
341 }
342
343 void rehash_if_required() {
344 if(size() > (bucket_count() * max_load_factor())) {
345 rehash(bucket_count() * 2u);
346 }
347 }
348
349public:
351 using key_type = Key;
353 using mapped_type = Type;
355 using value_type = std::pair<const Key, Type>;
357 using size_type = std::size_t;
359 using hasher = Hash;
361 using key_equal = KeyEqual;
363 using allocator_type = Allocator;
365 using iterator = internal::dense_map_iterator<typename packed_container_type::iterator>;
367 using const_iterator = internal::dense_map_iterator<typename packed_container_type::const_iterator>;
369 using local_iterator = internal::dense_map_local_iterator<typename packed_container_type::iterator>;
371 using const_local_iterator = internal::dense_map_local_iterator<typename packed_container_type::const_iterator>;
372
375 : dense_map{minimum_capacity} {}
376
381 explicit dense_map(const allocator_type &allocator)
382 : dense_map{minimum_capacity, hasher{}, key_equal{}, allocator} {}
383
390 dense_map(const size_type cnt, const allocator_type &allocator)
391 : dense_map{cnt, hasher{}, key_equal{}, allocator} {}
392
400 dense_map(const size_type cnt, const hasher &hash, const allocator_type &allocator)
401 : dense_map{cnt, hash, key_equal{}, allocator} {}
402
411 explicit dense_map(const size_type cnt, const hasher &hash = hasher{}, const key_equal &equal = key_equal{}, const allocator_type &allocator = allocator_type{})
412 : sparse{allocator, hash},
413 packed{allocator, equal},
414 threshold{default_threshold} {
415 rehash(cnt);
416 }
417
419 dense_map(const dense_map &) = default;
420
426 dense_map(const dense_map &other, const allocator_type &allocator)
427 : sparse{std::piecewise_construct, std::forward_as_tuple(other.sparse.first(), allocator), std::forward_as_tuple(other.sparse.second())},
428 packed{std::piecewise_construct, std::forward_as_tuple(other.packed.first(), allocator), std::forward_as_tuple(other.packed.second())},
429 threshold{other.threshold} {}
430
432 dense_map(dense_map &&) noexcept(std::is_nothrow_move_constructible_v<compressed_pair<sparse_container_type, hasher>> &&std::is_nothrow_move_constructible_v<compressed_pair<packed_container_type, key_equal>>) = default;
433
439 dense_map(dense_map &&other, const allocator_type &allocator)
440 : sparse{std::piecewise_construct, std::forward_as_tuple(std::move(other.sparse.first()), allocator), std::forward_as_tuple(std::move(other.sparse.second()))},
441 packed{std::piecewise_construct, std::forward_as_tuple(std::move(other.packed.first()), allocator), std::forward_as_tuple(std::move(other.packed.second()))},
442 threshold{other.threshold} {}
443
448 dense_map &operator=(const dense_map &) = default;
449
454 dense_map &operator=(dense_map &&) noexcept(std::is_nothrow_move_assignable_v<compressed_pair<sparse_container_type, hasher>> &&std::is_nothrow_move_assignable_v<compressed_pair<packed_container_type, key_equal>>) = default;
455
460 [[nodiscard]] constexpr allocator_type get_allocator() const noexcept {
461 return sparse.first().get_allocator();
462 }
463
471 [[nodiscard]] const_iterator cbegin() const noexcept {
472 return packed.first().begin();
473 }
474
476 [[nodiscard]] const_iterator begin() const noexcept {
477 return cbegin();
478 }
479
481 [[nodiscard]] iterator begin() noexcept {
482 return packed.first().begin();
483 }
484
490 [[nodiscard]] const_iterator cend() const noexcept {
491 return packed.first().end();
492 }
493
495 [[nodiscard]] const_iterator end() const noexcept {
496 return cend();
497 }
498
500 [[nodiscard]] iterator end() noexcept {
501 return packed.first().end();
502 }
503
508 [[nodiscard]] bool empty() const noexcept {
509 return packed.first().empty();
510 }
511
516 [[nodiscard]] size_type size() const noexcept {
517 return packed.first().size();
518 }
519
524 [[nodiscard]] size_type max_size() const noexcept {
525 return packed.first().max_size();
526 }
527
529 void clear() noexcept {
530 sparse.first().clear();
531 packed.first().clear();
532 rehash(0u);
533 }
534
542 std::pair<iterator, bool> insert(const value_type &value) {
543 return insert_or_do_nothing(value.first, value.second);
544 }
545
547 std::pair<iterator, bool> insert(value_type &&value) {
548 return insert_or_do_nothing(std::move(value.first), std::move(value.second));
549 }
550
555 template<typename Arg>
556 std::enable_if_t<std::is_constructible_v<value_type, Arg &&>, std::pair<iterator, bool>>
557 insert(Arg &&value) {
558 return insert_or_do_nothing(std::forward<Arg>(value).first, std::forward<Arg>(value).second);
559 }
560
567 template<typename It>
568 void insert(It first, It last) {
569 for(; first != last; ++first) {
570 insert(*first);
571 }
572 }
573
583 template<typename Arg>
584 std::pair<iterator, bool> insert_or_assign(const key_type &key, Arg &&value) {
585 return insert_or_overwrite(key, std::forward<Arg>(value));
586 }
587
589 template<typename Arg>
590 std::pair<iterator, bool> insert_or_assign(key_type &&key, Arg &&value) {
591 return insert_or_overwrite(std::move(key), std::forward<Arg>(value));
592 }
593
607 template<typename... Args>
608 std::pair<iterator, bool> emplace([[maybe_unused]] Args &&...args) {
609 if constexpr(sizeof...(Args) == 0u) {
610 return insert_or_do_nothing(key_type{});
611 } else if constexpr(sizeof...(Args) == 1u) {
612 return insert_or_do_nothing(std::forward<Args>(args).first..., std::forward<Args>(args).second...);
613 } else if constexpr(sizeof...(Args) == 2u) {
614 return insert_or_do_nothing(std::forward<Args>(args)...);
615 } else {
616 auto &node = packed.first().emplace_back(packed.first().size(), std::forward<Args>(args)...);
617 const auto index = key_to_bucket(node.element.first);
618
619 if(auto it = constrained_find(node.element.first, index); it != end()) {
620 packed.first().pop_back();
621 return std::make_pair(it, false);
622 }
623
624 std::swap(node.next, sparse.first()[index]);
625 rehash_if_required();
626
627 return std::make_pair(--end(), true);
628 }
629 }
630
642 template<typename... Args>
643 std::pair<iterator, bool> try_emplace(const key_type &key, Args &&...args) {
644 return insert_or_do_nothing(key, std::forward<Args>(args)...);
645 }
646
648 template<typename... Args>
649 std::pair<iterator, bool> try_emplace(key_type &&key, Args &&...args) {
650 return insert_or_do_nothing(std::move(key), std::forward<Args>(args)...);
651 }
652
659 const auto diff = pos - cbegin();
660 erase(pos->first);
661 return begin() + diff;
662 }
663
671 const auto dist = first - cbegin();
672
673 for(auto from = last - cbegin(); from != dist; --from) {
674 erase(packed.first()[from - 1u].element.first);
675 }
676
677 return (begin() + dist);
678 }
679
686 for(size_type *curr = sparse.first().data() + key_to_bucket(key); *curr != (std::numeric_limits<size_type>::max)(); curr = &packed.first()[*curr].next) {
687 if(packed.second()(packed.first()[*curr].element.first, key)) {
688 const auto index = *curr;
689 *curr = packed.first()[*curr].next;
690 move_and_pop(index);
691 return 1u;
692 }
693 }
694
695 return 0u;
696 }
697
702 void swap(dense_map &other) {
703 using std::swap;
704 swap(sparse, other.sparse);
705 swap(packed, other.packed);
706 swap(threshold, other.threshold);
707 }
708
714 [[nodiscard]] mapped_type &at(const key_type &key) {
715 auto it = find(key);
716 ENTT_ASSERT(it != end(), "Invalid key");
717 return it->second;
718 }
719
721 [[nodiscard]] const mapped_type &at(const key_type &key) const {
722 auto it = find(key);
723 ENTT_ASSERT(it != cend(), "Invalid key");
724 return it->second;
725 }
726
732 [[nodiscard]] mapped_type &operator[](const key_type &key) {
733 return insert_or_do_nothing(key).first->second;
734 }
735
741 [[nodiscard]] mapped_type &operator[](key_type &&key) {
742 return insert_or_do_nothing(std::move(key)).first->second;
743 }
744
750 [[nodiscard]] size_type count(const key_type &key) const {
751 return find(key) != end();
752 }
753
760 template<typename Other>
761 [[nodiscard]] std::enable_if_t<is_transparent_v<hasher> && is_transparent_v<key_equal>, std::conditional_t<false, Other, size_type>>
762 count(const Other &key) const {
763 return find(key) != end();
764 }
765
772 [[nodiscard]] iterator find(const key_type &key) {
773 return constrained_find(key, key_to_bucket(key));
774 }
775
777 [[nodiscard]] const_iterator find(const key_type &key) const {
778 return constrained_find(key, key_to_bucket(key));
779 }
780
789 template<typename Other>
790 [[nodiscard]] std::enable_if_t<is_transparent_v<hasher> && is_transparent_v<key_equal>, std::conditional_t<false, Other, iterator>>
791 find(const Other &key) {
792 return constrained_find(key, key_to_bucket(key));
793 }
794
796 template<typename Other>
797 [[nodiscard]] std::enable_if_t<is_transparent_v<hasher> && is_transparent_v<key_equal>, std::conditional_t<false, Other, const_iterator>>
798 find(const Other &key) const {
799 return constrained_find(key, key_to_bucket(key));
800 }
801
808 [[nodiscard]] std::pair<iterator, iterator> equal_range(const key_type &key) {
809 const auto it = find(key);
810 return {it, it + !(it == end())};
811 }
812
814 [[nodiscard]] std::pair<const_iterator, const_iterator> equal_range(const key_type &key) const {
815 const auto it = find(key);
816 return {it, it + !(it == cend())};
817 }
818
827 template<typename Other>
828 [[nodiscard]] std::enable_if_t<is_transparent_v<hasher> && is_transparent_v<key_equal>, std::conditional_t<false, Other, std::pair<iterator, iterator>>>
829 equal_range(const Other &key) {
830 const auto it = find(key);
831 return {it, it + !(it == end())};
832 }
833
835 template<typename Other>
836 [[nodiscard]] std::enable_if_t<is_transparent_v<hasher> && is_transparent_v<key_equal>, std::conditional_t<false, Other, std::pair<const_iterator, const_iterator>>>
837 equal_range(const Other &key) const {
838 const auto it = find(key);
839 return {it, it + !(it == cend())};
840 }
841
847 [[nodiscard]] bool contains(const key_type &key) const {
848 return (find(key) != cend());
849 }
850
858 template<typename Other>
859 [[nodiscard]] std::enable_if_t<is_transparent_v<hasher> && is_transparent_v<key_equal>, std::conditional_t<false, Other, bool>>
860 contains(const Other &key) const {
861 return (find(key) != cend());
862 }
863
869 [[nodiscard]] const_local_iterator cbegin(const size_type index) const {
870 return {packed.first().begin(), sparse.first()[index]};
871 }
872
878 [[nodiscard]] const_local_iterator begin(const size_type index) const {
879 return cbegin(index);
880 }
881
887 [[nodiscard]] local_iterator begin(const size_type index) {
888 return {packed.first().begin(), sparse.first()[index]};
889 }
890
896 [[nodiscard]] const_local_iterator cend([[maybe_unused]] const size_type index) const {
897 return {packed.first().begin(), (std::numeric_limits<size_type>::max)()};
898 }
899
905 [[nodiscard]] const_local_iterator end(const size_type index) const {
906 return cend(index);
907 }
908
914 [[nodiscard]] local_iterator end([[maybe_unused]] const size_type index) {
915 return {packed.first().begin(), (std::numeric_limits<size_type>::max)()};
916 }
917
922 [[nodiscard]] size_type bucket_count() const {
923 return sparse.first().size();
924 }
925
930 [[nodiscard]] size_type max_bucket_count() const {
931 return sparse.first().max_size();
932 }
933
939 [[nodiscard]] size_type bucket_size(const size_type index) const {
940 return static_cast<size_type>(std::distance(begin(index), end(index)));
941 }
942
948 [[nodiscard]] size_type bucket(const key_type &key) const {
949 return key_to_bucket(key);
950 }
951
956 [[nodiscard]] float load_factor() const {
957 return size() / static_cast<float>(bucket_count());
958 }
959
964 [[nodiscard]] float max_load_factor() const {
965 return threshold;
966 }
967
972 void max_load_factor(const float value) {
973 ENTT_ASSERT(value > 0.f, "Invalid load factor");
974 threshold = value;
975 rehash(0u);
976 }
977
983 void rehash(const size_type cnt) {
984 auto value = cnt > minimum_capacity ? cnt : minimum_capacity;
985 const auto cap = static_cast<size_type>(size() / max_load_factor());
986 value = value > cap ? value : cap;
987
988 if(const auto sz = next_power_of_two(value); sz != bucket_count()) {
989 sparse.first().resize(sz);
990
991 for(auto &&elem: sparse.first()) {
992 elem = std::numeric_limits<size_type>::max();
993 }
994
995 for(size_type pos{}, last = size(); pos < last; ++pos) {
996 const auto index = key_to_bucket(packed.first()[pos].element.first);
997 packed.first()[pos].next = std::exchange(sparse.first()[index], pos);
998 }
999 }
1000 }
1001
1007 void reserve(const size_type cnt) {
1008 packed.first().reserve(cnt);
1009 rehash(static_cast<size_type>(std::ceil(cnt / max_load_factor())));
1010 }
1011
1016 [[nodiscard]] hasher hash_function() const {
1017 return sparse.second();
1018 }
1019
1024 [[nodiscard]] key_equal key_eq() const {
1025 return packed.second();
1026 }
1027
1028private:
1031 float threshold;
1032};
1033
1034} // namespace entt
1035
1041namespace std {
1042
1043template<typename Key, typename Value, typename Allocator>
1044struct uses_allocator<entt::internal::dense_map_node<Key, Value>, Allocator>
1045 : std::true_type {};
1046
1047} // namespace std
1048
1054#endif
A compressed pair.
constexpr second_type & second() noexcept
Returns the second element that a pair stores.
constexpr first_type & first() noexcept
Returns the first element that a pair stores.
Associative container for key-value pairs with unique keys.
Definition: dense_map.hpp:264
dense_map(const size_type cnt, const hasher &hash=hasher{}, const key_equal &equal=key_equal{}, const allocator_type &allocator=allocator_type{})
Constructs an empty container with a given allocator, hash function, compare function and user suppli...
Definition: dense_map.hpp:411
dense_map(const allocator_type &allocator)
Constructs an empty container with a given allocator.
Definition: dense_map.hpp:381
void clear() noexcept
Clears the container.
Definition: dense_map.hpp:529
float load_factor() const
Returns the average number of elements per bucket.
Definition: dense_map.hpp:956
size_type erase(const key_type &key)
Removes the element associated with a given key.
Definition: dense_map.hpp:685
mapped_type & operator[](key_type &&key)
Accesses or inserts a given element.
Definition: dense_map.hpp:741
std::enable_if_t< is_transparent_v< hasher > &&is_transparent_v< key_equal >, std::conditional_t< false, Other, bool > > contains(const Other &key) const
Checks if the container contains an element with a key that compares equivalent to a given value.
Definition: dense_map.hpp:860
const_iterator cbegin() const noexcept
Returns an iterator to the beginning.
Definition: dense_map.hpp:471
const_local_iterator begin(const size_type index) const
Returns an iterator to the beginning of a given bucket.
Definition: dense_map.hpp:878
std::enable_if_t< is_transparent_v< hasher > &&is_transparent_v< key_equal >, std::conditional_t< false, Other, size_type > > count(const Other &key) const
Returns the number of elements matching a key (either 1 or 0).
Definition: dense_map.hpp:762
size_type size() const noexcept
Returns the number of elements in a container.
Definition: dense_map.hpp:516
std::size_t size_type
Unsigned integer type.
Definition: dense_map.hpp:357
const_local_iterator end(const size_type index) const
Returns an iterator to the end of a given bucket.
Definition: dense_map.hpp:905
void insert(It first, It last)
Inserts elements into the container, if their keys do not exist.
Definition: dense_map.hpp:568
std::enable_if_t< is_transparent_v< hasher > &&is_transparent_v< key_equal >, std::conditional_t< false, Other, std::pair< iterator, iterator > > > equal_range(const Other &key)
Returns a range containing all elements that compare equivalent to a given key.
Definition: dense_map.hpp:829
const mapped_type & at(const key_type &key) const
Accesses a given element with bounds checking.
Definition: dense_map.hpp:721
KeyEqual key_equal
Type of function to use to compare the keys for equality.
Definition: dense_map.hpp:361
size_type max_size() const noexcept
Returns the maximum possible number of elements.
Definition: dense_map.hpp:524
mapped_type & at(const key_type &key)
Accesses a given element with bounds checking.
Definition: dense_map.hpp:714
void reserve(const size_type cnt)
Reserves space for at least the specified number of elements and regenerates the hash table.
Definition: dense_map.hpp:1007
size_type max_bucket_count() const
Returns the maximum number of buckets.
Definition: dense_map.hpp:930
iterator erase(const_iterator first, const_iterator last)
Removes the given elements from a container.
Definition: dense_map.hpp:670
size_type count(const key_type &key) const
Returns the number of elements matching a key (either 1 or 0).
Definition: dense_map.hpp:750
local_iterator begin(const size_type index)
Returns an iterator to the beginning of a given bucket.
Definition: dense_map.hpp:887
std::enable_if_t< is_transparent_v< hasher > &&is_transparent_v< key_equal >, std::conditional_t< false, Other, const_iterator > > find(const Other &key) const
Finds an element with a given key.
Definition: dense_map.hpp:798
bool contains(const key_type &key) const
Checks if the container contains an element with a given key.
Definition: dense_map.hpp:847
const_iterator cend() const noexcept
Returns an iterator to the end.
Definition: dense_map.hpp:490
dense_map(const size_type cnt, const allocator_type &allocator)
Constructs an empty container with a given allocator and user supplied minimal number of buckets.
Definition: dense_map.hpp:390
std::pair< iterator, bool > try_emplace(const key_type &key, Args &&...args)
Inserts in-place if the key does not exist, does nothing if the key exists.
Definition: dense_map.hpp:643
float max_load_factor() const
Returns the maximum average number of elements per bucket.
Definition: dense_map.hpp:964
const_iterator find(const key_type &key) const
Finds an element with a given key.
Definition: dense_map.hpp:777
internal::dense_map_iterator< typename packed_container_type::const_iterator > const_iterator
Constant input iterator type.
Definition: dense_map.hpp:367
void max_load_factor(const float value)
Sets the desired maximum average number of elements per bucket.
Definition: dense_map.hpp:972
dense_map & operator=(const dense_map &)=default
Default copy assignment operator.
std::pair< iterator, bool > insert(value_type &&value)
Inserts an element into the container, if the key does not exist.
Definition: dense_map.hpp:547
iterator find(const key_type &key)
Finds an element with a given key.
Definition: dense_map.hpp:772
std::pair< iterator, iterator > equal_range(const key_type &key)
Returns a range containing all elements with a given key.
Definition: dense_map.hpp:808
const_iterator begin() const noexcept
Returns an iterator to the beginning.
Definition: dense_map.hpp:476
Type mapped_type
Mapped type of the container.
Definition: dense_map.hpp:353
void rehash(const size_type cnt)
Reserves at least the specified number of buckets and regenerates the hash table.
Definition: dense_map.hpp:983
const_local_iterator cend(const size_type index) const
Returns an iterator to the end of a given bucket.
Definition: dense_map.hpp:896
iterator erase(const_iterator pos)
Removes an element from a given position.
Definition: dense_map.hpp:658
dense_map(const dense_map &other, const allocator_type &allocator)
Allocator-extended copy constructor.
Definition: dense_map.hpp:426
std::enable_if_t< std::is_constructible_v< value_type, Arg && >, std::pair< iterator, bool > > insert(Arg &&value)
Inserts an element into the container, if the key does not exist.
Definition: dense_map.hpp:557
std::enable_if_t< is_transparent_v< hasher > &&is_transparent_v< key_equal >, std::conditional_t< false, Other, std::pair< const_iterator, const_iterator > > > equal_range(const Other &key) const
Returns a range containing all elements with a given key.
Definition: dense_map.hpp:837
size_type bucket(const key_type &key) const
Returns the bucket for a given key.
Definition: dense_map.hpp:948
std::pair< iterator, bool > insert_or_assign(key_type &&key, Arg &&value)
Inserts an element into the container or assigns to the current element if the key already exists.
Definition: dense_map.hpp:590
mapped_type & operator[](const key_type &key)
Accesses or inserts a given element.
Definition: dense_map.hpp:732
constexpr allocator_type get_allocator() const noexcept
Returns the associated allocator.
Definition: dense_map.hpp:460
const_local_iterator cbegin(const size_type index) const
Returns an iterator to the beginning of a given bucket.
Definition: dense_map.hpp:869
std::pair< const Key, Type > value_type
Key-value type of the container.
Definition: dense_map.hpp:355
dense_map(const dense_map &)=default
Default copy constructor.
dense_map & operator=(dense_map &&) noexcept(std::is_nothrow_move_assignable_v< compressed_pair< sparse_container_type, hasher > > &&std::is_nothrow_move_assignable_v< compressed_pair< packed_container_type, key_equal > >)=default
Default move assignment operator.
std::pair< iterator, bool > insert_or_assign(const key_type &key, Arg &&value)
Inserts an element into the container or assigns to the current element if the key already exists.
Definition: dense_map.hpp:584
std::pair< iterator, bool > emplace(Args &&...args)
Constructs an element in-place, if the key does not exist.
Definition: dense_map.hpp:608
std::pair< iterator, bool > try_emplace(key_type &&key, Args &&...args)
Inserts in-place if the key does not exist, does nothing if the key exists.
Definition: dense_map.hpp:649
void swap(dense_map &other)
Exchanges the contents with those of a given container.
Definition: dense_map.hpp:702
local_iterator end(const size_type index)
Returns an iterator to the end of a given bucket.
Definition: dense_map.hpp:914
std::enable_if_t< is_transparent_v< hasher > &&is_transparent_v< key_equal >, std::conditional_t< false, Other, iterator > > find(const Other &key)
Finds an element with a key that compares equivalent to a given key.
Definition: dense_map.hpp:791
key_equal key_eq() const
Returns the function used to compare keys for equality.
Definition: dense_map.hpp:1024
dense_map(const size_type cnt, const hasher &hash, const allocator_type &allocator)
Constructs an empty container with a given allocator, hash function and user supplied minimal number ...
Definition: dense_map.hpp:400
internal::dense_map_iterator< typename packed_container_type::iterator > iterator
Input iterator type.
Definition: dense_map.hpp:365
internal::dense_map_local_iterator< typename packed_container_type::iterator > local_iterator
Input iterator type.
Definition: dense_map.hpp:369
internal::dense_map_local_iterator< typename packed_container_type::const_iterator > const_local_iterator
Constant input iterator type.
Definition: dense_map.hpp:371
bool empty() const noexcept
Checks whether a container is empty.
Definition: dense_map.hpp:508
std::pair< iterator, bool > insert(const value_type &value)
Inserts an element into the container, if the key does not exist.
Definition: dense_map.hpp:542
Allocator allocator_type
Allocator type.
Definition: dense_map.hpp:363
size_type bucket_size(const size_type index) const
Returns the number of elements in a given bucket.
Definition: dense_map.hpp:939
Hash hasher
Type of function to use to hash the keys.
Definition: dense_map.hpp:359
Key key_type
Key type of the container.
Definition: dense_map.hpp:351
size_type bucket_count() const
Returns the number of buckets.
Definition: dense_map.hpp:922
dense_map()
Default constructor.
Definition: dense_map.hpp:374
std::pair< const_iterator, const_iterator > equal_range(const key_type &key) const
Returns a range containing all elements with a given key.
Definition: dense_map.hpp:814
hasher hash_function() const
Returns the function used to hash the keys.
Definition: dense_map.hpp:1016
const_iterator end() const noexcept
Returns an iterator to the end.
Definition: dense_map.hpp:495
iterator begin() noexcept
Returns an iterator to the beginning.
Definition: dense_map.hpp:481
iterator end() noexcept
Returns an iterator to the end.
Definition: dense_map.hpp:500
dense_map(dense_map &&) noexcept(std::is_nothrow_move_constructible_v< compressed_pair< sparse_container_type, hasher > > &&std::is_nothrow_move_constructible_v< compressed_pair< packed_container_type, key_equal > >)=default
Default move constructor.
EnTT default namespace.
Definition: dense_map.hpp:21
constexpr std::size_t fast_mod(const std::size_t value, const std::size_t mod) noexcept
Fast module utility function (powers of two only).
Definition: memory.hpp:45
constexpr bool operator<=(const basic_hashed_string< Char > &lhs, const basic_hashed_string< Char > &rhs) noexcept
Compares two hashed strings.
constexpr bool operator<(const basic_hashed_string< Char > &lhs, const basic_hashed_string< Char > &rhs) noexcept
Compares two hashed strings.
constexpr type_list< Type..., Other... > operator+(type_list< Type... >, type_list< Other... >)
Concatenates multiple type lists.
constexpr std::size_t next_power_of_two(const std::size_t value) noexcept
Computes the smallest power of two greater than or equal to a value.
Definition: memory.hpp:28
constexpr bool operator!=(const basic_hashed_string< Char > &lhs, const basic_hashed_string< Char > &rhs) noexcept
Compares two hashed strings.
constexpr bool operator>=(const basic_hashed_string< Char > &lhs, const basic_hashed_string< Char > &rhs) noexcept
Compares two hashed strings.
constexpr bool operator>(const basic_hashed_string< Char > &lhs, const basic_hashed_string< Char > &rhs) noexcept
Compares two hashed strings.
constexpr bool operator==(const basic_hashed_string< Char > &lhs, const basic_hashed_string< Char > &rhs) noexcept
Compares two hashed strings.
Helper type to use as pointer with input iterators.
Definition: iterator.hpp:16