一、deque queue stack 深度探索
1. 逻辑上, deque是双向开口的连续线性空间。
2. 标准库具体实现上, 内部是分段连续的, 通过map将各个连续的进行串联。
3. 通过中控(map),缓冲区, 迭代器 (这里是个random_access_iterator_tag类型)
4. 内部处理过程中遇到缓冲区编辑通过 set_node函数完成缓冲区之间跳转
5. stack, queue可以选择list, 的却做为一个底部结构, 并且不提供iterator
二、RB-tree 深度探索
1. 红黑树是一种平衡二叉搜索树。提供两种insertion insert_unique(), insert_equal()
三、set/multiset 深度探索
1. set/multiset 以 rb_tree为底层结构;
2. set/muliset 无法使用iterators改变元素。(const iterator)
3. set 可以是唯一的, multiset key可以重复
四、map/multimap深度探索
1. map/multimap 以 rb_tree为底层结构;
2. map/mulimap 无法使用iterators改变key可以改变data。
3. map可以是唯一的, multimap key可以重复
五、hashtable深度探索
1. 系统配置buckets数量质数列表,取值大致为实际数量的2倍;
2. 超过buckets数量后, 扩充buckets, 重新hash;
3. buckets 使用vector 进行管理, 数据存放再buckets执行的一个类似链表的结构上。
4. hash_set/hash_multiset, hash_map/hash_multimap
5、unordered 容器的概念 :对应 unodered_set, unordered_multiset, unodered_map, unordered_multimap