robin map
v1.3.0
robin-map 庫是快速哈希映射和哈希集的 C++ 實現，使用開放尋址和線性羅賓漢哈希以及向後移位刪除來解決衝突。
提供了四個類別： tsl::robin_map 、 tsl::robin_set 、 tsl::robin_pg_map和tsl::robin_pg_set 。前兩個速度更快，並且使用 2 的冪增長策略，後兩者則使用素數增長策略，並且能夠更好地應對較差的雜湊函數。如果雜湊的低位元有可能重複模式（例如，您使用身分雜湊函數儲存指標），請使用主要版本。有關詳細信息，請參閱增長政策。
可以在此處找到tsl::robin_map與其他哈希映射的基準測試。此頁面還提供了一些關於您應該為您的用例嘗試哪種哈希表結構的建議（如果您對tsl命名空間中的多個哈希表實現有點迷失，那麼這很有用）。
僅標頭庫，只需將包含目錄新增至包含路徑即可開始使用。如果您使用 CMake，也可以使用 CMakeLists.txt 中的tsl::robin_map匯出目標。
快速哈希表，檢查一些數字的基準。
支援僅移動和非預設可構造鍵/值。
支援異質查找，允許使用與Key不同的類型的find （例如，如果您有一個使用std::unique_ptr<foo>作為鍵的映射，則可以使用foo*或std::uintptr_t作為鍵參數find而不構造std::unique_ptr<foo> ，請參閱範例）。
無需從鍵中保留任何哨兵值。
如果散列或鍵相等函數的計算成本很高，則可以將散列值與儲存的鍵值一起存儲，以便更快地重新散列和查找。請注意，即使沒有明確詢問，當庫可以檢測到由於對齊而不會影響記憶體中結構的大小時，也可以儲存哈希。有關詳細信息，請參閱 StoreHash 模板參數。
如果在查找之前知道雜湊值，則可以將其作為參數傳遞以加快查找速度（請參閱 API 中的precalculated_hash參數）。
支援高效的序列化和反序列化（有關詳細信息，請參閱範例以及 API 中的serialize/deserialize方法）。
此函式庫可以在停用異常的情況下使用（透過 Clang 和 GCC 上的-fno-exceptions選項，在 MSVC 上沒有/EH選項或簡單地透過定義TSL_NO_EXCEPTIONS ）。 std::terminate用於在停用異常時取代throw指令。
API 與std::unordered_map和std::unordered_set非常相似。
std::unordered_map相比的差異tsl::robin_map嘗試擁有與std::unordered_map類似的接口，但存在一些差異。
只有當以下語句為真時，強異常保證才成立std::is_nothrow_swappable<value_type>::value && std::is_nothrow_move_constructible<value_type>::value （其中value_type是tsl::robin_set和std::pair<Key, T> Key std::pair<Key, T>表示tsl::robin_map ）。否則，如果在交換或移動期間引發異常，結構可能最終處於未定義狀態。請注意，根據標準，具有 noexcept 複製構造函數和無移動構造函數value_type也滿足此條件，因此將保證結構的強大異常保證（有關詳細信息，請參閱 API）。
類型Key以及映射情況下的T必須是可交換的。它們還必須是可複製和/或移動的。
迭代器失效的行為方式不同，任何修改哈希表的操作都會使它們失效（有關詳細信息，請參閱 API）。
映射中對鍵或值的引用和指標將以與這些鍵值的迭代器相同的方式失效。
對於tsl::robin_map的迭代器， operator*()和operator->()傳回一個引用和一個指向const std::pair<Key, T>而不是std::pair<const Key, T>的指標T不可修改。要修改值，您必須呼叫迭代器的value()方法來取得可變參考。例子：
tsl::robin_map<int, int> map = {{1, 1}, {2, 1}, {3, 1}};for(auto it = map.begin(); it != map.end() ;++it){//it->第二個=2; // Illegalit.value() = 2; // 好的}不支援某些與儲存桶相關的方法（例如bucket_size ， bucket ，...）。
這些差異也適用於std::unordered_set和tsl::robin_set之間。
線程安全保證與std::unordered_map/set相同（即可以有多個讀取器而沒有寫入器）。
該程式庫透過GrowthPolicy模板參數支援多種增長策略。圖書館提供了三項政策，但如果需要，您可以輕鬆實施自己的政策。
tsl::rh::two_growth_policy 的力量。 tsl::robin_map/set使用的預設策略。此策略將哈希表的儲存桶數組的大小保持為 2 的冪。此約束允許策略避免使用慢模運算將雜湊對應到儲存桶，而不是hash % 2 n ，而是使用hash & (2 n - 1) （請參閱快速模運算）。速度很快，但這可能會導致與較差的雜湊函數發生大量衝突，因為 2 的冪的模最終僅掩蓋了最高有效位。
tsl::rh::prime_growth_policy。 tsl::robin_pg_map/set所使用的預設策略。此策略將哈希表的桶數組的大小保持為素數。將雜湊映射到儲存桶時，使用素數作為模將導致雜湊在儲存桶中更好的分佈，即使雜湊函數很差。為了允許編譯器最佳化模運算，該策略使用具有常數素數模的查找表（有關詳細信息，請參閱 API）。比tsl::rh::power_of_two_growth_policy慢，但更安全。
tsl::rh::mod_growth_policy。此策略透過參數中傳遞的可自訂成長因子來成長地圖。然後它只使用模運算子將哈希映射到儲存桶。速度較慢但更靈活。
要實現您自己的策略，您必須實作以下介面。
struct custom_policy {// 在哈希表建構和重新哈希時調用，min_bucket_count_in_out 是哈希表需要的最小桶//。如果需要，策略可以將其變更為更高數量的儲存桶 // 並且雜湊表將使用該值作為儲存桶計數。如果要求 0 個儲存桶，則該值//必須保持在 0。 // 傳回hash所屬的bucket[0,bucket_count())。 // 如果bucket_count()為0，它必須永遠回傳0.std::size_t bucket_for_hash(std::size_t hash) const noexcept; // 傳回下次成長時應使用的桶數std::size_t next_bucket_count() const; // 策略支援的最大桶數std::size_t max_bucket_count() const; // 重置成長策略，就像該策略是在桶計數為 0 的情況下建立的一樣。
}要使用 robin-map，只需將包含目錄新增至包含路徑中即可。它是一個僅包含頭檔的庫。
如果您使用 CMake，也可以將 CMakeLists.txt 中的tsl::robin_map匯出目標與target_link_libraries結合。
# robin-map專案儲存在第三方目錄中的範例add_subdirectory(third-party/robin-map)target_link_libraries(your_target PRIVATE tsl::robin_map)
如果專案已經透過make install安裝，您也可以使用find_package(tsl-robin-map REQUIRED)而不是add_subdirectory 。
該庫在 vcpkg 和 conan 中可用。它也存在於 Debian、Ubuntu 和 Fedora 軟體包儲存庫中。
該程式碼應適用於任何符合 C++17 標準的編譯器。
要執行測試，您將需要 Boost Test 程式庫和 CMake。
git 克隆 https://github.com/Tessil/robin-map.gitcd robin-map/tests mkdir buildcd build .. cmake --build ../tsl_robin_map_tests
該 API 可以在這裡找到。
所有方法尚未記錄，但它們複製std::unordered_map和std::unordered_set中的行為，除非另有指定。
#include <cstdint>#include <iostream>#include <string>#include <tsl/robin_map.h>#include <tsl/robin_set.h>int main() {
tsl::robin_map<std::string, int> map = {{"a", 1}, {"b", 2}};
地圖[“c”] = 3;
地圖[“d”] = 4;
地圖.插入({“e”, 5});
地圖.擦除(“b”); for(auto it = map.begin(); it != map.end(); ++it) {//it->second += 2; // 無效.it.value() += 2;
} // {d, 6} {a, 3} {e, 7} {c, 5}for(const auto& key_value : 地圖) {
std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl;
}
if(map.find("a") != map.end()) {
std::cout <<“找到“a”。” << std::endl;
} const std::size_t precalculated_hash = std::hash<std::string>()("a");// 如果我們事先已經知道哈希值，我們可以將其傳遞到參數中以加速查找。 ( map.find("a", precalculated_hash) != map.end()) {
std::cout <<“找到有雜湊值的“a”<< precalculated_hash <<“。 << std::endl;
}
/* * 計算雜湊並比較兩個 std::string 可能會很慢。 * 我們可以將每個 std::string 的雜湊值儲存在雜湊映射中，以便透過將 StoreHash 設為 true 來加快插入和尋找速度。 */
tsl::robin_map<std::string, int, std::hash<std::string>,
std::equal_to<std::string>,
std::allocator<std::pair<std::string, int>>, true> map2;
地圖2[“a”] = 1;
地圖2[“b”] = 2; // {a, 1} {b, 2}for(const auto& key_value : map2) {
std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl;
}
tsl::robin_set<int> 設定；
set.insert({1, 9, 0});
set.insert({2, -1, 9}); // {0} {1} {2} {9} {-1}for(const auto& key : set) {
std::cout << "{" << 鍵 << "}" << std::endl;
}
}異質重載允許使用Key以外的其他類型進行查找和擦除操作，只要所使用的類型是可散列的並且與Key具有可比性。
要啟動tsl::robin_map/set中的異構重載，qualified-id KeyEqual::is_transparent必須有效。它的工作方式與std::map::find相同。您可以使用std::equal_to<>或定義自己的函數物件。
KeyEqual和Hash都需要能夠處理不同的型別。
#include <功能>#include <iostream>#include <字串>#include <tsl/robin_map.h>結構員工{employee(int id, std::string name) : m_id(id), m_name(std:: move （姓名）） {
// 要嘛我們在類別中包含比較器並使用 `std::equal_to<>`...friend bool operator==(const empl, int empl_id) {return empl.m_id == empl_id;
}friend bool 運算子==(int empl_id, const empl) {return empl_id == empl.m_id;
}friend bool 運算子 ==(const 員工& empl1, const 員工& empl2) {return empl1.m_id == empl2.m_id;
}
int m_id;
std::string m_name;
};// ...或我們實作一個單獨的類別來比較employees.struct equal_employee {using is_transparent = void; bool operator()(const empl, int empl_id) const {return empl.m_id == empl_id;
} bool operator()(int empl_id, const empl&empl) const {return empl_id == empl.m_id;
} bool 運算子()(const 員工& empl1, const 員工& empl2) const {return empl1.m_id == empl2.m_id;
}
}; 結構 hash_employee {
std::size_t 運算子()(const empl) const {return std::hash<int>()(empl.m_id);
}
std::size_t 運算子()(int id) const {return std::hash<int>()(id);
}
};int main() {// 使用 std::equal_to<> 會自動推導並轉送參數tsl::robin_map<employee, int, hash_employee, std::equal_to<>> map;
map.insert({employee(1, "John Doe"), 2001});
map.insert({employee(2, "Jane Doe"), 2002});
map.insert({employee(3, "John Smith"), 2003});// John Smith 2003auto it = map.find(3);if(it != map.end()) {
std::cout << it->first.m_name << " " << it->second << std::endl;
}
map.erase(1);// 使用具有 is_transparent 成員類型的自訂 KeyEqual tsl::robin_map<employee, int, hash_employee, equal_employee> map2;
map2.insert({employee(4, "Johnny Doe"), 2004});// 2004std::cout << map2.at(4) << std::endl;
}該庫提供了一種有效的方法來序列化和反序列化映射或集合，以便將其保存到文件或透過網路發送。為此，它要求使用者提供用於序列化和反序列化的函數物件。
struct serializer {// 必須支援 U 的以下類型： std::int16_t、std::uint32_t、// std::uint64_t、float 和 std::pair<Key, T>（如果使用映射或 Key for /） / a set.template<typename U>void operator()(const U& value);
}; struct deserializer {// 必須支援 U 的以下類型： std::int16_t、std::uint32_t、// std::uint64_t、float 和 std::pair<Key, T>（如果使用映射或 Key for /） / a set.template<類型名稱U>
U 運算子()();
};請注意，如果需要相容性，則實作會將序列化/反序列化類型的二進位相容性（位元組序、浮點二進位表示、int 大小等）保留在所提供的函數物件手中。
有關serialize和deserialize方法的更多詳細資訊可以在 API 中找到。
#include <cassert>#include <cstdint>#include <fstream>#include <type_traits>#include <tsl/robin_map.h>類別序列化器 {public:serializer(const char* file_name) {
m_ostream.exceptions(m_ostream.badbit | m_ostream.failbit);
m_ostream.open(檔案名稱, std::ios::binary);
} template<class T, 型別名稱 std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr>void operator()(const T& value) {
m_ostream.write(reinterpret_cast<const char*>(&value), sizeof(T));
} void 運算子()(const std::pair<std::int64_t, std::int64_t>& value) {
(*this)(值.first);
(*this)(值.第二);
}私有:std::ofstream m_ostream;
}; 類別反序列化器 {public:deserializer(const char* file_name) {
m_istream.exceptions(m_istream.badbit | m_istream.failbit | m_istream.eofbit);
m_istream.open(檔案名稱, std::ios::binary);
} 模板<類別 T>
T 運算子()() {
T值；反序列化（值）； 返回值；
}
private:template<class T, 型別名 std::enable_if<std::is_arithmetic<T>::value>::type* = nullptr>void deserialize(T& value) {
m_istream.read(reinterpret_cast<char*>(&value), sizeof(T));
} void deserialize(std::pair<std::int64_t, std::int64_t>& value) {deserialize(value.first);deserialize(value.second);
}私有:std::ifstream m_istream;
};int main() {const tsl::robin_map<std::int64_t, std::int64_t> 映射 = {{1, -1}, {2, -2}, {3, -3}, {4, -4}}；
const char* file_name = "robin_map.data";
{
序列化器序列（檔案名稱）；
映射.序列化(串列);
}
{
解串器 dserial(file_name);自動 map_deserialized = tsl::robin_map<std::int64_t, std::int64_t>::deserialize(dserial); 斷言（映射==映射_反序列化）；
}
{
解串器 dserial(file_name); /** * 如果序列化和反序列化映射是哈希相容的（請參閱API 中的條件）， * 將參數設為true 可以加快反序列化過程，因為我們不需要* 重新計算每個鍵的哈希值。我們也知道每個桶子需要多少空間。 */const bool hash_known = true;auto map_deserialized =
tsl::robin_map<std::int64_t，std::int64_t>::反序列化（dserial，hash_相容）； 斷言（映射==映射_反序列化）；
}
}可以使用序列化庫來避免樣板文件。
以下範例使用 Boost Serialization 和 Boost zlib 壓縮流來減少產生的序列化檔案的大小。由於在 lambda 中使用模板參數清單語法，因此此範例需要 C++20，但它可以適應較新的版本。
#include <boost/archive/binary_iarchive.hpp>#include <boost/archive/binary_oarchive.hpp>#include <boost/iostreams/filter/zlib.hpp>#include <boost/iostreams/filtering_stream.h>>pp. /serialization/split_free.hpp>#include <boost/serialization/utility.hpp>#include <cassert>#include <cstdint>#include <fstream>#include <tsl/robin_map.h>命名空間boost { 命名空間序列化{template<類別Archive，類別Key，類別T>void序列化（Archive＆ar，tsl :: robin_map <Key，T>＆map，const unsigned int版本）{split_free（ar，map，版本）;
}template<class Archive, class Key, class T>void save(Archive & ar, const tsl::robin_map<Key, T>& map, const unsigned int /*version*/) {自動序列化器= [&ar] (const自動& v) { ar & v; };
映射.序列化（序列化器）；
}template<class Archive, class Key, class T>void load(Archive & ar, tsl::robin_map<Key, T>& map, const unsigned int /*version*/) {auto deserializer = [&ar]<typename U >() { U u; ar & u;返回你； };
映射 = tsl::robin_map<Key, T>::deserialize(deserializer);
}
}}int main() {
tsl::robin_map<std::int64_t, std::int64_t> 映射 = {{1, -1}, {2, -2}, {3, -3}, {4, -4}};
const char* file_name = "robin_map.data";
{
std::ofstream ofs；
ofs.exceptions(ofs.badbit | ofs.failbit);
ofs.open(檔名, std::ios::binary);
boost::iostreams::filtering_ostream fo；
fo.push(boost::iostreams::zlib_compressor());
fo.push(ofs);
boost::archive::binary_oarchive oa(fo);
oa << 地圖；
}
{
std::ifstream ifs；
ifs.exceptions(ifs.badbit | ifs.failbit | ifs.eofbit);
ifs.open(檔名, std::ios::binary);
boost::iostreams::filtering_istream fi;
fi.push(boost::iostreams::zlib_decompressor());
fi.push(ifs);
boost::archive::binary_iarchive ia(fi);
tsl::robin_map<std::int64_t, std::int64_t> map_deserialized;
ia >> map_deserialized; 斷言（映射==映射_反序列化）；
}
}涉及tsl::robin_map和tsl::robin_set兩個潛在效能缺陷值得注意：
錯誤的哈希值。產生大量衝突的雜湊函數可能會導致以下令人驚訝的行為：當衝突次數超過一定閾值時，雜湊表將自動擴展以解決問題。然而，在退化情況下，這種擴展可能對衝突計數沒有影響，從而導致線性插入序列導致指數儲存增長的故障模式。
這種情況主要是在使用預設的二次冪增長策略和算術類型T的預設 STL std::hash<T>時觀察到的，這通常是一個恆等式！有關範例，請參閱問題 #39。解決方案很簡單：使用更好的雜湊函數和/或tsl::robin_pg_set / tsl::robin_pg_map 。
元件擦除和低負載係數。 tsl::robin_map和tsl::robin_set鏡像了 STL map/set API，它公開了一個iterator erase(iterator)方法，該方法刪除某個位置的元素，傳回一個指向下一個元素的有效迭代器。
建構這個新的迭代器物件需要走到表中的下一個非空桶，當雜湊表的負載因子較低時（即，當capacity()遠大於size()時），這可能是一個昂貴的操作。
此外， erase()方法永遠不會收縮和重新散列表，因為函數的規範不允許這樣做。沒有中間插入的隨機刪除的線性序列可能會導致具有二次運行時間成本的退化。
在這種情況下，通常甚至不需要迭代器傳回值，因此完全不需要成本。因此， tsl::robin_set和tsl::robin_map都提供了另一種擦除方法void erase_fast(iterator) ，該方法不傳回迭代器以避免尋找下一個元素。
該代碼已獲得 MIT 許可證的許可，有關詳細信息，請參閱許可證文件。
