STL与泛型编程 Week3 (Boolan) by Im4li

1-deque&queue和 stack深度探索
deque与vector不同，deque看似连续，却是由多个分段空间所连接起来的。deque通过一个map来指向各个分散空间。
deque的iterator构造如下图

iterator

其中cur指向当前的单个元素，first指向当前分段的首个元素，last指向当前分段的最后一个元素，node则指向map中当前分段的指针。
start iterator的node指向第一个分段的指针，last iterator的node指向map中最后一个指针的前一个，即最后一个分段的指针。
map的实质是一个指针数组。map_size表示其大小，并且会增长。
queue(FIFO)和stack(FILO)均默认使用deque为基础容器实现，但是依此实现的queue和stack均不允许遍历，也没有自己的iterator。（也都可以使用list作为底部容器，其中stack可以使用vector作为底部容器，而queue不可以。均不可以使用色图，map来作为底部容器）

queue<T,deque<T>> x;  //默认
stack<T,deque<T>> x;  //默认
queue<T,list<T>> x;  //√
stack<T,list<T>> x;  //√
queue<T,vector<T>> x;  //×
stack<T,vector<T>> x;  //√
queue<T,set<T>> x;  //×
stack<T,set<T>> x ;  //×
queue<T,map<T>> x  ;//×
stack<T,map<T>> x;  //×

2-RB-tree深度探索
rb_tree作为set与map的底层结构。
RB-tree是平衡二叉查找树中经常使用的一种。
平衡二叉查找树内部排列规律，有利于search和insert，并保持适度平衡，无任何节点过深。
3-set/multiset深度探索

set/multiset

4-map/multimap深度探索

map/multimap

map可以使用[]进行单个插入
5-hashtable深度探索
rehashing:当元素个数大于当前的hashtable的大小时，要进行扩大，成长。
6-hash_set/hash_multiset, hash_map/hash_multimap概念
相对于以RB tree为底层结构的容器来说，以hashtable为底层结构的容器没有自动排序，是无序的。
7-unordered容器概念