#tsl::robin_map# 关联式容器
志扬工作室
共 7323字,需浏览 15分钟
·
2023-08-07 22:02
关联式容器类型
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 Github
https://github.com/Tessil/robin-map
Tsl 特点
• 仅头文件
• 速度快
• 高效序列化
• API类似std::unordered_map和std::unordered_set
tsl 案例:
//
#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
评论