本文预览：
- deque\queue\stack深度探索
- RB-tree深度探索
- set\multiset深度探索
- map\multimap深度探索
- hashtable深度探索
- hash_set\hash_map
deque\queue\stack深度探索
deque是双向队列，两端都可以push和pop元素，它是向两端调整空间，双向队列依然是线性的，但是物理空间实现相对要复杂一些，功能比较强大，实际上，在STL里，queue和stack应该叫做适配器，而不是容器，因为queue和stack完全是由deque来实现的。
deque
deque实际上是由物理上连续的map和分散的buffer构成，deque之所以给人感觉是连续的，这完全是其爹地器的功劳。
queue
queue
stack
queue
stack(先进后出)，queue(先进先出)使用起来比较简单，接口也较少，deque完全可以实现他们的需求，因此queue和stack底层是deque，利用delegate模式。需要注意的是，在线性容器当中，他俩不提供迭代的功能，因此没有迭代器。
RB-tree深度探索
红黑树是关联容器set和map的底层支撑，绝大部分功能都是由红黑树来实现的，红黑树是一种高度平衡二叉树，左右子树比较均衡，不会某一分支深度过深，导致查找时间过长；关联容器在查找的时候非常快，因为红黑树结构在插入的时候都是排序好的。
红黑树
红黑树提供了两种插入接口，insert_unique()和insert_equal()俩接口，分别为set\map和multiset\multimap所调用。
set\multiset深度探索
需要注意的是，set和multiset不能使用迭代器修改元素的值，因为在set中key和value是同一个值，否则迭代器失效。
set\multiset
map\multimap深度探索
map重载了[]操作符
map\multimap
hashtable深度探索
hashtable
hashtable是另外一种底层实现结构，根据hash函数算出位置，放置元素，如果算出的位置相同，发生碰撞的时候，那就把这个位置的所有元素放入一个链表；如果元素的个数和bucket的个数相同的时候就把bucke的数量扩容到原来的两倍左右，从新计算元素的位置，从新排列，所有hashtable又叫做散列表。
这站图的信息可能更丰富一些：
hash.png
hash_set\hash_map
使用hashtable实现的set和map，在C++11以后统一称为unordered_map, unordered_set。
网友评论