29#ifndef ANKERL_UNORDERED_DENSE_H
30#define ANKERL_UNORDERED_DENSE_H
33#define ANKERL_UNORDERED_DENSE_VERSION_MAJOR \
35#define ANKERL_UNORDERED_DENSE_VERSION_MINOR \
37#define ANKERL_UNORDERED_DENSE_VERSION_PATCH \
44#define ANKERL_UNORDERED_DENSE_VERSION_CONCAT1(major, minor, patch) \
45 v##major##_##minor##_##patch
47#define ANKERL_UNORDERED_DENSE_VERSION_CONCAT(major, minor, patch) \
48 ANKERL_UNORDERED_DENSE_VERSION_CONCAT1(major, minor, patch)
49#define ANKERL_UNORDERED_DENSE_NAMESPACE \
50 ANKERL_UNORDERED_DENSE_VERSION_CONCAT(ANKERL_UNORDERED_DENSE_VERSION_MAJOR, \
51 ANKERL_UNORDERED_DENSE_VERSION_MINOR, \
52 ANKERL_UNORDERED_DENSE_VERSION_PATCH)
54#if defined(_MSVC_LANG)
55# define ANKERL_UNORDERED_DENSE_CPP_VERSION _MSVC_LANG
57# define ANKERL_UNORDERED_DENSE_CPP_VERSION __cplusplus
62# define ANKERL_UNORDERED_DENSE_PACK(decl) decl __attribute__((__packed__))
63#elif defined(_MSC_VER)
65# define ANKERL_UNORDERED_DENSE_PACK(decl) \
66 __pragma(pack(push, 1)) decl __pragma(pack(pop))
70#if defined(__cpp_exceptions) || defined(__EXCEPTIONS) || defined(_CPPUNWIND)
71# define ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS() \
74# define ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS() \
78# define ANKERL_UNORDERED_DENSE_NOINLINE __declspec(noinline)
80# define ANKERL_UNORDERED_DENSE_NOINLINE __attribute__((noinline))
84#if !defined(ANKERL_UNORDERED_DENSE_EXPORT)
85# define ANKERL_UNORDERED_DENSE_EXPORT
88#if ANKERL_UNORDERED_DENSE_CPP_VERSION < 201703L
89# error ankerl::unordered_dense requires C++17 or higher
95# include <initializer_list>
102# include <string_view>
104# include <type_traits>
107# if ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS() == 0
111# if defined(__has_include)
112# if __has_include(<memory_resource>)
113# define ANKERL_UNORDERED_DENSE_PMR \
115# include <memory_resource>
116# elif __has_include(<experimental/memory_resource>)
117# define ANKERL_UNORDERED_DENSE_PMR \
118 std::experimental::pmr
119# include <experimental/memory_resource>
123# if defined(_MSC_VER) && defined(_M_X64)
125# pragma intrinsic(_umul128)
128# if defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__clang__)
129# define ANKERL_UNORDERED_DENSE_LIKELY(x) \
130 __builtin_expect(x, 1)
131# define ANKERL_UNORDERED_DENSE_UNLIKELY(x) \
132 __builtin_expect(x, 0)
134# define ANKERL_UNORDERED_DENSE_LIKELY(x) \
136# define ANKERL_UNORDERED_DENSE_UNLIKELY(x) \
140namespace ankerl::unordered_dense
148# if ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS()
154 on_error_key_not_found()
156 throw std::out_of_range(
157 "ankerl::unordered_dense::map::at(): key not found");
160 on_error_bucket_overflow()
162 throw std::overflow_error(
163 "ankerl::unordered_dense: reached max bucket size, cannot increase size");
166 on_error_too_many_elements()
168 throw std::out_of_range(
169 "ankerl::unordered_dense::map::replace(): too many elements");
174 [[noreturn]]
inline void
175 on_error_key_not_found()
179 [[noreturn]]
inline void
180 on_error_bucket_overflow()
184 [[noreturn]]
inline void
185 on_error_too_many_elements()
201 namespace detail::wyhash
205 mum(uint64_t *a, uint64_t *b)
207# if defined(__SIZEOF_INT128__)
210 *a =
static_cast<uint64_t
>(r);
211 *b =
static_cast<uint64_t
>(r >> 64U);
212# elif defined(_MSC_VER) && defined(_M_X64)
213 *a = _umul128(*a, *b, b);
215 uint64_t ha = *a >> 32U;
216 uint64_t hb = *b >> 32U;
217 uint64_t la =
static_cast<uint32_t
>(*a);
218 uint64_t lb =
static_cast<uint32_t
>(*b);
221 uint64_t rh = ha * hb;
222 uint64_t rm0 = ha * lb;
223 uint64_t rm1 = hb * la;
224 uint64_t rl = la * lb;
225 uint64_t t = rl + (rm0 << 32U);
226 auto c =
static_cast<uint64_t
>(t < rl);
227 lo = t + (rm1 << 32U);
228 c +=
static_cast<uint64_t
>(lo < t);
229 hi = rh + (rm0 >> 32U) + (rm1 >> 32U) + c;
236 [[nodiscard]]
inline auto
237 mix(uint64_t a, uint64_t b) -> uint64_t
245 [[nodiscard]]
inline auto
246 r8(
const uint8_t *p) -> uint64_t
249 std::memcpy(&v, p, 8U);
253 [[nodiscard]]
inline auto
254 r4(
const uint8_t *p) -> uint64_t
257 std::memcpy(&v, p, 4);
262 [[nodiscard]]
inline auto
263 r3(
const uint8_t *p,
size_t k) -> uint64_t
265 return (
static_cast<uint64_t
>(p[0]) << 16U) |
266 (
static_cast<uint64_t
>(p[k >> 1U]) << 8U) | p[k - 1];
269 [[maybe_unused]] [[nodiscard]]
inline auto
270 hash(
void const *key,
size_t len) -> uint64_t
272 static constexpr auto secret = std::array{UINT64_C(0xa0761d6478bd642f),
273 UINT64_C(0xe7037ed1a0b428db),
274 UINT64_C(0x8ebc6af09c88c6e3),
275 UINT64_C(0x589965cc75374cc3)};
277 auto const *p =
static_cast<uint8_t
const *
>(key);
278 uint64_t seed = secret[0];
281 if (ANKERL_UNORDERED_DENSE_LIKELY(len <= 16))
283 if (ANKERL_UNORDERED_DENSE_LIKELY(len >= 4))
285 a = (r4(p) << 32U) | r4(p + ((len >> 3U) << 2U));
286 b = (r4(p + len - 4) << 32U) |
287 r4(p + len - 4 - ((len >> 3U) << 2U));
289 else if (ANKERL_UNORDERED_DENSE_LIKELY(len > 0))
303 if (ANKERL_UNORDERED_DENSE_UNLIKELY(i > 48))
305 uint64_t see1 = seed;
306 uint64_t see2 = seed;
309 seed = mix(r8(p) ^ secret[1], r8(p + 8) ^ seed);
310 see1 = mix(r8(p + 16) ^ secret[2], r8(p + 24) ^ see1);
311 see2 = mix(r8(p + 32) ^ secret[3], r8(p + 40) ^ see2);
315 while (ANKERL_UNORDERED_DENSE_LIKELY(i > 48));
318 while (ANKERL_UNORDERED_DENSE_UNLIKELY(i > 16))
320 seed = mix(r8(p) ^ secret[1], r8(p + 8) ^ seed);
328 return mix(secret[1] ^ len, mix(a ^ secret[1], b ^ seed));
331 [[nodiscard]]
inline auto
332 hash(uint64_t x) -> uint64_t
334 return detail::wyhash::mix(x, UINT64_C(0x9E3779B97F4A7C15));
343 operator()(T
const &obj)
const noexcept(
noexcept(
344 std::declval<std::hash<T>>().operator()(std::declval<T const &>())))
347 return std::hash<T>{}(obj);
351 template <
typename CharT>
352 struct hash<std::basic_string<CharT>>
354 using is_avalanching = void;
356 operator()(std::basic_string<CharT>
const &str)
const noexcept -> uint64_t
358 return detail::wyhash::hash(str.data(),
sizeof(CharT) * str.size());
362 template <
typename CharT>
363 struct hash<std::basic_string_view<CharT>>
365 using is_avalanching = void;
367 operator()(std::basic_string_view<CharT>
const &sv)
const noexcept
370 return detail::wyhash::hash(sv.data(),
sizeof(CharT) * sv.size());
377 using is_avalanching = void;
379 operator()(T *ptr)
const noexcept -> uint64_t
382 return detail::wyhash::hash(
reinterpret_cast<uintptr_t
>(ptr));
387 struct hash<std::unique_ptr<T>>
389 using is_avalanching = void;
391 operator()(std::unique_ptr<T>
const &ptr)
const noexcept -> uint64_t
394 return detail::wyhash::hash(
reinterpret_cast<uintptr_t
>(ptr.get()));
399 struct hash<std::shared_ptr<T>>
401 using is_avalanching = void;
403 operator()(std::shared_ptr<T>
const &ptr)
const noexcept -> uint64_t
406 return detail::wyhash::hash(
reinterpret_cast<uintptr_t
>(ptr.get()));
410 template <
typename Enum>
411 struct hash<Enum, typename std::enable_if<std::is_enum<Enum>::value>::type>
413 using is_avalanching = void;
415 operator()(Enum e)
const noexcept -> uint64_t
417 using underlying =
typename std::underlying_type_t<Enum>;
418 return detail::wyhash::hash(
static_cast<underlying
>(e));
422 template <
typename... Args>
423 struct tuple_hash_helper
427 template <
typename Arg>
428 [[nodiscard]]
constexpr static auto
429 to64(Arg
const &arg) -> uint64_t
431 if constexpr (std::is_integral_v<Arg> || std::is_enum_v<Arg>)
433 return static_cast<uint64_t
>(arg);
437 return hash<Arg>{}(arg);
441 [[nodiscard]]
static auto
442 mix64(uint64_t state, uint64_t v) -> uint64_t
444 return detail::wyhash::mix(state + v, uint64_t{0x9ddfea08eb382d69});
452 template <
typename T, std::size_t... Idx>
453 [[nodiscard]]
static auto
454 calc_hash(T
const &t, std::index_sequence<Idx...>)
noexcept -> uint64_t
457 ((h = mix64(h, to64(std::get<Idx>(t)))), ...);
462 template <
typename... Args>
463 struct hash<std::tuple<Args...>> : tuple_hash_helper<Args...>
465 using is_avalanching = void;
467 operator()(std::tuple<Args...>
const &t)
const noexcept -> uint64_t
469 return tuple_hash_helper<Args...>::calc_hash(
470 t, std::index_sequence_for<Args...>{});
474 template <
typename A,
typename B>
475 struct hash<std::pair<A, B>> : tuple_hash_helper<A, B>
477 using is_avalanching = void;
479 operator()(std::pair<A, B>
const &t)
const noexcept -> uint64_t
481 return tuple_hash_helper<A, B>::calc_hash(
482 t, std::index_sequence_for<A, B>{});
487# define ANKERL_UNORDERED_DENSE_HASH_STATICCAST(T) \
491 using is_avalanching = void; \
493 operator()(T const &obj) const noexcept -> uint64_t \
495 return detail::wyhash::hash(static_cast<uint64_t>(obj)); \
499# if defined(__GNUC__) && !defined(__clang__)
500# pragma GCC diagnostic push
501# pragma GCC diagnostic ignored "-Wuseless-cast"
504 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
bool);
505 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
char);
506 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
signed char);
507 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
unsigned char);
508# if ANKERL_UNORDERED_DENSE_CPP_VERSION >= 202002L && defined(__cpp_char8_t)
509 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
char8_t);
511 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
char16_t);
512 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
char32_t);
513 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
wchar_t);
514 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
short);
515 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
unsigned short);
516 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
int);
517 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
unsigned int);
518 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
long);
519 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
long long);
520 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
unsigned long);
521 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
unsigned long long);
523# if defined(__GNUC__) && !defined(__clang__)
524# pragma GCC diagnostic pop
529 namespace bucket_type
534 static constexpr uint32_t dist_inc = 1U
536 static constexpr uint32_t fingerprint_mask =
540 m_dist_and_fingerprint;
542 uint32_t m_value_idx;
545 ANKERL_UNORDERED_DENSE_PACK(
struct big {
546 static constexpr uint32_t dist_inc = 1U
548 static constexpr uint32_t fingerprint_mask =
552 m_dist_and_fingerprint;
565 template <
class Default,
572 using value_t = std::false_type;
573 using type = Default;
576 template <
class Default,
template <
class...>
class Op,
class... Args>
577 struct detector<Default, std::void_t<Op<Args...>>, Op, Args...>
579 using value_t = std::true_type;
580 using type = Op<Args...>;
583 template <
template <
class...>
class Op,
class... Args>
585 typename detail::detector<detail::nonesuch, void, Op, Args...>::value_t;
587 template <
template <
class...>
class Op,
class... Args>
588 constexpr bool is_detected_v = is_detected<Op, Args...>::value;
590 template <
typename T>
591 using detect_avalanching =
typename T::is_avalanching;
593 template <
typename T>
594 using detect_is_transparent =
typename T::is_transparent;
596 template <
typename T>
597 using detect_iterator =
typename T::iterator;
599 template <
typename T>
600 using detect_reserve =
decltype(std::declval<T &>().reserve(
size_t{}));
604 template <
typename Mapped>
605 constexpr bool is_map_v = !std::is_void_v<Mapped>;
608template <
typename Hash,
typename KeyEqual>
609constexpr bool is_transparent_v = is_detected_v<detect_is_transparent, Hash> && is_detected_v<detect_is_transparent, KeyEqual>;
612 template <
typename From,
typename To1,
typename To2>
613 constexpr bool is_neither_convertible_v =
614 !std::is_convertible_v<From, To1> && !std::is_convertible_v<From, To2>;
616 template <
typename T>
617 constexpr bool has_reserve = is_detected_v<detect_reserve, T>;
621 struct base_table_type_map
623 using mapped_type = T;
627 struct base_table_type_set
640 template <
typename T,
641 typename Allocator = std::allocator<T>,
642 size_t MaxSegmentSizeBytes = 4096>
643 class segmented_vector
645 template <
bool IsConst>
649 using allocator_type = Allocator;
650 using pointer =
typename std::allocator_traits<allocator_type>::pointer;
651 using const_pointer =
652 typename std::allocator_traits<allocator_type>::const_pointer;
653 using difference_type =
654 typename std::allocator_traits<allocator_type>::difference_type;
655 using value_type = T;
656 using size_type = std::size_t;
657 using reference = T &;
658 using const_reference = T
const &;
659 using iterator = iter_t<false>;
660 using const_iterator = iter_t<true>;
663 using vec_alloc =
typename std::allocator_traits<
664 Allocator>::template rebind_alloc<pointer>;
665 std::vector<pointer, vec_alloc> m_blocks{};
669 static constexpr auto
670 num_bits_closest(
size_t max_val,
size_t s) ->
size_t
673 while (s << (f + 1) <= max_val)
680 using self_t = segmented_vector<T, Allocator, MaxSegmentSizeBytes>;
681 static constexpr auto num_bits =
682 num_bits_closest(MaxSegmentSizeBytes,
sizeof(T));
683 static constexpr auto num_elements_in_block = 1U << num_bits;
684 static constexpr auto mask = num_elements_in_block - 1U;
689 template <
bool IsConst>
693 typename std::conditional_t<IsConst,
694 segmented_vector::const_pointer
const *,
695 segmented_vector::pointer *>;
703 using difference_type = segmented_vector::difference_type;
704 using value_type = T;
705 using reference =
typename std::
706 conditional_t<IsConst, value_type const &, value_type &>;
708 typename std::conditional_t<IsConst,
709 segmented_vector::const_pointer,
710 segmented_vector::pointer>;
711 using iterator_category = std::forward_iterator_tag;
713 iter_t()
noexcept =
default;
717 typename =
typename std::enable_if<IsConst && !OtherIsConst>::type>
719 constexpr iter_t(iter_t<OtherIsConst>
const &other) noexcept
720 : m_data(other.m_data)
724 constexpr iter_t(ptr_t data,
size_t idx) noexcept
731 typename =
typename std::enable_if<IsConst && !OtherIsConst>::type>
733 operator=(iter_t<OtherIsConst>
const &other)
noexcept -> iter_t &
735 m_data = other.m_data;
741 operator++()
noexcept -> iter_t &
748 operator+(difference_type diff)
noexcept -> iter_t
751 static_cast<size_t>(
static_cast<difference_type
>(m_idx) +
755 template <
bool OtherIsConst>
757 operator-(iter_t<OtherIsConst>
const &other)
noexcept -> difference_type
759 return static_cast<difference_type
>(m_idx) -
760 static_cast<difference_type
>(other.m_idx);
764 operator*()
const noexcept -> reference
766 return m_data[m_idx >> num_bits][m_idx & mask];
770 operator->()
const noexcept -> pointer
772 return &m_data[m_idx >> num_bits][m_idx & mask];
777 operator==(iter_t<O>
const &o)
const noexcept ->
bool
779 return m_idx == o.m_idx;
784 operator!=(iter_t<O>
const &o)
const noexcept ->
bool
786 return !(*
this == o);
794 auto ba = Allocator(m_blocks.get_allocator());
796 std::allocator_traits<Allocator>::allocate(ba, num_elements_in_block);
797 m_blocks.push_back(block);
802 append_everything_from(segmented_vector &&other)
804 reserve(size() + other.size());
805 for (
auto &&o : other)
807 emplace_back(std::move(o));
813 append_everything_from(segmented_vector
const &other)
815 reserve(size() + other.size());
816 for (
auto const &o : other)
825 auto ba = Allocator(m_blocks.get_allocator());
826 for (
auto ptr : m_blocks)
828 std::allocator_traits<Allocator>::deallocate(ba,
830 num_elements_in_block);
834 [[nodiscard]]
static constexpr auto
835 calc_num_blocks_for_capacity(
size_t capacity)
837 return (capacity + num_elements_in_block - 1U) / num_elements_in_block;
841 segmented_vector() =
default;
844 segmented_vector(Allocator alloc)
845 : m_blocks(vec_alloc(alloc))
848 segmented_vector(segmented_vector &&other, Allocator alloc)
849 : segmented_vector(alloc)
851 *
this = std::move(other);
854 segmented_vector(segmented_vector
const &other, Allocator alloc)
855 : m_blocks(vec_alloc(alloc))
857 append_everything_from(other);
860 segmented_vector(segmented_vector &&other) noexcept
861 : segmented_vector(std::move(other), get_allocator())
864 segmented_vector(segmented_vector
const &other)
866 append_everything_from(other);
870 operator=(segmented_vector
const &other) -> segmented_vector &
877 append_everything_from(other);
882 operator=(segmented_vector &&other)
noexcept -> segmented_vector &
886 if (other.get_allocator() == get_allocator())
888 m_blocks = std::move(other.m_blocks);
889 m_size = std::exchange(other.m_size, {});
895 std::vector<pointer, vec_alloc>(vec_alloc(other.get_allocator()));
896 append_everything_from(std::move(other));
907 [[nodiscard]]
constexpr auto
908 size()
const ->
size_t
913 [[nodiscard]]
constexpr auto
914 capacity()
const ->
size_t
916 return m_blocks.size() * num_elements_in_block;
920 [[nodiscard]]
constexpr auto
921 operator[](
size_t i)
const noexcept -> T
const &
923 return m_blocks[i >> num_bits][i & mask];
926 [[nodiscard]]
constexpr auto
927 operator[](
size_t i)
noexcept -> T &
929 return m_blocks[i >> num_bits][i & mask];
932 [[nodiscard]]
constexpr auto
935 return {m_blocks.data(), 0U};
937 [[nodiscard]]
constexpr auto
938 begin()
const -> const_iterator
940 return {m_blocks.data(), 0U};
942 [[nodiscard]]
constexpr auto
943 cbegin()
const -> const_iterator
945 return {m_blocks.data(), 0U};
948 [[nodiscard]]
constexpr auto
951 return {m_blocks.data(), m_size};
953 [[nodiscard]]
constexpr auto
954 end()
const -> const_iterator
956 return {m_blocks.data(), m_size};
958 [[nodiscard]]
constexpr auto
959 cend()
const -> const_iterator
961 return {m_blocks.data(), m_size};
964 [[nodiscard]]
constexpr auto
967 return operator[](m_size - 1);
969 [[nodiscard]]
constexpr auto
970 back()
const -> const_reference
972 return operator[](m_size - 1);
989 reserve(
size_t new_capacity)
991 m_blocks.reserve(calc_num_blocks_for_capacity(new_capacity));
992 while (new_capacity > capacity())
999 get_allocator()
const -> allocator_type
1001 return allocator_type{m_blocks.get_allocator()};
1004 template <
class... Args>
1006 emplace_back(Args &&...args) -> reference
1008 if (m_size == capacity())
1010 increase_capacity();
1012 auto *ptr =
static_cast<void *
>(&operator[](m_size));
1013 auto &ref = *
new (ptr) T(std::forward<Args>(args)...);
1021 if constexpr (!std::is_trivially_destructible_v<T>)
1023 for (
size_t i = 0, s = size(); i < s; ++i)
1034 auto ba = Allocator(m_blocks.get_allocator());
1035 auto num_blocks_required = calc_num_blocks_for_capacity(m_size);
1036 while (m_blocks.size() > num_blocks_required)
1038 std::allocator_traits<Allocator>::deallocate(ba,
1040 num_elements_in_block);
1041 m_blocks.pop_back();
1043 m_blocks.shrink_to_fit();
1052 template <
class Key,
1056 class AllocatorOrContainer,
1059 class table :
public std::conditional_t<is_map_v<T>,
1060 base_table_type_map<T>,
1061 base_table_type_set>
1063 using underlying_value_type =
1064 typename std::conditional_t<is_map_v<T>, std::pair<Key, T>, Key>;
1065 using underlying_container_type = std::conditional_t<
1067 segmented_vector<underlying_value_type, AllocatorOrContainer>,
1068 std::vector<underlying_value_type, AllocatorOrContainer>>;
1071 using value_container_type = std::conditional_t<
1072 is_detected_v<detect_iterator, AllocatorOrContainer>,
1073 AllocatorOrContainer,
1074 underlying_container_type>;
1077 using bucket_alloc =
typename std::allocator_traits<
1078 typename value_container_type::allocator_type>::
1079 template rebind_alloc<Bucket>;
1080 using bucket_alloc_traits = std::allocator_traits<bucket_alloc>;
1082 static constexpr uint8_t initial_shifts =
1084 static constexpr float default_max_load_factor = 0.8F;
1087 using key_type = Key;
1088 using value_type =
typename value_container_type::value_type;
1089 using size_type =
typename value_container_type::size_type;
1090 using difference_type =
typename value_container_type::difference_type;
1091 using hasher = Hash;
1092 using key_equal = KeyEqual;
1093 using allocator_type =
typename value_container_type::allocator_type;
1094 using reference =
typename value_container_type::reference;
1095 using const_reference =
typename value_container_type::const_reference;
1096 using pointer =
typename value_container_type::pointer;
1097 using const_pointer =
typename value_container_type::const_pointer;
1098 using const_iterator =
typename value_container_type::const_iterator;
1100 std::conditional_t<is_map_v<T>,
1101 typename value_container_type::iterator,
1103 using bucket_type = Bucket;
1106 using value_idx_type =
decltype(Bucket::m_value_idx);
1107 using dist_and_fingerprint_type =
1108 decltype(Bucket::m_dist_and_fingerprint);
1111 std::is_trivially_destructible_v<Bucket>,
1112 "assert there's no need to call destructor / std::destroy");
1113 static_assert(std::is_trivially_copyable_v<Bucket>,
1114 "assert we can just memset / memcpy");
1116 value_container_type
1119 using bucket_pointer =
1120 typename std::allocator_traits<bucket_alloc>::pointer;
1121 bucket_pointer m_buckets{};
1122 size_t m_num_buckets = 0;
1123 size_t m_max_bucket_capacity = 0;
1124 float m_max_load_factor = default_max_load_factor;
1127 uint8_t m_shifts = initial_shifts;
1130 next(value_idx_type bucket_idx)
const -> value_idx_type
1132 return ANKERL_UNORDERED_DENSE_UNLIKELY(bucket_idx + 1U ==
1135 static_cast<value_idx_type
>(bucket_idx + 1U);
1139 [[nodiscard]]
static constexpr auto
1140 at(bucket_pointer bucket_ptr,
size_t offset) -> Bucket &
1145 typename std::allocator_traits<bucket_alloc>::difference_type
>(
1151 [[nodiscard]]
static constexpr auto
1152 dist_inc(dist_and_fingerprint_type x) -> dist_and_fingerprint_type
1154 return static_cast<dist_and_fingerprint_type
>(x + Bucket::dist_inc);
1157 [[nodiscard]]
static constexpr auto
1158 dist_dec(dist_and_fingerprint_type x) -> dist_and_fingerprint_type
1160 return static_cast<dist_and_fingerprint_type
>(x - Bucket::dist_inc);
1165 template <
typename K>
1166 [[nodiscard]]
constexpr auto
1167 mixed_hash(K
const &key)
const -> uint64_t
1169 if constexpr (is_detected_v<detect_avalanching, Hash>)
1172 if constexpr (
sizeof(
decltype(m_hash(key))) <
sizeof(uint64_t))
1176 return m_hash(key) * UINT64_C(0x9ddfea08eb382d69);
1187 return wyhash::hash(m_hash(key));
1191 [[nodiscard]]
constexpr auto
1192 dist_and_fingerprint_from_hash(uint64_t hash)
const
1193 -> dist_and_fingerprint_type
1195 return Bucket::dist_inc |
1196 (
static_cast<dist_and_fingerprint_type
>(hash) &
1197 Bucket::fingerprint_mask);
1200 [[nodiscard]]
constexpr auto
1201 bucket_idx_from_hash(uint64_t hash)
const -> value_idx_type
1203 return static_cast<value_idx_type
>(hash >> m_shifts);
1206 [[nodiscard]]
static constexpr auto
1207 get_key(value_type
const &vt) -> key_type
const &
1209 if constexpr (is_map_v<T>)
1219 template <
typename K>
1221 next_while_less(K
const &key)
const -> Bucket
1223 auto hash = mixed_hash(key);
1224 auto dist_and_fingerprint = dist_and_fingerprint_from_hash(hash);
1225 auto bucket_idx = bucket_idx_from_hash(hash);
1227 while (dist_and_fingerprint <
1228 at(m_buckets, bucket_idx).m_dist_and_fingerprint)
1230 dist_and_fingerprint = dist_inc(dist_and_fingerprint);
1231 bucket_idx = next(bucket_idx);
1233 return {dist_and_fingerprint, bucket_idx};
1237 place_and_shift_up(Bucket bucket, value_idx_type place)
1239 while (0 != at(m_buckets, place).m_dist_and_fingerprint)
1241 bucket = std::exchange(at(m_buckets, place), bucket);
1242 bucket.m_dist_and_fingerprint =
1243 dist_inc(bucket.m_dist_and_fingerprint);
1244 place = next(place);
1246 at(m_buckets, place) = bucket;
1249 [[nodiscard]]
static constexpr auto
1250 calc_num_buckets(uint8_t shifts) ->
size_t
1252 return (std::min)(max_bucket_count(),
size_t{1} << (64U - shifts));
1255 [[nodiscard]]
constexpr auto
1256 calc_shifts_for_size(
size_t s)
const -> uint8_t
1258 auto shifts = initial_shifts;
1259 while (shifts > 0 &&
static_cast<size_t>(
1260 static_cast<float>(calc_num_buckets(shifts)) *
1261 max_load_factor()) < s)
1271 copy_buckets(table
const &other)
1278 allocate_buckets_from_shift();
1283 m_shifts = other.m_shifts;
1284 allocate_buckets_from_shift();
1285 std::memcpy(m_buckets,
1287 sizeof(Bucket) * bucket_count());
1296 is_full()
const ->
bool
1298 return size() > m_max_bucket_capacity;
1302 deallocate_buckets()
1304 auto ba = bucket_alloc(m_values.get_allocator());
1305 if (
nullptr != m_buckets)
1307 bucket_alloc_traits::deallocate(ba, m_buckets, bucket_count());
1308 m_buckets =
nullptr;
1311 m_max_bucket_capacity = 0;
1315 allocate_buckets_from_shift()
1317 auto ba = bucket_alloc(m_values.get_allocator());
1318 m_num_buckets = calc_num_buckets(m_shifts);
1319 m_buckets = bucket_alloc_traits::allocate(ba, m_num_buckets);
1320 if (m_num_buckets == max_bucket_count())
1323 m_max_bucket_capacity = max_bucket_count();
1327 m_max_bucket_capacity =
static_cast<value_idx_type
>(
1328 static_cast<float>(m_num_buckets) * max_load_factor());
1335 if (m_buckets !=
nullptr)
1337 std::memset(&*m_buckets, 0,
sizeof(Bucket) * bucket_count());
1342 clear_and_fill_buckets_from_values()
1347 end_idx =
static_cast<value_idx_type
>(m_values.size());
1348 value_idx < end_idx;
1351 auto const &key = get_key(m_values[value_idx]);
1352 auto [dist_and_fingerprint, bucket] = next_while_less(key);
1356 place_and_shift_up({dist_and_fingerprint, value_idx}, bucket);
1363 if (m_max_bucket_capacity == max_bucket_count())
1366 m_values.pop_back();
1367 on_error_bucket_overflow();
1370 deallocate_buckets();
1371 allocate_buckets_from_shift();
1372 clear_and_fill_buckets_from_values();
1375 template <
typename Op>
1377 do_erase(value_idx_type bucket_idx, Op handle_erased_value)
1379 auto const value_idx_to_remove =
1380 at(m_buckets, bucket_idx).m_value_idx;
1384 auto next_bucket_idx = next(bucket_idx);
1385 while (at(m_buckets, next_bucket_idx).m_dist_and_fingerprint >=
1386 Bucket::dist_inc * 2)
1388 at(m_buckets, bucket_idx) = {
1389 dist_dec(at(m_buckets, next_bucket_idx).m_dist_and_fingerprint),
1390 at(m_buckets, next_bucket_idx).m_value_idx};
1392 std::exchange(next_bucket_idx, next(next_bucket_idx));
1394 at(m_buckets, bucket_idx) = {};
1395 handle_erased_value(std::move(m_values[value_idx_to_remove]));
1398 if (value_idx_to_remove != m_values.size() - 1)
1402 auto &val = m_values[value_idx_to_remove];
1403 val = std::move(m_values.back());
1407 auto mh = mixed_hash(get_key(val));
1408 bucket_idx = bucket_idx_from_hash(mh);
1410 auto const values_idx_back =
1411 static_cast<value_idx_type
>(m_values.size() - 1);
1412 while (values_idx_back != at(m_buckets, bucket_idx).m_value_idx)
1414 bucket_idx = next(bucket_idx);
1416 at(m_buckets, bucket_idx).m_value_idx = value_idx_to_remove;
1418 m_values.pop_back();
1421 template <
typename K,
typename Op>
1423 do_erase_key(K &&key, Op handle_erased_value) ->
size_t
1430 auto [dist_and_fingerprint, bucket_idx] = next_while_less(key);
1433 dist_and_fingerprint ==
1434 at(m_buckets, bucket_idx).m_dist_and_fingerprint &&
1436 get_key(m_values[at(m_buckets, bucket_idx).m_value_idx])))
1438 dist_and_fingerprint = dist_inc(dist_and_fingerprint);
1439 bucket_idx = next(bucket_idx);
1442 if (dist_and_fingerprint !=
1443 at(m_buckets, bucket_idx).m_dist_and_fingerprint)
1447 do_erase(bucket_idx, handle_erased_value);
1451 template <
class K,
class M>
1453 do_insert_or_assign(K &&key, M &&mapped) -> std::pair<iterator, bool>
1455 auto it_isinserted =
1456 try_emplace(std::forward<K>(key), std::forward<M>(mapped));
1457 if (!it_isinserted.second)
1459 it_isinserted.first->second = std::forward<M>(mapped);
1461 return it_isinserted;
1464 template <
typename... Args>
1466 do_place_element(dist_and_fingerprint_type dist_and_fingerprint,
1467 value_idx_type bucket_idx,
1468 Args &&...args) -> std::pair<iterator, bool>
1472 m_values.emplace_back(std::forward<Args>(args)...);
1474 auto value_idx =
static_cast<value_idx_type
>(m_values.size() - 1);
1475 if (ANKERL_UNORDERED_DENSE_UNLIKELY(is_full()))
1481 place_and_shift_up({dist_and_fingerprint, value_idx}, bucket_idx);
1485 return {begin() +
static_cast<difference_type
>(value_idx),
true};
1488 template <
typename K,
typename... Args>
1490 do_try_emplace(K &&key, Args &&...args) -> std::pair<iterator, bool>
1492 auto hash = mixed_hash(key);
1493 auto dist_and_fingerprint = dist_and_fingerprint_from_hash(hash);
1494 auto bucket_idx = bucket_idx_from_hash(hash);
1498 auto *bucket = &at(m_buckets, bucket_idx);
1499 if (dist_and_fingerprint == bucket->m_dist_and_fingerprint)
1501 if (m_equal(key, get_key(m_values[bucket->m_value_idx])))
1503 return {begin() +
static_cast<difference_type
>(
1504 bucket->m_value_idx),
1508 else if (dist_and_fingerprint > bucket->m_dist_and_fingerprint)
1510 return do_place_element(
1511 dist_and_fingerprint,
1513 std::piecewise_construct,
1514 std::forward_as_tuple(std::forward<K>(key)),
1515 std::forward_as_tuple(std::forward<Args>(args)...));
1517 dist_and_fingerprint = dist_inc(dist_and_fingerprint);
1518 bucket_idx = next(bucket_idx);
1522 template <
typename K>
1524 do_find(K
const &key) -> iterator
1526 if (ANKERL_UNORDERED_DENSE_UNLIKELY(empty()))
1531 auto mh = mixed_hash(key);
1532 auto dist_and_fingerprint = dist_and_fingerprint_from_hash(mh);
1533 auto bucket_idx = bucket_idx_from_hash(mh);
1534 auto *bucket = &at(m_buckets, bucket_idx);
1538 if (dist_and_fingerprint == bucket->m_dist_and_fingerprint &&
1539 m_equal(key, get_key(m_values[bucket->m_value_idx])))
1542 static_cast<difference_type
>(bucket->m_value_idx);
1544 dist_and_fingerprint = dist_inc(dist_and_fingerprint);
1545 bucket_idx = next(bucket_idx);
1546 bucket = &at(m_buckets, bucket_idx);
1548 if (dist_and_fingerprint == bucket->m_dist_and_fingerprint &&
1549 m_equal(key, get_key(m_values[bucket->m_value_idx])))
1552 static_cast<difference_type
>(bucket->m_value_idx);
1554 dist_and_fingerprint = dist_inc(dist_and_fingerprint);
1555 bucket_idx = next(bucket_idx);
1556 bucket = &at(m_buckets, bucket_idx);
1560 if (dist_and_fingerprint == bucket->m_dist_and_fingerprint)
1562 if (m_equal(key, get_key(m_values[bucket->m_value_idx])))
1565 static_cast<difference_type
>(bucket->m_value_idx);
1568 else if (dist_and_fingerprint > bucket->m_dist_and_fingerprint)
1572 dist_and_fingerprint = dist_inc(dist_and_fingerprint);
1573 bucket_idx = next(bucket_idx);
1574 bucket = &at(m_buckets, bucket_idx);
1578 template <
typename K>
1580 do_find(K
const &key)
const -> const_iterator
1582 return const_cast<table *
>(
this)->do_find(
1586 template <
typename K,
1588 std::enable_if_t<is_map_v<Q>,
bool> =
true>
1590 do_at(K
const &key) -> Q &
1592 if (
auto it = find(key); ANKERL_UNORDERED_DENSE_LIKELY(end() != it))
1596 on_error_key_not_found();
1599 template <
typename K,
1601 std::enable_if_t<is_map_v<Q>,
bool> =
true>
1603 do_at(K
const &key)
const -> Q
const &
1605 return const_cast<table *
>(
this)->at(
1611 size_t bucket_count,
1612 Hash
const &hash = Hash(),
1613 KeyEqual
const &equal = KeyEqual(),
1614 allocator_type
const &alloc_or_container = allocator_type())
1615 : m_values(alloc_or_container)
1619 if (0 != bucket_count)
1621 reserve(bucket_count);
1625 allocate_buckets_from_shift();
1634 table(
size_t bucket_count, allocator_type
const &alloc)
1635 : table(bucket_count, Hash(), KeyEqual(), alloc)
1638 table(
size_t bucket_count,
1640 allocator_type
const &alloc)
1641 : table(bucket_count, hash, KeyEqual(), alloc)
1644 explicit table(allocator_type
const &alloc)
1645 : table(0, Hash(), KeyEqual(), alloc)
1648 template <
class InputIt>
1649 table(InputIt first,
1651 size_type bucket_count = 0,
1652 Hash
const &hash = Hash(),
1653 KeyEqual
const &equal = KeyEqual(),
1654 allocator_type
const &alloc = allocator_type())
1655 : table(bucket_count, hash, equal, alloc)
1657 insert(first, last);
1660 template <
class InputIt>
1661 table(InputIt first,
1663 size_type bucket_count,
1664 allocator_type
const &alloc)
1665 : table(first, last, bucket_count, Hash(), KeyEqual(), alloc)
1668 template <
class InputIt>
1669 table(InputIt first,
1671 size_type bucket_count,
1673 allocator_type
const &alloc)
1674 : table(first, last, bucket_count, hash, KeyEqual(), alloc)
1677 table(table
const &other)
1678 : table(other, other.m_values.get_allocator())
1681 table(table
const &other, allocator_type
const &alloc)
1682 : m_values(other.m_values, alloc)
1683 , m_max_load_factor(other.m_max_load_factor)
1684 , m_hash(other.m_hash)
1685 , m_equal(other.m_equal)
1687 copy_buckets(other);
1690 table(table &&other) noexcept
1691 : table(std::move(other), other.m_values.get_allocator())
1694 table(table &&other, allocator_type
const &alloc) noexcept
1697 *
this = std::move(other);
1700 table(std::initializer_list<value_type> ilist,
1701 size_t bucket_count = 0,
1702 Hash
const &hash = Hash(),
1703 KeyEqual
const &equal = KeyEqual(),
1704 allocator_type
const &alloc = allocator_type())
1705 : table(bucket_count, hash, equal, alloc)
1710 table(std::initializer_list<value_type> ilist,
1711 size_type bucket_count,
1712 allocator_type
const &alloc)
1713 : table(ilist, bucket_count, Hash(), KeyEqual(), alloc)
1716 table(std::initializer_list<value_type> init,
1717 size_type bucket_count,
1719 allocator_type
const &alloc)
1720 : table(init, bucket_count, hash, KeyEqual(), alloc)
1725 if (
nullptr != m_buckets)
1727 auto ba = bucket_alloc(m_values.get_allocator());
1728 bucket_alloc_traits::deallocate(ba, m_buckets, bucket_count());
1733 operator=(table
const &other) -> table &
1737 deallocate_buckets();
1739 m_values = other.m_values;
1740 m_max_load_factor = other.m_max_load_factor;
1741 m_hash = other.m_hash;
1742 m_equal = other.m_equal;
1743 m_shifts = initial_shifts;
1744 copy_buckets(other);
1750 operator=(table &&other)
noexcept(
noexcept(
1751 std::is_nothrow_move_assignable_v<value_container_type>
1752 &&std::is_nothrow_move_assignable_v<Hash>
1753 &&std::is_nothrow_move_assignable_v<KeyEqual>)) -> table &
1757 deallocate_buckets();
1759 m_values = std::move(other.m_values);
1760 other.m_values.clear();
1764 if (get_allocator() == other.get_allocator())
1766 m_buckets = std::exchange(other.m_buckets,
nullptr);
1767 m_num_buckets = std::exchange(other.m_num_buckets, 0);
1768 m_max_bucket_capacity =
1769 std::exchange(other.m_max_bucket_capacity, 0);
1770 m_shifts = std::exchange(other.m_shifts, initial_shifts);
1771 m_max_load_factor = std::exchange(other.m_max_load_factor,
1772 default_max_load_factor);
1773 m_hash = std::exchange(other.m_hash, {});
1774 m_equal = std::exchange(other.m_equal, {});
1775 other.allocate_buckets_from_shift();
1776 other.clear_buckets();
1782 m_max_load_factor = other.m_max_load_factor;
1786 copy_buckets(other);
1788 other.clear_buckets();
1789 m_hash = other.m_hash;
1790 m_equal = other.m_equal;
1798 operator=(std::initializer_list<value_type> ilist) -> table &
1806 get_allocator()
const noexcept -> allocator_type
1808 return m_values.get_allocator();
1815 begin()
noexcept -> iterator
1817 return m_values.begin();
1821 begin()
const noexcept -> const_iterator
1823 return m_values.begin();
1827 cbegin()
const noexcept -> const_iterator
1829 return m_values.cbegin();
1833 end()
noexcept -> iterator
1835 return m_values.end();
1839 cend()
const noexcept -> const_iterator
1841 return m_values.cend();
1845 end()
const noexcept -> const_iterator
1847 return m_values.end();
1854 empty()
const noexcept ->
bool
1856 return m_values.empty();
1860 size()
const noexcept ->
size_t
1862 return m_values.size();
1865 [[nodiscard]]
static constexpr auto
1866 max_size()
noexcept ->
size_t
1868 if constexpr ((std::numeric_limits<value_idx_type>::max)() ==
1869 (std::numeric_limits<size_t>::max)())
1871 return size_t{1} << (
sizeof(value_idx_type) * 8 - 1);
1875 return size_t{1} << (
sizeof(value_idx_type) * 8);
1890 insert(value_type
const &value) -> std::pair<iterator, bool>
1892 return emplace(value);
1896 insert(value_type &&value) -> std::pair<iterator, bool>
1898 return emplace(std::move(value));
1902 std::enable_if_t<std::is_constructible_v<value_type, P &&>,
1905 insert(P &&value) -> std::pair<iterator, bool>
1907 return emplace(std::forward<P>(value));
1911 insert(const_iterator , value_type
const &value) -> iterator
1913 return insert(value).first;
1917 insert(const_iterator , value_type &&value) -> iterator
1919 return insert(std::move(value)).first;
1923 std::enable_if_t<std::is_constructible_v<value_type, P &&>,
1926 insert(const_iterator , P &&value) -> iterator
1928 return insert(std::forward<P>(value)).first;
1931 template <
class InputIt>
1933 insert(InputIt first, InputIt last)
1935 while (first != last)
1943 insert(std::initializer_list<value_type> ilist)
1945 insert(ilist.begin(), ilist.end());
1952 extract() && -> value_container_type
1954 return std::move(m_values);
1961 replace(value_container_type &&container)
1963 if (ANKERL_UNORDERED_DENSE_UNLIKELY(container.size() > max_size()))
1965 on_error_too_many_elements();
1967 auto shifts = calc_shifts_for_size(container.size());
1968 if (0 == m_num_buckets || shifts < m_shifts ||
1969 container.get_allocator() != m_values.get_allocator())
1972 deallocate_buckets();
1973 allocate_buckets_from_shift();
1977 m_values = std::move(container);
1981 auto value_idx = value_idx_type{};
1985 while (value_idx !=
static_cast<value_idx_type
>(m_values.size()))
1987 auto const &key = get_key(m_values[value_idx]);
1989 auto hash = mixed_hash(key);
1990 auto dist_and_fingerprint = dist_and_fingerprint_from_hash(hash);
1991 auto bucket_idx = bucket_idx_from_hash(hash);
1993 bool key_found =
false;
1996 auto const &bucket = at(m_buckets, bucket_idx);
1997 if (dist_and_fingerprint > bucket.m_dist_and_fingerprint)
2001 if (dist_and_fingerprint == bucket.m_dist_and_fingerprint &&
2002 m_equal(key, get_key(m_values[bucket.m_value_idx])))
2007 dist_and_fingerprint = dist_inc(dist_and_fingerprint);
2008 bucket_idx = next(bucket_idx);
2014 static_cast<value_idx_type
>(m_values.size() - 1))
2016 m_values[value_idx] = std::move(m_values.back());
2018 m_values.pop_back();
2022 place_and_shift_up({dist_and_fingerprint, value_idx},
2031 std::enable_if_t<is_map_v<Q>,
bool> =
true>
2033 insert_or_assign(Key
const &key, M &&mapped)
2034 -> std::pair<iterator, bool>
2036 return do_insert_or_assign(key, std::forward<M>(mapped));
2041 std::enable_if_t<is_map_v<Q>,
bool> =
true>
2043 insert_or_assign(Key &&key, M &&mapped) -> std::pair<iterator, bool>
2045 return do_insert_or_assign(std::move(key), std::forward<M>(mapped));
2053 typename KE = KeyEqual,
2054 std::enable_if_t<is_map_v<Q> && is_transparent_v<H, KE>,
bool> =
true>
2056 insert_or_assign(K &&key, M &&mapped) -> std::pair<iterator, bool>
2058 return do_insert_or_assign(std::forward<K>(key),
2059 std::forward<M>(mapped));
2064 std::enable_if_t<is_map_v<Q>,
bool> =
true>
2066 insert_or_assign(const_iterator , Key
const &key, M &&mapped)
2069 return do_insert_or_assign(key, std::forward<M>(mapped)).first;
2074 std::enable_if_t<is_map_v<Q>,
bool> =
true>
2076 insert_or_assign(const_iterator , Key &&key, M &&mapped)
2079 return do_insert_or_assign(std::move(key), std::forward<M>(mapped))
2088 typename KE = KeyEqual,
2089 std::enable_if_t<is_map_v<Q> && is_transparent_v<H, KE>,
bool> =
true>
2091 insert_or_assign(const_iterator , K &&key, M &&mapped)
2094 return do_insert_or_assign(std::forward<K>(key),
2095 std::forward<M>(mapped))
2104 typename KE = KeyEqual,
2105 std::enable_if_t<!is_map_v<Q> && is_transparent_v<H, KE>,
2108 emplace(K &&key) -> std::pair<iterator, bool>
2110 auto hash = mixed_hash(key);
2111 auto dist_and_fingerprint = dist_and_fingerprint_from_hash(hash);
2112 auto bucket_idx = bucket_idx_from_hash(hash);
2114 while (dist_and_fingerprint <=
2115 at(m_buckets, bucket_idx).m_dist_and_fingerprint)
2117 if (dist_and_fingerprint ==
2118 at(m_buckets, bucket_idx).m_dist_and_fingerprint &&
2119 m_equal(key, m_values[at(m_buckets, bucket_idx).m_value_idx]))
2122 return {begin() +
static_cast<difference_type
>(
2123 at(m_buckets, bucket_idx).m_value_idx),
2126 dist_and_fingerprint = dist_inc(dist_and_fingerprint);
2127 bucket_idx = next(bucket_idx);
2132 return do_place_element(dist_and_fingerprint,
2134 std::forward<K>(key));
2137 template <
class... Args>
2139 emplace(Args &&...args) -> std::pair<iterator, bool>
2145 get_key(m_values.emplace_back(std::forward<Args>(args)...));
2146 auto hash = mixed_hash(key);
2147 auto dist_and_fingerprint = dist_and_fingerprint_from_hash(hash);
2148 auto bucket_idx = bucket_idx_from_hash(hash);
2150 while (dist_and_fingerprint <=
2151 at(m_buckets, bucket_idx).m_dist_and_fingerprint)
2153 if (dist_and_fingerprint ==
2154 at(m_buckets, bucket_idx).m_dist_and_fingerprint &&
2157 m_values[at(m_buckets, bucket_idx).m_value_idx])))
2161 return {begin() +
static_cast<difference_type
>(
2162 at(m_buckets, bucket_idx).m_value_idx),
2165 dist_and_fingerprint = dist_inc(dist_and_fingerprint);
2166 bucket_idx = next(bucket_idx);
2171 auto value_idx =
static_cast<value_idx_type
>(m_values.size() - 1);
2172 if (ANKERL_UNORDERED_DENSE_UNLIKELY(is_full()))
2180 place_and_shift_up({dist_and_fingerprint, value_idx}, bucket_idx);
2182 return {begin() +
static_cast<difference_type
>(value_idx),
true};
2185 template <
class... Args>
2187 emplace_hint(const_iterator , Args &&...args) -> iterator
2189 return emplace(std::forward<Args>(args)...).first;
2192 template <
class... Args,
2194 std::enable_if_t<is_map_v<Q>,
bool> =
true>
2196 try_emplace(Key
const &key, Args &&...args) -> std::pair<iterator, bool>
2198 return do_try_emplace(key, std::forward<Args>(args)...);
2201 template <
class... Args,
2203 std::enable_if_t<is_map_v<Q>,
bool> =
true>
2205 try_emplace(Key &&key, Args &&...args) -> std::pair<iterator, bool>
2207 return do_try_emplace(std::move(key), std::forward<Args>(args)...);
2210 template <
class... Args,
2212 std::enable_if_t<is_map_v<Q>,
bool> =
true>
2214 try_emplace(const_iterator , Key
const &key, Args &&...args)
2217 return do_try_emplace(key, std::forward<Args>(args)...).first;
2220 template <
class... Args,
2222 std::enable_if_t<is_map_v<Q>,
bool> =
true>
2224 try_emplace(const_iterator , Key &&key, Args &&...args)
2227 return do_try_emplace(std::move(key), std::forward<Args>(args)...)
2231 template <
typename K,
2235 typename KE = KeyEqual,
2237 is_map_v<Q> && is_transparent_v<H, KE> &&
2238 is_neither_convertible_v<K &&, iterator, const_iterator>,
2241 try_emplace(K &&key, Args &&...args) -> std::pair<iterator, bool>
2243 return do_try_emplace(std::forward<K>(key),
2244 std::forward<Args>(args)...);
2247 template <
typename K,
2251 typename KE = KeyEqual,
2253 is_map_v<Q> && is_transparent_v<H, KE> &&
2254 is_neither_convertible_v<K &&, iterator, const_iterator>,
2257 try_emplace(const_iterator , K &&key, Args &&...args)
2260 return do_try_emplace(std::forward<K>(key),
2261 std::forward<Args>(args)...)
2266 erase(iterator it) -> iterator
2268 auto hash = mixed_hash(get_key(*it));
2269 auto bucket_idx = bucket_idx_from_hash(hash);
2271 auto const value_idx_to_remove =
2272 static_cast<value_idx_type
>(it - cbegin());
2273 while (at(m_buckets, bucket_idx).m_value_idx != value_idx_to_remove)
2275 bucket_idx = next(bucket_idx);
2278 do_erase(bucket_idx, [](value_type && ) {});
2279 return begin() +
static_cast<difference_type
>(value_idx_to_remove);
2283 extract(iterator it) -> value_type
2285 auto hash = mixed_hash(get_key(*it));
2286 auto bucket_idx = bucket_idx_from_hash(hash);
2288 auto const value_idx_to_remove =
2289 static_cast<value_idx_type
>(it - cbegin());
2290 while (at(m_buckets, bucket_idx).m_value_idx != value_idx_to_remove)
2292 bucket_idx = next(bucket_idx);
2295 auto tmp = std::optional<value_type>{};
2296 do_erase(bucket_idx,
2297 [&tmp](value_type &&val) { tmp = std::move(val); });
2298 return std::move(tmp).value();
2301 template <
typename Q = T, std::enable_if_t<is_map_v<Q>,
bool> = true>
2303 erase(const_iterator it) -> iterator
2305 return erase(begin() + (it - cbegin()));
2308 template <
typename Q = T, std::enable_if_t<is_map_v<Q>,
bool> = true>
2310 extract(const_iterator it) -> value_type
2312 return extract(begin() + (it - cbegin()));
2316 erase(const_iterator first, const_iterator last) -> iterator
2318 auto const idx_first = first - cbegin();
2319 auto const idx_last = last - cbegin();
2320 auto const first_to_last = std::distance(first, last);
2321 auto const last_to_end = std::distance(last, cend());
2325 auto const mid = idx_first + (std::min)(first_to_last, last_to_end);
2326 auto idx = idx_first;
2329 erase(begin() + idx);
2339 erase(begin() + idx);
2342 return begin() + idx_first;
2346 erase(Key
const &key) ->
size_t
2348 return do_erase_key(key, [](value_type && ) {});
2352 extract(Key
const &key) -> std::optional<value_type>
2354 auto tmp = std::optional<value_type>{};
2355 do_erase_key(key, [&tmp](value_type &&val) { tmp = std::move(val); });
2361 class KE = KeyEqual,
2362 std::enable_if_t<is_transparent_v<H, KE>,
bool> =
true>
2364 erase(K &&key) ->
size_t
2366 return do_erase_key(std::forward<K>(key),
2367 [](value_type && ) {});
2372 class KE = KeyEqual,
2373 std::enable_if_t<is_transparent_v<H, KE>,
bool> =
true>
2375 extract(K &&key) -> std::optional<value_type>
2377 auto tmp = std::optional<value_type>{};
2378 do_erase_key(std::forward<K>(key),
2379 [&tmp](value_type &&val) { tmp = std::move(val); });
2384 swap(table &other)
noexcept(
2385 noexcept(std::is_nothrow_swappable_v<value_container_type>
2386 &&std::is_nothrow_swappable_v<Hash>
2387 &&std::is_nothrow_swappable_v<KeyEqual>))
2396 template <
typename Q = T, std::enable_if_t<is_map_v<Q>,
bool> = true>
2398 at(key_type
const &key) -> Q &
2407 typename KE = KeyEqual,
2408 std::enable_if_t<is_map_v<Q> && is_transparent_v<H, KE>,
bool> =
true>
2410 at(K
const &key) -> Q &
2415 template <
typename Q = T, std::enable_if_t<is_map_v<Q>,
bool> = true>
2417 at(key_type
const &key)
const -> Q
const &
2426 typename KE = KeyEqual,
2427 std::enable_if_t<is_map_v<Q> && is_transparent_v<H, KE>,
bool> =
true>
2429 at(K
const &key)
const -> Q
const &
2434 template <
typename Q = T, std::enable_if_t<is_map_v<Q>,
bool> = true>
2436 operator[](Key
const &key) -> Q &
2438 return try_emplace(key).first->second;
2441 template <
typename Q = T, std::enable_if_t<is_map_v<Q>,
bool> = true>
2443 operator[](Key &&key) -> Q &
2445 return try_emplace(std::move(key)).first->second;
2452 typename KE = KeyEqual,
2453 std::enable_if_t<is_map_v<Q> && is_transparent_v<H, KE>,
bool> =
true>
2455 operator[](K &&key) -> Q &
2457 return try_emplace(std::forward<K>(key)).first->second;
2461 count(Key
const &key)
const ->
size_t
2463 return find(key) == end() ? 0 : 1;
2468 class KE = KeyEqual,
2469 std::enable_if_t<is_transparent_v<H, KE>,
bool> =
true>
2471 count(K
const &key)
const ->
size_t
2473 return find(key) == end() ? 0 : 1;
2477 find(Key
const &key) -> iterator
2479 return do_find(key);
2483 find(Key
const &key)
const -> const_iterator
2485 return do_find(key);
2490 class KE = KeyEqual,
2491 std::enable_if_t<is_transparent_v<H, KE>,
bool> =
true>
2493 find(K
const &key) -> iterator
2495 return do_find(key);
2500 class KE = KeyEqual,
2501 std::enable_if_t<is_transparent_v<H, KE>,
bool> =
true>
2503 find(K
const &key)
const -> const_iterator
2505 return do_find(key);
2509 contains(Key
const &key)
const ->
bool
2511 return find(key) != end();
2516 class KE = KeyEqual,
2517 std::enable_if_t<is_transparent_v<H, KE>,
bool> =
true>
2519 contains(K
const &key)
const ->
bool
2521 return find(key) != end();
2525 equal_range(Key
const &key) -> std::pair<iterator, iterator>
2527 auto it = do_find(key);
2528 return {it, it == end() ? end() : it + 1};
2532 equal_range(
const Key &key)
const
2533 -> std::pair<const_iterator, const_iterator>
2535 auto it = do_find(key);
2536 return {it, it == end() ? end() : it + 1};
2541 class KE = KeyEqual,
2542 std::enable_if_t<is_transparent_v<H, KE>,
bool> =
true>
2544 equal_range(K
const &key) -> std::pair<iterator, iterator>
2546 auto it = do_find(key);
2547 return {it, it == end() ? end() : it + 1};
2552 class KE = KeyEqual,
2553 std::enable_if_t<is_transparent_v<H, KE>,
bool> =
true>
2555 equal_range(K
const &key)
const
2556 -> std::pair<const_iterator, const_iterator>
2558 auto it = do_find(key);
2559 return {it, it == end() ? end() : it + 1};
2566 bucket_count()
const noexcept ->
size_t
2568 return m_num_buckets;
2571 static constexpr auto
2572 max_bucket_count()
noexcept ->
size_t
2581 load_factor()
const ->
float
2583 return bucket_count() ?
static_cast<float>(size()) /
2584 static_cast<float>(bucket_count()) :
2589 max_load_factor()
const ->
float
2591 return m_max_load_factor;
2595 max_load_factor(
float ml)
2597 m_max_load_factor = ml;
2598 if (m_num_buckets != max_bucket_count())
2600 m_max_bucket_capacity =
static_cast<value_idx_type
>(
2601 static_cast<float>(bucket_count()) * max_load_factor());
2606 rehash(
size_t count)
2608 count = (std::min)(count, max_size());
2609 auto shifts = calc_shifts_for_size((std::max)(count, size()));
2610 if (shifts != m_shifts)
2613 deallocate_buckets();
2614 m_values.shrink_to_fit();
2615 allocate_buckets_from_shift();
2616 clear_and_fill_buckets_from_values();
2621 reserve(
size_t capa)
2623 capa = (std::min)(capa, max_size());
2624 if constexpr (has_reserve<value_container_type>)
2628 m_values.reserve(capa);
2630 auto shifts = calc_shifts_for_size((std::max)(capa, size()));
2631 if (0 == m_num_buckets || shifts < m_shifts)
2634 deallocate_buckets();
2635 allocate_buckets_from_shift();
2636 clear_and_fill_buckets_from_values();
2644 hash_function()
const -> hasher
2650 key_eq()
const -> key_equal
2657 values()
const noexcept -> value_container_type
const &
2666 operator==(table
const &a, table
const &b) ->
bool
2672 if (a.size() != b.size())
2676 for (
auto const &b_entry : b)
2678 auto it = a.find(get_key(b_entry));
2679 if constexpr (is_map_v<T>)
2683 if (a.end() == it || !(b_entry.second == it->second))
2701 operator!=(table
const &a, table
const &b) ->
bool
2712 class Hash = hash<Key>,
2713 class KeyEqual = std::equal_to<Key>,
2714 class AllocatorOrContainer = std::allocator<std::pair<Key, T>>,
2715 class Bucket = bucket_type::standard>
2716 using map = detail::
2717 table<Key, T, Hash, KeyEqual, AllocatorOrContainer, Bucket, false>;
2722 class Hash = hash<Key>,
2723 class KeyEqual = std::equal_to<Key>,
2724 class AllocatorOrContainer = std::allocator<std::pair<Key, T>>,
2725 class Bucket = bucket_type::standard>
2726 using segmented_map =
2727 detail::table<Key, T, Hash, KeyEqual, AllocatorOrContainer, Bucket, true>;
2731 class Hash = hash<Key>,
2732 class KeyEqual = std::equal_to<Key>,
2733 class AllocatorOrContainer = std::allocator<Key>,
2734 class Bucket = bucket_type::standard>
2735 using set = detail::
2736 table<Key, void, Hash, KeyEqual, AllocatorOrContainer, Bucket, false>;
2740 class Hash = hash<Key>,
2741 class KeyEqual = std::equal_to<Key>,
2742 class AllocatorOrContainer = std::allocator<Key>,
2743 class Bucket = bucket_type::standard>
2744 using segmented_set = detail::
2745 table<Key, void, Hash, KeyEqual, AllocatorOrContainer, Bucket, true>;
2747# if defined(ANKERL_UNORDERED_DENSE_PMR)
2755 class Hash = hash<Key>,
2756 class KeyEqual = std::equal_to<Key>,
2757 class Bucket = bucket_type::standard>
2758 using map = detail::table<
2763 ANKERL_UNORDERED_DENSE_PMR::polymorphic_allocator<std::pair<Key, T>>,
2770 class Hash = hash<Key>,
2771 class KeyEqual = std::equal_to<Key>,
2772 class Bucket = bucket_type::standard>
2773 using segmented_map = detail::table<
2778 ANKERL_UNORDERED_DENSE_PMR::polymorphic_allocator<std::pair<Key, T>>,
2784 class Hash = hash<Key>,
2785 class KeyEqual = std::equal_to<Key>,
2786 class Bucket = bucket_type::standard>
2792 ANKERL_UNORDERED_DENSE_PMR::polymorphic_allocator<Key>,
2798 class Hash = hash<Key>,
2799 class KeyEqual = std::equal_to<Key>,
2800 class Bucket = bucket_type::standard>
2801 using segmented_set =
2806 ANKERL_UNORDERED_DENSE_PMR::polymorphic_allocator<Key>,
2833 class AllocatorOrContainer,
2840 ankerl::unordered_dense::detail::
2841 table<Key, T, Hash, KeyEqual, AllocatorOrContainer, Bucket, IsSegmented>
2843 Pred pred) ->
size_t
2845 using map_t = ankerl::unordered_dense::detail::
2846 table<Key, T, Hash, KeyEqual, AllocatorOrContainer, Bucket, IsSegmented>;
2849 auto const old_size = map.size();
2850 auto idx = old_size;
2855 map.begin() +
static_cast<typename map_t::difference_type
>(idx);
2862 return old_size - map.size();
@ standard
Standard Navier-Stokes equations.
#define ANKERL_UNORDERED_DENSE_NAMESPACE
#define ANKERL_UNORDERED_DENSE_NOINLINE
#define ANKERL_UNORDERED_DENSE_EXPORT