STL与泛型编程
主要内容：
介绍了 STL 的体系结构，六大部件和主要的容器。并利用测试程序介绍了容器的使用方法。
目标
- Level 0: 使用 C++ 标准库
- Level 1: 深入认识 C++ 标准库（胸中自由丘壑）
- Level 2: 良好使用 C++ 标准库
- Level 3: 扩充 C++ 标准库
参考网站
- www.cplusplus.com
- en.cppreference.com
- gcc.gnu.org
推荐书籍
- C++ 标准库
- STL 源码剖析
使用一个东西，却不明白它的道理，不高明。--林语堂
一、STL 体系结构
1. 概述
- 六大部件
- 容器(Containers)：存放数据。
- 分配器(Allocators)：支持容器分配内存。
- 算法(Algorithms)：排序，查找... 利用迭代器处理容器的数据
- 迭代器(Iterators)：一种泛化的指针。
- 适配器(Adapters)：可以转换容器、泛函数、迭代器
- 仿函数(Functors)：函数功能的类
- 使用
- 用到哪个容器，就要引用哪个头文件。
- 在使用容器和算法时要根据使用场景，考虑复杂度。
vector<int,allocator<int>> vi(ia,ia+6); cout_if(vi.begin(), vi.end(), not1(bind2nd(less<int(), 40 )));
2. 容器-结构与分类
- 顺序容器
- array-无法扩展，元素数量在定时时就确定了
- vector-单项扩展，每次增大一倍容量
- deque-分段连续，双向扩展
- list-双向链表
- forward_list / slist-单项链表
- 关联容器
- set/multiset-内部利用红黑树实现，Key==Value
- map/multimap-内部利用红黑树实现，存放 Key 与 Value 的键值对 Pair<Key,Value>
- 无序容器（c++11）
- unordered set/multiset-利用hash table separeta chining 实现
- unordered map/multimap-利用hash table separeta chining 实现
3. 容器-使用示例
- array
- array.size(), array.front(), array.back(), array.data() (返回array首元素的地址
- vector
- capacity() 容量每次扩展是上次的二倍, size(), data(), front(), back(), push_back()
- push_back()，内存不够时会抛出异常 std::bad_alloc， 需要 abort() 退出程序。
- list
- max_size(), list.sort()
- list自己提供了sort()，用容器自己提供sort比用::sort()要好，效率更高。
- forward_list
- 本身也有sort(), 没有size() 和 back().
- slist 单向链表，是非标准库中的，gnc中的。
- include<ext\slist>
- deque
- max_size()
- 排序只能用::sort().
- 双向队列，分段连续（由一个个段组成，每段是连续的内存空间。用一个map存放每个段的指针）
- stack & queue是
- 技术上属于容器适配器，是利用deque实现的。
- stack先进后出。queue先进先出。push(), pop().
- set/multiset
- insert(), size(), max_size().
- 容器自己提供 find()
- map/multimap
- insert(), find()
- map可以用[]赋值，multimap不能使用[].
- unordered_set / unordered_multiset
- insert(),size(),max_size(),bucket_count()(篮子一定比元素要多，因为有些篮子可能是空的)
- bucket_size(i)（第i个篮子中元素的数量）当元素数量和篮子数量一致时，会分配原有的篮子数量的二倍的空间，之后重新分配元素的放置位置。
- load_factor(), max_load_factor(), max_bucket_count()。
- 容器自己提供 find()
- unordered_map / unordered_multimap
- hash_set, hash_map,hash_multiset,hash_multimap
- unordered的旧版本。
