第三讲
十八&十九、deque&queue和stack深度探索
1.容器deque
分段连续
vector里面的指针指向buffer
vector怎么双向增长呢？
所有的容器都维护了两个迭代器：start和finish。
一个deque的大小是40，start(16)+finish(16)+map(4)+map_size(4)=40
insert()可以往前或往后推，判断离头端近还是尾端近，选择近的往那一端推。
deque如何模拟连续空间：iterator操作符重载，提供[]操作符。
2.容器queue和stack
deque双向进出
stack先进后出
queue先进先出
queue和stack的底层容器是deque
stack和queue都不允许遍历，也不提供iterator。
stack和queue都可选择list或deque作为底层结构。
queue不可选择vector作为底层结构。stack可选择vector作为底层结构。
stack和queue都不可选择set或map作为底层结构。
二十、RB-tree深度探索
关联式容器底层用红黑树和哈希表作支持。
1.容器rb_tree
红黑树是平衡二元搜寻树。排列规则有利search和insert，并保持适度平衡，无任何解答过深。
rb_tree提供遍历操作及iterators。按正常规则（++ite）遍历，便能获得排序状态。
不应使用rb_tree的iterators改变元素值（因为元素有其严谨排列规则）。编程层面并未阻止此事。如此设计是正确的，因为rb_tree即将为set和map服务（作为其底部支持），而map允许元素的data被改变，只有元素的key才是不可改变的。
rb_tree提供两种insertion操作：insert_unique()和insert_equal()。前者表示节点key在整个tree中独一无二，否则安插失败；后者表示节点key可重复。
key+data=value
rb_tree大小：12（G2.9），24（G4.9）
2.容器_Rb_tree(G4.9)
使用handle-body。
二十一、set/multiset深度探索
关联式容器底层用红黑树和哈希表作支持。
1.容器set
set/multiset以rb_tree为底层结构，因此有元素自动排序特性。排序的依据是key，而set/multiset元素的value和key合一：value就是key。
set/multiset提供遍历操作及iterators。按正常规则（++ite）遍历，便能获得排序状态。
无法使用set/multiset的iterators改变元素值（因为元素有其严谨排列规则）。set/multiset的iterator是其底部的RB tree的const-iterator，就是为了禁止user对元素赋值。
set元素的key必须独一无二，因此其insert()用的rb_tree的insert_unique()。
multiset元素的key可以重复，因此其insert()用的rb_tree的insert_equal()。
set的所有操作，都呼叫底层t（红黑树）的操作。从这层意义看，set是个container adapter。
2.容器set，in VC6
VC6不提供identity()，_Kfn（内部class）相当于G2.9的identity()。
二十二、map/multimap深度探索
1.容器map
map/multimap以rb_tree为底层结构，因此有元素自动排序特性。排序的依据是key。和set的不同：key和data合成value。
map/multimap提供遍历操作及iterators。按正常规则（++ite）遍历，便能获得排序状态。
无法使用map/multimap的iterators改变元素的key（因为key有其严谨排列规则），但可以用它改变元素的data。因此map/multimap内部自动将user指定的key tyep设为const，禁止user对元素的key赋值。
map元素的key必须独一无二，因此其insert()用的rb_tree的insert_unique()。
multimap元素的key可以重复，因此其insert()用的rb_tree的insert_equal()。
容器map有四个模板参数，前两个Key和T（即data）没有默认值。map把Key和T包成pair<const Key,T>。
2.容器map，in VC6
VC6不提供select1st()，_Kfn（内部class）相当于G2.9的select1st()。
3.容器map，独特的operator[]
传回和key相关的data。如果key不存在，会用key创建一个pair，使用默认的data值。
二十三&二十四、hashtable深度探索
1.容器hashtable
如果发生碰撞，把它们放在一个链表串起来。Sepatate Chaining。
hashtable一开始有一定量的buckets（vector）。如果元素的个数比buckets个数多，就要rehashing。因为链表过长，搜寻速度慢。GUN C中一开始buckets的个数是53，扩展时*2然后找附近的质数即97。数字不是运行时才计算的，而是一开始就编好的。
可以用hashtable iterators改变元素的data，但不能改变元素的key。因为hashtable根据key实现严谨的元素排列。
sizeof(hashtable) = 1 + 1 +1 + sizeof(buckets)(12) + 4 = 19 ->20
GUN C用的单向链表，VC用的双向链表。
Hashtable需要指定6个模板参数。
2.hash-function，hash-code
hash function的目的，就是希望根据元素值算出一个hash code（一个可进行modulus运算的值），使得元素经hash code映射之后能够杂够乱够随机地被置于hashtable内。愈是杂乱，愈不容易发生碰撞。
3.modulus运算
二十五、hash_set/hash_multiset,hash_map/hash_multimap概念
二十六、unordered容器概念
只是换了名字，和hash一样。
