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类似的接口，但存在一些差异。
仅当以下语句为 true 时，强异常保证才成立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。explicit custom_policy(std::size_t& min_bucket_count_in_out); // 返回该哈希所属的桶[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 的情况下创建的一样。 // 清除后，当调用 bucket_for_hash() 时，该策略必须始终返回 0。 void clear() noexcept;
}要使用 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");// 如果我们事先已经知道哈希值，我们可以将其传递到参数中以加速查找。 if( 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);auto map_deserialized = tsl::robin_map<std::int64_t, std::int64_t>::deserialize(dserial); 断言（映射==映射_反序列化）；
}
{
解串器 dserial(file_name); /** * 如果序列化和反序列化映射是哈希兼容的（请参阅 API 中的条件）， * 将参数设置为 true 可以加快反序列化过程，因为我们不需要 * 重新计算每个键的哈希值。我们还知道每个桶需要多少空间。 */const bool hash_complete = 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.hpp>#include <boost /serialization/split_free.hpp>#include <boost/serialization/utility.hpp>#include <cassert>#include <cstdint>#include <fstream>#include <tsl/robin_map.h>namespace boost { 命名空间序列化 {template<class Archive, class Key, class T>void serialize(Archive & ar, tsl::robin_map <Key, T>& map, const unsigned int version) {split_free(ar, map, version);
}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 许可证的许可，有关详细信息，请参阅许可证文件。
