EnTT  3.10.0
dense_map.hpp
1 #ifndef ENTT_CONTAINER_DENSE_MAP_HPP
2 #define ENTT_CONTAINER_DENSE_MAP_HPP
3 
4 #include <algorithm>
5 #include <cmath>
6 #include <cstddef>
7 #include <functional>
8 #include <iterator>
9 #include <limits>
10 #include <memory>
11 #include <tuple>
12 #include <type_traits>
13 #include <utility>
14 #include <vector>
15 #include "../config/config.h"
16 #include "../core/compressed_pair.hpp"
17 #include "../core/iterator.hpp"
18 #include "../core/memory.hpp"
19 #include "../core/type_traits.hpp"
20 #include "fwd.hpp"
21 
22 namespace entt {
23 
29 namespace internal {
30 
31 template<typename Key, typename Type>
32 struct dense_map_node final {
33  using value_type = std::pair<Key, Type>;
34 
35  template<typename... Args>
36  dense_map_node(const std::size_t pos, Args &&...args)
37  : next{pos},
38  element{std::forward<Args>(args)...} {}
39 
40  template<typename Allocator, typename... Args>
41  dense_map_node(std::allocator_arg_t, const Allocator &allocator, const std::size_t pos, Args &&...args)
42  : next{pos},
43  element{entt::make_obj_using_allocator<value_type>(allocator, std::forward<Args>(args)...)} {}
44 
45  template<typename Allocator>
46  dense_map_node(std::allocator_arg_t, const Allocator &allocator, const dense_map_node &other)
47  : next{other.next},
48  element{entt::make_obj_using_allocator<value_type>(allocator, other.element)} {}
49 
50  template<typename Allocator>
51  dense_map_node(std::allocator_arg_t, const Allocator &allocator, dense_map_node &&other)
52  : next{other.next},
53  element{entt::make_obj_using_allocator<value_type>(allocator, std::move(other.element))} {}
54 
55  std::size_t next;
56  value_type element;
57 };
58 
59 template<typename It>
60 class dense_map_iterator final {
61  template<typename>
62  friend class dense_map_iterator;
63 
64  using first_type = decltype(std::as_const(std::declval<It>()->element.first));
65  using second_type = decltype((std::declval<It>()->element.second));
66 
67 public:
68  using value_type = std::pair<first_type, second_type>;
69  using pointer = input_iterator_pointer<value_type>;
70  using reference = value_type;
71  using difference_type = std::ptrdiff_t;
72  using iterator_category = std::input_iterator_tag;
73 
74  dense_map_iterator() ENTT_NOEXCEPT
75  : it{} {}
76 
77  dense_map_iterator(const It iter) ENTT_NOEXCEPT
78  : it{iter} {}
79 
80  template<typename Other, typename = std::enable_if_t<!std::is_same_v<It, Other> && std::is_constructible_v<It, Other>>>
81  dense_map_iterator(const dense_map_iterator<Other> &other) ENTT_NOEXCEPT
82  : it{other.it} {}
83 
84  dense_map_iterator &operator++() ENTT_NOEXCEPT {
85  return ++it, *this;
86  }
87 
88  dense_map_iterator operator++(int) ENTT_NOEXCEPT {
89  dense_map_iterator orig = *this;
90  return ++(*this), orig;
91  }
92 
93  dense_map_iterator &operator--() ENTT_NOEXCEPT {
94  return --it, *this;
95  }
96 
97  dense_map_iterator operator--(int) ENTT_NOEXCEPT {
98  dense_map_iterator orig = *this;
99  return operator--(), orig;
100  }
101 
102  dense_map_iterator &operator+=(const difference_type value) ENTT_NOEXCEPT {
103  it += value;
104  return *this;
105  }
106 
107  dense_map_iterator operator+(const difference_type value) const ENTT_NOEXCEPT {
108  dense_map_iterator copy = *this;
109  return (copy += value);
110  }
111 
112  dense_map_iterator &operator-=(const difference_type value) ENTT_NOEXCEPT {
113  return (*this += -value);
114  }
115 
116  dense_map_iterator operator-(const difference_type value) const ENTT_NOEXCEPT {
117  return (*this + -value);
118  }
119 
120  [[nodiscard]] reference operator[](const difference_type value) const ENTT_NOEXCEPT {
121  return {it[value].element.first, it[value].element.second};
122  }
123 
124  [[nodiscard]] pointer operator->() const ENTT_NOEXCEPT {
125  return operator*();
126  }
127 
128  [[nodiscard]] reference operator*() const ENTT_NOEXCEPT {
129  return {it->element.first, it->element.second};
130  }
131 
132  template<typename ILhs, typename IRhs>
133  friend std::ptrdiff_t operator-(const dense_map_iterator<ILhs> &, const dense_map_iterator<IRhs> &) ENTT_NOEXCEPT;
134 
135  template<typename ILhs, typename IRhs>
136  friend bool operator==(const dense_map_iterator<ILhs> &, const dense_map_iterator<IRhs> &) ENTT_NOEXCEPT;
137 
138  template<typename ILhs, typename IRhs>
139  friend bool operator<(const dense_map_iterator<ILhs> &, const dense_map_iterator<IRhs> &) ENTT_NOEXCEPT;
140 
141 private:
142  It it;
143 };
144 
145 template<typename ILhs, typename IRhs>
146 [[nodiscard]] std::ptrdiff_t operator-(const dense_map_iterator<ILhs> &lhs, const dense_map_iterator<IRhs> &rhs) ENTT_NOEXCEPT {
147  return lhs.it - rhs.it;
148 }
149 
150 template<typename ILhs, typename IRhs>
151 [[nodiscard]] bool operator==(const dense_map_iterator<ILhs> &lhs, const dense_map_iterator<IRhs> &rhs) ENTT_NOEXCEPT {
152  return lhs.it == rhs.it;
153 }
154 
155 template<typename ILhs, typename IRhs>
156 [[nodiscard]] bool operator!=(const dense_map_iterator<ILhs> &lhs, const dense_map_iterator<IRhs> &rhs) ENTT_NOEXCEPT {
157  return !(lhs == rhs);
158 }
159 
160 template<typename ILhs, typename IRhs>
161 [[nodiscard]] bool operator<(const dense_map_iterator<ILhs> &lhs, const dense_map_iterator<IRhs> &rhs) ENTT_NOEXCEPT {
162  return lhs.it < rhs.it;
163 }
164 
165 template<typename ILhs, typename IRhs>
166 [[nodiscard]] bool operator>(const dense_map_iterator<ILhs> &lhs, const dense_map_iterator<IRhs> &rhs) ENTT_NOEXCEPT {
167  return rhs < lhs;
168 }
169 
170 template<typename ILhs, typename IRhs>
171 [[nodiscard]] bool operator<=(const dense_map_iterator<ILhs> &lhs, const dense_map_iterator<IRhs> &rhs) ENTT_NOEXCEPT {
172  return !(lhs > rhs);
173 }
174 
175 template<typename ILhs, typename IRhs>
176 [[nodiscard]] bool operator>=(const dense_map_iterator<ILhs> &lhs, const dense_map_iterator<IRhs> &rhs) ENTT_NOEXCEPT {
177  return !(lhs < rhs);
178 }
179 
180 template<typename It>
181 class dense_map_local_iterator final {
182  template<typename>
183  friend class dense_map_local_iterator;
184 
185  using first_type = decltype(std::as_const(std::declval<It>()->element.first));
186  using second_type = decltype((std::declval<It>()->element.second));
187 
188 public:
189  using value_type = std::pair<first_type, second_type>;
190  using pointer = input_iterator_pointer<value_type>;
191  using reference = value_type;
192  using difference_type = std::ptrdiff_t;
193  using iterator_category = std::input_iterator_tag;
194 
195  dense_map_local_iterator() ENTT_NOEXCEPT
196  : it{},
197  offset{} {}
198 
199  dense_map_local_iterator(It iter, const std::size_t pos) ENTT_NOEXCEPT
200  : it{iter},
201  offset{pos} {}
202 
203  template<typename Other, typename = std::enable_if_t<!std::is_same_v<It, Other> && std::is_constructible_v<It, Other>>>
204  dense_map_local_iterator(const dense_map_local_iterator<Other> &other) ENTT_NOEXCEPT
205  : it{other.it},
206  offset{other.offset} {}
207 
208  dense_map_local_iterator &operator++() ENTT_NOEXCEPT {
209  return offset = it[offset].next, *this;
210  }
211 
212  dense_map_local_iterator operator++(int) ENTT_NOEXCEPT {
213  dense_map_local_iterator orig = *this;
214  return ++(*this), orig;
215  }
216 
217  [[nodiscard]] pointer operator->() const ENTT_NOEXCEPT {
218  return operator*();
219  }
220 
221  [[nodiscard]] reference operator*() const ENTT_NOEXCEPT {
222  return {it[offset].element.first, it[offset].element.second};
223  }
224 
225  [[nodiscard]] std::size_t index() const ENTT_NOEXCEPT {
226  return offset;
227  }
228 
229 private:
230  It it;
231  std::size_t offset;
232 };
233 
234 template<typename ILhs, typename IRhs>
235 [[nodiscard]] bool operator==(const dense_map_local_iterator<ILhs> &lhs, const dense_map_local_iterator<IRhs> &rhs) ENTT_NOEXCEPT {
236  return lhs.index() == rhs.index();
237 }
238 
239 template<typename ILhs, typename IRhs>
240 [[nodiscard]] bool operator!=(const dense_map_local_iterator<ILhs> &lhs, const dense_map_local_iterator<IRhs> &rhs) ENTT_NOEXCEPT {
241  return !(lhs == rhs);
242 }
243 
244 } // namespace internal
245 
264 template<typename Key, typename Type, typename Hash, typename KeyEqual, typename Allocator>
265 class dense_map {
266  static constexpr float default_threshold = 0.875f;
267  static constexpr std::size_t minimum_capacity = 8u;
268 
269  using node_type = internal::dense_map_node<Key, Type>;
270  using alloc_traits = typename std::allocator_traits<Allocator>;
271  static_assert(std::is_same_v<typename alloc_traits::value_type, std::pair<const Key, Type>>, "Invalid value type");
272  using sparse_container_type = std::vector<std::size_t, typename alloc_traits::template rebind_alloc<std::size_t>>;
273  using packed_container_type = std::vector<node_type, typename alloc_traits::template rebind_alloc<node_type>>;
274 
275  template<typename Other>
276  [[nodiscard]] std::size_t key_to_bucket(const Other &key) const ENTT_NOEXCEPT {
277  return fast_mod(sparse.second()(key), bucket_count());
278  }
279 
280  template<typename Other>
281  [[nodiscard]] auto constrained_find(const Other &key, std::size_t bucket) {
282  for(auto it = begin(bucket), last = end(bucket); it != last; ++it) {
283  if(packed.second()(it->first, key)) {
284  return begin() + static_cast<typename iterator::difference_type>(it.index());
285  }
286  }
287 
288  return end();
289  }
290 
291  template<typename Other>
292  [[nodiscard]] auto constrained_find(const Other &key, std::size_t bucket) const {
293  for(auto it = cbegin(bucket), last = cend(bucket); it != last; ++it) {
294  if(packed.second()(it->first, key)) {
295  return cbegin() + static_cast<typename iterator::difference_type>(it.index());
296  }
297  }
298 
299  return cend();
300  }
301 
302  template<typename Other, typename... Args>
303  [[nodiscard]] auto insert_or_do_nothing(Other &&key, Args &&...args) {
304  const auto index = key_to_bucket(key);
305 
306  if(auto it = constrained_find(key, index); it != end()) {
307  return std::make_pair(it, false);
308  }
309 
310  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)...));
311  sparse.first()[index] = packed.first().size() - 1u;
312  rehash_if_required();
313 
314  return std::make_pair(--end(), true);
315  }
316 
317  template<typename Other, typename Arg>
318  [[nodiscard]] auto insert_or_overwrite(Other &&key, Arg &&value) {
319  const auto index = key_to_bucket(key);
320 
321  if(auto it = constrained_find(key, index); it != end()) {
322  it->second = std::forward<Arg>(value);
323  return std::make_pair(it, false);
324  }
325 
326  packed.first().emplace_back(sparse.first()[index], std::forward<Other>(key), std::forward<Arg>(value));
327  sparse.first()[index] = packed.first().size() - 1u;
328  rehash_if_required();
329 
330  return std::make_pair(--end(), true);
331  }
332 
333  void move_and_pop(const std::size_t pos) {
334  if(const auto last = size() - 1u; pos != last) {
335  packed.first()[pos] = std::move(packed.first().back());
336  size_type *curr = sparse.first().data() + key_to_bucket(packed.first().back().element.first);
337  for(; *curr != last; curr = &packed.first()[*curr].next) {}
338  *curr = pos;
339  }
340 
341  packed.first().pop_back();
342  }
343 
344  void rehash_if_required() {
345  if(size() > (bucket_count() * max_load_factor())) {
346  rehash(bucket_count() * 2u);
347  }
348  }
349 
350 public:
352  using key_type = Key;
354  using mapped_type = Type;
356  using value_type = std::pair<const Key, Type>;
358  using size_type = std::size_t;
360  using hasher = Hash;
362  using key_equal = KeyEqual;
364  using allocator_type = Allocator;
366  using iterator = internal::dense_map_iterator<typename packed_container_type::iterator>;
368  using const_iterator = internal::dense_map_iterator<typename packed_container_type::const_iterator>;
370  using local_iterator = internal::dense_map_local_iterator<typename packed_container_type::iterator>;
372  using const_local_iterator = internal::dense_map_local_iterator<typename packed_container_type::const_iterator>;
373 
376  : dense_map(minimum_capacity) {}
377 
382  explicit dense_map(const allocator_type &allocator)
383  : dense_map{minimum_capacity, hasher{}, key_equal{}, allocator} {}
384 
392  : dense_map{bucket_count, hasher{}, key_equal{}, allocator} {}
393 
401  dense_map(const size_type bucket_count, const hasher &hash, const allocator_type &allocator)
402  : dense_map{bucket_count, hash, key_equal{}, allocator} {}
403 
412  explicit dense_map(const size_type bucket_count, const hasher &hash = hasher{}, const key_equal &equal = key_equal{}, const allocator_type &allocator = allocator_type{})
413  : sparse{allocator, hash},
414  packed{allocator, equal},
415  threshold{default_threshold} {
417  }
418 
420  dense_map(const dense_map &) = default;
421 
427  dense_map(const dense_map &other, const allocator_type &allocator)
428  : sparse{std::piecewise_construct, std::forward_as_tuple(other.sparse.first(), allocator), std::forward_as_tuple(other.sparse.second())},
429  packed{std::piecewise_construct, std::forward_as_tuple(other.packed.first(), allocator), std::forward_as_tuple(other.packed.second())},
430  threshold{other.threshold} {}
431 
433  dense_map(dense_map &&) = default;
434 
440  dense_map(dense_map &&other, const allocator_type &allocator)
441  : sparse{std::piecewise_construct, std::forward_as_tuple(std::move(other.sparse.first()), allocator), std::forward_as_tuple(std::move(other.sparse.second()))},
442  packed{std::piecewise_construct, std::forward_as_tuple(std::move(other.packed.first()), allocator), std::forward_as_tuple(std::move(other.packed.second()))},
443  threshold{other.threshold} {}
444 
449  dense_map &operator=(const dense_map &) = default;
450 
455  dense_map &operator=(dense_map &&) = default;
456 
461  [[nodiscard]] constexpr allocator_type get_allocator() const ENTT_NOEXCEPT {
462  return sparse.first().get_allocator();
463  }
464 
473  [[nodiscard]] const_iterator cbegin() const ENTT_NOEXCEPT {
474  return packed.first().begin();
475  }
476 
478  [[nodiscard]] const_iterator begin() const ENTT_NOEXCEPT {
479  return cbegin();
480  }
481 
483  [[nodiscard]] iterator begin() ENTT_NOEXCEPT {
484  return packed.first().begin();
485  }
486 
497  [[nodiscard]] const_iterator cend() const ENTT_NOEXCEPT {
498  return packed.first().end();
499  }
500 
502  [[nodiscard]] const_iterator end() const ENTT_NOEXCEPT {
503  return cend();
504  }
505 
507  [[nodiscard]] iterator end() ENTT_NOEXCEPT {
508  return packed.first().end();
509  }
510 
515  [[nodiscard]] bool empty() const ENTT_NOEXCEPT {
516  return packed.first().empty();
517  }
518 
523  [[nodiscard]] size_type size() const ENTT_NOEXCEPT {
524  return packed.first().size();
525  }
526 
528  void clear() ENTT_NOEXCEPT {
529  sparse.first().clear();
530  packed.first().clear();
531  rehash(0u);
532  }
533 
541  std::pair<iterator, bool> insert(const value_type &value) {
542  return insert_or_do_nothing(value.first, value.second);
543  }
544 
546  std::pair<iterator, bool> insert(value_type &&value) {
547  return insert_or_do_nothing(std::move(value.first), std::move(value.second));
548  }
549 
554  template<typename Arg>
555  std::enable_if_t<std::is_constructible_v<value_type, Arg &&>, std::pair<iterator, bool>>
556  insert(Arg &&value) {
557  return insert_or_do_nothing(std::forward<Arg>(value).first, std::forward<Arg>(value).second);
558  }
559 
566  template<typename It>
567  void insert(It first, It last) {
568  for(; first != last; ++first) {
569  insert(*first);
570  }
571  }
572 
582  template<typename Arg>
583  std::pair<iterator, bool> insert_or_assign(const key_type &key, Arg &&value) {
584  return insert_or_overwrite(key, std::forward<Arg>(value));
585  }
586 
588  template<typename Arg>
589  std::pair<iterator, bool> insert_or_assign(key_type &&key, Arg &&value) {
590  return insert_or_overwrite(std::move(key), std::forward<Arg>(value));
591  }
592 
606  template<typename... Args>
607  std::pair<iterator, bool> emplace([[maybe_unused]] Args &&...args) {
608  if constexpr(sizeof...(Args) == 0u) {
609  return insert_or_do_nothing(key_type{});
610  } else if constexpr(sizeof...(Args) == 1u) {
611  return insert_or_do_nothing(std::forward<Args>(args).first..., std::forward<Args>(args).second...);
612  } else if constexpr(sizeof...(Args) == 2u) {
613  return insert_or_do_nothing(std::forward<Args>(args)...);
614  } else {
615  auto &node = packed.first().emplace_back(packed.first().size(), std::forward<Args>(args)...);
616  const auto index = key_to_bucket(node.element.first);
617 
618  if(auto it = constrained_find(node.element.first, index); it != end()) {
619  packed.first().pop_back();
620  return std::make_pair(it, false);
621  }
622 
623  std::swap(node.next, sparse.first()[index]);
624  rehash_if_required();
625 
626  return std::make_pair(--end(), true);
627  }
628  }
629 
641  template<typename... Args>
642  std::pair<iterator, bool> try_emplace(const key_type &key, Args &&...args) {
643  return insert_or_do_nothing(key, std::forward<Args>(args)...);
644  }
645 
647  template<typename... Args>
648  std::pair<iterator, bool> try_emplace(key_type &&key, Args &&...args) {
649  return insert_or_do_nothing(std::move(key), std::forward<Args>(args)...);
650  }
651 
658  const auto diff = pos - cbegin();
659  erase(pos->first);
660  return begin() + diff;
661  }
662 
670  const auto dist = first - cbegin();
671 
672  for(auto from = last - cbegin(); from != dist; --from) {
673  erase(packed.first()[from - 1u].element.first);
674  }
675 
676  return (begin() + dist);
677  }
678 
684  size_type erase(const key_type &key) {
685  for(size_type *curr = sparse.first().data() + key_to_bucket(key); *curr != (std::numeric_limits<size_type>::max)(); curr = &packed.first()[*curr].next) {
686  if(packed.second()(packed.first()[*curr].element.first, key)) {
687  const auto index = *curr;
688  *curr = packed.first()[*curr].next;
689  move_and_pop(index);
690  return 1u;
691  }
692  }
693 
694  return 0u;
695  }
696 
701  void swap(dense_map &other) {
702  using std::swap;
703  swap(sparse, other.sparse);
704  swap(packed, other.packed);
705  swap(threshold, other.threshold);
706  }
707 
713  [[nodiscard]] mapped_type &at(const key_type &key) {
714  auto it = find(key);
715  ENTT_ASSERT(it != end(), "Invalid key");
716  return it->second;
717  }
718 
720  [[nodiscard]] const mapped_type &at(const key_type &key) const {
721  auto it = find(key);
722  ENTT_ASSERT(it != cend(), "Invalid key");
723  return it->second;
724  }
725 
731  [[nodiscard]] mapped_type &operator[](const key_type &key) {
732  return insert_or_do_nothing(key).first->second;
733  }
734 
740  [[nodiscard]] mapped_type &operator[](key_type &&key) {
741  return insert_or_do_nothing(std::move(key)).first->second;
742  }
743 
750  [[nodiscard]] iterator find(const key_type &key) {
751  return constrained_find(key, key_to_bucket(key));
752  }
753 
755  [[nodiscard]] const_iterator find(const key_type &key) const {
756  return constrained_find(key, key_to_bucket(key));
757  }
758 
767  template<typename Other>
768  [[nodiscard]] std::enable_if_t<is_transparent_v<hasher> && is_transparent_v<key_equal>, std::conditional_t<false, Other, iterator>>
769  find(const Other &key) {
770  return constrained_find(key, key_to_bucket(key));
771  }
772 
774  template<typename Other>
775  [[nodiscard]] std::enable_if_t<is_transparent_v<hasher> && is_transparent_v<key_equal>, std::conditional_t<false, Other, const_iterator>>
776  find(const Other &key) const {
777  return constrained_find(key, key_to_bucket(key));
778  }
779 
785  [[nodiscard]] bool contains(const key_type &key) const {
786  return (find(key) != cend());
787  }
788 
796  template<typename Other>
797  [[nodiscard]] std::enable_if_t<is_transparent_v<hasher> && is_transparent_v<key_equal>, std::conditional_t<false, Other, bool>>
798  contains(const Other &key) const {
799  return (find(key) != cend());
800  }
801 
807  [[nodiscard]] const_local_iterator cbegin(const size_type index) const {
808  return {packed.first().begin(), sparse.first()[index]};
809  }
810 
816  [[nodiscard]] const_local_iterator begin(const size_type index) const {
817  return cbegin(index);
818  }
819 
825  [[nodiscard]] local_iterator begin(const size_type index) {
826  return {packed.first().begin(), sparse.first()[index]};
827  }
828 
834  [[nodiscard]] const_local_iterator cend([[maybe_unused]] const size_type index) const {
835  return {packed.first().begin(), (std::numeric_limits<size_type>::max)()};
836  }
837 
843  [[nodiscard]] const_local_iterator end([[maybe_unused]] const size_type index) const {
844  return cend(index);
845  }
846 
852  [[nodiscard]] local_iterator end([[maybe_unused]] const size_type index) {
853  return {packed.first().begin(), (std::numeric_limits<size_type>::max)()};
854  }
855 
860  [[nodiscard]] size_type bucket_count() const {
861  return sparse.first().size();
862  }
863 
868  [[nodiscard]] size_type max_bucket_count() const {
869  return sparse.first().max_size();
870  }
871 
877  [[nodiscard]] size_type bucket_size(const size_type index) const {
878  return static_cast<size_type>(std::distance(begin(index), end(index)));
879  }
880 
886  [[nodiscard]] size_type bucket(const key_type &key) const {
887  return key_to_bucket(key);
888  }
889 
894  [[nodiscard]] float load_factor() const {
895  return size() / static_cast<float>(bucket_count());
896  }
897 
902  [[nodiscard]] float max_load_factor() const {
903  return threshold;
904  }
905 
910  void max_load_factor(const float value) {
911  ENTT_ASSERT(value > 0.f, "Invalid load factor");
912  threshold = value;
913  rehash(0u);
914  }
915 
921  void rehash(const size_type count) {
922  auto value = (std::max)(count, minimum_capacity);
923  value = (std::max)(value, static_cast<size_type>(size() / max_load_factor()));
924 
925  if(const auto sz = next_power_of_two(value); sz != bucket_count()) {
926  sparse.first().resize(sz);
927  std::fill(sparse.first().begin(), sparse.first().end(), (std::numeric_limits<size_type>::max)());
928 
929  for(size_type pos{}, last = size(); pos < last; ++pos) {
930  const auto index = key_to_bucket(packed.first()[pos].element.first);
931  packed.first()[pos].next = std::exchange(sparse.first()[index], pos);
932  }
933  }
934  }
935 
941  void reserve(const size_type count) {
942  packed.first().reserve(count);
943  rehash(static_cast<size_type>(std::ceil(count / max_load_factor())));
944  }
945 
950  [[nodiscard]] hasher hash_function() const {
951  return sparse.second();
952  }
953 
958  [[nodiscard]] key_equal key_eq() const {
959  return packed.second();
960  }
961 
962 private:
965  float threshold;
966 };
967 
968 } // namespace entt
969 
975 namespace std {
976 
977 template<typename Key, typename Value, typename Allocator>
978 struct uses_allocator<entt::internal::dense_map_node<Key, Value>, Allocator>
979  : std::true_type {};
980 
981 } // namespace std
982 
988 #endif
second_type & second()
Returns the second element that a pair stores.
first_type & first()
Returns the first element that a pair stores.
Associative container for key-value pairs with unique keys.
Definition: dense_map.hpp:265
mapped_type & at(const key_type &key)
Accesses a given element with bounds checking.
Definition: dense_map.hpp:713
dense_map(const allocator_type &allocator)
Constructs an empty container with a given allocator.
Definition: dense_map.hpp:382
dense_map & operator=(dense_map &&)=default
Default move assignment operator.
float load_factor() const
Returns the average number of elements per bucket.
Definition: dense_map.hpp:894
const_iterator cend() const
Returns an iterator to the end.
Definition: dense_map.hpp:497
size_type erase(const key_type &key)
Removes the element associated with a given key.
Definition: dense_map.hpp:684
mapped_type & operator[](const key_type &key)
Accesses or inserts a given element.
Definition: dense_map.hpp:731
const_iterator begin() const
Returns an iterator to the beginning.
Definition: dense_map.hpp:478
dense_map(const size_type bucket_count, 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:412
const_local_iterator begin(const size_type index) const
Returns an iterator to the beginning of a given bucket.
Definition: dense_map.hpp:816
dense_map(dense_map &&other, const allocator_type &allocator)
Allocator-extended move constructor.
Definition: dense_map.hpp:440
std::size_t size_type
Unsigned integer type.
Definition: dense_map.hpp:358
void insert(It first, It last)
Inserts elements into the container, if their keys do not exist.
Definition: dense_map.hpp:567
KeyEqual key_equal
Type of function to use to compare the keys for equality.
Definition: dense_map.hpp:362
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:648
iterator end()
Returns an iterator to the end.
Definition: dense_map.hpp:507
size_type max_bucket_count() const
Returns the maximum number of buckets.
Definition: dense_map.hpp:868
iterator erase(const_iterator first, const_iterator last)
Removes the given elements from a container.
Definition: dense_map.hpp:669
local_iterator begin(const size_type index)
Returns an iterator to the beginning of a given bucket.
Definition: dense_map.hpp:825
bool contains(const key_type &key) const
Checks if the container contains an element with a given key.
Definition: dense_map.hpp:785
iterator begin()
Returns an iterator to the beginning.
Definition: dense_map.hpp:483
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:541
float max_load_factor() const
Returns the maximum average number of elements per bucket.
Definition: dense_map.hpp:902
const_iterator find(const key_type &key) const
Finds an element with a given key.
Definition: dense_map.hpp:755
internal::dense_map_iterator< typename packed_container_type::const_iterator > const_iterator
Constant input iterator type.
Definition: dense_map.hpp:368
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:589
void max_load_factor(const float value)
Sets the desired maximum average number of elements per bucket.
Definition: dense_map.hpp:910
std::pair< iterator, bool > insert(value_type &&value)
Inserts an element into the container, if the key does not exist.
Definition: dense_map.hpp:546
iterator find(const key_type &key)
Finds an element with a given key.
Definition: dense_map.hpp:750
Type mapped_type
Mapped type of the container.
Definition: dense_map.hpp:354
const_iterator cbegin() const
Returns an iterator to the beginning.
Definition: dense_map.hpp:473
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:556
iterator erase(const_iterator pos)
Removes an element from a given position.
Definition: dense_map.hpp:657
void clear()
Clears the container.
Definition: dense_map.hpp:528
dense_map(const size_type bucket_count, 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:401
dense_map(const dense_map &other, const allocator_type &allocator)
Allocator-extended copy constructor.
Definition: dense_map.hpp:427
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:583
const_local_iterator end([[maybe_unused]] const size_type index) const
Returns an iterator to the end of a given bucket.
Definition: dense_map.hpp:843
const mapped_type & at(const key_type &key) const
Accesses a given element with bounds checking.
Definition: dense_map.hpp:720
local_iterator end([[maybe_unused]] const size_type index)
Returns an iterator to the end of a given bucket.
Definition: dense_map.hpp:852
const_iterator end() const
Returns an iterator to the end.
Definition: dense_map.hpp:502
size_type bucket(const key_type &key) const
Returns the bucket for a given key.
Definition: dense_map.hpp:886
const_local_iterator cbegin(const size_type index) const
Returns an iterator to the beginning of a given bucket.
Definition: dense_map.hpp:807
dense_map & operator=(const dense_map &)=default
Default copy assignment operator.
std::pair< const Key, Type > value_type
Key-value type of the container.
Definition: dense_map.hpp:356
dense_map(const dense_map &)=default
Default copy constructor.
std::pair< iterator, bool > emplace([[maybe_unused]] Args &&...args)
Constructs an element in-place, if the key does not exist.
Definition: dense_map.hpp:607
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 value.
Definition: dense_map.hpp:769
void swap(dense_map &other)
Exchanges the contents with those of a given container.
Definition: dense_map.hpp:701
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:798
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:642
key_equal key_eq() const
Returns the function used to compare keys for equality.
Definition: dense_map.hpp:958
internal::dense_map_iterator< typename packed_container_type::iterator > iterator
Input iterator type.
Definition: dense_map.hpp:366
void rehash(const size_type count)
Reserves at least the specified number of buckets and regenerates the hash table.
Definition: dense_map.hpp:921
internal::dense_map_local_iterator< typename packed_container_type::iterator > local_iterator
Input iterator type.
Definition: dense_map.hpp:370
internal::dense_map_local_iterator< typename packed_container_type::const_iterator > const_local_iterator
Constant input iterator type.
Definition: dense_map.hpp:372
mapped_type & operator[](key_type &&key)
Accesses or inserts a given element.
Definition: dense_map.hpp:740
Allocator allocator_type
Allocator type.
Definition: dense_map.hpp:364
constexpr allocator_type get_allocator() const
Returns the associated allocator.
Definition: dense_map.hpp:461
size_type bucket_size(const size_type index) const
Returns the number of elements in a given bucket.
Definition: dense_map.hpp:877
dense_map(dense_map &&)=default
Default move constructor.
Hash hasher
Type of function to use to hash the keys.
Definition: dense_map.hpp:360
bool empty() const
Checks whether a container is empty.
Definition: dense_map.hpp:515
Key key_type
Key type of the container.
Definition: dense_map.hpp:352
size_type bucket_count() const
Returns the number of buckets.
Definition: dense_map.hpp:860
void reserve(const size_type count)
Reserves space for at least the specified number of elements and regenerates the hash table.
Definition: dense_map.hpp:941
dense_map()
Default constructor.
Definition: dense_map.hpp:375
const_local_iterator cend([[maybe_unused]] const size_type index) const
Returns an iterator to the end of a given bucket.
Definition: dense_map.hpp:834
dense_map(const size_type bucket_count, const allocator_type &allocator)
Constructs an empty container with a given allocator and user supplied minimal number of buckets.
Definition: dense_map.hpp:391
hasher hash_function() const
Returns the function used to hash the keys.
Definition: dense_map.hpp:950
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:776
size_type size() const
Returns the number of elements in a container.
Definition: dense_map.hpp:523
EnTT default namespace.
Definition: dense_map.hpp:22
constexpr bool operator==(const basic_hashed_string< Char > &lhs, const basic_hashed_string< Char > &rhs)
Compares two hashed strings.
constexpr std::size_t fast_mod(const std::size_t value, const std::size_t mod)
Fast module utility function (powers of two only).
Definition: memory.hpp:102
constexpr bool operator<=(const basic_hashed_string< Char > &lhs, const basic_hashed_string< Char > &rhs)
Compares two hashed strings.
constexpr std::size_t next_power_of_two(const std::size_t value)
Computes the smallest power of two greater than or equal to a value.
Definition: memory.hpp:85
constexpr bool operator>=(const basic_hashed_string< Char > &lhs, const basic_hashed_string< Char > &rhs)
Compares two hashed strings.
constexpr type_list< Type..., Other... > operator+(type_list< Type... >, type_list< Other... >)
Concatenates multiple type lists.
constexpr bool operator<(const basic_hashed_string< Char > &lhs, const basic_hashed_string< Char > &rhs)
Compares two hashed strings.
bool operator!=(const basic_any< Len, Align > &lhs, const basic_any< Len, Align > &rhs)
Checks if two wrappers differ in their content.
Definition: any.hpp:402
constexpr bool operator>(const basic_hashed_string< Char > &lhs, const basic_hashed_string< Char > &rhs)
Compares two hashed strings.
Helper type to use as pointer with input iterators.
Definition: iterator.hpp:16