19. C++ STL标准模板库介绍
C++ 的标准模板库（Standard Template Library，STL）是泛型程序设计最成功应用的实例。STL 是一些常用数据结构（如链表、可变长数组、排序二叉树）和算法（如排序、查找）的模板的集合。
容器用于存放数据的类模板。
可变长数组、链表、平衡二叉树等数据结构在 STL 中都被实现为容器。
程序员使用容器时，即将容器类模板实例化为容器类时，会指明容器中存放的元素是什么类型的。
容器中可以存放基本类型的变量，也可以存放对象。对象或基本类型的变量被插入容器中时，实际插入的是对象或变量的一个复制品。
STL 中的许多算法（即函数模板），如排序、查找等算法，在执行过程中会对容器中的元素进行比较。这些算法在比较元素是否相等时通常用运算符进行，比较大小通常用<运算符进行，因此，被放入容器的对象所属的类最好重载==和<运算符，以使得两个对象用==和<进行比较是有定义的。
19.1 容器分为两大类：
1、顺序容器
顺序容器有以下三种：可变长动态数组 vector、双端队列 deque、双向链表 list。
之所以被称为顺序容器，是因为元素在容器中的位置同元素的值无关，即容器不是排序的。将元素插入容器时，指定在什么位置（尾部、头部或中间某处）插入，元素就会位于什么位置。
2、关联容器
关联容器有以下四种：set、multiset、map、multimap。
关联容器内的元素是排序的。插入元素时，容器会按一定的排序规则将元素放到适当的位置上，因此插入元素时不能指定位置。默认情况下，关联容器中的元素是从小到大排序（或按关键字从小到大排序）的，而且用<运算符比较元素或关键字大小。因为是排好序的，所以关联容器在查找时具有非常好的性能。
除了以上两类容器外，STL 还在两类容器的基础上屏蔽一部分功能，突出或增加另一部分功能，实现了三种容器适配器：栈 stack、队列 queue、优先级队列 priority_queue。
所有容器都有以下两个成员函数：
int size()：返回容器对象中元素的个数。
bool empty()：判断容器对象是否为空。
顺序容器和关联容器还有以下成员函数：
begin()：返回指向容器中第一个元素的迭代器。
end()：返回指向容器中最后一个元素后面的位置的迭代器。
rbegin()：返回指向容器中最后一个元素的反向迭代器。
rend()：返回指向容器中第一个元素前面的位置的反向迭代器。
erase(...)：从容器中删除一个或几个元素。该函数参数较复杂，此处省略。
clear()：从容器中删除所有元素。
如果一个容器是空的，则 begin() 和 end() 的返回值相等，rbegin() 和 rend() 的返回值也相等。
顺序容器还有以下常用成员函数：
front()：返回容器中第一个元素的引用。
back()：返回容器中最后一个元素的引用。
push_back()：在容器末尾增加新元素。
pop_back()：删除容器末尾的元素。
insert(...)：插入一个或多个元素。
19.2 STL迭代器(iterator)详解
要访问顺序容器和关联容器中的元素，需要通过iterator进行。iterator是一个变量，相当于容器和操纵容器的算法之间的中介。迭代器可以指向容器中的某个元素，通过迭代器就可以读写它指向的元素。从这一点上看，迭代器和指针类似。
迭代器按照定义方式分成以下四种。
1) 正向迭代器，定义方法如下：
容器类名::iterator 迭代器名;
2) 常量正向迭代器，定义方法如下：
容器类名::const_iterator 迭代器名;
3) 反向迭代器，定义方法如下：
容器类名::reverse_iterator 迭代器名;
4) 常量反向迭代器，定义方法如下：
容器类名::const_reverse_iterator 迭代器名;
迭代器用法示例通过迭代器可以读取它指向的元素，*迭代器名就表示迭代器指向的元素。通过非常量迭代器还能修改其指向的元素。
迭代器都可以进行++操作。反向迭代器和正向迭代器的区别在于：
1、对正向迭代器进行++操作时，迭代器会指向容器中的后一个元素；
2、而对反向迭代器进行++操作时，迭代器会指向容器中的前一个元素。
实例：迭代器遍历一个 vector 容器
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v; //v是存放int类型变量的可变长数组，开始时没有元素
for (int n = 0; n<5; ++n)
v.push_back(n); //push_back成员函数在vector容器尾部添加一个元素
vector<int>::iterator i; //定义正向迭代器
for (i = v.begin(); i != v.end(); ++i) { //用迭代器遍历容器
cout << *i << " "; //*i 就是迭代器i指向的元素
}
cout << endl;
//用反向迭代器遍历容器
for (vector<int>::reverse_iterator j = v.rbegin(); j != v.rend(); ++j)
cout << *j << " ";
return 0;
}
运行结果.png
注意：
1、写前置++相比于写后置++，程序的执行速度更快。
2、后置++要多生成一个局部对象 tmp，因此执行速度比前置的慢。同理，迭代器是一个对象，STL 在重载迭代器的++运算符时，后置形式也比前置形式慢。在次数很多的循环中，我们提倡使用前置++。
3、容器适配器 stack、queue 和 priority_queue 没有迭代器。容器适配器有一些成员函数，可以用来对元素进行访问。
19.3 迭代器的功能分类
不同容器的迭代器，其功能强弱有所不同。容器的迭代器的功能强弱，决定了该容器是否支持 STL 中的某种算法。例如，排序算法需要通过随机访问迭代器来访问容器中的元素，因此有的容器就不支持排序算法。
常用的迭代器按功能强弱分为输入、输出、正向、双向、随机访问五种，我们介绍三种应用度较高的。
1、正向迭代器。假设 p 是一个正向迭代器，则 p 支持以下操作：++p，p++，*p。此外，两个正向迭代器可以互相赋值，还可以用==和!=运算符进行比较。
2、双向迭代器。双向迭代器具有正向迭代器的全部功能。除此之外，若 p 是一个双向迭代器，则--p和p--都是有定义的。--p使得 p 朝和++p相反的方向移动。
3、随机访问迭代器。随机访问迭代器具有双向迭代器的全部功能。若 p 是一个随机访问迭代器，i 是一个整型变量或常量，则 p 还支持以下操作：
p+=i：使得 p 往后移动 i 个元素。
p-=i：使得 p 往前移动 i 个元素。
p+i：返回 p 后面第 i 个元素的迭代器。
p-i：返回 p 前面第 i 个元素的迭代器。
p[i]：返回 p 后面第 i 个元素的引用。
对于随机访问迭代器还要注意：
1、两个随机访问迭代器 p1、p2 还可以用 <、>、<=、>= 运算符进行比较。p1<p2的含义是：p1 经过若干次（至少一次）++操作后，就会等于 p2。其他比较方式的含义与此类似。
2、对于两个随机访问迭代器 p1、p2，表达式p2-p1也是有定义的，其返回值是 p2 所指向元素和 p1 所指向元素的序号之差（也可以说是 p2 和 p1 之间的元素个数减一）。
迭代器功能.png
vector 的迭代器是随机迭代器例程：
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v(5); //v被初始化成有5个元素
for(int i = 0; i < v.size(); ++i) //size返回元素个数
{
cout << v[i]; //像普通数组一样使用vector容器
}
cout << endl;
vector<int>::iterator i;
for(i = v.begin(); i != v.end(); ++i) //用 != 比较两个迭代器
{
cout << *i;
}
cout << endl;
for(i = v.begin(); i < v.end();++i) //用 < 比较两个迭代器
{
cout << *i;
}
cout << endl;
i = v.begin();
while(i < v.end()) { //间隔一个输出
cout << *i;
i += 2; // 随机访问迭代器支持 "+= 整数" 的操作
}
}
运行结果.png
list 容器的迭代器是双向迭代器
如定义如下：
list<int> v;
list<int>::const_iterator i;
则以下代码是合法的：
for(i=v.begin(); i!=v.end(); ++i) cout << *i;
以下代码则不合法：
for(i=v.begin(); i<v.end(); ++i) cout << *i;
因为双向迭代器不支持用“<”进行比较。以下代码也不合法：
for(int i=0; i<v.size(); ++i) cout << v[i];
因为 list 不支持随机访问迭代器的容器，也不支持用下标随机访问其元素。
在 C++ 中，数组也是容器。数组的迭代器就是指针，而且是随机访问迭代器。
例如，对于数组 int a[10]，int * 类型的指针就是其迭代器。则 a、a+1、a+2 都是 a 的迭代器。
19.4 迭代器的辅助函数
STL 中有用于操作迭代器的三个函数模板，涉及的头文件 algorithm，这三个函授木板是：
//使迭代器 p 向前或向后移动 n 个元素。
advance(p, n);
//计算两个迭代器之间的距离，即迭代器 p 经过多少次 + + 操作后和迭代器 q 相等。
//如果调用时 p 已经指向 q 的后面，则这个函数会陷入死循环。
distance(p, q);
//用于交换两个迭代器 p、q 指向的值。
iter_swap(p, q);
三个函数模板例程：
#include <list>
#include <iostream>
#include <algorithm> //要使用操作迭代器的函数模板，需要包含此文件
using namespace std;
int main()
{
int a[5] = { 1, 2, 3, 4, 5 };
list <int> lst(a, a+5);
list <int>::iterator p = lst.begin();
advance(p, 2); //p向后移动两个元素，指向3
cout << "1:" << *p << endl; //输出 1:3
advance(p, -1); //p向前移动一个元素，指向2
cout << "2:" << *p << endl; //输出 2:2
list<int>::iterator q = lst.end();
q--; //q 指向 5
cout << "3:" << distance(p, q) << endl; //输出 3:3
iter_swap(p, q); //交换 2 和 5
cout << "4:";
for (p = lst.begin(); p != lst.end(); ++p){
cout << *p << " ";
}
return 0;
}
运行结果.png
19.5 STL算法详解
STL 提供能在各种容器中通用的算法（大约有70种），如插入、删除、查找、排序等。算法就是函数模板。算法通过迭代器来操纵容器中的元素。
许多算法操作的是容器上的一个区间（也可以是整个容器），因此需要两个参数，一个是区间起点元素的迭代器，另一个是区间终点元素的后面一个元素的迭代器。例如，排序和查找算法都需要这两个参数来指明待排序或待查找的区间。有的算法返回一个迭代器。例如，find 算法在容器中查找一个元素，并返回一个指向该元素的迭代器。
算法可以处理容器，也可以处理普通的数组。
有的算法会改变其所作用的容器。如：
copy：将一个容器的内容复制到另一个容器。
remove：在容器中删除一个元素。
random_shuffle：随机打乱容器中的元素。
fill：用某个值填充容器。
有的算法不会改变其所作用的容器。例如：
find：在容器中查找元素。
count_if：统计容器中符合某种条件的元素的个数。
STL 中的大部分常用算法都在头文件 algorithm 中定义。此外，头文件 numeric 中也有一些算法。
因为种类繁多，需要自行查看API文档
这里我们就一个例子：
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
int a[10] = {5, 6, 7, 8};
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4); //此后v里放着4个元素：1,2,3,4
vector<int>::iterator p;
p = find(v.begin(),v.end(),3); //在v中查找3
if(p != v.end()){ //若找不到,find返回 v.end()
cout << "1: " << * p << endl; //找到了
}
p = find(v.begin(),v.end(),9);
if(p == v.end()){
cout << "没找到 " << endl;
}
p = find(v.begin()+1,v.end()-1,4); //在,3 这两个元素中查找4
cout << "2: " << * p << endl;
int * pp = find(a,a+4,20);
if(pp == a + 4){
cout << "没找到" << endl;
}
else{
cout << "3: " <<* pp << endl;
}
}
运行结果.png
