#tsl::robin_map# 关联式容器-技术圈

“ 文章所涉及内容更多来自网络，在此声明，并感谢知识的贡献者！”

关联式容器类型

—

关联式容器类型
map: 红黑树具有自动排序的功能，是非严格的二叉搜索树。map内部的所有元素都是有序的，使用中序遍历可将键值按照从小到大遍历出来。
优点：有序性，内部实现的红黑树的查找，插入和删除的复杂度都是O(logn),因此效率非常高。
缺点：空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点，孩子节点和红。黑性质，使得每一个节点都占用大量的空间。
适用：对于有顺序要求的问题，用map会高效一些。
unordered_map: 哈希表（也叫散列表，通过关键码值映射到Hash表中一个位置来访问记录，查找的复杂度是O(1)。无序的（海量数据广泛应用）。
优点：因为内部实现哈希表，因此其查找速度非常快
缺点：哈希表的建立比较耗费时间，有可能还会哈希冲突（开链法避免地址冲突）
适用：常用于查找问题。
tsl
使用循环哈希的快速哈希映射和哈希集的C++实现
循环映射库是一个快速哈希映射和哈希集的C++实现，使用开放寻址和线性循环哈希以及后移删除来解决冲突。
提供了四个类：tsl:：robin_map、tsl::robin_set、tsl：：robin_pg_map和tsl::robin_pg _set。前两种速度更快，使用二次幂增长策略，后两种使用主要增长策略，能够更好地应对糟糕的哈希函数。
据传：用 tsl::robin_map 替换了原来的 boost::unordered_map，整体性能提升了 5 倍

关联式容器函数

—

关联式容器的常用函数：
map的所有成员函数的列表：
构造函数/析构函数
Functions    Description
constructors    Construct map
destructors    Map destructor
operator=    Copy elements of the map to another map.
迭代器
Functions    Description
begin    Returns an iterator pointing to the first element in the map.
cbegin    Returns a const iterator pointing to the first element in the map.
end    Returns an iterator pointing to the past-end.
cend    Returns a constant iterator pointing to the past-end.
rbegin    Returns a reverse iterator pointing to the end.
rend    Returns a reverse iterator pointing to the beginning.
crbegin    Returns a constant reverse iterator pointing to the end.
crend    Returns a constant reverse iterator pointing to the beginning.
容量
Functions    Description
empty    Returns true if map is empty.
size    Returns the number of elements in the map.
max_size    Returns the maximum size of the map.
元素访问
Functions    Description
operator[]    Retrieve the element with given key.
at    Retrieve the element with given key.
修饰符
Functions    Description
insert    Insert element in the map.
erase    Erase elements from the map.
swap    Exchange the content of the map.
clear    Delete all the elements of the map.
emplace    Construct and insert the new elements into the map.
emplace_hint    Construct and insert new elements into the map by hint.
观察者
Functions    Description
key_comp    Return a copy of key comparison object.
value_comp    Return a copy of value comparison object.
运作方式
Functions    Description
find    Search for an element with given key.
count    Gets the number of elements matching with given key.
lower_bound    Returns an iterator to lower bound.
upper_bound    Returns an iterator to upper bound.
equal_range    Returns the range of elements matches with given key.
分配者
Functions    Description
get_allocator    Returns an allocator object that is used to construct the map.
非成员重载函数
Functions    Description
operator==    Checks whether the two maps are equal or not.
operator!=    Checks whether the two maps are equal or not.
operator<    Checks whether the first map is less than other or not.
operator<=    Checks whether the first map is less than or equal to other or not.
operator>    Checks whether the first map is greater than other or not.
operator>=    Checks whether the first map is greater than equal to other or not.
swap()    Exchanges the element of two maps.

关联式容器-tsl

—

Tsl Github
https://github.com/Tessil/robin-map

Tsl 特点
• 仅头文件
• 速度快
• 高效序列化
• API类似std::unordered_map和std::unordered_set

tsl 案例：

// Test.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#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} };
   map["c"] = 3;
   map["d"] = 4;

   map.insert({ "e", 5 });
   map.erase("b");

   std::cout << map["e"] << std::endl;
   std::cout << map["f"] << std::endl;

   for (auto it = map.begin(); it != map.end(); ++it) {
       //it->second += 2; // Not valid.
       it.value() += 2;
   }

   // {d, 6} {a, 3} {e, 7} {c, 5}
   for (const auto& key_value : map) {
       std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl;
   }

   if (map.find("a") != map.end()) {
       std::cout << "Found \"a\"." << std::endl;
   }

   const std::size_t precalculated_hash = std::hash<std::string>()("a");
   // If we already know the hash beforehand, we can pass it in parameter to speed-up lookups.
   if (map.find("a", precalculated_hash) != map.end()) {
       std::cout << "Found \"a\" with hash " << precalculated_hash << "." << std::endl;
   }

   /*
   * Calculating the hash and comparing two std::string may be slow.
   * We can store the hash of each std::string in the hash map to make
   * the inserts and lookups faster by setting StoreHash to 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;

   map2["a"] = 1;
   map2["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;
   set.insert({ 1, 9, 0 });
   set.insert({ 2, -1, 9 });

   // {0} {1} {2} {9} {-1}
   for (const auto& key : set) {
       std::cout << "{" << key << "}" << std::endl;
   }
}

参考资料

—

参考资料：
https://zhuanlan.zhihu.com/p/266741325
https://blog.csdn.net/yelede2009/article/details/120186206
https://blog.csdn.net/hatlonely/article/details/81349986
http://www.aiuxian.com/article/p-bkrgjqnd-ke.html
https://www.codfox.com/archives/20220121-1.html
https://www.imangodoc.com/16691.html