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"
26template<
typename Key,
typename Type>
27struct dense_map_node final {
28 using value_type = std::pair<Key, Type>;
30 template<
typename... Args>
31 dense_map_node(
const std::size_t pos, Args &&...args)
33 element{std::forward<Args>(args)...} {}
35 template<
typename Allocator,
typename... Args>
36 dense_map_node(std::allocator_arg_t,
const Allocator &allocator,
const std::size_t pos, Args &&...args)
38 element{entt::make_obj_using_allocator<value_type>(allocator, std::forward<Args>(args)...)} {}
40 template<
typename Allocator>
41 dense_map_node(std::allocator_arg_t,
const Allocator &allocator,
const dense_map_node &other)
43 element{entt::make_obj_using_allocator<value_type>(allocator, other.element)} {}
45 template<
typename Allocator>
46 dense_map_node(std::allocator_arg_t,
const Allocator &allocator, dense_map_node &&other)
48 element{entt::make_obj_using_allocator<value_type>(allocator, std::move(other.element))} {}
55class dense_map_iterator final {
57 friend class dense_map_iterator;
59 using first_type =
decltype(std::as_const(std::declval<It>()->element.first));
60 using second_type =
decltype((std::declval<It>()->element.second));
63 using value_type = std::pair<first_type, second_type>;
65 using reference = value_type;
66 using difference_type = std::ptrdiff_t;
67 using iterator_category = std::input_iterator_tag;
68 using iterator_concept = std::random_access_iterator_tag;
70 constexpr dense_map_iterator() noexcept
73 constexpr dense_map_iterator(
const It iter) noexcept
76 template<
typename Other,
typename = std::enable_if_t<!std::is_same_v<It, Other> && std::is_constructible_v<It, Other>>>
77 constexpr dense_map_iterator(
const dense_map_iterator<Other> &other) noexcept
80 constexpr dense_map_iterator &operator++()
noexcept {
84 constexpr dense_map_iterator operator++(
int)
noexcept {
85 dense_map_iterator orig = *
this;
86 return ++(*this), orig;
89 constexpr dense_map_iterator &operator--()
noexcept {
93 constexpr dense_map_iterator operator--(
int)
noexcept {
94 dense_map_iterator orig = *
this;
95 return operator--(), orig;
98 constexpr dense_map_iterator &operator+=(
const difference_type value)
noexcept {
103 constexpr dense_map_iterator
operator+(
const difference_type value)
const noexcept {
104 dense_map_iterator copy = *
this;
105 return (copy += value);
108 constexpr dense_map_iterator &operator-=(
const difference_type value)
noexcept {
109 return (*
this += -value);
112 constexpr dense_map_iterator operator-(
const difference_type value)
const noexcept {
113 return (*
this + -value);
116 [[nodiscard]]
constexpr reference operator[](
const difference_type value)
const noexcept {
117 return {it[value].element.first, it[value].element.second};
120 [[nodiscard]]
constexpr pointer operator->()
const noexcept {
124 [[nodiscard]]
constexpr reference operator*()
const noexcept {
125 return {it->element.first, it->element.second};
128 template<
typename Lhs,
typename Rhs>
129 friend constexpr std::ptrdiff_t operator-(
const dense_map_iterator<Lhs> &,
const dense_map_iterator<Rhs> &)
noexcept;
131 template<
typename Lhs,
typename Rhs>
132 friend constexpr bool 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;
141template<
typename Lhs,
typename Rhs>
142[[nodiscard]]
constexpr std::ptrdiff_t operator-(
const dense_map_iterator<Lhs> &lhs,
const dense_map_iterator<Rhs> &rhs)
noexcept {
143 return lhs.it - rhs.it;
146template<
typename Lhs,
typename Rhs>
147[[nodiscard]]
constexpr bool operator==(
const dense_map_iterator<Lhs> &lhs,
const dense_map_iterator<Rhs> &rhs)
noexcept {
148 return lhs.it == rhs.it;
151template<
typename Lhs,
typename Rhs>
152[[nodiscard]]
constexpr bool operator!=(
const dense_map_iterator<Lhs> &lhs,
const dense_map_iterator<Rhs> &rhs)
noexcept {
153 return !(lhs == rhs);
156template<
typename Lhs,
typename Rhs>
157[[nodiscard]]
constexpr bool operator<(
const dense_map_iterator<Lhs> &lhs,
const dense_map_iterator<Rhs> &rhs)
noexcept {
158 return lhs.it < rhs.it;
161template<
typename Lhs,
typename Rhs>
162[[nodiscard]]
constexpr bool operator>(
const dense_map_iterator<Lhs> &lhs,
const dense_map_iterator<Rhs> &rhs)
noexcept {
166template<
typename Lhs,
typename Rhs>
167[[nodiscard]]
constexpr bool operator<=(
const dense_map_iterator<Lhs> &lhs,
const dense_map_iterator<Rhs> &rhs)
noexcept {
171template<
typename Lhs,
typename Rhs>
172[[nodiscard]]
constexpr bool operator>=(
const dense_map_iterator<Lhs> &lhs,
const dense_map_iterator<Rhs> &rhs)
noexcept {
177class dense_map_local_iterator final {
179 friend class dense_map_local_iterator;
181 using first_type =
decltype(std::as_const(std::declval<It>()->element.first));
182 using second_type =
decltype((std::declval<It>()->element.second));
185 using value_type = std::pair<first_type, second_type>;
187 using reference = value_type;
188 using difference_type = std::ptrdiff_t;
189 using iterator_category = std::input_iterator_tag;
190 using iterator_concept = std::forward_iterator_tag;
192 constexpr dense_map_local_iterator() noexcept
196 constexpr dense_map_local_iterator(It iter,
const std::size_t pos) noexcept
200 template<
typename Other,
typename = std::enable_if_t<!std::is_same_v<It, Other> && std::is_constructible_v<It, Other>>>
201 constexpr dense_map_local_iterator(
const dense_map_local_iterator<Other> &other) noexcept
203 offset{other.offset} {}
205 constexpr dense_map_local_iterator &operator++()
noexcept {
206 return offset = it[offset].next, *
this;
209 constexpr dense_map_local_iterator operator++(
int)
noexcept {
210 dense_map_local_iterator orig = *
this;
211 return ++(*this), orig;
214 [[nodiscard]]
constexpr pointer operator->()
const noexcept {
218 [[nodiscard]]
constexpr reference operator*()
const noexcept {
219 return {it[offset].element.first, it[offset].element.second};
222 [[nodiscard]]
constexpr std::size_t index()
const noexcept {
231template<
typename Lhs,
typename Rhs>
232[[nodiscard]]
constexpr bool operator==(
const dense_map_local_iterator<Lhs> &lhs,
const dense_map_local_iterator<Rhs> &rhs)
noexcept {
233 return lhs.index() == rhs.index();
236template<
typename Lhs,
typename Rhs>
237[[nodiscard]]
constexpr bool operator!=(
const dense_map_local_iterator<Lhs> &lhs,
const dense_map_local_iterator<Rhs> &rhs)
noexcept {
238 return !(lhs == rhs);
257template<
typename Key,
typename Type,
typename Hash,
typename KeyEqual,
typename Allocator>
259 static constexpr float default_threshold = 0.875f;
260 static constexpr std::size_t minimum_capacity = 8u;
262 using node_type = internal::dense_map_node<Key, Type>;
263 using alloc_traits = std::allocator_traits<Allocator>;
264 static_assert(std::is_same_v<typename alloc_traits::value_type, std::pair<const Key, Type>>,
"Invalid value type");
265 using sparse_container_type = std::vector<std::size_t, typename alloc_traits::template rebind_alloc<std::size_t>>;
266 using packed_container_type = std::vector<node_type, typename alloc_traits::template rebind_alloc<node_type>>;
268 template<
typename Other>
269 [[nodiscard]] std::size_t key_to_bucket(
const Other &key)
const noexcept {
273 template<
typename Other>
274 [[nodiscard]]
auto constrained_find(
const Other &key, std::size_t
bucket) {
276 if(packed.
second()(it->first, key)) {
277 return begin() +
static_cast<typename iterator::difference_type
>(it.index());
284 template<
typename Other>
285 [[nodiscard]]
auto constrained_find(
const Other &key, std::size_t
bucket)
const {
287 if(packed.
second()(it->first, key)) {
288 return cbegin() +
static_cast<typename iterator::difference_type
>(it.index());
295 template<
typename Other,
typename... Args>
296 [[nodiscard]]
auto insert_or_do_nothing(Other &&key, Args &&...args) {
297 const auto index = key_to_bucket(key);
299 if(
auto it = constrained_find(key, index); it !=
end()) {
300 return std::make_pair(it,
false);
303 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)...));
304 sparse.
first()[index] = packed.
first().size() - 1u;
305 rehash_if_required();
307 return std::make_pair(--
end(),
true);
310 template<
typename Other,
typename Arg>
311 [[nodiscard]]
auto insert_or_overwrite(Other &&key, Arg &&value) {
312 const auto index = key_to_bucket(key);
314 if(
auto it = constrained_find(key, index); it !=
end()) {
315 it->second = std::forward<Arg>(value);
316 return std::make_pair(it,
false);
319 packed.
first().emplace_back(sparse.
first()[index], std::forward<Other>(key), std::forward<Arg>(value));
320 sparse.
first()[index] = packed.
first().size() - 1u;
321 rehash_if_required();
323 return std::make_pair(--
end(),
true);
326 void move_and_pop(
const std::size_t pos) {
327 if(
const auto last =
size() - 1u; pos != last) {
328 size_type *curr = sparse.
first().data() + key_to_bucket(packed.
first().back().element.first);
329 packed.
first()[pos] = std::move(packed.
first().back());
330 for(; *curr != last; curr = &packed.
first()[*curr].next) {}
334 packed.
first().pop_back();
337 void rehash_if_required() {
359 using iterator = internal::dense_map_iterator<typename packed_container_type::iterator>;
361 using const_iterator = internal::dense_map_iterator<typename packed_container_type::const_iterator>;
363 using local_iterator = internal::dense_map_local_iterator<typename packed_container_type::iterator>;
365 using const_local_iterator = internal::dense_map_local_iterator<typename packed_container_type::const_iterator>;
406 : sparse{allocator, hash},
407 packed{allocator, equal},
408 threshold{default_threshold} {
421 : sparse{std::piecewise_construct, std::forward_as_tuple(other.sparse.first(), allocator), std::forward_as_tuple(other.sparse.second())},
422 packed{std::piecewise_construct, std::forward_as_tuple(other.packed.first(), allocator), std::forward_as_tuple(other.packed.second())},
423 threshold{other.threshold} {}
434 : sparse{std::piecewise_construct, std::forward_as_tuple(std::move(other.sparse.first()), allocator), std::forward_as_tuple(std::move(other.sparse.second()))},
435 packed{std::piecewise_construct, std::forward_as_tuple(std::move(other.packed.first()), allocator), std::forward_as_tuple(std::move(other.packed.second()))},
436 threshold{other.threshold} {}
455 return sparse.
first().get_allocator();
466 return packed.
first().begin();
476 return packed.
first().begin();
485 return packed.
first().end();
495 return packed.
first().end();
502 [[nodiscard]]
bool empty() const noexcept {
503 return packed.
first().empty();
511 return packed.
first().size();
519 return packed.
first().max_size();
524 sparse.
first().clear();
525 packed.
first().clear();
537 return insert_or_do_nothing(value.first, value.second);
542 return insert_or_do_nothing(std::move(value.first), std::move(value.second));
549 template<
typename Arg>
550 std::enable_if_t<std::is_constructible_v<value_type, Arg &&>, std::pair<iterator, bool>>
552 return insert_or_do_nothing(std::forward<Arg>(value).first, std::forward<Arg>(value).second);
561 template<
typename It>
563 for(; first != last; ++first) {
577 template<
typename Arg>
579 return insert_or_overwrite(key, std::forward<Arg>(value));
583 template<
typename Arg>
585 return insert_or_overwrite(std::move(key), std::forward<Arg>(value));
601 template<
typename... Args>
602 std::pair<iterator, bool>
emplace([[maybe_unused]] Args &&...args) {
603 if constexpr(
sizeof...(Args) == 0u) {
604 return insert_or_do_nothing(
key_type{});
605 }
else if constexpr(
sizeof...(Args) == 1u) {
606 return insert_or_do_nothing(std::forward<Args>(args).first..., std::forward<Args>(args).second...);
607 }
else if constexpr(
sizeof...(Args) == 2u) {
608 return insert_or_do_nothing(std::forward<Args>(args)...);
610 auto &node = packed.
first().emplace_back(packed.
first().size(), std::forward<Args>(args)...);
611 const auto index = key_to_bucket(node.element.first);
613 if(
auto it = constrained_find(node.element.first, index); it !=
end()) {
614 packed.
first().pop_back();
615 return std::make_pair(it,
false);
618 std::swap(node.next, sparse.
first()[index]);
619 rehash_if_required();
621 return std::make_pair(--
end(),
true);
636 template<
typename... Args>
638 return insert_or_do_nothing(key, std::forward<Args>(args)...);
642 template<
typename... Args>
644 return insert_or_do_nothing(std::move(key), std::forward<Args>(args)...);
653 const auto diff = pos -
cbegin();
655 return begin() + diff;
665 const auto dist = first -
cbegin();
667 for(
auto from = last -
cbegin(); from != dist; --from) {
668 erase(packed.
first()[from - 1u].element.first);
671 return (
begin() + dist);
680 for(
size_type *curr = sparse.
first().data() + key_to_bucket(key); *curr != (std::numeric_limits<size_type>::max)(); curr = &packed.
first()[*curr].next) {
681 if(packed.
second()(packed.
first()[*curr].element.first, key)) {
682 const auto index = *curr;
683 *curr = packed.
first()[*curr].next;
698 swap(sparse, other.sparse);
699 swap(packed, other.packed);
700 swap(threshold, other.threshold);
710 ENTT_ASSERT(it !=
end(),
"Invalid key");
717 ENTT_ASSERT(it !=
cend(),
"Invalid key");
727 return insert_or_do_nothing(key).first->second;
736 return insert_or_do_nothing(std::move(key)).first->second;
754 template<
typename Other>
755 [[nodiscard]] std::enable_if_t<is_transparent_v<hasher> && is_transparent_v<key_equal>, std::conditional_t<false, Other, size_type>>
767 return constrained_find(key, key_to_bucket(key));
772 return constrained_find(key, key_to_bucket(key));
783 template<
typename Other>
784 [[nodiscard]] std::enable_if_t<is_transparent_v<hasher> && is_transparent_v<key_equal>, std::conditional_t<false, Other, iterator>>
786 return constrained_find(key, key_to_bucket(key));
790 template<
typename Other>
791 [[nodiscard]] std::enable_if_t<is_transparent_v<hasher> && is_transparent_v<key_equal>, std::conditional_t<false, Other, const_iterator>>
793 return constrained_find(key, key_to_bucket(key));
803 const auto it =
find(key);
804 return {it, it + !(it ==
end())};
809 const auto it =
find(key);
810 return {it, it + !(it ==
cend())};
821 template<
typename Other>
822 [[nodiscard]] std::enable_if_t<is_transparent_v<hasher> && is_transparent_v<key_equal>, std::conditional_t<false, Other, std::pair<iterator, iterator>>>
824 const auto it =
find(key);
825 return {it, it + !(it ==
end())};
829 template<
typename Other>
830 [[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>>>
832 const auto it =
find(key);
833 return {it, it + !(it ==
cend())};
852 template<
typename Other>
853 [[nodiscard]] std::enable_if_t<is_transparent_v<hasher> && is_transparent_v<key_equal>, std::conditional_t<false, Other, bool>>
864 return {packed.
first().begin(), sparse.
first()[index]};
882 return {packed.
first().begin(), sparse.
first()[index]};
891 return {packed.
first().begin(), (std::numeric_limits<size_type>::max)()};
909 return {packed.
first().begin(), (std::numeric_limits<size_type>::max)()};
917 return sparse.
first().size();
925 return sparse.
first().max_size();
943 return key_to_bucket(key);
967 ENTT_ASSERT(value > 0.f,
"Invalid load factor");
978 auto value = cnt > minimum_capacity ? cnt : minimum_capacity;
980 value = value > cap ? value : cap;
983 sparse.
first().resize(sz);
985 for(
auto &&elem: sparse.
first()) {
986 elem = (std::numeric_limits<size_type>::max)();
990 const auto index = key_to_bucket(packed.
first()[pos].element.first);
991 packed.
first()[pos].next = std::exchange(sparse.
first()[index], pos);
1002 packed.
first().reserve(cnt);
1033template<
typename Key,
typename Value,
typename Allocator>
1034struct uses_allocator<
entt::internal::dense_map_node<Key, Value>, Allocator>
1035 : 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 (waiting for C++20 and std::bit_c...
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.