1#ifndef ENTT_CONTAINER_DENSE_MAP_HPP
2#define ENTT_CONTAINER_DENSE_MAP_HPP
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"
30template<
typename Key,
typename Type>
31struct dense_map_node final {
32 using value_type = std::pair<Key, Type>;
34 template<
typename... Args>
35 dense_map_node(
const std::size_t pos, Args &&...args)
37 element{std::forward<Args>(args)...} {}
39 template<
typename Allocator,
typename... Args>
40 dense_map_node(std::allocator_arg_t,
const Allocator &allocator,
const std::size_t pos, Args &&...args)
42 element{entt::make_obj_using_allocator<value_type>(allocator, std::forward<Args>(args)...)} {}
44 template<
typename Allocator>
45 dense_map_node(std::allocator_arg_t,
const Allocator &allocator,
const dense_map_node &other)
47 element{entt::make_obj_using_allocator<value_type>(allocator, other.element)} {}
49 template<
typename Allocator>
50 dense_map_node(std::allocator_arg_t,
const Allocator &allocator, dense_map_node &&other)
52 element{entt::make_obj_using_allocator<value_type>(allocator, std::move(other.element))} {}
59class dense_map_iterator final {
61 friend class dense_map_iterator;
63 using first_type =
decltype(std::as_const(std::declval<It>()->element.first));
64 using second_type =
decltype((std::declval<It>()->element.second));
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;
73 constexpr dense_map_iterator() noexcept
76 constexpr dense_map_iterator(
const It iter) noexcept
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
83 constexpr dense_map_iterator &operator++()
noexcept {
87 constexpr dense_map_iterator operator++(
int)
noexcept {
88 dense_map_iterator orig = *
this;
89 return ++(*this), orig;
92 constexpr dense_map_iterator &operator--()
noexcept {
96 constexpr dense_map_iterator operator--(
int)
noexcept {
97 dense_map_iterator orig = *
this;
98 return operator--(), orig;
101 constexpr dense_map_iterator &operator+=(
const difference_type value)
noexcept {
106 constexpr dense_map_iterator
operator+(
const difference_type value)
const noexcept {
107 dense_map_iterator copy = *
this;
108 return (copy += value);
111 constexpr dense_map_iterator &operator-=(
const difference_type value)
noexcept {
112 return (*
this += -value);
115 constexpr dense_map_iterator operator-(
const difference_type value)
const noexcept {
116 return (*
this + -value);
119 [[nodiscard]]
constexpr reference operator[](
const difference_type value)
const noexcept {
120 return {it[value].element.first, it[value].element.second};
123 [[nodiscard]]
constexpr pointer operator->()
const noexcept {
127 [[nodiscard]]
constexpr reference operator*()
const noexcept {
128 return {it->element.first, it->element.second};
131 template<
typename Lhs,
typename Rhs>
132 friend constexpr std::ptrdiff_t operator-(
const dense_map_iterator<Lhs> &,
const dense_map_iterator<Rhs> &)
noexcept;
134 template<
typename Lhs,
typename Rhs>
135 friend constexpr bool operator==(
const dense_map_iterator<Lhs> &,
const dense_map_iterator<Rhs> &)
noexcept;
137 template<
typename Lhs,
typename Rhs>
138 friend constexpr bool operator<(
const dense_map_iterator<Lhs> &,
const dense_map_iterator<Rhs> &)
noexcept;
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;
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;
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);
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;
164template<
typename Lhs,
typename Rhs>
165[[nodiscard]]
constexpr bool operator>(
const dense_map_iterator<Lhs> &lhs,
const dense_map_iterator<Rhs> &rhs)
noexcept {
169template<
typename Lhs,
typename Rhs>
170[[nodiscard]]
constexpr bool operator<=(
const dense_map_iterator<Lhs> &lhs,
const dense_map_iterator<Rhs> &rhs)
noexcept {
174template<
typename Lhs,
typename Rhs>
175[[nodiscard]]
constexpr bool operator>=(
const dense_map_iterator<Lhs> &lhs,
const dense_map_iterator<Rhs> &rhs)
noexcept {
180class dense_map_local_iterator final {
182 friend class dense_map_local_iterator;
184 using first_type =
decltype(std::as_const(std::declval<It>()->element.first));
185 using second_type =
decltype((std::declval<It>()->element.second));
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;
194 constexpr dense_map_local_iterator() noexcept
198 constexpr dense_map_local_iterator(It iter,
const std::size_t pos) noexcept
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
205 offset{other.offset} {}
207 constexpr dense_map_local_iterator &operator++()
noexcept {
208 return offset = it[offset].next, *
this;
211 constexpr dense_map_local_iterator operator++(
int)
noexcept {
212 dense_map_local_iterator orig = *
this;
213 return ++(*this), orig;
216 [[nodiscard]]
constexpr pointer operator->()
const noexcept {
220 [[nodiscard]]
constexpr reference operator*()
const noexcept {
221 return {it[offset].element.first, it[offset].element.second};
224 [[nodiscard]]
constexpr std::size_t index()
const noexcept {
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();
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);
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;
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>>;
274 template<
typename Other>
275 [[nodiscard]] std::size_t key_to_bucket(
const Other &key)
const noexcept {
279 template<
typename Other>
280 [[nodiscard]]
auto constrained_find(
const Other &key, std::size_t
bucket) {
282 if(packed.
second()(it->first, key)) {
283 return begin() +
static_cast<typename iterator::difference_type
>(it.index());
290 template<
typename Other>
291 [[nodiscard]]
auto constrained_find(
const Other &key, std::size_t
bucket)
const {
293 if(packed.
second()(it->first, key)) {
294 return cbegin() +
static_cast<typename iterator::difference_type
>(it.index());
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);
305 if(
auto it = constrained_find(key, index); it !=
end()) {
306 return std::make_pair(it,
false);
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();
313 return std::make_pair(--
end(),
true);
316 template<
typename Other,
typename Arg>
317 [[nodiscard]]
auto insert_or_overwrite(Other &&key, Arg &&value) {
318 const auto index = key_to_bucket(key);
320 if(
auto it = constrained_find(key, index); it !=
end()) {
321 it->second = std::forward<Arg>(value);
322 return std::make_pair(it,
false);
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();
329 return std::make_pair(--
end(),
true);
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) {}
340 packed.
first().pop_back();
343 void rehash_if_required() {
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>;
412 : sparse{allocator, hash},
413 packed{allocator, equal},
414 threshold{default_threshold} {
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} {}
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} {}
461 return sparse.
first().get_allocator();
472 return packed.
first().begin();
482 return packed.
first().begin();
491 return packed.
first().end();
501 return packed.
first().end();
508 [[nodiscard]]
bool empty() const noexcept {
509 return packed.
first().empty();
517 return packed.
first().size();
525 return packed.
first().max_size();
530 sparse.
first().clear();
531 packed.
first().clear();
543 return insert_or_do_nothing(value.first, value.second);
548 return insert_or_do_nothing(std::move(value.first), std::move(value.second));
555 template<
typename Arg>
556 std::enable_if_t<std::is_constructible_v<value_type, Arg &&>, std::pair<iterator, bool>>
558 return insert_or_do_nothing(std::forward<Arg>(value).first, std::forward<Arg>(value).second);
567 template<
typename It>
569 for(; first != last; ++first) {
583 template<
typename Arg>
585 return insert_or_overwrite(key, std::forward<Arg>(value));
589 template<
typename Arg>
591 return insert_or_overwrite(std::move(key), std::forward<Arg>(value));
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)...);
616 auto &node = packed.
first().emplace_back(packed.
first().size(), std::forward<Args>(args)...);
617 const auto index = key_to_bucket(node.element.first);
619 if(
auto it = constrained_find(node.element.first, index); it !=
end()) {
620 packed.
first().pop_back();
621 return std::make_pair(it,
false);
624 std::swap(node.next, sparse.
first()[index]);
625 rehash_if_required();
627 return std::make_pair(--
end(),
true);
642 template<
typename... Args>
644 return insert_or_do_nothing(key, std::forward<Args>(args)...);
648 template<
typename... Args>
650 return insert_or_do_nothing(std::move(key), std::forward<Args>(args)...);
659 const auto diff = pos -
cbegin();
661 return begin() + diff;
671 const auto dist = first -
cbegin();
673 for(
auto from = last -
cbegin(); from != dist; --from) {
674 erase(packed.
first()[from - 1u].element.first);
677 return (
begin() + dist);
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;
704 swap(sparse, other.sparse);
705 swap(packed, other.packed);
706 swap(threshold, other.threshold);
716 ENTT_ASSERT(it !=
end(),
"Invalid key");
723 ENTT_ASSERT(it !=
cend(),
"Invalid key");
733 return insert_or_do_nothing(key).first->second;
742 return insert_or_do_nothing(std::move(key)).first->second;
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>>
773 return constrained_find(key, key_to_bucket(key));
778 return constrained_find(key, key_to_bucket(key));
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>>
792 return constrained_find(key, key_to_bucket(key));
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>>
799 return constrained_find(key, key_to_bucket(key));
809 const auto it =
find(key);
810 return {it, it + !(it ==
end())};
815 const auto it =
find(key);
816 return {it, it + !(it ==
cend())};
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>>>
830 const auto it =
find(key);
831 return {it, it + !(it ==
end())};
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>>>
838 const auto it =
find(key);
839 return {it, it + !(it ==
cend())};
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>>
870 return {packed.
first().begin(), sparse.
first()[index]};
888 return {packed.
first().begin(), sparse.
first()[index]};
897 return {packed.
first().begin(), (std::numeric_limits<size_type>::max)()};
915 return {packed.
first().begin(), (std::numeric_limits<size_type>::max)()};
923 return sparse.
first().size();
931 return sparse.
first().max_size();
949 return key_to_bucket(key);
973 ENTT_ASSERT(value > 0.f,
"Invalid load factor");
984 auto value = cnt > minimum_capacity ? cnt : minimum_capacity;
986 value = value > cap ? value : cap;
989 sparse.
first().resize(sz);
991 for(
auto &&elem: sparse.
first()) {
992 elem = std::numeric_limits<size_type>::max();
996 const auto index = key_to_bucket(packed.
first()[pos].element.first);
997 packed.
first()[pos].next = std::exchange(sparse.
first()[index], pos);
1008 packed.
first().reserve(cnt);
1043template<
typename Key,
typename Value,
typename Allocator>
1044struct uses_allocator<
entt::internal::dense_map_node<Key, Value>, Allocator>
1045 : std::true_type {};
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.
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...
dense_map(const allocator_type &allocator)
Constructs an empty container with a given allocator.
void clear() noexcept
Clears the container.
float load_factor() const
Returns the average number of elements per bucket.
size_type erase(const key_type &key)
Removes the element associated with a given key.
mapped_type & operator[](key_type &&key)
Accesses or inserts a given element.
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.
const_iterator cbegin() const noexcept
Returns an iterator to the beginning.
const_local_iterator begin(const size_type index) const
Returns an iterator to the beginning of a given bucket.
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).
size_type size() const noexcept
Returns the number of elements in a container.
std::size_t size_type
Unsigned integer type.
const_local_iterator end(const size_type index) const
Returns an iterator to the end of a given bucket.
void insert(It first, It last)
Inserts elements into the container, if their keys do not exist.
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.
const mapped_type & at(const key_type &key) const
Accesses a given element with bounds checking.
KeyEqual key_equal
Type of function to use to compare the keys for equality.
size_type max_size() const noexcept
Returns the maximum possible number of elements.
mapped_type & at(const key_type &key)
Accesses a given element with bounds checking.
void reserve(const size_type cnt)
Reserves space for at least the specified number of elements and regenerates the hash table.
size_type max_bucket_count() const
Returns the maximum number of buckets.
iterator erase(const_iterator first, const_iterator last)
Removes the given elements from a container.
size_type count(const key_type &key) const
Returns the number of elements matching a key (either 1 or 0).
local_iterator begin(const size_type index)
Returns an iterator to the beginning of a given bucket.
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.
bool contains(const key_type &key) const
Checks if the container contains an element with a given key.
const_iterator cend() const noexcept
Returns an iterator to the end.
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.
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.
float max_load_factor() const
Returns the maximum average number of elements per bucket.
const_iterator find(const key_type &key) const
Finds an element with a given key.
internal::dense_map_iterator< typename packed_container_type::const_iterator > const_iterator
Constant input iterator type.
void max_load_factor(const float value)
Sets the desired maximum average number of elements per bucket.
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.
iterator find(const key_type &key)
Finds an element with a given key.
std::pair< iterator, iterator > equal_range(const key_type &key)
Returns a range containing all elements with a given key.
const_iterator begin() const noexcept
Returns an iterator to the beginning.
Type mapped_type
Mapped type of the container.
void rehash(const size_type cnt)
Reserves at least the specified number of buckets and regenerates the hash table.
const_local_iterator cend(const size_type index) const
Returns an iterator to the end of a given bucket.
iterator erase(const_iterator pos)
Removes an element from a given position.
dense_map(const dense_map &other, const allocator_type &allocator)
Allocator-extended copy constructor.
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.
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.
size_type bucket(const key_type &key) const
Returns the bucket for a given key.
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.
mapped_type & operator[](const key_type &key)
Accesses or inserts a given element.
constexpr allocator_type get_allocator() const noexcept
Returns the associated allocator.
const_local_iterator cbegin(const size_type index) const
Returns an iterator to the beginning of a given bucket.
std::pair< const Key, Type > value_type
Key-value type of the container.
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.
std::pair< iterator, bool > emplace(Args &&...args)
Constructs an element in-place, if the key does not exist.
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.
void swap(dense_map &other)
Exchanges the contents with those of a given container.
local_iterator end(const size_type index)
Returns an iterator to the end of a given bucket.
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.
key_equal key_eq() const
Returns the function used to compare keys for equality.
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 ...
internal::dense_map_iterator< typename packed_container_type::iterator > iterator
Input iterator type.
internal::dense_map_local_iterator< typename packed_container_type::iterator > local_iterator
Input iterator type.
internal::dense_map_local_iterator< typename packed_container_type::const_iterator > const_local_iterator
Constant input iterator type.
bool empty() const noexcept
Checks whether a container is empty.
std::pair< iterator, bool > insert(const value_type &value)
Inserts an element into the container, if the key does not exist.
Allocator allocator_type
Allocator type.
size_type bucket_size(const size_type index) const
Returns the number of elements in a given bucket.
Hash hasher
Type of function to use to hash the keys.
Key key_type
Key type of the container.
size_type bucket_count() const
Returns the number of buckets.
dense_map()
Default constructor.
std::pair< const_iterator, const_iterator > equal_range(const key_type &key) const
Returns a range containing all elements with a given key.
hasher hash_function() const
Returns the function used to hash the keys.
const_iterator end() const noexcept
Returns an iterator to the end.
iterator begin() noexcept
Returns an iterator to the beginning.
iterator end() noexcept
Returns an iterator to the end.
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.
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).
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.
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.