unordered_dense
v4.5.0
基於Robin-Hood向後移位刪除C ++ 17及更高版本的快速且密集的哈希圖和哈希集。
ankerl::unordered_dense::map and std::unordered_set ankerl::unordered_dense::set是（幾乎） std::unordered_map 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上進行了快速搜索，以查看此地圖是否在任何流行的開源項目中都使用。這是我發現的一些項目。如果您願意在該列表中，請給我發便箋！
