16.3

STL提供了一组表示容器、迭代器、函数对象和算法的模板。

容器是一个与数组类似的单元， 可以存储若干值。

容器是同质的， 及存储的值的类型相同

算法是完成特定任务（如对数组进行排序或在链表中查找特定值）的处方

迭代器能够用来遍历容器的对象， 与能够遍历数组的指针相似， 是广义指针。

函数对象是类似于函数的对象， 可以是类对象或函数指针

STL不是面向对象的编程， 而是一种不同的编程模式——泛型编程。

简单介绍STL， 附录G对各种STL方法和函数进行了总结。

头文件：

vector使用动态内存分配， 可以用初始化参数确定需要多少元素。

运算符[]被重载， 可以使用常用的数组表示法访问各个元素。

分配器：每个STL容器模板都接受一个可选的模板参数， 这个参数指定用哪个分配器对象来管理内存。

如果省略模板参数的值， 则容器模板将默认使用allocator这个类， 这个类使用new和delete

所有容器模板基本都包含：

size()——返回容器中的元素数目。

swap()——交换两个对象的内容。

begin()——返回一个指向容器中第一个元素的迭代器。

end()——返回一个表示超过容器尾的迭代器。

迭代器：一个广义指针。STL能够为各种不同的容器类提供统一的接口。

每个容器类都定义了一个合适的迭代器， 该迭代器的类型是一个名为iterator的typedef， 其作用域为整个类。

例：

迭代器的行为就像指针， 可以进行 * 和 ++ 操作

可以使用auto直接类型推断。

什么是超过结尾呢？即指向容器超过最后一个元素的迭代器。

vector还包含一些只有部分STL容器才有的方法：

push_back()将元素添加到矢量末尾。这样做时， 他还负责内存管理， 增加矢量的长度， 以便容纳新的成员。

erase()删除矢量中给定区间的元素， 接受两个迭代器参数：迭代器还定义了加法（begin() + 2）[p1, p2)

insert()和erase()相反， 接受三个迭代器参数， 第一个指定新元素插入的位置， 第二三个参数指定插入的区间。该区间通常是另一个容器对象的一部分。

矢量模板类不包含对数组等的搜索、排序、随机排序等方法。

定义适用于所有容器类的非成员函数。

但是一般有些成员函数方法效率更高。

非成员函数可以交换两个类型不同的容器中的内容。

for_each()函数可以对指定区间的迭代器进行统一函数操作：但是不能改变值。可以避免显式使用迭代器变量。可以代替for循环。

Random_shuffle()函数接受两个指定区间的迭代器参数， 并随机排列该区间中的元素。需要容器类允许随机访问， vector可以。

sort()函数也要求容器支持随机访问：

版本1：接受两个指定区间的迭代器参数， 并使用在容器元素类型中定义的 < 运算符， 对区间中进行排序操作。如果容器元素是用户定义的类型， 必须有operator<()方法。升序

版本2：第三个参数函数指针（函数对象）， 而不是使用operator<()， 返回值应当可以转换位true表示顺序正确或false表示顺序不正确。

全排序：如果a < b 和 b < a 都不成立， 则a和b必定相同。

完整弱排序：他们可能相同， 也可能只是在某方面相同。

括号内的代码声明了一个类型与容器存储的内容相同的变量， 然后指出了容器的名称。 接下来， 循环体使用指定的变量依次访问容器的每个元素。

基于范围的for循环可以改变容器的内容， 诀窍是指定一个引用参数。