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-->插入或删除.