16.4
16.4 泛型编程
STL是一种泛型编程。面向对象编程关注的是编程的数据方面， 而泛型编程关注的是算法。
它们之间的共同点是抽象和创建可重用代码， 但它们的理念不同。
泛型编程旨在写出独立于数据类型的代码。
为何使用迭代器
模板使得算法独立于存储的数据类型， 而迭代器使算法独立于使用的容器类型。
例：实现find函数， 迭代器的特征：
1.能够对迭代器执行接触引用的操作。
2.能够将一个迭代器赋给另外一个。
3.能够将一个迭代器和另一个迭代器进行比较， 看是否相等。
4.能够将一个迭代器遍历容器中的所有元素， 通过迭代器中定义的p++和++p实现。
STL按功能的强弱定义了多种级别的迭代器。
P686 实现迭代器不同的编写和修改
区分左++和右++：
iterator & operator++() {} // 左++
iterator & operator++(int) {} // 右++
STL迭代器的基本功能：P687
使用容器类时， 无需知道迭代器是如何实现的， 无需知道超尾是如何实现的， 只需要知道基本功能即可。
STL通过每个类定义适当的迭代器， 并用统一的风格设计了， 能够对内部表示绝然不同的容器， 编写相同的代码。
迭代器类型
STL定义了五种迭代器：
输入迭代器、输出迭代器、正向迭代器、双向迭代器、随机访问迭代器
输入迭代器
来自迭代器的信息视为输入
需要输入迭代器的算法不会修改容器中的值。
必须能访问容器中所有的值。
输入迭代器任何算法都应当是单通行的， 不依赖于前一次遍历时的迭代器值， 也不依赖于本次遍历中前面的迭代器值。
不保证先前的迭代器仍然可以被接触引用。
单向迭代器， 可以递增， 但不能倒退。
输出迭代器
将信息从程序传递给容器的迭代器视为输出。
与输入迭代器相似， 只能写， 不能读。
单通行。
正向迭代器
和输入迭代器、输出迭代器类似， 只是用++运算符遍历容器， 它总是按照一定的顺序遍历一系列值。
可以对前面的迭代器解除引用（如果保存了）
既可以只读， 也可以读写。
双向迭代器
具有正向迭代器的所有特性， 同时支持++和--（前缀和后缀）。
随机访问迭代器
具有双向迭代器的所有特性， 同时添加了支持随机访问的操作和用于对元素进行排序的关系运算符。
迭代器层次结构
为何需要这么多的迭代器：
目的是为了在编写算法时尽可能使用要求最低的迭代器， 并让它适用于容器的最大区间。
类型不是确定的， 只是一种概念性描述。
iterator：是随机访问迭代器
概念、改进和模型
STL中包含用于标准种类的迭代器模板。
将指针用于迭代器
指针同样支持++、--、*等操作
const int SIZE = 100;
double Receipts[SIZE];
sort(Receipts, Receipts + SIZE);
头文件：
ostream_iterator迭代器
istream_iterator迭代器
其他有用的迭代器
头文件还提供了其他一些专用的预定义迭代器类型。
反向迭代器：++被写成了--操作。
三种插入迭代器通过将复制改为插入改善了copy无法改变容器长度的问题。
添加新元素， 使用动态内存分配确保能够容纳新的信息。
都是输出迭代器概念的模型。
容器种类
附录G
以前有11中容器类型， C++新增了5种， 并移除了一种。
容器概念
描述了所有容器都通用的元素。
C++11新增的容器要求
序列：deque、C++11新增：forward_list list queue priority_queue stack vector
array也被归为序列容器， 虽然她并不满足所有条件
序列
1.迭代器至少是正向迭代器，保证元素有特定顺序。（可以执行特定位置/区间的插入、删除等操作）
2.要求其元素按严格的线性顺序排列，即存在最后一个元素、第一个元素，除了第一个和最后一个每个元素前后都各有一个元素。（链表和数组是，分支结构不是）
序列的要求+序列的可选要求
P697
vector：
是数组的一种表示， 可以动态改变长度， 并随着元素的增加和删除而增大或缩小。
除了序列， vector还是可反转容器概念的模型：rbegin()和rend()
仅在结尾处的删除和插入时间是固定的。
强调随机访问。
deque：
双端队列， 头文件：
类似于vector， 支持随机访问， 但是不像vector那样， 它在起始/结尾处插入会消耗线性的时间， 他的时间是固定的。
比vector更复杂， 所以除了起始/结尾插入更好外， 其他操作都比vector慢。
list：
双向链表， 在任意位置插入和删除都是固定的。
强调链表的快速插入和删除
也是可反转容器， 但是不支持随机访问和数组表示法。
除了序列和可反转容器外， 还包含了专用的成员函数。P699
forward_list：C++11
单链表， 只需要正向迭代器。 不可反转的容器。
queue：
头文件：
是一个适配器类。（ostream_iterator也是一个适配器类）
queue模板让底层类（默认queue）展示典型的队列接口。
STL提供了序列式容器，同时针对序列式容器提供了应用于不同场景的容器适配器，通俗讲适配器就是以序列式容器为底层数据结构，进一步封装了的为适应场景应用的容器。STL中提供了三种适配器，分别为stack，queue和priority_queue。
不允许随机访问， 不允许遍历队列， 限制队列的基本操作：队首、队尾等操作。
queue的操作：P701
priority_queue：
另一个适配器类：操作和queue相同。
区别：最大的元素被移动到队首， 默认的底层类是vector。
修改哪个元素放到队首：
priority_queue pq2(greater);
greater() 函数是一个预定义的函数对象， 稍后介绍。
stack：
适配器类。底层类默认vector。
不允许随机访问栈， 不允许遍历栈， 限制基本操作。
stack操作：P701
array：C++11
头文件：， 不是STL容器， 因为长度是固定的。 因此没有定义调整容器大小的操作。
定义了[]、at等。
很多标准STL算法可以用于array对象：copy()、for_each()。
关联容器
关联容器时对容器概念的另一个改进。 将值和键放在一起， 使用键来查找值。
查找更快， 使用某种树实现。
STL提供4中关联容器：set、multiset、map、multimap。
头文件：、
set：值类型和键相同， 键是唯一的， 不可以重复。
multiset：类似于set， 可能有多个值的键相同。
map：键和值类型可以不同， 键是唯一的， 每个键只对应一个值。
multimap：和map类似， 一个键可以和多个值关联。
set
set：关联集合、可反转、可排序， 键唯一。
set A;
set[InvalidCharacterError: "STRING," did not match the Name production]
less<> 稍后讨论。
set容器是经过排序的。
关于set的介绍：P702
multimap
可反转的， 经过排序的关联容器。
mutimap[InvalidCharacterError: "INT," did not match the Name production]
第三个模板参数是可选的。默认为less<>
STL使用模板类pair将键和值存到一个对象中。 再将pair插入。
对于pair对象， 可以用first和second访问。
P705multimap的使用。pair和multimap的组合使用。
无序关联容器：C++11
和关联容器一样， 无序关联容器也将值和键关联起来， 并使用键查找值。
底层的差别在于：关联容器基于树结构， 无序关联容器基于数据结构哈希表。
提高添加和删除元素的速度和查找算法的效率。
四种无序关联容器：unordered_set、unordered_muliset、unordered_map、unordered_mulimap——附录G