unordered_dense
v4.5.0
基于Robin-Hood向后移位删除C ++ 17及更高版本的快速且密集的哈希图和哈希集。
ankerl::unordered_dense::map and ankerl::unordered_dense::set是（几乎） std::unordered_map和std::unordered_set的（几乎）替换。尽管他们没有强大的迭代 /参考稳定性保证，但通常会更快。
此外，还有ankerl::unordered_dense::segmented_map和ankerl::unordered_dense::segmented_set具有较低的峰值内存使用情况。和稳定的迭代器/插入中的引用。
ankerl::unordered_dense::hashis_transparent异质过载std::hashauto extract() && -> value_container_typeextract()单元素[[nodiscard]] auto values() const noexcept -> value_container_type const&auto replace(value_container_type&& container)ankerl::unordered_dense::bucket_type::standardankerl::unordered_dense::bucket_type::bigsegmented_map和segmented_set所选的设计比std::unordered_map具有一些优势：
std::vector中，所有数据都是连续的！absl::flat_hash_map的同一球场上std::allocators和多态性分配器的全面支持。有ankerl::unordered_dense::pmr Typedefs可用std::vector转换到boost::interprocess::vector或任何其他兼容的随机访问容器。std::vector调试器中都可以轻松看到基础数据。没有免费的午餐，所以有一些缺点：
std::pair<Key, Value> no const Key >默认安装位置是/usr/local 。
克隆存储库并将这些命令运行在克隆文件夹中：
mkdir build && cd build
cmake ..
cmake --build . --target install如果您不想安装unordered_dense系统宽，请考虑设置安装前缀，例如：
mkdir build && cd build
cmake -DCMAKE_INSTALL_PREFIX:PATH= ${HOME} /unordered_dense_install ..
cmake --build . --target install要使用已安装的库，请将其添加到您的项目中：
find_package (unordered_dense CONFIG REQUIRED)
target_link_libraries (your_project_name unordered_dense::unordered_dense)ankerl::unordered_dense支持C ++ 20模块。只需编译src/ankerl.unordered_dense.cpp并使用结果模块，例如这样：
clang++ -std=c++20 -I include --precompile -x c++-module src/ankerl.unordered_dense.cpp
clang++ -std=c++20 -c ankerl.unordered_dense.pcm要在module_test.cpp中使用与EG一起使用的模块，请使用
import ankerl.unordered_dense;并用例如
clang++ -std=c++20 -fprebuilt-module-path=. ankerl.unordered_dense.o module_test.cpp -o main可以在test/modules中找到一个简单的演示脚本。
ankerl::unordered_dense::hash是基于Wyhash的快速而高质量的哈希。 ankerl::unordered_dense MAP/设置高质量哈希（良好的雪崩效果）和不良质量之间的区分。质量高的哈希包含一个特殊的标记：
using is_avalanching = void ;这是专业bool ， char ， unsigned char signed char char8_t ，char16_t， char16_t ， char32_t ， wchar_t ， short ， unsigned short ，int， int ， unsigned int ， long ， long long ， unsigned long ，长，长时间长， enum unsigned long long ， T* ，t*，std std::unique_ptr<T> std::shared_ptr<T> std::basic_string<C> std::basic_string_view<C> 。
认为不包含这种标记的哈希被认为是质量不佳，并在地图/设置实现内接收另一个混合步骤。
考虑一种简单的自定义密钥类型：
struct id {
uint64_t value{};
auto operator ==(id const & other) const -> bool {
return value == other. value ;
}
};哈希的最简单实现是这样的：
struct custom_hash_simple {
auto operator ()(id const & x) const noexcept -> uint64_t {
return x. value ;
}
};这可以与
auto ids = ankerl::unordered_dense::set<id, custom_hash_simple>();因为custom_hash_simple没有using is_avalanching = void;标记被认为是不良的质量，并且在集合中自动提供x.value的其他混合。
回到id示例，我们可以轻松地实现更高质量的哈希：
struct custom_hash_avalanching {
using is_avalanching = void ;
auto operator ()(id const & x) const noexcept -> uint64_t {
return ankerl::unordered_dense::detail::wyhash::hash (x. value );
}
};我们知道wyhash::hash具有高质量，因此我们可以using is_avalanching = void;使地图/集合直接使用返回的值。
ankerl::unordered_dense::hash与其创建新课程，还可以专业化ankerl::unordered_dense::hash ：
template <>
struct ankerl ::unordered_dense::hash<id> {
using is_avalanching = void ;
[[nodiscard]] auto operator ()(id const & x) const noexcept -> uint64_t {
return detail::wyhash::hash (x. value );
}
};is_transparent异质过载如P2363中所述，该地图/集合支持异质过载，扩展了具有剩余的异质过载的关联容器，该过载针对C ++ 26。这具有用于find ， count ， contains超载， equal_range （请参见p0919r3）， erase （请参见p2077r2）和try_emplace ， insert_or_assign ， operator[] ， at和insert ＆ emplace的集合（请参阅P2363R3）。
为了使异质过载具有影响， hasher和key_equal都需要将属性is_transparent集。
这是一个示例实现，可与任何可转换为std::string_view字符串类型一起使用（例如char const* and std::string ）：
struct string_hash {
using is_transparent = void ; // enable heterogeneous overloads
using is_avalanching = void ; // mark class as high quality avalanching hash
[[nodiscard]] auto operator ()(std::string_view str) const noexcept -> uint64_t {
return ankerl::unordered_dense::hash<std::string_view>{}(str);
}
}; key_equal is_transparent此哈希
auto map = ankerl::unordered_dense::map<std::string, size_t , string_hash, std::equal_to<>>();有关更多信息，请参见test/unit/transparent.cpp中的示例。
std::hash当可以使用自定义类型的std::hash的实现时，这将自动使用并假定为质量不好（因此使用了std::hash ，但执行了附加的混合步骤）。
当该类型具有唯一的对象表示（无填充，可琐碎的复制）时，就可以放置对象的内存。考虑一个简单的课程
struct point {
int x{};
int y{};
auto operator ==(point const & other) const -> bool {
return x == other. x && y == other. y ;
}
};可以像这样轻松地提供快速，高质量的哈希：
struct custom_hash_unique_object_representation {
using is_avalanching = void ;
[[nodiscard]] auto operator ()(point const & f) const noexcept -> uint64_t {
static_assert (std::has_unique_object_representations_v<point>);
return ankerl::unordered_dense::detail::wyhash::hash (&f, sizeof (f));
}
};除了标准std::unordered_map api（请参阅https://en.cppreference.com/w/cpp/container/unordered_map）我们还有其他API，与节点API有些相似，但是利用了我们内部使用随机访问容器的事实：
auto extract() && -> value_container_type提取内部使用的容器。 *this被清空了。
extract()单元素类似于erase()我有一个API调用extract() 。它的行为与erase完全相同，只是返回值是从容器中删除的移动元素：
auto extract(const_iterator it) -> value_typeauto extract(Key const& key) -> std::optional<value_type>template <class K> auto extract(K&& key) -> std::optional<value_type>请注意， extract(key) API返回一个std::optional<value_type>未找到键时为空的。
[[nodiscard]] auto values() const noexcept -> value_container_type const&公开基础值容器。
auto replace(value_container_type&& container)丢弃内部持有的容器，并用一个通过的容器代替。除去非唯一元素，并在发现非唯一元素时部分重新排序容器。
unordered_dense接受自定义分配器，但您还可以为该模板参数指定自定义容器。这样，可以用EG std::deque或任何其他容器（例如boost::interprocess::vector替换内部使用的std::vector vector。这支持了花式指针（例如OffSet_ptr），因此可以将容器与EG boost::interprocess提供的共享内存一起使用。
地图/集合支持两种不同的存储桶类型。默认值几乎应该对每个人都有好处。
ankerl::unordered_dense::bucket_type::standardankerl::unordered_dense::bucket_type::bigsegmented_map和segmented_set ankerl::unordered_dense提供了一个自定义的容器实现，其内存要求较低，而默认的std::vector 。内存不是连续的，但是它可以分配段，而无需重新分配和移动所有元素。总而言之，这导致
std::vector相比，索引略慢，因为需要额外的间接方向。这是与absl::flat_hash_map和ankerl::unordered_dense::map插入1000万条目时的比较
对于这个简单的插入测试，Abseil是最快的，需要超过0.8秒的时间。峰值内存使用率约为430 MB。请注意，在最后一个峰值之后，内存使用情况如何下降；当降低到〜290MB时，它已经完成重新进行，并且可以释放先前使用的内存块。
ankerl::unordered_dense::segmented_map没有这些峰，而是对内存使用的平稳增加。请注意，由于索引数据结构需求仍然需要增加固定因素，因此仍存在突然的下降和增加的内存。但是，由于将数据固定在单独的容器中，我们可以首先释放旧数据结构，然后分配一个新的，更大的索引结构。因此，我们没有峰值。
地图/集有两个数据结构：
std::vector<value_type>保存所有数据。地图/设置迭代器只是std::vector<value_type>::iterator ！每当添加元素时，都会将其emplace_back到向量。密钥是哈希，并且在存储库数组中的相应位置添加了一个条目（存储桶）。水桶具有这种结构：
struct Bucket {
uint32_t dist_and_fingerprint;
uint32_t value_idx;
};每个桶存储3件事：
dist_and_fingerprint中的3个最重要的字节）dist_and_fingerprint中的最低字节）该结构是专门为碰撞解决策略而设计的，罗宾·霍德（Robin-Hood Hoshing）和向后偏移删除。
钥匙是哈希，如果用指纹在该位置有条目，则搜索水桶阵列。当发现时，比较数据向量中的密钥，当返回值时，将其返回。
由于所有数据都存储在向量中，因此删除更为复杂：
value_idx 。这需要另一个查找。 在2023-09-10，我在Github上进行了快速搜索，以查看此地图是否在任何流行的开源项目中都使用。这是我发现的一些项目。如果您愿意在该列表中，请给我发便笺！
