29 #ifndef ANKERL_UNORDERED_DENSE_H
30 #define ANKERL_UNORDERED_DENSE_H
33 #define ANKERL_UNORDERED_DENSE_VERSION_MAJOR 4
34 #define ANKERL_UNORDERED_DENSE_VERSION_MINOR 4
35 #define ANKERL_UNORDERED_DENSE_VERSION_PATCH 0
40 #define ANKERL_UNORDERED_DENSE_VERSION_CONCAT1(major, minor, patch) v##major##_##minor##_##patch
42 #define ANKERL_UNORDERED_DENSE_VERSION_CONCAT(major, minor, patch) ANKERL_UNORDERED_DENSE_VERSION_CONCAT1(major, minor, patch)
43 #define ANKERL_UNORDERED_DENSE_NAMESPACE \
44 ANKERL_UNORDERED_DENSE_VERSION_CONCAT( \
45 ANKERL_UNORDERED_DENSE_VERSION_MAJOR, ANKERL_UNORDERED_DENSE_VERSION_MINOR, ANKERL_UNORDERED_DENSE_VERSION_PATCH)
47 #if defined(_MSVC_LANG)
48 # define ANKERL_UNORDERED_DENSE_CPP_VERSION _MSVC_LANG
50 # define ANKERL_UNORDERED_DENSE_CPP_VERSION __cplusplus
55 # define ANKERL_UNORDERED_DENSE_PACK(decl) decl __attribute__((__packed__))
56 #elif defined(_MSC_VER)
58 # define ANKERL_UNORDERED_DENSE_PACK(decl) __pragma(pack(push, 1)) decl __pragma(pack(pop))
62 #if defined(__cpp_exceptions) || defined(__EXCEPTIONS) || defined(_CPPUNWIND)
63 # define ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS() 1
65 # define ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS() 0
68 # define ANKERL_UNORDERED_DENSE_NOINLINE __declspec(noinline)
70 # define ANKERL_UNORDERED_DENSE_NOINLINE __attribute__((noinline))
74 #if !defined(ANKERL_UNORDERED_DENSE_EXPORT)
75 # define ANKERL_UNORDERED_DENSE_EXPORT
78 #if ANKERL_UNORDERED_DENSE_CPP_VERSION < 201703L
79 # error ankerl::unordered_dense requires C++17 or higher
84 # include <functional>
85 # include <initializer_list>
92 # include <string_view>
94 # include <type_traits>
97 # if ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS() == 0
101 # if defined(__has_include)
102 # if __has_include(<memory_resource>)
103 # define ANKERL_UNORDERED_DENSE_PMR std::pmr
104 # include <memory_resource>
105 # elif __has_include(<experimental/memory_resource>)
106 # define ANKERL_UNORDERED_DENSE_PMR std::experimental::pmr
107 # include <experimental/memory_resource>
111 # if defined(_MSC_VER) && defined(_M_X64)
113 # pragma intrinsic(_umul128)
116 # if defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__clang__)
117 # define ANKERL_UNORDERED_DENSE_LIKELY(x) __builtin_expect(x, 1)
118 # define ANKERL_UNORDERED_DENSE_UNLIKELY(x) __builtin_expect(x, 0)
120 # define ANKERL_UNORDERED_DENSE_LIKELY(x) (x)
121 # define ANKERL_UNORDERED_DENSE_UNLIKELY(x) (x)
124 namespace ankerl::unordered_dense {
125 inline namespace ANKERL_UNORDERED_DENSE_NAMESPACE {
129 # if ANKERL_UNORDERED_DENSE_HAS_EXCEPTIONS()
133 [[noreturn]]
inline ANKERL_UNORDERED_DENSE_NOINLINE
void on_error_key_not_found() {
134 throw std::out_of_range(
"ankerl::unordered_dense::map::at(): key not found");
136 [[noreturn]]
inline ANKERL_UNORDERED_DENSE_NOINLINE
void on_error_bucket_overflow() {
137 throw std::overflow_error(
"ankerl::unordered_dense: reached max bucket size, cannot increase size");
139 [[noreturn]]
inline ANKERL_UNORDERED_DENSE_NOINLINE
void on_error_too_many_elements() {
140 throw std::out_of_range(
"ankerl::unordered_dense::map::replace(): too many elements");
145 [[noreturn]]
inline void on_error_key_not_found() {
148 [[noreturn]]
inline void on_error_bucket_overflow() {
151 [[noreturn]]
inline void on_error_too_many_elements() {
164 namespace detail::wyhash {
166 inline void mum(uint64_t* a, uint64_t* b) {
167 # if defined(__SIZEOF_INT128__)
170 *a =
static_cast<uint64_t
>(r);
171 *b =
static_cast<uint64_t
>(r >> 64U);
172 # elif defined(_MSC_VER) && defined(_M_X64)
173 *a = _umul128(*a, *b, b);
175 uint64_t ha = *a >> 32U;
176 uint64_t hb = *b >> 32U;
177 uint64_t la =
static_cast<uint32_t
>(*a);
178 uint64_t lb =
static_cast<uint32_t
>(*b);
181 uint64_t rh = ha * hb;
182 uint64_t rm0 = ha * lb;
183 uint64_t rm1 = hb * la;
184 uint64_t rl = la * lb;
185 uint64_t t = rl + (rm0 << 32U);
186 auto c =
static_cast<uint64_t
>(t < rl);
187 lo = t + (rm1 << 32U);
188 c +=
static_cast<uint64_t
>(lo < t);
189 hi = rh + (rm0 >> 32U) + (rm1 >> 32U) + c;
196 [[nodiscard]]
inline auto mix(uint64_t a, uint64_t b) -> uint64_t {
202 [[nodiscard]]
inline auto r8(
const uint8_t* p) -> uint64_t {
204 std::memcpy(&v, p, 8U);
208 [[nodiscard]]
inline auto r4(
const uint8_t* p) -> uint64_t {
210 std::memcpy(&v, p, 4);
215 [[nodiscard]]
inline auto r3(
const uint8_t* p,
size_t k) -> uint64_t {
216 return (
static_cast<uint64_t
>(p[0]) << 16U) | (
static_cast<uint64_t
>(p[k >> 1U]) << 8U) | p[k - 1];
219 [[maybe_unused]] [[nodiscard]]
inline auto hash(
void const* key,
size_t len) -> uint64_t {
220 static constexpr
auto secret = std::array{UINT64_C(0xa0761d6478bd642f),
221 UINT64_C(0xe7037ed1a0b428db),
222 UINT64_C(0x8ebc6af09c88c6e3),
223 UINT64_C(0x589965cc75374cc3)};
225 auto const* p =
static_cast<uint8_t const*
>(key);
226 uint64_t seed = secret[0];
229 if (ANKERL_UNORDERED_DENSE_LIKELY(len <= 16)) {
230 if (ANKERL_UNORDERED_DENSE_LIKELY(len >= 4)) {
231 a = (r4(p) << 32U) | r4(p + ((len >> 3U) << 2U));
232 b = (r4(p + len - 4) << 32U) | r4(p + len - 4 - ((len >> 3U) << 2U));
233 }
else if (ANKERL_UNORDERED_DENSE_LIKELY(len > 0)) {
242 if (ANKERL_UNORDERED_DENSE_UNLIKELY(i > 48)) {
243 uint64_t see1 = seed;
244 uint64_t see2 = seed;
246 seed = mix(r8(p) ^ secret[1], r8(p + 8) ^ seed);
247 see1 = mix(r8(p + 16) ^ secret[2], r8(p + 24) ^ see1);
248 see2 = mix(r8(p + 32) ^ secret[3], r8(p + 40) ^ see2);
251 }
while (ANKERL_UNORDERED_DENSE_LIKELY(i > 48));
254 while (ANKERL_UNORDERED_DENSE_UNLIKELY(i > 16)) {
255 seed = mix(r8(p) ^ secret[1], r8(p + 8) ^ seed);
263 return mix(secret[1] ^ len, mix(a ^ secret[1], b ^ seed));
266 [[nodiscard]]
inline auto hash(uint64_t x) -> uint64_t {
267 return detail::wyhash::mix(x, UINT64_C(0x9E3779B97F4A7C15));
272 ANKERL_UNORDERED_DENSE_EXPORT
template <
typename T,
typename Enable =
void>
274 auto operator()(T
const& obj)
const
275 noexcept(noexcept(std::declval<std::hash<T>>().
operator()(std::declval<T const&>()))) -> uint64_t {
276 return std::hash<T>{}(obj);
280 template <
typename T>
281 struct hash<T, typename std::hash<T>::is_avalanching> {
282 using is_avalanching = void;
283 auto operator()(T
const& obj)
const
284 noexcept(noexcept(std::declval<std::hash<T>>().
operator()(std::declval<T const&>()))) -> uint64_t {
285 return std::hash<T>{}(obj);
289 template <
typename CharT>
290 struct hash<std::basic_string<CharT>> {
291 using is_avalanching = void;
292 auto operator()(std::basic_string<CharT>
const& str)
const noexcept -> uint64_t {
293 return detail::wyhash::hash(str.data(),
sizeof(CharT) * str.size());
297 template <
typename CharT>
298 struct hash<std::basic_string_view<CharT>> {
299 using is_avalanching = void;
300 auto operator()(std::basic_string_view<CharT>
const& sv)
const noexcept -> uint64_t {
301 return detail::wyhash::hash(sv.data(),
sizeof(CharT) * sv.size());
307 using is_avalanching = void;
308 auto operator()(T* ptr)
const noexcept -> uint64_t {
310 return detail::wyhash::hash(
reinterpret_cast<uintptr_t
>(ptr));
315 struct hash<std::unique_ptr<T>> {
316 using is_avalanching = void;
317 auto operator()(std::unique_ptr<T>
const& ptr)
const noexcept -> uint64_t {
319 return detail::wyhash::hash(
reinterpret_cast<uintptr_t
>(ptr.get()));
324 struct hash<std::shared_ptr<T>> {
325 using is_avalanching = void;
326 auto operator()(std::shared_ptr<T>
const& ptr)
const noexcept -> uint64_t {
328 return detail::wyhash::hash(
reinterpret_cast<uintptr_t
>(ptr.get()));
332 template <
typename Enum>
333 struct hash<Enum, typename std::enable_if<std::is_enum<Enum>::value>::type> {
334 using is_avalanching = void;
335 auto operator()(Enum e)
const noexcept -> uint64_t {
336 using underlying =
typename std::underlying_type_t<Enum>;
337 return detail::wyhash::hash(
static_cast<underlying
>(e));
341 template <
typename... Args>
342 struct tuple_hash_helper {
345 template <
typename Arg>
346 [[nodiscard]] constexpr
static auto to64(Arg
const& arg) -> uint64_t {
347 if constexpr (std::is_integral_v<Arg> || std::is_enum_v<Arg>) {
348 return static_cast<uint64_t
>(arg);
350 return hash<Arg>{}(arg);
354 [[nodiscard]]
static auto mix64(uint64_t state, uint64_t v) -> uint64_t {
355 return detail::wyhash::mix(state + v, uint64_t{0x9ddfea08eb382d69});
361 template <
typename T, std::size_t... Idx>
362 [[nodiscard]]
static auto calc_hash(T
const& t, std::index_sequence<Idx...>) noexcept -> uint64_t {
364 ((h = mix64(h, to64(std::get<Idx>(t)))), ...);
369 template <
typename... Args>
370 struct hash<std::tuple<Args...>> : tuple_hash_helper<Args...> {
371 using is_avalanching = void;
372 auto operator()(std::tuple<Args...>
const& t)
const noexcept -> uint64_t {
373 return tuple_hash_helper<Args...>::calc_hash(t, std::index_sequence_for<Args...>{});
377 template <
typename A,
typename B>
378 struct hash<std::pair<A, B>> : tuple_hash_helper<A, B> {
379 using is_avalanching = void;
380 auto operator()(std::pair<A, B>
const& t)
const noexcept -> uint64_t {
381 return tuple_hash_helper<A, B>::calc_hash(t, std::index_sequence_for<A, B>{});
386 # define ANKERL_UNORDERED_DENSE_HASH_STATICCAST(T) \
389 using is_avalanching = void; \
390 auto operator()(T const& obj) const noexcept -> uint64_t { \
391 return detail::wyhash::hash(static_cast<uint64_t>(obj)); \
395 # if defined(__GNUC__) && !defined(__clang__)
396 # pragma GCC diagnostic push
397 # pragma GCC diagnostic ignored "-Wuseless-cast"
400 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
bool);
401 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
char);
402 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
signed char);
403 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
unsigned char);
404 # if ANKERL_UNORDERED_DENSE_CPP_VERSION >= 202002L && defined(__cpp_char8_t)
405 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(char8_t);
407 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(char16_t);
408 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(char32_t);
409 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
wchar_t);
410 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
short);
411 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
unsigned short);
412 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
int);
413 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
unsigned int);
414 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
long);
415 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
long long);
416 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
unsigned long);
417 ANKERL_UNORDERED_DENSE_HASH_STATICCAST(
unsigned long long);
419 # if defined(__GNUC__) && !defined(__clang__)
420 # pragma GCC diagnostic pop
425 namespace bucket_type {
428 static constexpr uint32_t dist_inc = 1U << 8U;
429 static constexpr uint32_t fingerprint_mask = dist_inc - 1;
431 uint32_t m_dist_and_fingerprint;
432 uint32_t m_value_idx;
435 ANKERL_UNORDERED_DENSE_PACK(
struct big {
436 static constexpr uint32_t dist_inc = 1U << 8U;
437 static constexpr uint32_t fingerprint_mask = dist_inc - 1;
439 uint32_t m_dist_and_fingerprint;
448 struct default_container_t {};
450 template <
class Default,
class AlwaysVoid,
template <
class...>
class Op,
class... Args>
452 using value_t = std::false_type;
453 using type = Default;
456 template <
class Default,
template <
class...>
class Op,
class... Args>
457 struct detector<Default, std::void_t<Op<Args...>>, Op, Args...> {
458 using value_t = std::true_type;
459 using type = Op<Args...>;
462 template <
template <
class...>
class Op,
class... Args>
463 using is_detected =
typename detail::detector<detail::nonesuch, void, Op, Args...>::value_t;
465 template <
template <
class...>
class Op,
class... Args>
466 constexpr
bool is_detected_v = is_detected<Op, Args...>::value;
468 template <
typename T>
469 using detect_avalanching =
typename T::is_avalanching;
471 template <
typename T>
472 using detect_is_transparent =
typename T::is_transparent;
474 template <
typename T>
475 using detect_iterator =
typename T::iterator;
477 template <
typename T>
478 using detect_reserve = decltype(std::declval<T&>().reserve(
size_t{}));
482 template <
typename Mapped>
483 constexpr
bool is_map_v = !std::is_void_v<Mapped>;
486 template <
typename Hash,
typename KeyEqual>
487 constexpr
bool is_transparent_v = is_detected_v<detect_is_transparent, Hash> && is_detected_v<detect_is_transparent, KeyEqual>;
490 template <
typename From,
typename To1,
typename To2>
491 constexpr
bool is_neither_convertible_v = !std::is_convertible_v<From, To1> && !std::is_convertible_v<From, To2>;
493 template <
typename T>
494 constexpr
bool has_reserve = is_detected_v<detect_reserve, T>;
498 struct base_table_type_map {
499 using mapped_type = T;
503 struct base_table_type_set {};
512 template <
typename T,
typename Allocator = std::allocator<T>,
size_t MaxSegmentSizeBytes = 4096>
513 class segmented_vector {
514 template <
bool IsConst>
518 using allocator_type = Allocator;
519 using pointer =
typename std::allocator_traits<allocator_type>::pointer;
520 using const_pointer =
typename std::allocator_traits<allocator_type>::const_pointer;
521 using difference_type =
typename std::allocator_traits<allocator_type>::difference_type;
522 using value_type = T;
523 using size_type = std::size_t;
524 using reference = T&;
525 using const_reference = T
const&;
526 using iterator = iter_t<false>;
527 using const_iterator = iter_t<true>;
530 using vec_alloc =
typename std::allocator_traits<Allocator>::template rebind_alloc<pointer>;
531 std::vector<pointer, vec_alloc> m_blocks{};
535 static constexpr
auto num_bits_closest(
size_t max_val,
size_t s) ->
size_t {
537 while (s << (f + 1) <= max_val) {
543 using self_t = segmented_vector<T, Allocator, MaxSegmentSizeBytes>;
544 static constexpr
auto num_bits = num_bits_closest(MaxSegmentSizeBytes,
sizeof(T));
545 static constexpr
auto num_elements_in_block = 1U << num_bits;
546 static constexpr
auto mask = num_elements_in_block - 1U;
551 template <
bool IsConst>
553 using ptr_t =
typename std::conditional_t<IsConst, segmented_vector::const_pointer const*, segmented_vector::pointer*>;
561 using difference_type = segmented_vector::difference_type;
562 using value_type = T;
563 using reference =
typename std::conditional_t<IsConst, value_type const&, value_type&>;
564 using pointer =
typename std::conditional_t<IsConst, segmented_vector::const_pointer, segmented_vector::pointer>;
565 using iterator_category = std::forward_iterator_tag;
567 iter_t() noexcept = default;
569 template <
bool OtherIsConst, typename = typename std::enable_if<IsConst && !OtherIsConst>::type>
571 constexpr iter_t(iter_t<OtherIsConst> const& other) noexcept
572 : m_data(other.m_data)
573 , m_idx(other.m_idx) {}
575 constexpr iter_t(ptr_t data,
size_t idx) noexcept
579 template <bool OtherIsConst, typename = typename std::enable_if<IsConst && !OtherIsConst>::type>
580 constexpr
auto operator=(iter_t<OtherIsConst>
const& other) noexcept -> iter_t& {
581 m_data = other.m_data;
586 constexpr
auto operator++() noexcept -> iter_t& {
591 constexpr
auto operator+(difference_type diff) noexcept -> iter_t {
592 return {m_data,
static_cast<size_t>(
static_cast<difference_type
>(m_idx) + diff)};
595 template <
bool OtherIsConst>
596 constexpr
auto operator-(iter_t<OtherIsConst>
const& other) noexcept -> difference_type {
597 return static_cast<difference_type
>(m_idx) -
static_cast<difference_type
>(other.m_idx);
600 constexpr
auto operator*() const noexcept -> reference {
601 return m_data[m_idx >> num_bits][m_idx & mask];
604 constexpr
auto operator->() const noexcept -> pointer {
605 return &m_data[m_idx >> num_bits][m_idx & mask];
609 constexpr
auto operator==(iter_t<O>
const& o)
const noexcept ->
bool {
610 return m_idx == o.m_idx;
614 constexpr
auto operator!=(iter_t<O>
const& o)
const noexcept ->
bool {
615 return !(*
this == o);
620 void increase_capacity() {
621 auto ba = Allocator(m_blocks.get_allocator());
622 pointer block = std::allocator_traits<Allocator>::allocate(ba, num_elements_in_block);
623 m_blocks.push_back(block);
627 void append_everything_from(segmented_vector&& other) {
628 reserve(size() + other.size());
629 for (
auto&& o : other) {
630 emplace_back(std::move(o));
635 void append_everything_from(segmented_vector
const& other) {
636 reserve(size() + other.size());
637 for (
auto const& o : other) {
643 auto ba = Allocator(m_blocks.get_allocator());
644 for (
auto ptr : m_blocks) {
645 std::allocator_traits<Allocator>::deallocate(ba, ptr, num_elements_in_block);
649 [[nodiscard]]
static constexpr
auto calc_num_blocks_for_capacity(
size_t capacity) {
650 return (capacity + num_elements_in_block - 1U) / num_elements_in_block;
654 segmented_vector() =
default;
657 segmented_vector(Allocator alloc)
658 : m_blocks(vec_alloc(alloc)) {}
660 segmented_vector(segmented_vector&& other, Allocator alloc)
661 : segmented_vector(alloc) {
662 *
this = std::move(other);
665 segmented_vector(segmented_vector
const& other, Allocator alloc)
666 : m_blocks(vec_alloc(alloc)) {
667 append_everything_from(other);
670 segmented_vector(segmented_vector&& other) noexcept
671 : segmented_vector(std::move(other), get_allocator()) {}
673 segmented_vector(segmented_vector
const& other) {
674 append_everything_from(other);
677 auto operator=(segmented_vector
const& other) -> segmented_vector& {
678 if (
this == &other) {
682 append_everything_from(other);
686 auto operator=(segmented_vector&& other) noexcept -> segmented_vector& {
689 if (other.get_allocator() == get_allocator()) {
690 m_blocks = std::move(other.m_blocks);
691 m_size = std::exchange(other.m_size, {});
694 m_blocks = std::vector<pointer, vec_alloc>(vec_alloc(other.get_allocator()));
695 append_everything_from(std::move(other));
700 ~segmented_vector() {
705 [[nodiscard]] constexpr
auto size() const ->
size_t {
709 [[nodiscard]] constexpr
auto capacity() const ->
size_t {
710 return m_blocks.size() * num_elements_in_block;
714 [[nodiscard]] constexpr
auto operator[](
size_t i)
const noexcept -> T
const& {
715 return m_blocks[i >> num_bits][i & mask];
718 [[nodiscard]] constexpr
auto operator[](
size_t i) noexcept -> T& {
719 return m_blocks[i >> num_bits][i & mask];
722 [[nodiscard]] constexpr
auto begin() -> iterator {
723 return {m_blocks.data(), 0U};
725 [[nodiscard]] constexpr
auto begin() const -> const_iterator {
726 return {m_blocks.data(), 0U};
728 [[nodiscard]] constexpr
auto cbegin() const -> const_iterator {
729 return {m_blocks.data(), 0U};
732 [[nodiscard]] constexpr
auto end() -> iterator {
733 return {m_blocks.data(), m_size};
735 [[nodiscard]] constexpr
auto end() const -> const_iterator {
736 return {m_blocks.data(), m_size};
738 [[nodiscard]] constexpr
auto cend() const -> const_iterator {
739 return {m_blocks.data(), m_size};
742 [[nodiscard]] constexpr
auto back() -> reference {
743 return operator[](m_size - 1);
745 [[nodiscard]] constexpr
auto back() const -> const_reference {
746 return operator[](m_size - 1);
754 [[nodiscard]]
auto empty()
const {
758 void reserve(
size_t new_capacity) {
759 m_blocks.reserve(calc_num_blocks_for_capacity(new_capacity));
760 while (new_capacity > capacity()) {
765 [[nodiscard]]
auto get_allocator() const -> allocator_type {
766 return allocator_type{m_blocks.get_allocator()};
769 template <
class... Args>
770 auto emplace_back(Args&&... args) -> reference {
771 if (m_size == capacity()) {
774 auto* ptr =
static_cast<void*
>(&operator[](m_size));
775 auto& ref = *
new (ptr) T(std::forward<Args>(args)...);
781 if constexpr (!std::is_trivially_destructible_v<T>) {
782 for (
size_t i = 0, s = size(); i < s; ++i) {
789 void shrink_to_fit() {
790 auto ba = Allocator(m_blocks.get_allocator());
791 auto num_blocks_required = calc_num_blocks_for_capacity(m_size);
792 while (m_blocks.size() > num_blocks_required) {
793 std::allocator_traits<Allocator>::deallocate(ba, m_blocks.back(), num_elements_in_block);
796 m_blocks.shrink_to_fit();
807 class AllocatorOrContainer,
809 class BucketContainer,
811 class table :
public std::conditional_t<is_map_v<T>, base_table_type_map<T>, base_table_type_set> {
812 using underlying_value_type =
typename std::conditional_t<is_map_v<T>, std::pair<Key, T>, Key>;
813 using underlying_container_type = std::conditional_t<IsSegmented,
814 segmented_vector<underlying_value_type, AllocatorOrContainer>,
815 std::vector<underlying_value_type, AllocatorOrContainer>>;
818 using value_container_type = std::
819 conditional_t<is_detected_v<detect_iterator, AllocatorOrContainer>, AllocatorOrContainer, underlying_container_type>;
823 typename std::allocator_traits<typename value_container_type::allocator_type>::template rebind_alloc<Bucket>;
824 using default_bucket_container_type =
825 std::conditional_t<IsSegmented, segmented_vector<Bucket, bucket_alloc>, std::vector<Bucket, bucket_alloc>>;
827 using bucket_container_type = std::conditional_t<std::is_same_v<BucketContainer, detail::default_container_t>,
828 default_bucket_container_type,
831 static constexpr uint8_t initial_shifts = 64 - 2;
832 static constexpr
float default_max_load_factor = 0.8F;
835 using key_type = Key;
836 using value_type =
typename value_container_type::value_type;
837 using size_type =
typename value_container_type::size_type;
838 using difference_type =
typename value_container_type::difference_type;
840 using key_equal = KeyEqual;
841 using allocator_type =
typename value_container_type::allocator_type;
842 using reference =
typename value_container_type::reference;
843 using const_reference =
typename value_container_type::const_reference;
844 using pointer =
typename value_container_type::pointer;
845 using const_pointer =
typename value_container_type::const_pointer;
846 using const_iterator =
typename value_container_type::const_iterator;
847 using iterator = std::conditional_t<is_map_v<T>,
typename value_container_type::iterator, const_iterator>;
848 using bucket_type = Bucket;
851 using value_idx_type = decltype(Bucket::m_value_idx);
852 using dist_and_fingerprint_type = decltype(Bucket::m_dist_and_fingerprint);
854 static_assert(std::is_trivially_destructible_v<Bucket>,
"assert there's no need to call destructor / std::destroy");
855 static_assert(std::is_trivially_copyable_v<Bucket>,
"assert we can just memset / memcpy");
857 value_container_type m_values{};
858 bucket_container_type m_buckets{};
859 size_t m_max_bucket_capacity = 0;
860 float m_max_load_factor = default_max_load_factor;
863 uint8_t m_shifts = initial_shifts;
865 [[nodiscard]]
auto next(value_idx_type bucket_idx)
const -> value_idx_type {
866 return ANKERL_UNORDERED_DENSE_UNLIKELY(bucket_idx + 1U == bucket_count())
868 :
static_cast<value_idx_type
>(bucket_idx + 1U);
872 [[nodiscard]]
static constexpr
auto at(bucket_container_type& bucket,
size_t offset) -> Bucket& {
873 return bucket[offset];
876 [[nodiscard]]
static constexpr
auto at(
const bucket_container_type& bucket,
size_t offset) ->
const Bucket& {
877 return bucket[offset];
881 [[nodiscard]]
static constexpr
auto dist_inc(dist_and_fingerprint_type x) -> dist_and_fingerprint_type {
882 return static_cast<dist_and_fingerprint_type
>(x + Bucket::dist_inc);
885 [[nodiscard]]
static constexpr
auto dist_dec(dist_and_fingerprint_type x) -> dist_and_fingerprint_type {
886 return static_cast<dist_and_fingerprint_type
>(x - Bucket::dist_inc);
890 template <
typename K>
891 [[nodiscard]] constexpr
auto mixed_hash(K
const& key)
const -> uint64_t {
892 if constexpr (is_detected_v<detect_avalanching, Hash>) {
894 if constexpr (
sizeof(decltype(m_hash(key))) <
sizeof(uint64_t)) {
896 return m_hash(key) * UINT64_C(0x9ddfea08eb382d69);
903 return wyhash::hash(m_hash(key));
907 [[nodiscard]] constexpr
auto dist_and_fingerprint_from_hash(uint64_t hash)
const -> dist_and_fingerprint_type {
908 return Bucket::dist_inc | (
static_cast<dist_and_fingerprint_type
>(hash) & Bucket::fingerprint_mask);
911 [[nodiscard]] constexpr
auto bucket_idx_from_hash(uint64_t hash)
const -> value_idx_type {
912 return static_cast<value_idx_type
>(hash >> m_shifts);
915 [[nodiscard]]
static constexpr
auto get_key(value_type
const& vt) -> key_type
const& {
916 if constexpr (is_map_v<T>) {
923 template <
typename K>
924 [[nodiscard]]
auto next_while_less(K
const& key)
const -> Bucket {
925 auto hash = mixed_hash(key);
926 auto dist_and_fingerprint = dist_and_fingerprint_from_hash(hash);
927 auto bucket_idx = bucket_idx_from_hash(hash);
929 while (dist_and_fingerprint < at(m_buckets, bucket_idx).m_dist_and_fingerprint) {
930 dist_and_fingerprint = dist_inc(dist_and_fingerprint);
931 bucket_idx = next(bucket_idx);
933 return {dist_and_fingerprint, bucket_idx};
936 void place_and_shift_up(Bucket bucket, value_idx_type place) {
937 while (0 != at(m_buckets, place).m_dist_and_fingerprint) {
938 bucket = std::exchange(at(m_buckets, place), bucket);
939 bucket.m_dist_and_fingerprint = dist_inc(bucket.m_dist_and_fingerprint);
942 at(m_buckets, place) = bucket;
945 [[nodiscard]]
static constexpr
auto calc_num_buckets(uint8_t shifts) ->
size_t {
946 return (std::min)(max_bucket_count(),
size_t{1} << (64U - shifts));
949 [[nodiscard]] constexpr
auto calc_shifts_for_size(
size_t s)
const -> uint8_t {
950 auto shifts = initial_shifts;
951 while (shifts > 0 &&
static_cast<size_t>(
static_cast<float>(calc_num_buckets(shifts)) * max_load_factor()) < s) {
958 void copy_buckets(table
const& other) {
962 allocate_buckets_from_shift();
965 m_shifts = other.m_shifts;
966 allocate_buckets_from_shift();
967 if constexpr (IsSegmented || !std::is_same_v<BucketContainer, default_container_t>) {
968 for (
auto i = 0UL; i < bucket_count(); ++i) {
969 at(m_buckets, i) = at(other.m_buckets, i);
972 std::memcpy(m_buckets.data(), other.m_buckets.data(),
sizeof(Bucket) * bucket_count());
980 [[nodiscard]]
auto is_full() const ->
bool {
981 return size() > m_max_bucket_capacity;
984 void deallocate_buckets() {
986 m_buckets.shrink_to_fit();
987 m_max_bucket_capacity = 0;
990 void allocate_buckets_from_shift() {
991 auto num_buckets = calc_num_buckets(m_shifts);
992 if constexpr (IsSegmented || !std::is_same_v<BucketContainer, default_container_t>) {
993 if constexpr (has_reserve<bucket_container_type>) {
994 m_buckets.reserve(num_buckets);
996 for (
size_t i = m_buckets.size(); i < num_buckets; ++i) {
997 m_buckets.emplace_back();
1000 m_buckets.resize(num_buckets);
1002 if (num_buckets == max_bucket_count()) {
1004 m_max_bucket_capacity = max_bucket_count();
1006 m_max_bucket_capacity =
static_cast<value_idx_type
>(
static_cast<float>(num_buckets) * max_load_factor());
1010 void clear_buckets() {
1011 if constexpr (IsSegmented || !std::is_same_v<BucketContainer, default_container_t>) {
1012 for (
auto&& e : m_buckets) {
1013 std::memset(&e, 0,
sizeof(e));
1016 std::memset(m_buckets.data(), 0,
sizeof(Bucket) * bucket_count());
1020 void clear_and_fill_buckets_from_values() {
1022 for (value_idx_type value_idx = 0, end_idx =
static_cast<value_idx_type
>(m_values.size()); value_idx < end_idx;
1024 auto const& key = get_key(m_values[value_idx]);
1025 auto [dist_and_fingerprint, bucket] = next_while_less(key);
1028 place_and_shift_up({dist_and_fingerprint, value_idx}, bucket);
1032 void increase_size() {
1033 if (m_max_bucket_capacity == max_bucket_count()) {
1035 m_values.pop_back();
1036 on_error_bucket_overflow();
1039 if constexpr (!IsSegmented || std::is_same_v<BucketContainer, default_container_t>) {
1040 deallocate_buckets();
1042 allocate_buckets_from_shift();
1043 clear_and_fill_buckets_from_values();
1046 template <
typename Op>
1047 void do_erase(value_idx_type bucket_idx, Op handle_erased_value) {
1048 auto const value_idx_to_remove = at(m_buckets, bucket_idx).m_value_idx;
1051 auto next_bucket_idx = next(bucket_idx);
1052 while (at(m_buckets, next_bucket_idx).m_dist_and_fingerprint >= Bucket::dist_inc * 2) {
1053 at(m_buckets, bucket_idx) = {dist_dec(at(m_buckets, next_bucket_idx).m_dist_and_fingerprint),
1054 at(m_buckets, next_bucket_idx).m_value_idx};
1055 bucket_idx = std::exchange(next_bucket_idx, next(next_bucket_idx));
1057 at(m_buckets, bucket_idx) = {};
1058 handle_erased_value(std::move(m_values[value_idx_to_remove]));
1061 if (value_idx_to_remove != m_values.size() - 1) {
1063 auto& val = m_values[value_idx_to_remove];
1064 val = std::move(m_values.back());
1067 auto mh = mixed_hash(get_key(val));
1068 bucket_idx = bucket_idx_from_hash(mh);
1070 auto const values_idx_back =
static_cast<value_idx_type
>(m_values.size() - 1);
1071 while (values_idx_back != at(m_buckets, bucket_idx).m_value_idx) {
1072 bucket_idx = next(bucket_idx);
1074 at(m_buckets, bucket_idx).m_value_idx = value_idx_to_remove;
1076 m_values.pop_back();
1079 template <
typename K,
typename Op>
1080 auto do_erase_key(K&& key, Op handle_erased_value) ->
size_t {
1085 auto [dist_and_fingerprint, bucket_idx] = next_while_less(key);
1087 while (dist_and_fingerprint == at(m_buckets, bucket_idx).m_dist_and_fingerprint &&
1088 !m_equal(key, get_key(m_values[at(m_buckets, bucket_idx).m_value_idx]))) {
1089 dist_and_fingerprint = dist_inc(dist_and_fingerprint);
1090 bucket_idx = next(bucket_idx);
1093 if (dist_and_fingerprint != at(m_buckets, bucket_idx).m_dist_and_fingerprint) {
1096 do_erase(bucket_idx, handle_erased_value);
1100 template <
class K,
class M>
1101 auto do_insert_or_assign(K&& key, M&& mapped) -> std::pair<iterator, bool> {
1102 auto it_isinserted = try_emplace(std::forward<K>(key), std::forward<M>(mapped));
1103 if (!it_isinserted.second) {
1104 it_isinserted.first->second = std::forward<M>(mapped);
1106 return it_isinserted;
1109 template <
typename... Args>
1110 auto do_place_element(dist_and_fingerprint_type dist_and_fingerprint,
1111 value_idx_type bucket_idx,
1112 Args&&... args) -> std::pair<iterator, bool> {
1115 m_values.emplace_back(std::forward<Args>(args)...);
1117 auto value_idx =
static_cast<value_idx_type
>(m_values.size() - 1);
1118 if (ANKERL_UNORDERED_DENSE_UNLIKELY(is_full())) {
1121 place_and_shift_up({dist_and_fingerprint, value_idx}, bucket_idx);
1125 return {begin() +
static_cast<difference_type
>(value_idx),
true};
1128 template <
typename K,
typename... Args>
1129 auto do_try_emplace(K&& key, Args&&... args) -> std::pair<iterator, bool> {
1130 auto hash = mixed_hash(key);
1131 auto dist_and_fingerprint = dist_and_fingerprint_from_hash(hash);
1132 auto bucket_idx = bucket_idx_from_hash(hash);
1135 auto* bucket = &at(m_buckets, bucket_idx);
1136 if (dist_and_fingerprint == bucket->m_dist_and_fingerprint) {
1137 if (m_equal(key, get_key(m_values[bucket->m_value_idx]))) {
1138 return {begin() +
static_cast<difference_type
>(bucket->m_value_idx),
false};
1140 }
else if (dist_and_fingerprint > bucket->m_dist_and_fingerprint) {
1141 return do_place_element(dist_and_fingerprint,
1143 std::piecewise_construct,
1144 std::forward_as_tuple(std::forward<K>(key)),
1145 std::forward_as_tuple(std::forward<Args>(args)...));
1147 dist_and_fingerprint = dist_inc(dist_and_fingerprint);
1148 bucket_idx = next(bucket_idx);
1152 template <
typename K>
1153 auto do_find(K
const& key) -> iterator {
1154 if (ANKERL_UNORDERED_DENSE_UNLIKELY(empty())) {
1158 auto mh = mixed_hash(key);
1159 auto dist_and_fingerprint = dist_and_fingerprint_from_hash(mh);
1160 auto bucket_idx = bucket_idx_from_hash(mh);
1161 auto* bucket = &at(m_buckets, bucket_idx);
1164 if (dist_and_fingerprint == bucket->m_dist_and_fingerprint && m_equal(key, get_key(m_values[bucket->m_value_idx]))) {
1165 return begin() +
static_cast<difference_type
>(bucket->m_value_idx);
1167 dist_and_fingerprint = dist_inc(dist_and_fingerprint);
1168 bucket_idx = next(bucket_idx);
1169 bucket = &at(m_buckets, bucket_idx);
1171 if (dist_and_fingerprint == bucket->m_dist_and_fingerprint && m_equal(key, get_key(m_values[bucket->m_value_idx]))) {
1172 return begin() +
static_cast<difference_type
>(bucket->m_value_idx);
1174 dist_and_fingerprint = dist_inc(dist_and_fingerprint);
1175 bucket_idx = next(bucket_idx);
1176 bucket = &at(m_buckets, bucket_idx);
1179 if (dist_and_fingerprint == bucket->m_dist_and_fingerprint) {
1180 if (m_equal(key, get_key(m_values[bucket->m_value_idx]))) {
1181 return begin() +
static_cast<difference_type
>(bucket->m_value_idx);
1183 }
else if (dist_and_fingerprint > bucket->m_dist_and_fingerprint) {
1186 dist_and_fingerprint = dist_inc(dist_and_fingerprint);
1187 bucket_idx = next(bucket_idx);
1188 bucket = &at(m_buckets, bucket_idx);
1192 template <
typename K>
1193 auto do_find(K
const& key)
const -> const_iterator {
1194 return const_cast<table*
>(
this)->do_find(key);
1197 template <
typename K,
typename Q = T, std::enable_if_t<is_map_v<Q>,
bool> = true>
1198 auto do_at(K
const& key) -> Q& {
1199 if (
auto it = find(key); ANKERL_UNORDERED_DENSE_LIKELY(end() != it)) {
1202 on_error_key_not_found();
1205 template <
typename K,
typename Q = T, std::enable_if_t<is_map_v<Q>,
bool> = true>
1206 auto do_at(K
const& key)
const -> Q
const& {
1207 return const_cast<table*
>(
this)->at(key);
1211 explicit table(
size_t bucket_count,
1212 Hash
const& hash = Hash(),
1213 KeyEqual
const& equal = KeyEqual(),
1214 allocator_type
const& alloc_or_container = allocator_type())
1215 : m_values(alloc_or_container)
1216 , m_buckets(alloc_or_container)
1219 if (0 != bucket_count) {
1220 reserve(bucket_count);
1222 allocate_buckets_from_shift();
1230 table(
size_t bucket_count, allocator_type
const& alloc)
1231 : table(bucket_count, Hash(), KeyEqual(), alloc) {}
1233 table(
size_t bucket_count, Hash
const& hash, allocator_type
const& alloc)
1234 : table(bucket_count, hash, KeyEqual(), alloc) {}
1236 explicit table(allocator_type
const& alloc)
1237 : table(0, Hash(), KeyEqual(), alloc) {}
1239 template <
class InputIt>
1240 table(InputIt first,
1242 size_type bucket_count = 0,
1243 Hash
const& hash = Hash(),
1244 KeyEqual
const& equal = KeyEqual(),
1245 allocator_type
const& alloc = allocator_type())
1246 : table(bucket_count, hash, equal, alloc) {
1247 insert(first, last);
1250 template <
class InputIt>
1251 table(InputIt first, InputIt last, size_type bucket_count, allocator_type
const& alloc)
1252 : table(first, last, bucket_count, Hash(), KeyEqual(), alloc) {}
1254 template <
class InputIt>
1255 table(InputIt first, InputIt last, size_type bucket_count, Hash
const& hash, allocator_type
const& alloc)
1256 : table(first, last, bucket_count, hash, KeyEqual(), alloc) {}
1258 table(table
const& other)
1259 : table(other, other.m_values.get_allocator()) {}
1261 table(table
const& other, allocator_type
const& alloc)
1262 : m_values(other.m_values, alloc)
1263 , m_max_load_factor(other.m_max_load_factor)
1264 , m_hash(other.m_hash)
1265 , m_equal(other.m_equal) {
1266 copy_buckets(other);
1269 table(table&& other) noexcept
1270 : table(std::move(other), other.m_values.get_allocator()) {}
1272 table(table&& other, allocator_type
const& alloc) noexcept
1274 *
this = std::move(other);
1277 table(std::initializer_list<value_type> ilist,
1278 size_t bucket_count = 0,
1279 Hash
const& hash = Hash(),
1280 KeyEqual
const& equal = KeyEqual(),
1281 allocator_type
const& alloc = allocator_type())
1282 : table(bucket_count, hash, equal, alloc) {
1286 table(std::initializer_list<value_type> ilist, size_type bucket_count, allocator_type
const& alloc)
1287 : table(ilist, bucket_count, Hash(), KeyEqual(), alloc) {}
1289 table(std::initializer_list<value_type> init, size_type bucket_count, Hash
const& hash, allocator_type
const& alloc)
1290 : table(init, bucket_count, hash, KeyEqual(), alloc) {}
1294 auto operator=(table
const& other) -> table& {
1295 if (&other !=
this) {
1296 deallocate_buckets();
1297 m_values = other.m_values;
1298 m_max_load_factor = other.m_max_load_factor;
1299 m_hash = other.m_hash;
1300 m_equal = other.m_equal;
1301 m_shifts = initial_shifts;
1302 copy_buckets(other);
1307 auto operator=(table&& other) noexcept(noexcept(std::is_nothrow_move_assignable_v<value_container_type> &&
1308 std::is_nothrow_move_assignable_v<Hash> &&
1309 std::is_nothrow_move_assignable_v<KeyEqual>)) -> table& {
1310 if (&other !=
this) {
1311 deallocate_buckets();
1312 m_values = std::move(other.m_values);
1313 other.m_values.clear();
1316 if (get_allocator() == other.get_allocator()) {
1317 m_buckets = std::move(other.m_buckets);
1318 other.m_buckets.clear();
1319 m_max_bucket_capacity = std::exchange(other.m_max_bucket_capacity, 0);
1320 m_shifts = std::exchange(other.m_shifts, initial_shifts);
1321 m_max_load_factor = std::exchange(other.m_max_load_factor, default_max_load_factor);
1322 m_hash = std::exchange(other.m_hash, {});
1323 m_equal = std::exchange(other.m_equal, {});
1324 other.allocate_buckets_from_shift();
1325 other.clear_buckets();
1329 m_max_load_factor = other.m_max_load_factor;
1332 copy_buckets(other);
1334 other.clear_buckets();
1335 m_hash = other.m_hash;
1336 m_equal = other.m_equal;
1343 auto operator=(std::initializer_list<value_type> ilist) -> table& {
1349 auto get_allocator() const noexcept -> allocator_type {
1350 return m_values.get_allocator();
1355 auto begin() noexcept -> iterator {
1356 return m_values.begin();
1359 auto begin() const noexcept -> const_iterator {
1360 return m_values.begin();
1363 auto cbegin() const noexcept -> const_iterator {
1364 return m_values.cbegin();
1367 auto end() noexcept -> iterator {
1368 return m_values.end();
1371 auto cend() const noexcept -> const_iterator {
1372 return m_values.cend();
1375 auto end() const noexcept -> const_iterator {
1376 return m_values.end();
1381 [[nodiscard]]
auto empty() const noexcept ->
bool {
1382 return m_values.empty();
1385 [[nodiscard]]
auto size() const noexcept ->
size_t {
1386 return m_values.size();
1389 [[nodiscard]]
static constexpr
auto max_size() noexcept ->
size_t {
1390 if constexpr ((std::numeric_limits<value_idx_type>::max)() == (std::numeric_limits<size_t>::max)()) {
1391 return size_t{1} << (
sizeof(value_idx_type) * 8 - 1);
1393 return size_t{1} << (
sizeof(value_idx_type) * 8);
1404 auto insert(value_type
const& value) -> std::pair<iterator, bool> {
1405 return emplace(value);
1408 auto insert(value_type&& value) -> std::pair<iterator, bool> {
1409 return emplace(std::move(value));
1412 template <
class P, std::enable_if_t<std::is_constructible_v<value_type, P&&>,
bool> = true>
1413 auto insert(P&& value) -> std::pair<iterator, bool> {
1414 return emplace(std::forward<P>(value));
1417 auto insert(const_iterator , value_type
const& value) -> iterator {
1418 return insert(value).first;
1421 auto insert(const_iterator , value_type&& value) -> iterator {
1422 return insert(std::move(value)).first;
1425 template <
class P, std::enable_if_t<std::is_constructible_v<value_type, P&&>,
bool> = true>
1426 auto insert(const_iterator , P&& value) -> iterator {
1427 return insert(std::forward<P>(value)).first;
1430 template <
class InputIt>
1431 void insert(InputIt first, InputIt last) {
1432 while (first != last) {
1438 void insert(std::initializer_list<value_type> ilist) {
1439 insert(ilist.begin(), ilist.end());
1444 auto extract() && -> value_container_type {
1445 return std::move(m_values);
1450 auto replace(value_container_type&& container) {
1451 if (ANKERL_UNORDERED_DENSE_UNLIKELY(container.size() > max_size())) {
1452 on_error_too_many_elements();
1454 auto shifts = calc_shifts_for_size(container.size());
1455 if (0 == bucket_count() || shifts < m_shifts || container.get_allocator() != m_values.get_allocator()) {
1457 deallocate_buckets();
1458 allocate_buckets_from_shift();
1462 m_values = std::move(container);
1465 auto value_idx = value_idx_type{};
1468 while (value_idx !=
static_cast<value_idx_type
>(m_values.size())) {
1469 auto const& key = get_key(m_values[value_idx]);
1471 auto hash = mixed_hash(key);
1472 auto dist_and_fingerprint = dist_and_fingerprint_from_hash(hash);
1473 auto bucket_idx = bucket_idx_from_hash(hash);
1475 bool key_found =
false;
1477 auto const& bucket = at(m_buckets, bucket_idx);
1478 if (dist_and_fingerprint > bucket.m_dist_and_fingerprint) {
1481 if (dist_and_fingerprint == bucket.m_dist_and_fingerprint &&
1482 m_equal(key, get_key(m_values[bucket.m_value_idx]))) {
1486 dist_and_fingerprint = dist_inc(dist_and_fingerprint);
1487 bucket_idx = next(bucket_idx);
1491 if (value_idx !=
static_cast<value_idx_type
>(m_values.size() - 1)) {
1492 m_values[value_idx] = std::move(m_values.back());
1494 m_values.pop_back();
1496 place_and_shift_up({dist_and_fingerprint, value_idx}, bucket_idx);
1502 template <
class M,
typename Q = T, std::enable_if_t<is_map_v<Q>,
bool> = true>
1503 auto insert_or_assign(Key
const& key, M&& mapped) -> std::pair<iterator, bool> {
1504 return do_insert_or_assign(key, std::forward<M>(mapped));
1507 template <
class M,
typename Q = T, std::enable_if_t<is_map_v<Q>,
bool> = true>
1508 auto insert_or_assign(Key&& key, M&& mapped) -> std::pair<iterator, bool> {
1509 return do_insert_or_assign(std::move(key), std::forward<M>(mapped));
1512 template <
typename K,
1516 typename KE = KeyEqual,
1517 std::enable_if_t<is_map_v<Q> && is_transparent_v<H, KE>,
bool> =
true>
1518 auto insert_or_assign(K&& key, M&& mapped) -> std::pair<iterator, bool> {
1519 return do_insert_or_assign(std::forward<K>(key), std::forward<M>(mapped));
1522 template <
class M,
typename Q = T, std::enable_if_t<is_map_v<Q>,
bool> = true>
1523 auto insert_or_assign(const_iterator , Key
const& key, M&& mapped) -> iterator {
1524 return do_insert_or_assign(key, std::forward<M>(mapped)).first;
1527 template <
class M,
typename Q = T, std::enable_if_t<is_map_v<Q>,
bool> = true>
1528 auto insert_or_assign(const_iterator , Key&& key, M&& mapped) -> iterator {
1529 return do_insert_or_assign(std::move(key), std::forward<M>(mapped)).first;
1532 template <
typename K,
1536 typename KE = KeyEqual,
1537 std::enable_if_t<is_map_v<Q> && is_transparent_v<H, KE>,
bool> =
true>
1538 auto insert_or_assign(const_iterator , K&& key, M&& mapped) -> iterator {
1539 return do_insert_or_assign(std::forward<K>(key), std::forward<M>(mapped)).first;
1546 typename KE = KeyEqual,
1547 std::enable_if_t<!is_map_v<Q> && is_transparent_v<H, KE>,
bool> =
true>
1548 auto emplace(K&& key) -> std::pair<iterator, bool> {
1549 auto hash = mixed_hash(key);
1550 auto dist_and_fingerprint = dist_and_fingerprint_from_hash(hash);
1551 auto bucket_idx = bucket_idx_from_hash(hash);
1553 while (dist_and_fingerprint <= at(m_buckets, bucket_idx).m_dist_and_fingerprint) {
1554 if (dist_and_fingerprint == at(m_buckets, bucket_idx).m_dist_and_fingerprint &&
1555 m_equal(key, m_values[at(m_buckets, bucket_idx).m_value_idx])) {
1557 return {begin() +
static_cast<difference_type
>(at(m_buckets, bucket_idx).m_value_idx),
false};
1559 dist_and_fingerprint = dist_inc(dist_and_fingerprint);
1560 bucket_idx = next(bucket_idx);
1564 return do_place_element(dist_and_fingerprint, bucket_idx, std::forward<K>(key));
1567 template <
class... Args>
1568 auto emplace(Args&&... args) -> std::pair<iterator, bool> {
1571 auto& key = get_key(m_values.emplace_back(std::forward<Args>(args)...));
1572 auto hash = mixed_hash(key);
1573 auto dist_and_fingerprint = dist_and_fingerprint_from_hash(hash);
1574 auto bucket_idx = bucket_idx_from_hash(hash);
1576 while (dist_and_fingerprint <= at(m_buckets, bucket_idx).m_dist_and_fingerprint) {
1577 if (dist_and_fingerprint == at(m_buckets, bucket_idx).m_dist_and_fingerprint &&
1578 m_equal(key, get_key(m_values[at(m_buckets, bucket_idx).m_value_idx]))) {
1579 m_values.pop_back();
1580 return {begin() +
static_cast<difference_type
>(at(m_buckets, bucket_idx).m_value_idx),
false};
1582 dist_and_fingerprint = dist_inc(dist_and_fingerprint);
1583 bucket_idx = next(bucket_idx);
1587 auto value_idx =
static_cast<value_idx_type
>(m_values.size() - 1);
1588 if (ANKERL_UNORDERED_DENSE_UNLIKELY(is_full())) {
1593 place_and_shift_up({dist_and_fingerprint, value_idx}, bucket_idx);
1595 return {begin() +
static_cast<difference_type
>(value_idx),
true};
1598 template <
class... Args>
1599 auto emplace_hint(const_iterator , Args&&... args) -> iterator {
1600 return emplace(std::forward<Args>(args)...).first;
1603 template <
class... Args,
typename Q = T, std::enable_if_t<is_map_v<Q>,
bool> =
true>
1604 auto try_emplace(Key
const& key, Args&&... args) -> std::pair<iterator, bool> {
1605 return do_try_emplace(key, std::forward<Args>(args)...);
1608 template <
class... Args,
typename Q = T, std::enable_if_t<is_map_v<Q>,
bool> =
true>
1609 auto try_emplace(Key&& key, Args&&... args) -> std::pair<iterator, bool> {
1610 return do_try_emplace(std::move(key), std::forward<Args>(args)...);
1613 template <
class... Args,
typename Q = T, std::enable_if_t<is_map_v<Q>,
bool> =
true>
1614 auto try_emplace(const_iterator , Key
const& key, Args&&... args) -> iterator {
1615 return do_try_emplace(key, std::forward<Args>(args)...).first;
1618 template <
class... Args,
typename Q = T, std::enable_if_t<is_map_v<Q>,
bool> =
true>
1619 auto try_emplace(const_iterator , Key&& key, Args&&... args) -> iterator {
1620 return do_try_emplace(std::move(key), std::forward<Args>(args)...).first;
1628 typename KE = KeyEqual,
1629 std::enable_if_t<is_map_v<Q> && is_transparent_v<H, KE> && is_neither_convertible_v<K&&, iterator, const_iterator>,
1631 auto try_emplace(K&& key, Args&&... args) -> std::pair<iterator, bool> {
1632 return do_try_emplace(std::forward<K>(key), std::forward<Args>(args)...);
1640 typename KE = KeyEqual,
1641 std::enable_if_t<is_map_v<Q> && is_transparent_v<H, KE> && is_neither_convertible_v<K&&, iterator, const_iterator>,
1643 auto try_emplace(const_iterator , K&& key, Args&&... args) -> iterator {
1644 return do_try_emplace(std::forward<K>(key), std::forward<Args>(args)...).first;
1647 auto erase(iterator it) -> iterator {
1648 auto hash = mixed_hash(get_key(*it));
1649 auto bucket_idx = bucket_idx_from_hash(hash);
1651 auto const value_idx_to_remove =
static_cast<value_idx_type
>(it - cbegin());
1652 while (at(m_buckets, bucket_idx).m_value_idx != value_idx_to_remove) {
1653 bucket_idx = next(bucket_idx);
1656 do_erase(bucket_idx, [](value_type&& ) {
1658 return begin() +
static_cast<difference_type
>(value_idx_to_remove);
1661 auto extract(iterator it) -> value_type {
1662 auto hash = mixed_hash(get_key(*it));
1663 auto bucket_idx = bucket_idx_from_hash(hash);
1665 auto const value_idx_to_remove =
static_cast<value_idx_type
>(it - cbegin());
1666 while (at(m_buckets, bucket_idx).m_value_idx != value_idx_to_remove) {
1667 bucket_idx = next(bucket_idx);
1670 auto tmp = std::optional<value_type>{};
1671 do_erase(bucket_idx, [&tmp](value_type&& val) {
1672 tmp = std::move(val);
1674 return std::move(tmp).value();
1677 template <
typename Q = T, std::enable_if_t<is_map_v<Q>,
bool> = true>
1678 auto erase(const_iterator it) -> iterator {
1679 return erase(begin() + (it - cbegin()));
1682 template <
typename Q = T, std::enable_if_t<is_map_v<Q>,
bool> = true>
1683 auto extract(const_iterator it) -> value_type {
1684 return extract(begin() + (it - cbegin()));
1687 auto erase(const_iterator first, const_iterator last) -> iterator {
1688 auto const idx_first = first - cbegin();
1689 auto const idx_last = last - cbegin();
1690 auto const first_to_last = std::distance(first, last);
1691 auto const last_to_end = std::distance(last, cend());
1694 auto const mid = idx_first + (std::min)(first_to_last, last_to_end);
1695 auto idx = idx_first;
1696 while (idx != mid) {
1697 erase(begin() + idx);
1703 while (idx != mid) {
1705 erase(begin() + idx);
1708 return begin() + idx_first;
1711 auto erase(Key
const& key) ->
size_t {
1712 return do_erase_key(key, [](value_type&& ) {
1716 auto extract(Key
const& key) -> std::optional<value_type> {
1717 auto tmp = std::optional<value_type>{};
1718 do_erase_key(key, [&tmp](value_type&& val) {
1719 tmp = std::move(val);
1724 template <
class K,
class H = Hash,
class KE = KeyEqual, std::enable_if_t<is_transparent_v<H, KE>,
bool> = true>
1725 auto erase(K&& key) ->
size_t {
1726 return do_erase_key(std::forward<K>(key), [](value_type&& ) {
1730 template <
class K,
class H = Hash,
class KE = KeyEqual, std::enable_if_t<is_transparent_v<H, KE>,
bool> = true>
1731 auto extract(K&& key) -> std::optional<value_type> {
1732 auto tmp = std::optional<value_type>{};
1733 do_erase_key(std::forward<K>(key), [&tmp](value_type&& val) {
1734 tmp = std::move(val);
1739 void swap(table& other) noexcept(noexcept(std::is_nothrow_swappable_v<value_container_type> &&
1740 std::is_nothrow_swappable_v<Hash> && std::is_nothrow_swappable_v<KeyEqual>)) {
1747 template <
typename Q = T, std::enable_if_t<is_map_v<Q>,
bool> = true>
1748 auto at(key_type
const& key) -> Q& {
1752 template <
typename K,
1755 typename KE = KeyEqual,
1756 std::enable_if_t<is_map_v<Q> && is_transparent_v<H, KE>,
bool> =
true>
1757 auto at(K
const& key) -> Q& {
1761 template <
typename Q = T, std::enable_if_t<is_map_v<Q>,
bool> = true>
1762 auto at(key_type
const& key)
const -> Q
const& {
1766 template <
typename K,
1769 typename KE = KeyEqual,
1770 std::enable_if_t<is_map_v<Q> && is_transparent_v<H, KE>,
bool> =
true>
1771 auto at(K
const& key)
const -> Q
const& {
1775 template <
typename Q = T, std::enable_if_t<is_map_v<Q>,
bool> = true>
1776 auto operator[](Key
const& key) -> Q& {
1777 return try_emplace(key).first->second;
1780 template <
typename Q = T, std::enable_if_t<is_map_v<Q>,
bool> = true>
1781 auto operator[](Key&& key) -> Q& {
1782 return try_emplace(std::move(key)).first->second;
1785 template <
typename K,
1788 typename KE = KeyEqual,
1789 std::enable_if_t<is_map_v<Q> && is_transparent_v<H, KE>,
bool> =
true>
1790 auto operator[](K&& key) -> Q& {
1791 return try_emplace(std::forward<K>(key)).first->second;
1794 auto count(Key
const& key)
const ->
size_t {
1795 return find(key) == end() ? 0 : 1;
1798 template <
class K,
class H = Hash,
class KE = KeyEqual, std::enable_if_t<is_transparent_v<H, KE>,
bool> = true>
1799 auto count(K
const& key)
const ->
size_t {
1800 return find(key) == end() ? 0 : 1;
1803 auto find(Key
const& key) -> iterator {
1804 return do_find(key);
1807 auto find(Key
const& key)
const -> const_iterator {
1808 return do_find(key);
1811 template <
class K,
class H = Hash,
class KE = KeyEqual, std::enable_if_t<is_transparent_v<H, KE>,
bool> = true>
1812 auto find(K
const& key) -> iterator {
1813 return do_find(key);
1816 template <
class K,
class H = Hash,
class KE = KeyEqual, std::enable_if_t<is_transparent_v<H, KE>,
bool> = true>
1817 auto find(K
const& key)
const -> const_iterator {
1818 return do_find(key);
1821 auto contains(Key
const& key)
const ->
bool {
1822 return find(key) != end();
1825 template <
class K,
class H = Hash,
class KE = KeyEqual, std::enable_if_t<is_transparent_v<H, KE>,
bool> = true>
1826 auto contains(K
const& key)
const ->
bool {
1827 return find(key) != end();
1830 auto equal_range(Key
const& key) -> std::pair<iterator, iterator> {
1831 auto it = do_find(key);
1832 return {it, it == end() ? end() : it + 1};
1835 auto equal_range(
const Key& key)
const -> std::pair<const_iterator, const_iterator> {
1836 auto it = do_find(key);
1837 return {it, it == end() ? end() : it + 1};
1840 template <
class K,
class H = Hash,
class KE = KeyEqual, std::enable_if_t<is_transparent_v<H, KE>,
bool> = true>
1841 auto equal_range(K
const& key) -> std::pair<iterator, iterator> {
1842 auto it = do_find(key);
1843 return {it, it == end() ? end() : it + 1};
1846 template <
class K,
class H = Hash,
class KE = KeyEqual, std::enable_if_t<is_transparent_v<H, KE>,
bool> = true>
1847 auto equal_range(K
const& key)
const -> std::pair<const_iterator, const_iterator> {
1848 auto it = do_find(key);
1849 return {it, it == end() ? end() : it + 1};
1854 auto bucket_count() const noexcept ->
size_t {
1855 return m_buckets.size();
1858 static constexpr
auto max_bucket_count() noexcept ->
size_t {
1864 [[nodiscard]]
auto load_factor() const ->
float {
1865 return bucket_count() ?
static_cast<float>(size()) /
static_cast<float>(bucket_count()) : 0.0F;
1868 [[nodiscard]]
auto max_load_factor() const ->
float {
1869 return m_max_load_factor;
1872 void max_load_factor(
float ml) {
1873 m_max_load_factor = ml;
1874 if (bucket_count() != max_bucket_count()) {
1875 m_max_bucket_capacity =
static_cast<value_idx_type
>(
static_cast<float>(bucket_count()) * max_load_factor());
1879 void rehash(
size_t count) {
1880 count = (std::min)(count, max_size());
1881 auto shifts = calc_shifts_for_size((std::max)(count, size()));
1882 if (shifts != m_shifts) {
1884 deallocate_buckets();
1885 m_values.shrink_to_fit();
1886 allocate_buckets_from_shift();
1887 clear_and_fill_buckets_from_values();
1891 void reserve(
size_t capa) {
1892 capa = (std::min)(capa, max_size());
1893 if constexpr (has_reserve<value_container_type>) {
1895 m_values.reserve(capa);
1897 auto shifts = calc_shifts_for_size((std::max)(capa, size()));
1898 if (0 == bucket_count() || shifts < m_shifts) {
1900 deallocate_buckets();
1901 allocate_buckets_from_shift();
1902 clear_and_fill_buckets_from_values();
1908 auto hash_function() const -> hasher {
1912 auto key_eq() const -> key_equal {
1917 [[nodiscard]]
auto values() const noexcept -> value_container_type const& {
1923 friend auto operator==(table
const& a, table
const& b) ->
bool {
1927 if (a.size() != b.size()) {
1930 for (
auto const& b_entry : b) {
1931 auto it = a.find(get_key(b_entry));
1932 if constexpr (is_map_v<T>) {
1934 if (a.end() == it || !(b_entry.second == it->second)) {
1939 if (a.end() == it) {
1947 friend auto operator!=(table
const& a, table
const& b) ->
bool {
1954 ANKERL_UNORDERED_DENSE_EXPORT
template <
class Key,
1956 class Hash = hash<Key>,
1957 class KeyEqual = std::equal_to<Key>,
1958 class AllocatorOrContainer = std::allocator<std::pair<Key, T>>,
1959 class Bucket = bucket_type::standard,
1960 class BucketContainer = detail::default_container_t>
1961 using map = detail::table<Key, T, Hash, KeyEqual, AllocatorOrContainer, Bucket, BucketContainer, false>;
1963 ANKERL_UNORDERED_DENSE_EXPORT
template <
class Key,
1965 class Hash = hash<Key>,
1966 class KeyEqual = std::equal_to<Key>,
1967 class AllocatorOrContainer = std::allocator<std::pair<Key, T>>,
1968 class Bucket = bucket_type::standard,
1969 class BucketContainer = detail::default_container_t>
1970 using segmented_map = detail::table<Key, T, Hash, KeyEqual, AllocatorOrContainer, Bucket, BucketContainer, true>;
1972 ANKERL_UNORDERED_DENSE_EXPORT
template <
class Key,
1973 class Hash = hash<Key>,
1974 class KeyEqual = std::equal_to<Key>,
1975 class AllocatorOrContainer = std::allocator<Key>,
1976 class Bucket = bucket_type::standard,
1977 class BucketContainer = detail::default_container_t>
1978 using set = detail::table<Key, void, Hash, KeyEqual, AllocatorOrContainer, Bucket, BucketContainer, false>;
1980 ANKERL_UNORDERED_DENSE_EXPORT
template <
class Key,
1981 class Hash = hash<Key>,
1982 class KeyEqual = std::equal_to<Key>,
1983 class AllocatorOrContainer = std::allocator<Key>,
1984 class Bucket = bucket_type::standard,
1985 class BucketContainer = detail::default_container_t>
1986 using segmented_set = detail::table<Key, void, Hash, KeyEqual, AllocatorOrContainer, Bucket, BucketContainer, true>;
1988 # if defined(ANKERL_UNORDERED_DENSE_PMR)
1992 ANKERL_UNORDERED_DENSE_EXPORT
template <
class Key,
1994 class Hash = hash<Key>,
1995 class KeyEqual = std::equal_to<Key>,
1996 class Bucket = bucket_type::standard>
1997 using map = detail::table<Key,
2001 ANKERL_UNORDERED_DENSE_PMR::polymorphic_allocator<std::pair<Key, T>>,
2003 detail::default_container_t,
2006 ANKERL_UNORDERED_DENSE_EXPORT
template <
class Key,
2008 class Hash = hash<Key>,
2009 class KeyEqual = std::equal_to<Key>,
2010 class Bucket = bucket_type::standard>
2011 using segmented_map = detail::table<Key,
2015 ANKERL_UNORDERED_DENSE_PMR::polymorphic_allocator<std::pair<Key, T>>,
2017 detail::default_container_t,
2020 ANKERL_UNORDERED_DENSE_EXPORT
template <
class Key,
2021 class Hash = hash<Key>,
2022 class KeyEqual = std::equal_to<Key>,
2023 class Bucket = bucket_type::standard>
2024 using set = detail::table<Key,
2028 ANKERL_UNORDERED_DENSE_PMR::polymorphic_allocator<Key>,
2030 detail::default_container_t,
2033 ANKERL_UNORDERED_DENSE_EXPORT
template <
class Key,
2034 class Hash = hash<Key>,
2035 class KeyEqual = std::equal_to<Key>,
2036 class Bucket = bucket_type::standard>
2037 using segmented_set = detail::table<Key,
2041 ANKERL_UNORDERED_DENSE_PMR::polymorphic_allocator<Key>,
2043 detail::default_container_t,
2062 ANKERL_UNORDERED_DENSE_EXPORT
template <
class Key,
2066 class AllocatorOrContainer,
2069 class BucketContainer,
2073 ankerl::unordered_dense::detail::table<Key, T, Hash, KeyEqual, AllocatorOrContainer, Bucket, BucketContainer, IsSegmented>&
2075 Pred pred) ->
size_t {
2076 using map_t = ankerl::unordered_dense::detail::
2077 table<Key, T, Hash, KeyEqual, AllocatorOrContainer, Bucket, BucketContainer, IsSegmented>;
2080 auto const old_size = map.size();
2081 auto idx = old_size;
2084 auto it = map.begin() +
static_cast<typename map_t::difference_type
>(idx);
2090 return old_size - map.size();