1#ifndef ENTT_CONTAINER_DENSE_SET_HPP
2#define ENTT_CONTAINER_DENSE_SET_HPP
14#include "../config/config.h"
15#include "../core/bit.hpp"
16#include "../core/compressed_pair.hpp"
17#include "../core/type_traits.hpp"
26class dense_set_iterator final {
28 friend class dense_set_iterator;
31 using value_type =
typename It::value_type::second_type;
32 using pointer =
const value_type *;
33 using reference =
const value_type &;
34 using difference_type = std::ptrdiff_t;
35 using iterator_category = std::random_access_iterator_tag;
37 constexpr dense_set_iterator() noexcept
40 constexpr dense_set_iterator(
const It iter) noexcept
43 template<
typename Other,
typename = std::enable_if_t<!std::is_same_v<It, Other> && std::is_constructible_v<It, Other>>>
44 constexpr dense_set_iterator(
const dense_set_iterator<Other> &other) noexcept
47 constexpr dense_set_iterator &operator++() noexcept {
51 constexpr dense_set_iterator operator++(
int)
noexcept {
52 const dense_set_iterator orig = *
this;
53 return ++(*this), orig;
56 constexpr dense_set_iterator &operator--() noexcept {
60 constexpr dense_set_iterator operator--(
int)
noexcept {
61 const dense_set_iterator orig = *
this;
62 return operator--(), orig;
65 constexpr dense_set_iterator &operator+=(
const difference_type value)
noexcept {
70 constexpr dense_set_iterator
operator+(
const difference_type value)
const noexcept {
71 dense_set_iterator copy = *
this;
72 return (copy += value);
75 constexpr dense_set_iterator &operator-=(
const difference_type value)
noexcept {
76 return (*
this += -value);
79 constexpr dense_set_iterator operator-(
const difference_type value)
const noexcept {
80 return (*
this + -value);
83 [[nodiscard]]
constexpr reference operator[](
const difference_type value)
const noexcept {
84 return it[value].second;
87 [[nodiscard]]
constexpr pointer operator->() const noexcept {
88 return std::addressof(
operator[](0));
91 [[nodiscard]]
constexpr reference operator*() const noexcept {
95 template<
typename Lhs,
typename Rhs>
96 friend constexpr std::ptrdiff_t operator-(
const dense_set_iterator<Lhs> &,
const dense_set_iterator<Rhs> &)
noexcept;
98 template<
typename Lhs,
typename Rhs>
99 friend constexpr bool operator==(
const dense_set_iterator<Lhs> &,
const dense_set_iterator<Rhs> &)
noexcept;
101 template<
typename Lhs,
typename Rhs>
102 friend constexpr bool operator<(
const dense_set_iterator<Lhs> &,
const dense_set_iterator<Rhs> &)
noexcept;
108template<
typename Lhs,
typename Rhs>
109[[nodiscard]]
constexpr std::ptrdiff_t operator-(
const dense_set_iterator<Lhs> &lhs,
const dense_set_iterator<Rhs> &rhs)
noexcept {
110 return lhs.it - rhs.it;
113template<
typename Lhs,
typename Rhs>
114[[nodiscard]]
constexpr bool operator==(
const dense_set_iterator<Lhs> &lhs,
const dense_set_iterator<Rhs> &rhs)
noexcept {
115 return lhs.it == rhs.it;
118template<
typename Lhs,
typename Rhs>
119[[nodiscard]]
constexpr bool operator!=(
const dense_set_iterator<Lhs> &lhs,
const dense_set_iterator<Rhs> &rhs)
noexcept {
120 return !(lhs == rhs);
123template<
typename Lhs,
typename Rhs>
124[[nodiscard]]
constexpr bool operator<(
const dense_set_iterator<Lhs> &lhs,
const dense_set_iterator<Rhs> &rhs)
noexcept {
125 return lhs.it < rhs.it;
128template<
typename Lhs,
typename Rhs>
129[[nodiscard]]
constexpr bool operator>(
const dense_set_iterator<Lhs> &lhs,
const dense_set_iterator<Rhs> &rhs)
noexcept {
133template<
typename Lhs,
typename Rhs>
134[[nodiscard]]
constexpr bool operator<=(
const dense_set_iterator<Lhs> &lhs,
const dense_set_iterator<Rhs> &rhs)
noexcept {
138template<
typename Lhs,
typename Rhs>
139[[nodiscard]]
constexpr bool operator>=(
const dense_set_iterator<Lhs> &lhs,
const dense_set_iterator<Rhs> &rhs)
noexcept {
144class dense_set_local_iterator final {
146 friend class dense_set_local_iterator;
149 using value_type =
typename It::value_type::second_type;
150 using pointer =
const value_type *;
151 using reference =
const value_type &;
152 using difference_type = std::ptrdiff_t;
153 using iterator_category = std::forward_iterator_tag;
155 constexpr dense_set_local_iterator() noexcept
159 constexpr dense_set_local_iterator(It iter,
const std::size_t pos) noexcept
163 template<
typename Other,
typename = std::enable_if_t<!std::is_same_v<It, Other> && std::is_constructible_v<It, Other>>>
164 constexpr dense_set_local_iterator(
const dense_set_local_iterator<Other> &other) noexcept
166 offset{other.offset} {}
168 constexpr dense_set_local_iterator &operator++() noexcept {
169 return offset = it[
static_cast<typename It::difference_type
>(offset)].first, *
this;
172 constexpr dense_set_local_iterator operator++(
int)
noexcept {
173 const dense_set_local_iterator orig = *
this;
174 return ++(*this), orig;
177 [[nodiscard]]
constexpr pointer operator->() const noexcept {
178 return std::addressof(it[
static_cast<typename It::difference_type
>(offset)].second);
181 [[nodiscard]]
constexpr reference operator*() const noexcept {
182 return *operator->();
185 [[nodiscard]]
constexpr std::size_t index() const noexcept {
194template<
typename Lhs,
typename Rhs>
195[[nodiscard]]
constexpr bool operator==(
const dense_set_local_iterator<Lhs> &lhs,
const dense_set_local_iterator<Rhs> &rhs)
noexcept {
196 return lhs.index() == rhs.index();
199template<
typename Lhs,
typename Rhs>
200[[nodiscard]]
constexpr bool operator!=(
const dense_set_local_iterator<Lhs> &lhs,
const dense_set_local_iterator<Rhs> &rhs)
noexcept {
201 return !(lhs == rhs);
219template<
typename Type,
typename Hash,
typename KeyEqual,
typename Allocator>
221 static constexpr float default_threshold = 0.875f;
222 static constexpr std::size_t minimum_capacity = 8u;
224 using node_type = std::pair<std::size_t, Type>;
225 using alloc_traits = std::allocator_traits<Allocator>;
226 static_assert(std::is_same_v<typename alloc_traits::value_type, Type>,
"Invalid value type");
227 using sparse_container_type = std::vector<std::size_t, typename alloc_traits::template rebind_alloc<std::size_t>>;
228 using packed_container_type = std::vector<node_type, typename alloc_traits::template rebind_alloc<node_type>>;
230 template<
typename Other>
231 [[nodiscard]] std::size_t value_to_bucket(
const Other &value)
const noexcept {
235 template<
typename Other>
236 [[nodiscard]]
auto constrained_find(
const Other &value, std::size_t
bucket) {
238 if(packed.second()(*it, value)) {
246 template<
typename Other>
247 [[nodiscard]]
auto constrained_find(
const Other &value, std::size_t
bucket)
const {
249 if(packed.second()(*it, value)) {
257 template<
typename Other>
258 [[nodiscard]]
auto insert_or_do_nothing(Other &&value) {
259 const auto index = value_to_bucket(value);
261 if(
auto it = constrained_find(value, index); it !=
end()) {
262 return std::make_pair(it,
false);
265 packed.first().emplace_back(sparse.first()[index], std::forward<Other>(value));
266 sparse.first()[index] = packed.first().size() - 1u;
267 rehash_if_required();
269 return std::make_pair(--
end(),
true);
272 void move_and_pop(
const std::size_t pos) {
273 if(
const auto last =
size() - 1u; pos != last) {
274 size_type *curr = &sparse.first()[value_to_bucket(packed.first().back().second)];
275 packed.first()[pos] = std::move(packed.first().back());
276 for(; *curr != last; curr = &packed.first()[*curr].first) {}
280 packed.first().pop_back();
283 void rehash_if_required() {
305 using iterator = internal::dense_set_iterator<typename packed_container_type::iterator>;
307 using const_iterator = internal::dense_set_iterator<typename packed_container_type::const_iterator>;
313 using local_iterator = internal::dense_set_local_iterator<typename packed_container_type::iterator>;
315 using const_local_iterator = internal::dense_set_local_iterator<typename packed_container_type::const_iterator>;
356 : sparse{allocator, hash},
357 packed{allocator, equal} {
370 : sparse{std::piecewise_construct, std::forward_as_tuple(other.sparse.first(), allocator), std::forward_as_tuple(other.sparse.second())},
371 packed{std::piecewise_construct, std::forward_as_tuple(other.packed.first(), allocator), std::forward_as_tuple(other.packed.second())},
372 threshold{other.threshold} {}
383 : sparse{std::piecewise_construct, std::forward_as_tuple(std::move(other.sparse.first()), allocator), std::forward_as_tuple(std::move(other.sparse.second()))},
384 packed{std::piecewise_construct, std::forward_as_tuple(std::move(other.packed.first()), allocator), std::forward_as_tuple(std::move(other.packed.second()))},
385 threshold{other.threshold} {}
408 swap(sparse, other.sparse);
409 swap(packed, other.packed);
410 swap(threshold, other.threshold);
418 return sparse.first().get_allocator();
429 return packed.first().begin();
439 return packed.first().begin();
448 return packed.first().end();
458 return packed.first().end();
469 return std::make_reverse_iterator(
cend());
479 return std::make_reverse_iterator(
end());
488 return std::make_reverse_iterator(
cbegin());
498 return std::make_reverse_iterator(
begin());
505 [[nodiscard]]
bool empty() const noexcept {
506 return packed.first().empty();
514 return packed.first().size();
522 return packed.first().max_size();
527 sparse.first().clear();
528 packed.first().clear();
540 return insert_or_do_nothing(value);
545 return insert_or_do_nothing(std::move(value));
554 template<
typename It>
556 for(; first != last; ++first) {
574 template<
typename... Args>
575 std::pair<iterator, bool>
emplace(Args &&...args) {
576 if constexpr(((
sizeof...(Args) == 1u) && ... && std::is_same_v<std::decay_t<Args>,
value_type>)) {
577 return insert_or_do_nothing(std::forward<Args>(args)...);
579 auto &node = packed.first().emplace_back(std::piecewise_construct, std::make_tuple(packed.first().size()), std::forward_as_tuple(std::forward<Args>(args)...));
580 const auto index = value_to_bucket(node.second);
582 if(
auto it = constrained_find(node.second, index); it !=
end()) {
583 packed.first().pop_back();
584 return std::make_pair(it,
false);
587 std::swap(node.first, sparse.first()[index]);
588 rehash_if_required();
590 return std::make_pair(--
end(),
true);
600 const auto diff = pos -
cbegin();
602 return begin() + diff;
612 const auto dist = first -
cbegin();
614 for(
auto from = last -
cbegin(); from != dist; --from) {
618 return (
begin() + dist);
627 for(
size_type *curr = &sparse.first()[value_to_bucket(value)]; *curr != (std::numeric_limits<size_type>::max)(); curr = &packed.first()[*curr].first) {
628 if(packed.second()(packed.first()[*curr].second, value)) {
629 const auto index = *curr;
630 *curr = packed.first()[*curr].first;
654 template<
typename Other>
655 [[nodiscard]] std::enable_if_t<is_transparent_v<hasher> &&
is_transparent_v<key_equal>, std::conditional_t<false, Other, size_type>>
667 return constrained_find(value, value_to_bucket(value));
672 return constrained_find(value, value_to_bucket(value));
682 template<
typename Other>
683 [[nodiscard]] std::enable_if_t<is_transparent_v<hasher> &&
is_transparent_v<key_equal>, std::conditional_t<false, Other, iterator>>
685 return constrained_find(value, value_to_bucket(value));
689 template<
typename Other>
690 [[nodiscard]] std::enable_if_t<is_transparent_v<hasher> &&
is_transparent_v<key_equal>, std::conditional_t<false, Other, const_iterator>>
691 find(
const Other &value)
const {
692 return constrained_find(value, value_to_bucket(value));
702 const auto it =
find(value);
703 return {it, it + !(it ==
end())};
708 const auto it =
find(value);
709 return {it, it + !(it ==
cend())};
720 template<
typename Other>
721 [[nodiscard]] std::enable_if_t<is_transparent_v<hasher> &&
is_transparent_v<key_equal>, std::conditional_t<false, Other, std::pair<iterator, iterator>>>
723 const auto it =
find(value);
724 return {it, it + !(it ==
end())};
728 template<
typename Other>
729 [[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>>>
731 const auto it =
find(value);
732 return {it, it + !(it ==
cend())};
751 template<
typename Other>
763 return {packed.first().begin(), sparse.first()[index]};
781 return {packed.first().begin(), sparse.first()[index]};
790 return {packed.first().begin(), (std::numeric_limits<size_type>::max)()};
808 return {packed.first().begin(), (std::numeric_limits<size_type>::max)()};
816 return sparse.first().size();
824 return sparse.first().max_size();
842 return value_to_bucket(value);
866 ENTT_ASSERT(value > 0.f,
"Invalid load factor");
877 auto value = cnt > minimum_capacity ? cnt : minimum_capacity;
879 value = value > cap ? value : cap;
882 sparse.first().resize(sz);
884 for(
auto &&elem: sparse.first()) {
885 elem = (std::numeric_limits<size_type>::max)();
889 const auto index = value_to_bucket(packed.first()[pos].second);
890 packed.first()[pos].first = std::exchange(sparse.first()[index], pos);
901 packed.first().reserve(cnt);
910 return sparse.second();
918 return packed.second();
924 float threshold{default_threshold};
size_type bucket_size(const size_type index) const
Returns the number of elements in a given bucket.
void clear() noexcept
Clears the container.
internal::dense_set_local_iterator< typename packed_container_type::const_iterator > const_local_iterator
Constant forward iterator type.
const_reverse_iterator crbegin() const noexcept
Returns a reverse iterator to the beginning.
std::ptrdiff_t difference_type
Signed integer type.
const_iterator begin() const noexcept
Returns an iterator to the beginning.
key_equal key_eq() const
Returns the function used to compare elements for equality.
KeyEqual key_equal
Type of function to use to compare the elements for equality.
internal::dense_set_iterator< typename packed_container_type::const_iterator > const_iterator
Constant random access iterator type.
const_iterator cend() const noexcept
Returns an iterator to the end.
iterator erase(const_iterator first, const_iterator last)
Removes the given elements from a container.
std::enable_if_t< is_transparent_v< hasher > &&is_transparent_v< key_equal >, std::conditional_t< false, Other, bool > > contains(const Other &value) const
Checks if the container contains an element that compares equivalent to a given value.
Hash hasher
Type of function to use to hash the elements.
std::size_t size_type
Unsigned integer type.
size_type bucket(const value_type &value) const
Returns the bucket for a given element.
reverse_iterator rbegin() noexcept
Returns a reverse iterator to the beginning.
iterator find(const value_type &value)
Finds an element with a given value.
Type key_type
Key type of the container.
Type value_type
Value type of the container.
internal::dense_set_iterator< typename packed_container_type::iterator > iterator
Random access iterator type.
std::pair< iterator, bool > emplace(Args &&...args)
Constructs an element in-place, if it does not exist.
dense_set & operator=(dense_set &&) noexcept=default
Default move assignment operator.
size_type bucket_count() const
Returns the number of buckets.
size_type max_size() const noexcept
Returns the maximum possible number of elements.
size_type size() const noexcept
Returns the number of elements in a container.
std::pair< iterator, iterator > equal_range(const value_type &value)
Returns a range containing all elements with a given value.
std::reverse_iterator< const_iterator > const_reverse_iterator
Constant reverse iterator type.
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 &value)
Returns a range containing all elements that compare equivalent to a given value.
local_iterator end(const size_type index)
Returns an iterator to the end of a given bucket.
dense_set(const dense_set &other, const allocator_type &allocator)
Allocator-extended copy constructor.
bool empty() const noexcept
Checks whether a container is empty.
dense_set(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 ...
const_iterator find(const value_type &value) const
Finds an element with a given value.
const_iterator cbegin() const noexcept
Returns an iterator to the beginning.
const_reverse_iterator rend() const noexcept
Returns a reverse iterator to the end.
dense_set(const size_type cnt, const allocator_type &allocator)
Constructs an empty container with a given allocator and user supplied minimal number of buckets.
hasher hash_function() const
Returns the function used to hash the elements.
std::pair< iterator, bool > insert(const value_type &value)
Inserts an element into the container, if it does not exist.
internal::dense_set_local_iterator< typename packed_container_type::iterator > local_iterator
Forward iterator type.
~dense_set()=default
Default destructor.
void reserve(const size_type cnt)
Reserves space for at least the specified number of elements and regenerates the hash table.
const_local_iterator cend(const size_type index) const
Returns an iterator to the end of a given bucket.
std::reverse_iterator< iterator > reverse_iterator
Reverse iterator type.
Allocator allocator_type
Allocator type.
size_type count(const value_type &key) const
Returns the number of elements matching a value (either 1 or 0).
iterator end() noexcept
Returns an iterator to the end.
std::enable_if_t< is_transparent_v< hasher > &&is_transparent_v< key_equal >, std::conditional_t< false, Other, const_iterator > > find(const Other &value) const
Finds an element with a given value.
dense_set(const dense_set &)=default
Default copy constructor.
void swap(dense_set &other) noexcept
dense_set(dense_set &&) noexcept=default
Default move constructor.
const_local_iterator end(const size_type index) const
Returns an iterator to the end of a given bucket.
void max_load_factor(const float value)
Sets the desired maximum average number of elements per bucket.
float load_factor() const
Returns the average number of elements per bucket.
size_type erase(const value_type &value)
Removes the element associated with a given value.
std::pair< iterator, bool > insert(value_type &&value)
Inserts an element into the container, if it does not exist.
size_type max_bucket_count() const
Returns the maximum number of buckets.
dense_set(const allocator_type &allocator)
Constructs an empty container with a given allocator.
const_reverse_iterator rbegin() const noexcept
Returns a reverse iterator to the beginning.
dense_set()
Default constructor.
const_iterator end() const noexcept
Returns an iterator to the end.
dense_set & operator=(const dense_set &)=default
Default copy assignment operator.
dense_set(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...
iterator erase(const_iterator pos)
Removes an element from a given position.
std::enable_if_t< is_transparent_v< hasher > &&is_transparent_v< key_equal >, std::conditional_t< false, Other, iterator > > find(const Other &value)
Finds an element that compares equivalent to a given value.
void rehash(const size_type cnt)
Reserves at least the specified number of buckets and regenerates the hash table.
const_reverse_iterator crend() const noexcept
Returns a reverse iterator to the end.
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).
constexpr allocator_type get_allocator() const noexcept
Returns the associated allocator.
void insert(It first, It last)
Inserts elements into the container, if they do not exist.
reverse_iterator rend() noexcept
Returns a reverse iterator to the end.
float max_load_factor() const
Returns the maximum average number of elements per bucket.
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 &value) const
Returns a range containing all elements with a given value.
std::pair< const_iterator, const_iterator > equal_range(const value_type &value) const
Returns a range containing all elements with a given value.
const_local_iterator begin(const size_type index) const
Returns an iterator to the beginning of a given bucket.
local_iterator begin(const size_type index)
Returns an iterator to the beginning of a given bucket.
const_local_iterator cbegin(const size_type index) const
Returns an iterator to the beginning of a given bucket.
bool contains(const value_type &value) const
Checks if the container contains an element with a given value.
iterator begin() noexcept
Returns an iterator to the beginning.
constexpr std::enable_if_t< std::is_unsigned_v< Type >, Type > fast_mod(const Type value, const std::size_t mod) noexcept
Fast module utility function (powers of two only).
constexpr bool is_transparent_v
Helper variable template.
constexpr bool operator<=(const basic_hashed_string< Char > &lhs, const basic_hashed_string< Char > &rhs) noexcept
Compares two hashed strings.
constexpr std::enable_if_t< std::is_unsigned_v< Type >, Type > next_power_of_two(const Type 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 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) 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.