STL之关联容器的映射底层
STL的关联容器有set, map, multiset, multimap.用于实现它们的底层容器有划入标准的rb_tree和待增加标准的hashtable.
底层容器rb_tree为上层容器提供了一种有序的服务.关键步骤时间复杂度为O(lgN);
底层容器hashtable为上层容器提供的是无序的服务,但其关键步骤的时间复杂度为O(1).
那么上层容器是怎么映射究竟层容器中去的呢?以下以set和map为例,说明它们是怎样映射到rb_tree和hashtable的.
1 rb_tree模板头
对于rb_tree的节点,事实上仅仅是保存了Value对象,并没有直接保存Key.
也就是说rb_tree仅仅能直接看到Value,而看不到Key.因此要为rb_tree提供一个间接获取Key的方法.
即KeyOfValue, 它负责从Value获取相应的Key, 用于rb_tree中须要用到key值(比較)的地方.
2 hashtable模板头
与rb_tre一样, hashtable也是如此.它通过ExtractKey来提取Value相应的Key.
3 set
3.1 set的特点
键值就是实值,即key = value
3.2 set到rb_tree映射
1) set模板头
2) 到rb_tree的映射
key_type 与 value_type都是set的 Key.
3.3 set到hash_table的映射
1) set模板
2) 到hashtable的映射
4 map
4.1 map特点
通常键值与实值不等,即 key != value,为用户提供了一种key到value映射服务.
4.2 map到rb_tree映射
4.3 map到hashtable映射
在hashtable中看到的仅仅是pai<const Key, T>.
5 总结
5.1 rb_tree
value--(KeyOfValue)-->key---(Campare)->插入或删除
5.2 hashtable
value--(ExtractKey)--> key --(HashFcn)--> hashcode--(%n)--> bkt_num-->插入或删除.
相关文章
- Laravel 中 IoC 容器 服务提供者和门面的使用
- Docker最全教程——数据库容器化之持久保存数据(十一)
- 提高 K8S 容器运行时的可观察性最佳方法之一
- 科技云报道:容器与虚拟机之争?不存在的!
- 大厂都在使用的开源容器Docker,速度掌握这套面试题
- c++STL map(映射)容器总结
- Docker容器-----搭建本地私有仓库
- Jenkins使用aqua-microscanner-plugin进行容器漏洞扫描
- Spring Ioc容器核心类继承图
- 解决docker容器映射信息修改问题
- docker gitlab-ce 容器root密码重置小记
- 【转】Spring学习---SpringIOC容器的初始化过程
- C++ STL bitset 容器详解
- Docker发布容器平台新版 引入秘密管理功能
- 对Windows Server容器的数据保护改进了吗?
- 思科扩展Docker合作 开发容器网络软件
- docker容器和宿主机的主机名映射失败