第三讲

十八&十九、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一样。