#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

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





浏览 198
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报