STL源码剖析

vector

• 变长数组
• 内存空间连续分配

deque、queue、stack

1. deque

• 双向队列，号称是连续的，但是其底层实现不是连续的——分段连续状态
• 允许遍历，提供itetator：++，--，+=
• 作为stack和queue的默认底层结构

2. queue和stack

• queue和stack可以使用list作为底层结构，queue不可以使用vector作为底层结构。
• queue和stack都不可选择set或map作为底部结构

RB_tree, set, multiset, map, multimap

1. RB_tree

• _Rb_tree<int,int,_Identity<int>,less<int>> itree;</int></int>
• identity是从keyofvalue内获得key——这里的默认实现为返回原值
• insert_unique——唯一插入；insert_equal——重复插入

2.set与multiset

• 使用const_iterator保证key值不被修改
• insert函数的区别实现两种容器功能
• key与data为同一个值
• 支持遍历

3.map与multimap

• pair<const Key, T> value_type作为value——保证key值不被修改
• select1st取代identity函数，获取key值
• 支持遍历
• 独特的operator[ ]——二分查找迭代器，如果找到则传回，未找到则创建并插入。

hashtable, unordered_set, unordered_map

1. hashtable

• buckets vector——大小可以为质数（53）

• 质数取模后数据不会集中在某个点上。

• 哈希冲突

  • 拉链法（separate chaining)
  • 扩容法（rehashing: 53->97->193....)——防止链表过长（链表长度大于篮子长度时候）

• 篮子个数大于元素个数（非重复个数）

Algorithm

1. 算法的形式

• 语言层面：function template
• 对容器一无所知，它u哦需要的一切信息都必须从iterators取得。iterators必须能够回答Algorithm的所有提问，才能代培该Algorithm的所有操作。

2. 迭代器的分类

• output_iterator_tag——otream

• input_iterator_tag——istream

• forward_iterator_tag——forward_list|hashtable

• bidirectional_iterator_tag——list|rb_tree

• radom_access_iterator_tag——vector|array|deque

3. iterator_category对算法的影响

• distance函数——计算两个迭代器之间的距离
• advance函数——移动迭代器
• copy函数——不同的iterator traits和type traits导致copy函数的底层实现不同
• destory函数同上

3. 算法剖析

• accumulate——求和？（可拓展a+2*b）
• for_each——for_each(InputIterator first,InputIterator last, Function f )对每一个对象执行f(*it)
• replace, replace_if, replace_copy
• count, count_if
• find, find_if
• sort
• reverse
• binary_search
  • lower_bound
  • upper_bound

仿函数functors

1. 算术类：plus(+), minus(-),
2. 逻辑运算类：logical_and(&)
3. 相对关系类：equal_to, less
4. 其他（GNU c++)：identity, select1st, select2nd