#tsl::robin_map# 關(guān)聯(lián)式容器
關(guān)聯(lián)式容器類(lèi)型
map: 紅黑樹(shù) 具有自動(dòng)排序的功能，是非嚴(yán)格的二叉搜索樹(shù)。map內(nèi)部的所有元素都是有序的，使用中序遍歷可將鍵值按照從小到大遍歷出來(lái)。
優(yōu)點(diǎn)：有序性，內(nèi)部實(shí)現(xiàn)的紅黑樹(shù)的查找，插入和刪除的復(fù)雜度都是O(logn),因此效率非常高。
缺點(diǎn)：空間占用率高，因?yàn)閙ap內(nèi)部實(shí)現(xiàn)了紅黑樹(shù)，雖然提高了運(yùn)行效率，但是因?yàn)槊恳粋€(gè)節(jié)點(diǎn)都需要額外保存父節(jié)點(diǎn)，孩子節(jié)點(diǎn)和紅。黑性質(zhì)，使得每一個(gè)節(jié)點(diǎn)都占用大量的空間。
適用：對(duì)于有順序要求的問(wèn)題，用map會(huì)高效一些。
unordered_map: 哈希表（也叫散列表，通過(guò)關(guān)鍵碼值映射到Hash表中一個(gè)位置來(lái)訪問(wèn)記錄，查找的復(fù)雜度是O(1)。無(wú)序的 （海量數(shù)據(jù)廣泛應(yīng)用）。
優(yōu)點(diǎn)：因?yàn)閮?nèi)部實(shí)現(xiàn)哈希表，因此其查找速度非常快
缺點(diǎn)：哈希表的建立比較耗費(fèi)時(shí)間，有可能還會(huì)哈希沖突（開(kāi)鏈法避免地址沖突）
適用：常用于查找問(wèn)題。
tsl
使用循環(huán)哈希的快速哈希映射和哈希集的C++實(shí)現(xiàn)
循環(huán)映射庫(kù)是一個(gè)快速哈希映射和哈希集的C++實(shí)現(xiàn)，使用開(kāi)放尋址和線性循環(huán)哈希以及后移刪除來(lái)解決沖突。
提供了四個(gè)類(lèi)：tsl:：robin_map、tsl::robin_set、tsl：：robin_pg_map和tsl::robin_pg _set。前兩種速度更快，使用二次冪增長(zhǎng)策略，后兩種使用主要增長(zhǎng)策略，能夠更好地應(yīng)對(duì)糟糕的哈希函數(shù)。
據(jù)傳：用 tsl::robin_map 替換了原來(lái)的 boost::unordered_map，整體性能提升了 5 倍
關(guān)聯(lián)式容器的常用函數(shù)：
map的所有成員函數(shù)的列表：
構(gòu)造函數(shù)/析構(gòu)函數(shù)
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.
元素訪問(wèn)
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.
運(yùn)作方式
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.
非成員重載函數(shù)
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 特點(diǎn)
? 僅頭文件
? 速度快
? 高效序列化
? API類(lèi)似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
評(píng)論
圖片
表情