图7-1 STL组件结构图
★ 了解STL组件构成
★ 掌握序列容器
★ 掌握关联容器
★ 掌握容器适配器
★ 了解常见的迭代器
★ 了解迭代器适配器
★ 掌握常用的算法
标准模板库（Standard Tem plate Library，STL）是所有C++编译器和操作系统平台都支持的一种模板库。STL提供了大量的复用软件组织，能让C++程序设计者快速而高效地进行开发。本章将针对STL中的容器、迭代器、算法等核心内容进行讲解。
STL是惠普实验室开发的一系列标准化组件的统称。它是由Alexander Stepanov、M eng Lee和David R.M usser在惠普实验室工作时开发出来的。在1994年，STL被纳入C++标准，成为C++库的重要组成部分。
STL主要由六个部分组成：空间配置器（Allocator）、适配器（Adapters）、容器（Containers）、迭代器（Iterator）、仿函数（Functors）和算法（Algorithm）。STL的一个基本理念就是将数据和操作分离，数据由容器加以管理，操作则由可定制的算法完成，迭代器在两者之间充当“黏合剂”。STL的组件结构图如图7-1所示。
图7-1展示了STL各组件之间的关系，STL中的每个组件都有其特定功能，组件之间又密切关联。下面分别对每个组件进行简单介绍。
1. 容器
容器是存储其他对象的对象，它存储的对象可以是自定义数据类型的对象，也可以是内置数据类型的对象。这些被存储的对象必须是同一种数据类型，它们归容器所有，称为容器的元素。当容器失效时，容器中的元素也会失效。容器本身包含了处理这些数据的方法。STL中的容器共有13种，如表7-1所示。
图7-1 STL组件结构图
表7-1 STL容器的分类关联容器
2. 空间配置器
C++标准库采用了空间配置器实现对象内存空间的分配和归还，空间配置器是特殊的内存模型。例如，使用vector容器，存储数据的空间由空间配置器完成内存的分配和资源回收。空间配置器本质上是对new和delete运算符再次封装而成的类模板，对外提供可用的接口，实现内存资源的自动化管理。
3. 适配器
适配器主要指容器适配器。容器适配器也是一类容器，它除了能存储普通数据，还可以存储list、vector、deque等容器。容器适配器采用特定的数据管理策略，能够使容器在操作数据时表现出另一种行为。例如，使用容器适配器stack封装一个vector<int>容器，使vector<int>容器在处理数据时，表现出栈这种数据结构的特点（先进后出）。STL提供了三个容器适配器：stack（栈）、queue（队列）和priority_queue（优先队列）。适配器体现了STL设计的通用性，极大提高了编程效率。
4. 迭代器
迭代器是STL提供的用于操作容器中元素的类模板，STL算法利用迭代器遍历容器中的元素，迭代器本身也提供了操作容器元素的方法，使容器元素访问更便捷。迭代器将容器与算法联系起来，起到了“黏合剂”的作用，STL提供的算法几乎都通过迭代器实现元素访问。
STL提供了输入迭代器、输出迭代器、正向迭代器、双向迭代器和随机访问迭代器五种类型的迭代器，使用迭代器访问容器元素更简单、易用，且代码更加紧凑、简洁。
5. 仿函数
在前面3.4节我们学习了仿函数，仿函数通过重载(）运算符实现，使类具有函数一样的行为。仿函数也称为函数对象，是STL很重要的组成部分，它使STL的应用更加灵活方便，增强了算法的通用性。大多数STL算法可以使用一个仿函数作为参数，以达到某种数据操作的目的。例如，在排序算法中，可以使用仿函数less或greater作为参数，以实现数据从大到小或从小到大的排序。
6. 算法
算法是STL定义的一系列函数模板，是STL非常重要的一部分内容。算法可以对容器中的元素施加特定操作。STL算法不依赖于容器的实现细节，只要容器的迭代器符合算法要求，算法就可以通过迭代器处理容器中的元素。
序列容器（Sequence Containers）也叫作顺序容器，序列容器各元素之间有顺序关系，每个元素都有固定位置，除非使用插入或删除操作改变这个元素的位置。序列容器是一种线性结构的有序群集，它最重要的特点就是可以在容器一端添加、删除元素。对于双向序列容器，允许在两端添加和删除元素。序列容器有连续存储和链式存储两种存储方式，如图7-2所示。
STL提供的基本序列容器包括vector、deque、list、array和forward_list五种，在使用这五种容器时分别需要包含相应的头文件，示例代码如下：
#include<vector> #include<deque> #include<list> #include<array> #include<forward_list>
图7-2 序列容器的两种存储方式
vector容器与动态数组相同，在插入或删除元素时能够自动调整自身大小，即vector容器能够自动处理存储数据所需的空间。vector容器中的元素放置在连续的内存空间中，可以使用迭代器对其进行访问和遍历。vector容器的存储结构如图7-3所示。
图7-3 vector容器的存储结构
vector容器在插入元素时，插入位置之后的元素都要被顺序地向后移动，因此，在总体上vector容器插入操作效率并不高。插入位置越靠前，执行插入所需的时间就越多，但在vector容器尾部插入元素的效率比较高。
删除vector容器中的元素时，被删除元素后面的元素会顺序向前移动，将被删除元素留下的空位补上。删除操作的效率和插入类似，被删除元素越靠前，删除操作所需的时间就越多。
下面讲解vector容器的常见用法。
1. 创建vector容器
vector模板中定义了多个重载构造函数，因此vector容器的创建与初始化也有多种方式。vector容器的创建方式主要有四种。
（1）指定容器大小
指定容器大小的格式如下：
vector<元素类型> 对象名（容器大小）;
在上述格式中，“<>”中的元素类型名表示容器中元素的类型，如int表示容器中存储的是int类型的数据。“()”中指定容器大小。示例代码如下所示：
vector<int> v1(10); vector<string> v2(5);
上述代码中，第一行代码创建了一个存储int类型数据的容器v1，容器大小为10；第二行代码创建了一个存储string类型数据的容器v2，容器大小为5。需要注意的是，vector对象在定义后所有元素都会被初始化，如果是基本数据类型的容器，则都会被初始化为0；如果是其他类型容器，则由类的默认构造函数初始化。
（2）指定初始值
在创建vector容器时，可以同时指定vector容器大小和初始值，格式如下所示：
vector<元素类型>对象名（容器大小，元素初始值）;
按照上述格式创建vector容器，示例代码如下所示：
vector<int> v1(10, 1); vector<string> v3(3, "aa");
上述代码中，第一行代码创建存储int类型数据的容器v1，容器大小为10，10个元素的初始值均为1。第二行代码创建存储string类型数据的容器v2，容器大小为3，3个元素的初始值均为"aa"。
（3）列表初始化
C++11新标准还提供了另外一种vector容器初始化方式，即用值的列表初始化，示例代码如下所示：
vector<int> v1{1, 2}; //v1有两个元素
vector<string> v2 = { "a", "b", "c" }; //v2有三个元素
使用列表初始化时，带“=”符号与不带“=”符号均可。
（4）初始化状态为空
初始化状态为空，即创建vector对象时不指定大小也不指定初始值，示例代码如下所示：
vector<int> v1; //创建存储int类型数据的容器v1
除了上述方式，vector容器还可以用另外一个vector容器完成初始化，示例代码如下所示：
vector<int> v1(10, 1); vector<int> v2(v1); //用容器v1初始化容器v2 vector<int> v3 = v2; //用容器v2给容器v3赋值
需要注意的是，用一个vector容器初始化另一个容器或相互赋值时，两个vector容器的元素类型必须相同。
2. 获取容器容量和实际元素个数
vector容器的容量与容器实际元素个数并不一定相同，容器容量指容器最多可以存储的元素个数，是容器预分配的内存空间。而容器实际元素个数可能小于容器容量。vector提供了两个函数capacity()和size()，分别用于获取容器容量和容器实际元素个数，这两个函数的调用形式如下所示：
v.capacity()； v.size();
在上述代码中，v是创建的vector容器，如无特殊说明，后续讲解的vector容器的函数调用，其中v均指vector容器。capacity()函数返回容器的容量，size()函数返回容器实际元素个数。
3. 访问容器中的元素
由于vector重载了“[]”运算符，因此可以使用索引方式访问vector容器中的元素。此外，vector容器还提供了一个成员函数at()，用于随机访问容器中的元素。at()函数调用形式如下所示：
v.at(int idx);
在上述at()函数的调用形式中，参数idx表示索引。at()函数返回值为索引指向的数据。
4. 赋值函数
vector容器中的元素可以在创建容器时指定，也可以通过“[]”运算符完成赋值。除此之外，vector容器还提供了一个成员函数assign()，用于给空的vector容器赋值。assign()函数有两种重载形式，分别如下所示：
v.assign(n, elem); //将n个elem元素赋值给容器 v.assign(begin, end); //将[begin, end)区间中的元素赋值给容器
assign()函数的两种重载形式都可以完成容器元素赋值：第一种形式给元素赋同样的数据值；第二种形式以指定区间给元素赋值。需要注意的是，区间是左闭右开，即第一个区间值可以使用，最后一个区间值不可以使用。
5. 获取头部和尾部元素
vector容器提供了front()函数与back()函数，分别用于获取容器的头、尾元素。front()函数和back()函数调用形式如下所示：
v.front(); //获取容器头部元素（第一个元素） v.back(); //获取容器尾部元素（最后一个元素）
6. 从尾部插入和删除元素
vector容器提供了一对函数push_back()与pop_back()，分别用于从尾部添加元素和删除尾部元素。push_back()函数和pop_back()函数调用形式如下所示：
v.push_back(type elem& t); v.pop_back();
下面通过案例演示vector容器的用法，如例7-1所示。
例7-1 element.cpp
1 #include<iostream>
2 #include<vector>
3 using namespace std;
4 int main()
5 {
6 vector<int> v; //创建一个空的vector容器v
7 for(int i=0;i<10;i++)
8 v.push_back(i+1); //从尾部向容器v中插入10个元素
9 for(int i=0;i<10;i++)
10 cout<<v[i]<<" "; //输出容器v中的元素
11 cout<<endl;
12 v.pop_back(); //删除尾部元素
13 for(int i=0;i<9;i++) //此时元素个数为9
14 cout<<v[i]<<" "; //输出容器v中的元素
15 cout<<endl;
16 return 0;
17 }
例7-1运行结果如图7-4所示。
图7-4 例7-1运行结果
在例7-1中，第6行代码创建了一个空的vector容器v。第7～10行代码在for循环中调用push_back()函数向容器尾部添加元素，并输出容器v中元素。由图7-4可知，10个元素均添加成功，且成功输出了10个元素。第12行代码调用pop_back()函数删除了末尾的元素10。第13～14行代码在for循环中输出容器v中的元素。由图7-4可知，末尾元素10删除成功。
7. 容器的迭代器
vector容器提供了迭代器，通过迭代器可以访问、修改容器中的元素。vector容器提供了iterator、const_iterator、reverse_iterator和const_reverse_iterator四种迭代器，这四种迭代器作用分别如下。
在使用迭代器之前，必须先定义迭代器对象，vector容器迭代器对象的定义格式如下所示：
vector<元素类型> 迭代器 迭代器对象名称;
在实际编程中，通常将创建的迭代器对象简称为迭代器。迭代器可以执行++、−−、与整数相加减等算术运算，以达到遍历容器元素的目的。
vector提供了获取上述四种迭代器的成员函数，如表7-2所示。
表7-2 vector容器获取迭代器的函数含义
需要注意的是，迭代器遍历容器到达尾部时，指向最后一个元素的后面，而不是指向最后一个元素，即使用end()函数、rend()函数、cend()函数和crend()函数获取的迭代器，指向最后一个元素后面的位置，而不是指向最后一个元素。
下面通过案例演示迭代器的用法，如例7-2所示。
例7-2 iterator.cpp
1 #include<iostream>
2 #include<vector>
3 using namespace std;
4 int main()
5 {
6 vector<int> c={1,2,3}; //创建vector容器c
7 vector<int>::iterator pos; //定义iterator迭代器pos
8 vector<int>::reverse_iterator pos_r; //定义reverse_iterator迭代器pos_r
9 cout<<"iterator迭代器:";
10 for(pos=c.begin();pos!=c.end();++pos) //使用迭代器pos遍历容器c中的元素
11 {
12 cout<<*pos<<" ";
13 }
14 cout<<endl<<"reverse_iterator迭代器:";
15 //使用迭代器pos_r反向遍历容器c中的元素
16 for(pos_r=c.rbegin();pos_r!=c.rend();++pos_r)
17 {
18 cout<<*pos_r<<" ";
19 }
20 return 0;
21 }
例7-2运行结果如图7-5所示。
图7-5 例7-2运行结果
在例7-2中，第6行代码创建了一个vector容器c；第7~8行代码分别创建了iterator迭代器对象pos和reverse_iterator迭代器对象pos_r。第10~13行代码通过for循环使用迭代器pos遍历容器c中的元素并输出。由图7-5可知，使用迭代器pos成功遍历了容器c中的元素。第16~19行代码通过for循环使用迭代器pos_r遍历容器c。由图7-5可知，迭代器pos_r反向遍历容器c中的元素。
vector容器是一个顺序容器，在内存中是一块连续的内存，当插入或删除一个元素后，内存中的数据会移动，从而保证数据的连续。当插入或删除数据后，其他数据的地址可能会发生变化，迭代器获取容器位置信息的数据不正确，即迭代器失效，会导致访问出错。
8. 在任意位置插入和删除元素
vector提供了一对向容器任意位置插入和删除元素的函数insert()与erase()。其中，insert()函数用于向容器中插入元素，它有三种重载形式，分别如下所示：
v.insert(pos, elem); //在pos位置插入元素elem v.insert(pos, n, elem): //在pos位置插入n个elem元素 v.insert(pos, begin, end); //在pos位置插入[begin, end)区间的数据
erase()函数用于删除容器中的元素，它有两种重载形式，分别如下所示：
v.erase(pos); //删除pos位置上的元素 v.erase(begin, end); //删除[begin, end)区间的数据
insert()函数与erase()函数中的位置参数只能由begin()、end()等函数返回的迭代器指示，不能用纯粹的数字。下面通过案例演示这两个函数的用法，如例7-3所示。
例7-3 randomInsert.cpp
1 #include<iostream>
2 #include<vector>
3 using namespace std;
4 int main()
5 {
6 vector<char> v; //创建空的vector容器v
7 v.insert(v.begin(), 'a'); //在头部位置插入元素a
8 v.insert(v.begin(), 'b'); //在头部位置插入元素b
9 v.insert(v.begin(), 'c'); //在头部位置插入元素c
10 v.insert(v.begin() + 1, 5, 't'); //在v.begin()+1位置插入5个元素t
11 for(int i = 0; i < 8; i++) //输出容器v中的元素
12 cout << v[i] << " ";
13 cout << endl;
14 cout << "after erase elems:\n";
15 //删除begin()+1到begin()+6区间的5个元素
16 v.erase(v.begin() + 1, v.begin() + 6);
17 for(int i = 0; i <3; i++) //输出容器v中的元素
18 cout << v[i] << " ";
19 cout << endl;
20 return 0;
21 }
例7-3运行结果如图7-6所示。
在例7-3中，第6行代码创建了一个存储char类型数据的空容器v。第7～9行代码调用insert()函数在容器v头部分别插入元素a、b、c；第10行代码调用insert()函数在容器第2个位置插入5个元素t，此时，元素b和元素a会依次向后移动5个位置。第11～12行代码通过for循环遍历输出容器v中的元素，由图7-6可知，调用insert()函数成功插入了各个元素。第16行代码调用erase()函数删除第2个位置到第6个位置之间的5个元素。需要注意的是，删除区间元素时，区间是左闭右开，即第2个位置上的元素会删除，而第6个位置上的元素不会删除。由图7-6可知，erase()函数删除了5个元素t。
图7-6 例7-3运行结果
deque容器与vector容器非常相似，采用动态内存管理的方式存储元素。与vector不同的是，deque是两端开口的，支持从两端插入、删除数据，并支持元素的随机访问。deque容器的存储结构如图7-7所示。
图7-7 deque容器的存储结构
deque的操作方法和vector容器几乎相同。最大的区别是deque容器不支持vector容器中的reserve()函数、capacity()函数和data()函数，并且新增了pop_front()、push_front()函数，用于从队首弹出、插入元素。
array是C++11标准新增加的容器，它也是一个序列容器，只是array的大小是固定的，一旦分配了array容器，其大小就不能再改变，不允许向array容器插入元素或从array容器中删除元素，即array容器不支持插入、删除操作。array容器的存储结构如图7-8所示。
由图7-8可知，array容器的存储结构和数组的存储结构一致，但是它比数组更灵活。下面分别讲解array容器的常见用法。
图7-8 array容器的存储结构
1. 创建array容器
创建array容器的时候需要指定元素类型和元素个数，示例代码如下：
array<int,3>a1; //定义大小为3的array容器a1
array<int,3>a2={1,2,3}; //定义array容器a2
2. 修改容器元素
array提供了fill()函数和swap()函数用于修改元素。fill()函数使用指定的数据填充容器；swap()函数用于交换两个容器的元素。fill()函数和swap()函数的调用形式如下所示：
fill(val); //使用val填充容器 a1.swap(a2); //交换容器a1和容器a2的元素
下面通过案例演示array容器的使用，如例7-4所示。
例7-4 array.cpp
1 #include<iostream>
2 #include<array>
3 using namespace std;
4 int main()
5 {
6 array<int,3>c={1,2,3}; //创建array容器c
7 array<int,3>c1={2,3,4}; //创建array容器c1
8 array<int,3>::iterator pos; //定义iterator迭代器pos
9 c.swap(c1); //交换容器c和容器c1的元素
10 for(pos=c.begin();pos!=c.end();++pos) //使用迭代器pos遍历容器c中的元素
11 {
12 cout<<*pos<<" ";
13 }
14 return 0;
15 }
例7-4运行结果如图7-9所示。
在例7-4中，第6~7行代码创建了两个array容器c和c1。第8行代码定义了array容器的iterator迭代器pos。第9行代码调用swap()函数交换容器c和容器c1的元素。第10~13行代码在for循环中使用迭代器pos遍历容器c，并输出元素。由图7-9可知，容器c和容器c1交换成功，并且使用迭代器pos成功遍历了容器c。
图7-9 例7-4运行结果
list容器以双向链表形式实现，list容器通过指针将前面的元素和后边的元素链接到一起。list容器的存储结构如图7-10所示。
与vector容器和deque容器相比，list容器只能通过迭代器访问元素，不能通过索引方式访问元素。因为同为序列容器，list容器的接口大部分与vector和deque容器都相同，所以读者学习起来也比较容易。下面讲解list容器的常见用法。
图7-10 list容器的存储结构
1. 创建list容器
list类模板中也实现了多个重载构造函数，因此list容器的创建也有多种方式。创建list容器的几种常见方式如下所示：
list<T> lt; //创建一个空的list容器lt list<T> lt(n); //创建一个list容器lt，大小为n list<T> lt(n, elem); //创建一个list容器lt，包含n个elem元素 list<T> lt(begin, end); //创建一个list容器lt，用[begin, end)区间的值为元素赋值 list<T> lt(lt1); //创建一个list容器lt，用容器lt1初始化
2. 赋值
list容器也提供了assign()函数为容器元素赋值，assign()函数有两种重载形式，分别如下所示：
lt.assign(n, elem); //将n个elem元素的值赋给lt lt.assign(begin, end); //用[begin, end)区间的值给lt中的元素赋值
在list容器中，assign()函数的用法和vector中的assign()函数用法一样，这里不再举例说明。
3. 元素访问
因为list容器是由链表实现的，内存区域并不连续，所以无法用“[]”运算符访问元素，也没有可随机访问元素的at()方法，但list容器提供了front()函数和back()函数用于获取头部元素和尾部元素。此外，list容器也支持迭代器访问元素，提供了iterator、const_iterator、reverse_iterator和const_reverse_iterator四种迭代器，还提供了获取这四种迭代器的成员函数。list迭代器的用法与vector迭代器相同，这里不再举例演示。
4. 插入元素和删除元素
list容器提供了多个函数用于向容器中添加元素，这些函数调用形式如下所示：
lt.push_back(); //在尾部插入元素 lt.push_front(); //在头部插入元素 lt.insert(pos, elem); //在pos位置插入元素elem lt.insert(pos, n, elem); //在pos位置插入n个元素elem lt.insert(pos, begin, end); //在pos位置插入[begin, end)区间的值作为元素
上述函数的用法与deque容器中的函数用法一样，即list容器可以从头尾两端添加元素，也可以从中间添加元素。list容器也提供了多个函数用于删除元素，可以从头尾两端删除元素，也可以删除中间任意一个元素。list各个删除函数调用形式如下所示：
lt.pop_back(); //从尾部删除元素 lt.pop_front(); //从头部删除元素 lt.erase(pos); //从中间删除元素 lt.erase(begin, end); //删除[begin, end)区间的元素 lt.remove(elem); //从容器中删除所有与elem匹配的元素
下面通过案例演示list容器的使用，如例7-5所示。
例7-5 listfunc.cpp
1 #include<iostream>
2 #include<list>
3 using namespace std;
4 template<typename T>
5 void print(list<T> mylist) //定义函数模板，输出list容器元素
6 {
7 typename list<T>::iterator it; //创建list的iterator迭代器
8 for(it = mylist.begin(); it != mylist.end(); it++)
9 cout << *it << " ";
10 cout << endl;
11 }
12 int main()
13 {
14 list<int> lt; //创建空的list容器lt
15 for(int i = 0; i < 10; i++)
16 lt.push_back(i + 1); //向容器中添加元素
17 cout << "输出list容器中的元素：" << endl;
18 print(lt);
19 lt.pop_back(); //删除最后一个元素
20 lt.push_front(5); //在头部添加元素5
21 cout << "再次输出list容器中的元素：" << endl;
22 print(lt);
23 lt.remove(5);
24 cout << "删除5之后，输出list容器中的元素：" << endl;
25 print(lt);
26 return 0;
27 }
例7-5运行结果如图7-11所示。
图7-11 例7-5运行结果
在例7-5中，第4～11行代码定义了一个函数模板print()用于输出list容器中的元素。print()函数模板的参数为list容器，在函数模板内部，创建list的iterator迭代器，通过迭代器遍历容器元素并输出。第14～16行代码创建list容器lt，并在for循环中调用push_back()函数从尾部插入元素。第18行代码调用print()函数输出容器lt中的元素。由图7-11可知，print()成功输出了容器lt中的元素。第19行代码调用pop_back()函数删除容器lt尾部元素10。第20行代码调用push_front()函数将元素5插入容器lt的头部。第22行代码再次调用print()函数输出容器lt中的元素，由图7-11可知，容器lt的元素10被删除，头部元素为5。第23行代码调用rem ove()函数删除元素5；第25行代码调用print()函数输出容器lt中的元素，由图7-11可知，容器lt中的元素5已经被删除。
C++11标准新增了forward_list容器，该容器由单链表实现。在forward_list容器中，除了最后一个元素，每个元素与下一个元素通过指针链接。由于forward_list容器是单链表实现的，因此它只能向后迭代。forward_list容器的存储结构如图7-12所示。
图7-12 forward_list容器的存储结构
由于同为链式存储的容器，因此forward_list的接口与list大部分相同。但是又因为forward_list是单链式存储，所以forward_list还提供了一些自己特有的函数，下面分别进行讲解。
1. 插入和删除元素
forward_list容器不支持insert()函数和erase()函数，但它提供了insert_after()函数和erase_after()函数用于插入和删除元素。insert_after()函数和erase_after()函数的调用形式如下所示：
insert_after(pos,val); //将元素val插入pos位置 insert_after(pos,begin,end); //在pos位置插入[begin,end）区间内的元素 erase_after(pos); //删除pos位置的元素 erase_after(begin,end); //删除[begin,end）区间内的元素
2. 获取迭代器
forward_list新增了两个函数before_begin()和cbefore_begin()，其中，before_begin()函数用于获取指向容器第一个元素之前位置的迭代器；cbefore_begin()用于获取指向容器第一个元素之前位置的const_iterator迭代器。
由于forward_list容器的用法与list容器相似，这里不再使用案例演示。
序列容器中元素的顺序都是由程序设计者决定的，程序设计者可以随意指定新元素的插入位置，而关联容器的所有元素都是经过排序的，即关联容器都是有序的。它的每一个元素都有一个键（key），容器中的元素是按照键的取值升序排列的。
关联容器内部实现为一个二叉树，在二叉树中，每个元素都有一个父节点和两个子节点，左子树的所有元素都比父节点小，右子树的所有元素都比父节点大。关联容器的有序二叉树如图7-13所示。
关联容器内部结构都以这种二叉树结构实现，这也使得它可以高效地查找容器中的每一个元素，但却不能实现任意位置的操作。
图7-13 关联容器的有序二叉树
STL提供了四种关联容器，分别是set、multiset、m ap和multim ap，其中set与multiset包含在头文件set中，m ap与multim ap包含在头文件m ap中。下面分别对这四种容器进行简单介绍。
1.set与multiset
set与multiset都是集合，用于存储一组相同数据类型的元素。两者的区别是set用来存储一组无重复的元素，而multiset允许存储有重复的元素。
集合支持插入、删除、查找等操作，但集合中的元素值不可以直接修改，因为这些元素都是自动排序的，如果想修改其中某一个元素的值，必须先删除原有的元素，再插入新的元素。
2.map与multimap
m ap与multim ap称为映射，映射与集合的主要区别在于，集合的元素是键本身，而映射的元素是由键和附加数据构成的二元组，它很像“字典”，通过给定的键，可以快速找出与键对应的值。因此，映射的二叉树节点中存储了两个数据，一个是用来定位的数据，称为键；另一个是与键对应的数据，称为值。通常也说，映射中存储的是一键值对，映射的一种通常用法就是根据键查找对应的值。
映射可分为单重映射（m ap）与多重映射（multim ap），两者的主要区别是：m ap存储的是无重复键的元素对，而multim ap允许相同的键重复出现，即一个键可以对应多个值，如图7-14所示。
图7-14 map与multimap
如前所述，set与multiset的区别在于是否允许有重复元素，其他用法都很相似，因此将这两种容器放在一起讲解。下面讲解set和multiset的常用方法。
1. 创建set与multiset容器
set与multiset都重载了多个构造函数，因此创建set和multiset容器的方式有多种。set容器的创建方式主要有以下五种：
set<T> s; //创建一个空的set容器，默认升序排列 set<T,op> s; //创建一个空的set容器，按op规则排序 set<T> s(begin,end); //创建一个容器，用[begin,end)区间为其初始化 set<T,op> s(begin,end); //创建一个容器，用[begin,end)区间为其初始化，并按op规则排序 set<T> s(s1); //创建一个空的set容器，用另一个容器s1初始化
下面分别用这五种方式创建set容器，示例代码如下所示：
set<char> s1; set<int,greater<int>()> s2; set<float> s3(begin,end); set<string,greater<string>()> s4(begin,end); set<int> s5(s2);
上述代码分别用不同的方式定义了char、int等类型的set容器，其中容器s2与s4中的greater<T>是排序规则，指定容器中的元素按照从大到小的顺序排列。如果没有指定排序规则，则默认规则是less<T>，即容器中元素按照从小到大的顺序排列。greater<T>、less<T>是STL中定义的函数对象，包含在functional头文件中。
multiset容器的创建方式与set容器相同，示例代码如下所示：
multiset<char> ms1; multiset<int,greater<int>()> ms2; multiset<float> ms3(begin,end); multiset<string,greater<string>()> ms4(begin,end); multiset<int> ms5(s2);
2. 容器的大小
与其他容器一样，set与multiset容器也提供了获取容器实际元素个数的函数size()、判断容器是否为空的函数em pty()，以及返回容器容量的成员函数m ax_size()，这些函数的调用形式如下所示：
s.size(); //返回容器中实际元素个数 s.empty(); //判断容器是否为空 s.max_size(); //返回容器容量
上述函数调用中的s指集合容器，如无特殊说明，s既可以是set容器也可以是multiset容器，即两个容器都提供了这样的函数。
3. 容器元素的查找和统计
set与multiset容器还提供了查找函数find()和统计函数count()，这两种函数的调用形式如下所示：
s.find(elem); s.count(elem);
find()函数的功能是在容器中查找elem元素是否存在，如果元素存在，返回指向查找元素的迭代器；如果元素不存在，返回末尾迭代器。count()函数用于统计elem元素的个数。对于set容器，count()函数的返回值只能是0或1；对于multiset容器，count()函数返回值可能大于1。
4. 容器的迭代器
set与multiset容器支持迭代器操作，提供了iterator、const_iterator、reverse_iterator和const_reverse_iterator四种迭代器，并且提供了获取这四种迭代器的成员函数。set与multiset的迭代用法与vector迭代器相同。
5. 插入和删除元素
set与multiset容器提供了insert()函数与erase()函数，用于向容器中插入和删除元素。insert()函数主要有三种重载形式，分别如下所示：
s.insert(elem); //在容器中插入元素elem s.insert(pos,elem); //在pos位置插入元素elem s.insert(begin,end); //在容器中插入[begin,end)区间的元素
第一种形式的insert()函数将元素elem插入容器中。对于set容器，第一种形式的insert()函数调用的返回值是一个pair<iterator,bool>对象。pair<iterator,bool>对象的第一个参数iterator是迭代器，指示元素插入的位置；第二个参数bool类型的值代表元素是否插入成功。这是因为set容器中不允许存在重复的元素，如果要插入一个容器中已存在的元素，则插入操作会失败，而pair中的bool值标志插入是否成功。multiset容器则不存在这样的情况，因此multiset容器返回的是一个iterator。
第二种形式的insert()函数将元素elem插入指定位置pos，返回指向pos位置的迭代器。
第三种形式的insert()函数将[begin,end）区间的元素插入容器，函数没有返回值。
set与multiset容器提供的erase()函数主要有三种重载形式，分别如下所示：
s.erase(pos); //删除pos位置上的元素 s.erase(begin,end); //删除[begin, end)区间的元素 s.erase(elem); //删除元素elem
下面通过案例演示set与multiset容器的使用，如例7-6所示。
例7-6 set_multiset.cpp
1 #include<iostream>
2 #include<set>
3 #include<functional>
4 using namespace std;
5 int main()
6 {
7 set<int,greater<int>> s; //创建set容器s，元素按降序排列
8 multiset<char> ms; //创建multiset容器ms
9 //向s中插入元素
10 pair<set<int>::iterator,bool> ps;
11 ps = s.insert(12);
12 if(ps.second == true)
13 cout << "insert success" << endl;
14 s.insert(39);
15 s.insert(32);
16 s.insert(26);
17 //向ms中插入元素
18 ms.insert('a');
19 ms.insert('z');
20 ms.insert('T');
21 ms.insert('u');
22 ms.insert('u');
23 //输出两个容器中的元素
24 set<int>::iterator its; //创建容器s的迭代器，用于获取元素
25 cout << "s容器中元素：";
26 for(its = s.begin(); its != s.end(); its++)
27 cout << *its << " ";
28 cout << endl;
29 multiset<char>::iterator itms; //创建容器ms的迭代器
30 cout << "ms容器中元素：";
31 for(itms = ms.begin(); itms != ms.end(); itms++)
32 cout << *itms << " ";
33 cout << endl;
34 //查找容器ms中元素u的个数
35 cout <<"ms容器中u元素个数："<< ms.count('u') << endl;
36 return 0;
37 }
例7-6运行结果如图7-15所示。
图7-15 例7-6运行结果
在例7-6中，第7～8行代码分别创建了set容器s和multiset容器m s，其中，容器s存储int类型数据，元素按照由大到小的顺序排列；容器m s存储char类型的数据。第10～13行代码创建一个pair对象，并调用insert()函数将pair对象表示的元素插入容器s中。由图7-15可知，元素插入成功。第14～16行代码调用insert()函数向容器s中插入其他元素。第18～22行代码调用insert()函数向容器m s中插入元素。
第24～32行代码定义容器s和容器m s的iterator迭代器，使用迭代器遍历容器中的元素并输出。由图7-15可知，容器s和容器m s中的元素成功遍历输出。第35行代码通过容器m s调用count()函数，查找容器m s中元素u的个数。由图7-15可知，容器m s中元素u的个数为2。
在头文件utility中，定义了一个类模板pair。pair类模板的定义如下所示：
template<class T1, class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair():first(T1()), second(T2()) {}
pair(const T1& a, const T2& b):first(a), second(b) {}
#ifdef __STL_MEMBER_TEMPLATES
// 允许使用兼容的pair进行复制构造
template<class U1, class U2>
pair(const pair<U1, U2>& p):first(p.first), second(p.second) {}
#endif
};
pair的主要作用是将两个数据进行组合，用来表示一个二元组或一个元素对，两个数据可以是同一个类型，也可以是不同的类型。
当需要将两个元素组合在一起时，可以选择构造pair对象。当一个函数需要返回两个数据时，可以返回一个pair对象。例如，set容器的insert()函数第一种重载形式，就返回一个pair对象。下面讲解一下pair对象的创建与使用。
1. 创建pair对象
创建pair对象可以调用pair的构造函数，还可以调用STL提供的make_pair()函数。make_pair()是一个函数模板，原型如下所示：
template<class T1,class T2> pair<V1,V2> make_pair(T1&& t, T2&& u)
在上述函数模板原型中，参数t与u是构成pair对象的两个数据。make_pair()函数内部调用的仍然是pair构造函数。
使用pair构造函数和make_pair()函数创建pair对象，示例代码如下所示：
pair<int,string> p1(1, "abc"); make_pair(1, "abc");
2.pair对象的使用
pair类模板提供了两个成员变量first与second，first表示pair对象中的第一个元素，second表示第二个元素。例如下面的代码：
pair<int,string> p1(1, "abc"); cout << p1.first << endl; cout << p1.second << endl;
上述代码创建了一个pair对象p1，p1.first获取的是第一个元素，即int类型的1；p1.second获取的是第二个元素，即string类型的"abc"。
m ap与multim ap容器中存储的是元素对（key-value），因此m ap和multim ap容器通常也被理解为关联数组，可以使用键（key）作为下标获取对应的值（value）。关联的本质在于元素的值与某个特定的键相关联，而不是通过位置索引获取元素。下面讲解m ap和multim ap容器的创建及常用操作方法。
1. 创建map与multimap容器
m ap与multim ap重载了多个构造函数，因此m ap和multim ap容器的创建方式有多种。m ap容器的创建方式主要有以下五种：
map<T1,T2> m; //创建一个空的map容器 map<T1,T2,op> m; //创建一个空的map容器，以op为准则排序 map<T1,T2> m(begin,end); //创建一个map容器，用[begin, end)区间赋值 map<T1,T2> m(begin,end,op); //创建一个map容器，用[begin, end)区间赋值，op为排序准则 map<T1,T2> m(m1); //创建一个map容器，用另一个map容器m1初始化
下面分别用五种方式创建m ap容器，示例代码如下所示：
map<int, int> m1; map<char, float, greater<int>()> m2; map<string, int> m3(begin, end); map<string, int, greater<string>()> m4(begin, end); map<int, int> m5(m1)
上述代码分别调用不同的构造函数创建了五个m ap容器。需要注意的是，创建m ap容器时，类型参数必须有两个，这两个类型参数可以相同，也可以不同。
multim ap容器的创建方式与m ap容器相同，创建multim ap容器的示例代码如下所示：
multimap<int, int> mt1; multimap<char, float, greater<int>()> mt2; multimap<string, int> mt3(begin, end); multimap<string, int, greater<string>()> mt4(begin, end); multimap<int, int> mt5(m1)
2. 容器大小
m ap和multim ap容器提供了m ax_size()函数、size()函数和count()函数，其中，m ax_size()函数和size()函数用于计算容器最大存储量和容器实际元素个数；count()函数用于统计指定元素的个数。这三个函数调用形式如下所示：
m.count(key); m.max_size(); m.size();
由于m ap容器中无重复元素，因此m ap容器的count()函数返回值只有0和1，而multim ap容器的count()函数返回值可能大于1。
3. 容器元素的访问
m ap容器重载了“[]”运算符，可以通过m[key]的方式获取key对应的值。此外，m ap容器也提供了at()函数用于访问指定键对应的值。例如，访问key对应的值，示例代码如下：
m[key]; m.at(key);
m ap容器可以通过上述两种方式随机访问容器中元素，但multim ap容器中允许存在重复的键值，因此无法使用上述两种方式随机访问容器中元素。
通过“[]”运算符和at()函数可以访问m ap容器中的元素，那么同样通过“[]”运算符和at()函数可以修改容器中的元素，示例代码如下：
m[key] = value; m.at(key) = value
如果key尚未存在，则插入元素对；如果key已存在，则新插入的value覆盖key原来的值。
4. 容器的迭代器
m ap与multim ap容器支持迭代器操作，提供了iterator、const_iterator、reverse_iterator和const_reverse_iterator四种迭代器，并且提供了获取这四种迭代器的成员函数。m ap与multim ap迭代器用法与vector迭代器相同，这里不再介绍。
5. 插入和删除元素
m ap和multim ap容器提供了成员函数insert()用于插入元素，insert()函数主要有三种重载形式，示例代码分别如下所示：
m.insert(elem); //在容器中插入元素elem m.insert(pos, elem); //在pos位置插入元素elem m.insert(begin, end); //在容器中插入[begin, end)区间的值
由于m ap和multim ap容器中存储的是键值对，因此其插入函数insert()与其他容器的稍有不同，每次插入的是一对元素，参数中的elem指的是一对元素。在插入元素时，使用pair<>语句或m ake_pair()函数创建一个pair对象，将pair对象作为insert()函数的参数，插入容器中。
与insert()函数相对应，m ap与multim ap容器也提供了erase()函数用于删除容器中的元素，erase()函数主要有三种重载形式，示例代码分别如下所示：
m.erase(pos); //删除pos位置上的元素 m.erase(begin, end); //删除[begin, end)区间内的元素 m.erase(key); //删除键为key的元素对
下面通过案例演示m ap和multim ap容器的用法，如例7-7所示。
例7-7 map_multimap.cpp
1 #include<iostream>
2 #include<map>
3 #include<functional>
4 #include<string>
5 using namespace std;
6 //定义printm()函数输出map容器元素
7 void printm(map<char, double> mymap)
8 {
9 pair<char, double> p; //创建pair对象p
10 map<char, double>::iterator it; //定义map的iterator迭代器it
11 for(it = mymap.begin(); it != mymap.end(); it++)
12 {
13 p = (pair<char, double>)*it; //将迭代器指向的一对元素存放到p中
14 cout << p.first << "->" << p.second << endl; //输出一对元素
15 }
16 }
17 //定义printmt()函数输出multimap容器元素
18 void printmt(multimap<int, string> mymul)
19 {
20 pair<int, string> p;
21 multimap<int, string>::iterator it;
22 for(it = mymul.begin(); it != mymul.end(); it++)
23 {
24 p = (pair<int, string>)*it;
25 cout << p.first << "->" << p.second << endl;
26 }
27 }
28 int main()
29 {
30 map<char, double> m; //创建一个map容器m
31 //向容器m中插入元素
32 m['a'] = 1.2;
33 m['b'] = 3.6;
34 m['c'] = 6.4;
35 m['d'] = 0.8;
36 m['e'] = 5.3;
37 m['f'] = 3.6;
38 cout << "map: " << endl;
39 printm(m); //调用printm()函数输出容器m中的元素
40 cout << "map中key=a的值：" << m.at('a') << endl;
41 cout << "map中key=f的元素个数：" << m.count('f') << endl;
42 multimap<int, string> mt; //创建一个multimap容器mt
43 //向容器mt中插入元素
44 mt.insert(pair<int, string>(1, "Hello"));
45 mt.insert(make_pair(1, "China"));
46 mt.insert(make_pair(2, "!"));
47 cout << "multimap: " << endl;
48 printmt(mt); //调用printmt()函数输出容器mt中的元素
49 return 0;
50 }
例7-7运行结果如图7-16所示。
在例7-7中，第7～16行代码定义了printm()函数，用于输出map<char,double>容器元素。在printm()函数内部，第9行代码创建了pair<char,double>对象p；第10行代码定义了m ap的iterator迭代器it。第11～15行代码在for循环中遍历m ap容器的元素，将元素赋值给对象p，并输出对象p表示的元素对。
第18～27行代码定义了printmt()函数，用于输出multim ap容器元素。printmt()函数和printm()函数的实现原理相同。
第30～37行代码定义了m ap容器m，并通过索引方式插入元素。第39行代码调用printm()函数输出容器m中的元素，由图7-16可知，printm()函数成功输出了容器m中的元素。第40行代码调用at()函数查找键'a'对应的值，由图7-16可知，键'a'对应的值为1.2。第41行代码计算键'f'的个数，由图7-16可知，键'f'的个数为1。
第42行代码创建multim ap容器mt；第44～46行代码调用insert()函数插入元素。需要注意的是，第44行代码插入元素时，使用pair<>语句构建元素对；第45～46行代码插入元素时，调用m ake_pair()函数构建元素对。第48行代码调用printm t()函数输出容器mt中的元素，由图7-16可知，printm t()函数成功输出了容器mt中的元素。
图7-16 例7-7运行结果
C++标准库中提供了三个容器适配器：stack（栈）、queue（队列）和priority queue（优先队列）。这三种容器适配器提供了简单易用的接口，满足了编程中的特殊数据处理需求，本节将针对这三种容器适配器进行讲解。
stack中的元素具有后进先出的特点。stack只能从一端插入、删除、读取元素，不允许一次插入或删除多个元素，且不支持迭代器操作。stack存储结构如图7-17所示。
下面分别介绍stack的常见用法。
1. 创建stack
创建stack主要有两种方式，分别如下所示。
（1）创建空的stack。
创建空的stack，用于存储基本数据类型的元素，示例代码如下所示：
图7-17 stack存储结构
stack<int> st;
上述代码创建了一个空的stack容器适配器st，向st中插入元素可以调用push()函数。
（2）创建存储序列容器的stack。
创建存储序列容器的stack，stack的类型参数有两个，第一个类型参数为元素的数据类型，第二个类型参数为容器类型，示例代码如下所示：
vector<int> v = { 1,2,3 }; //创建vector容器v
stack<int,vector <int >> s(v); //创建stack容器适配器s，存储容器v
2. 元素访问
stack除了具有vector容器相同功能的成员函数，如em pty()、size()、em place()和swap()函数，还提供以下操作函数，如表7-3所示。
表7-3 stack元素操作函数含义
下面通过案例演示stack的具体用法，如例7-8所示。
例7-8 stack.cpp
1 #include<iostream>
2 #include<vector>
3 #include<stack> //包含头文件stack
4 using namespace std;
5 int main()
6 {
7 vector<int> v = { 1,2,3 }; //创建vector容器v
8 stack<int, vector<int >> s(v); //创建stack容器适配器s
9 s.push(4);
10 s.emplace(5);
11 s.pop();
12 while (!s.empty())
13 {
14 cout << " "<<s.top();
15 s.pop();
16 }
17 return 0;
18 }
例7-8运行结果如图7-18所示。
图7-18 例7-8运行结果
在例7-8中，第7行代码创建了vector容器v。第8行代码创建了stack容器适配器s，s封装了容器v。第9～10行代码调用push()函数和em place()函数向s中插入元素4和5；第11行代码调用pop()函数删除最后插入的元素（5）。第12～16行代码在while循环中调用top()函数获取最后插入的元素，然后调用pop()函数将最后插入的元素删除，直到s为空。由图7-18可知，程序成功输出了s中的元素。
queue中的元素具有先进先出的特点，元素只能从一端使用push()函数进行插入，从另一端使用pop()函数进行删除。queue的存储结构如图7-19所示。
queue也不允许一次插入或删除多个元素，且不支持迭代器操作。queue创建对象的方式与stack相同，并且其接口与stack大部分都相同。除了提供了与vector相同的接口，queue还提供两个自己特有的成员函数，如表7-4所示。
图7-19 queue的存储结构
表7-4 queue的操作函数含义
下面通过案例演示queue的用法，如例7-9所示。
例7-9 queue.cpp
1 #include<iostream>
2 #include<list>
3 #include<queue> //包含头文件queue
4 using namespace std;
5 int main()
6 {
7 list<int> l = { 1,2,3 }; //创建list容器l
8 queue<int, list<int>> q(l); //创建queue容器适配器q
9 q.push(4);
10 q.emplace(5);
11 q.pop();
12 cout << "第一个元素" << q.front() << endl; //获取第一个元素
13 cout << "最后一个元素" << q.back() << endl; //获取最后一个元素
14 while(!q.empty())
15 {
16 cout << " "<<q.front();
17 q.pop();
18 }
19 return 0;
20 }
例7-9运行结果如图7-20所示。
图7-20 例7-9运行结果
在例7-9中，第7行代码创建了list容器l。第8行代码创建了queue容器适配器q，封装容器l。第9～10行代码分别调用push()函数和em place()函数在q尾部插入元素4和5。第11行代码调用pop()函数删除q头部元素，即第一个元素。第12～13行代码分别调用front()函数和back()函数获取第一个元素和最后一个元素并输出。由图7-20可知，程序输出的第一个元素和最后一个元素分别是2和5。第14～18行代码在while循环中调用front()函数获取第一个元素并输出，然后调用pop()函数删除第一个元素。由图7-20可知，程序成功输出了q中的元素。
priority_queue中的元素可以按照自定义的方式进行动态排序。向priority_queue中插入或删除元素时，priority_queue会动态地调整，以保证元素有序。priority_queue的存储结构如图7-21所示。
priority_queue创建方式与queue相同，只是在创建priority_queue时，可以指定优先规则，即最后一个模板参数可以是一个函数对象，指定元素排序规则。创建priority_queue的示例代码如下：
图7-21 priority_queue的存储结构
priority_queue<int,vector<int>,greater<int>> pq;
priority_queue的接口与queue相同，使用比较简单。下面通过案例演示priority_queue的具体用法，如例7-10所示。
例7-10 priority_queue.cpp
1 #include<iostream>
2 #include<queue>
3 using namespace std;
4 class Comp
5 {
6 public:
7 bool operator()(int x, int y) { return x > y; }
8 };
9 template<class T>
10 void print(T& q)
11 {
12 while (!q.empty())
13 {
14 cout << q.top() << " ";
15 q.pop();
16 }
17 cout << endl;
18 }
19 int main()
20 {
21 priority_queue<int> q;
22 for(int n:{ 1, 4, 9, 6, 7, 2, 8, 3, 5 })
23 q.push(n);
24 print(q);
25 priority_queue<int,vector<int>,greater<int>> q1;
26 for(int n:{ 1, 4, 9, 6, 7, 2, 8, 3, 5 })
27 q1.push(n);
28 print(q1);
29 priority_queue<int, vector<int>, Comp> q2;
30 for(int n:{ 1, 4, 9, 6, 7, 2, 8, 3, 5 })
31 q2.push(n);
32 print(q2);
33 return 0;
34 }
例7-10运行结果如图7-22所示。
在例7-10中，第4～8行代码定义了类Com p，该类重载了“()”运算符，用于比较两个int类型数据的大小。第9～18行代码定义了函数模板print()，用于输出容器中的元素。第21行代码定义了priority_queue容器适配器q，第22～23行代码通过for循环进行q的初始化，第24行代码调用print()函数输出q中的元素。由图7-22可知，q默认从大到小排列数据。
图7-22 例7-10运行结果
第25行代码定义了priority_queue容器适配器q1，并通过greater<int>指定数据按照从小到大的顺序排列。第26～28行代码通过for循环初始化q1，并调用print()函数输出q1中的元素。由图7-22可知，q1中的元素从小到大排列。
第29行代码定义了priority_queue容器适配器q2，通过函数对象Com p指定q2中的数据排序方式为从小到大；第30～32行代码通过for循环初始化q2，并调用print()函数输出q2的元素。由图7-22可知，q2中的元素从小到大排列。
通过迭代器既可分离容器与算法，又可连接容器与算法。从容器的角度看，只需提供适当的迭代器，就可以遍历容器中的数据，而不必关心数据将用于何种操作；从算法的角度看，只需要通过迭代器操作数据，不必关心是什么类型的容器。容器设计者只需要专注于容器的设计，算法设计者只需要专注于算法的设计，这样就可以很好地实现数据结构与算法的分离。STL提供了五种基本的迭代器：输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机迭代器。本节将针对这五种迭代器进行讲解。
输入迭代器和输出迭代器是最基本、要求最低的迭代器，几乎所有的迭代器都具备这两个迭代器的功能。
1. 输入迭代器
输入迭代器（Input Iterator）只能一次一个地向后读取元素，并按此顺序传回元素值。输入迭代器支持对序列进行不可重复的单向遍历。输入迭代器支持的操作如表7-5所示。
表7-5 输入迭代器支持的操作
输入迭代器只能读取元素一次，迭代器移动到下一个位置后，不能保证之前的迭代器还有效，即执行−−itr不能保证还能读取到原来的元素。
如果有两个输入迭代器itr1和itr2，且有itr1==itr2，但这并不保证++itr1==++itr2，更不能保证*(++itr1)==*(++itr2)。因此，使用输入迭代器读入的序列不能保证是可重复的。
2. 输出迭代器
输出迭代器（Output Iterator）与输入迭代器相反，其作用是将元素逐个写入容器。输出迭代器也支持对序列进行单向遍历，当把迭代器移到下一个位置后，也不能保证之前的迭代器是有效的。输出迭代器支持的操作如表7-6所示。
表7-6 输出迭代器支持的操作含义
前向迭代器（Forward Iterator）是输入迭代器和输出迭代器的集合，具有输入迭代器和输出迭代器的全部功能。前向迭代器支持对序列进行可重复的单向遍历，可以多次解析一个迭代器指定的位置，因此可以对一个值进行多次读写。
前向迭代器去掉了输入迭代器与输出迭代器的一些不确定性，例如，如果有两个前向迭代器itr1和itr2，且有itr1==itr2，那么++itr1==++itr2一定是成立的。前后两次使用相等的前向迭代器读取同一个序列，只要序列的值在这个过程中没有被改写，就一定会得到相同的结果。
双向迭代器（Bidirectional Iterator）是在前向迭代器的基础上增加了一个反向操作，即双向迭代器既可以前进，又可以后退，因此它比前向迭代器新增一个功能，可以进行自减操作，如itr−−或者−−itr。
随机访问迭代器（Random Iterator）是在双向迭代器的基础上又支持直接将迭代器向前或向后移动n个元素，而且还支持比较运算的操作。因此，随机访问迭代器的功能几乎和指针一样。随机访问迭代器支持的操作如表7-7所示。
表7-7 随机访问迭代器支持的操作含义
算法实际上是一系列的函数模板，STL定义了大约70个算法，这些算法以迭代器为参数，可以处理各种类型容器的元素。学习STL算法时，读者可以不必知道算法是如何设计的，但需要知道如何在自己的程序中使用这些算法。本节将介绍STL算法。
下面分别从算法的头文件、算法的分类两个方面对STL算法进行简单介绍。
1. 算法的头文件
STL中提供的所有算法都包含在algorithm、num eric、functional三个头文件中。其中，algorithm是最大的一个算法头文件，它由一系列函数模板组成，涉及的功能有比较、交换、查找、遍历、复制、修改、删除、合并、排序等。
头文件num eric比较小，只包括在容器中进行简单数学运算的几个函数模板。
头文件functional中定义了一些类模板，用于生成一些函数对象。
2. 算法的分类
STL中的算法大致可分为4类，分别如下所示。
STL提供了大量的算法，在编程中使用这些算法可以提高编程效率，下面介绍几个常用的算法。
1.for_each()算法
for_each()属于不可变序列算法，该算法可以依次处理容器中的每一个元素。for_each()算法原型如下所示：
template<typename InputIterator, typename Function> for_each(InputIterator begin, InputIterator end, Function fun
在上述算法原型中，参数begin、end表示要操作的元素区间；参数func是一个函数对象，表示对[begin,end)区间中的每个元素要施加的操作。for_each()算法只是对取出的元素进行相应操作，它不会对容器中的元素做任何修改，也不会改变原来容器的元素次序。
2.find()算法
find()也是不可变序列算法，用于在指定区间查找某一元素是否存在。find()算法原型如下所示：
template<typename InputIterator, typename T> InputIterator find(InputIterator begin, InputIterator end, const T& valu
在上述算法原型中，参数begin、end表示要查找的元素区间；参数value表示要查找的元素值。find()算法是在[begin,end)区间查找value元素是否存在，如果存在，就返回指向这个元素的迭代器；如果不存在，就返回指向容器末尾的迭代器。
3.copy()算法
copy()算法在讲解迭代器时几次都用到了，它的功能是完成元素的复制。copy()算法原型如下所示：
template<typename InputIterator, typename OutputIterator> OutputIterator copy(InputIterator begin, InputIterator end, OutputIterator DestBe
在上述算法原型中，参数begin、end表示要复制的元素区间；参数D estBeg表示目的存储空间的起始位置。由于在讲解迭代器时，已经多次调用copy()函数将元素复制到cout流对象中从而输出到屏幕，因此这里不再赘述。
4.sort()算法
sort()算法属于可变序列算法，用于对容器元素进行排序。sort()算法有两种重载形式，分别如下所示：
template<typename RanIt> //第一种形式 void sort(RanIt begin, RanIt end); template<typename RanIt, typename Pred> //第二种形式 void sort(RanIt begin, RanIt end, Pred op);
第一种形式是默认的，按从小到大的顺序排列容器中的元素；第二种形式可以指定排序规则。第二种重载形式比第一种形式更加通用。
5.accumulate()算法
accumulate()算法属于数值算法，用于累加指定区间的元素值。accumulate()算法原型如下所示：
template<typename InputIterator, typename T> T accumulate(InputIterator begin, InputIterator end, T ini
在上述算法原型中，参数begin、end表示要累加的元素区间；参数init表示累加的初始值。
下面通过案例演示STL算法的具体用法，如例7-11所示。
例7-11 algorithm.cpp
1 #include<iostream>
2 #include<vector>
3 #include<algorithm>
4 #include<functional>
5 #include<iterator>
6 #include<numeric>
7 using namespace std;
8 template<typename T>
9 class Multi //定义类模板
10 {
11 private:
12 T value;
13 public:
14 Multi(const T& v):value(v){} //构造函数
15 void operator()(T& elem) const //重载“()”运算符
16 {
17 elem *= value;
18 }
19 };
20 int main()
21 {
22 int arr[] = { 5,3,2,1,6,4 };
23 vector<int>
24 v.assign(arr, arr + sizeof(arr) / sizeof(int)); //用数组为v容器赋值
25 //调用for_each()函数将容器中每个元素都乘以2
26 for_each(v.begin(), v.begin(), Multi<int>(2));
27 //调用copy()构造函数将容器中的元素输出到屏幕
28 copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
29 cout << endl;
30 //调用find()算法查找容器中是否存在值为200的元素
31 vector<int>::iterator it = find(v.begin(), v.end(), 200);
32 if(it!= v.end())
33 cout << "容器中有值为200的元素" << endl;
34 else
35 cout << "容器中不存在值为200的元素" << endl;
36 //调用sort()算法将容器中的元素从小到大排序
37 sort(v.begin(), v.end());
38 cout << "排序之后：" << endl;
39 copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
40 cout << endl;
41 int sum = accumulate(v.begin(), v.end(), 0); //累加容器中的元素
42 cout << "sum = " << sum << endl;
43 return 0;
44 }
例7-11运行结果如图7-23所示。
图7-23 例7-11运行结果
在例7-11中，第8～19行代码定义了类模板M ulti，该类模板重载了“()”运算符，用于让元素elem乘以值value。第22～24行代码定义了int类型数组arr和vector<int>容器v，并调用assign()函数使用数组arr中的元素为容器v赋值。第26行代码调用for_each()算法，使容器v中的元素都乘以2。copy()算法第三个参数为M ulti<int>(2)，是一个函数对象，作用是让元素乘以2。第28行代码调用copy()算法将容器v中的元素输出到屏幕，由图7-23可知，虽然for_each()算法都让[v.begin(),v.end()）区间的元素乘以2，但容器v中的元素并没有被改动。第31～35行代码调用find()算法查找容器v中是否存在元素200，并输出相应查找信息。由图7-23可知，容器v中不存在元素200。第37行代码调用sort()算法将容器v中的元素从小到大排序。第39行代码调用copy()算法将排序后的容器v中的元素输出到屏幕，由图7-23可知，容器v排序成功。第41～42行代码调用accumulate()算法计算容器v中的元素之和，并输出计算结果。由图7-23可知，accumulate()算法成功计算出了容器v中的元素之和为21。
1. 学校演讲比赛
一场演讲比赛共有24个人参加，分三轮，前两轮为淘汰赛，第三轮为决赛。比赛规则如下。
（1）第一轮分为4个小组，每组6人。每人分别按照抽签顺序演讲，当小组演讲完后，淘汰组内排名最后的3个选手，然后继续下一个小组的比赛。
（2）第二轮分为2个小组，每组6人。比赛完毕，淘汰组内排名最后的3个选手，然后继续下一个小组的比赛。
（3）第三轮只剩下6个人，本轮为决赛，选出前三名。
（4）每个选手演讲完由10个评委分别打分。选手的最终得分是去掉一个最高分和一个最低分后剩下的8个分数的平均分。选手的名次按得分降序排列，若得分一样，按参赛号升序排名。
2. 实现以下功能
打乱参赛选手的顺序，将选手随机分组。制定比赛规则，每一轮比赛之后，打印晋级者分数与姓名。
针对案例需求参赛人数为24，可以使用英文字母（A～Z）作为选手的名字，在26个字母中随机选取24个参赛者进行分组，也可以使用文件的形式存储参赛选手，通过读取文件随机选取。定义参赛选手类Player，Player类的设计如图7-24所示。
图7-24 Player类设计图
Player类中封装了存储选手姓名和最终得分的成员变量，通过随机选取选手、抽签、最终评分的形式进行比赛。Player类的成员函数有以下4个。
（1）选手分组——createPlayer(m ap<int,Player>&,vector<int>&)。
选手分组，在分组之前将选手随机排列。每个选手都有唯一的编号，将参赛选手的编号和姓名保存到m ap<int,Player>类型的容器中，将参赛选手的编号单独存储到vector<int>类型的容器中，用于下一轮比赛抽签。
（2）选手抽签——select(vector<int>&)。
随机选取选手，将比赛后选手的编号存储到vector<int>容器中。
（3）比赛评分——sartM atch(int,vector<int>&,m ap<int,Player>&,vector<int>&)。
对分组后的选手进行比赛评分，共有10个评委打分，将选手的分数存储到deque<int>中，并进行升序排列，计算平均分后，将分数保存。分组的参赛选手得分存储到m ap<int,Player>容器中。
（4）比赛结果显示——showInfor(int,vector<int>&,m ap<int,Player>&)。
用于显示三轮比赛中胜出选手的姓名和分数。
1. 实现思路
根据演讲比赛的要求进行分析，需要存储选手的姓名和每轮参赛选手的分数。每轮比赛随机选取参赛选手，通过随机数模拟评委评分，经过计算后得到每轮选手的分数，并淘汰每组分数排列在后三位的选手。经过三轮比赛选取分数前三的选手作为胜利者。
案例实现使用了STL容器存储选手的编号、姓名、分数。
（1）根据Player类的设计，实现Player类的每个功能。
（2）在主函数m ain()中，创建Player对象，创建保存选手编号的容器，每轮比赛后将胜利者保存到容器中，作为下轮比赛随机选取选手的依据。每轮比赛后将胜出选手的信息保存到容器中，最后选取排名前三的选手作为胜利者。
2. 完成代码
请扫描右侧二维码，查看演讲比赛的具体实现。
本章讲解了STL的基础知识，首先讲解了几种常用的容器及容器适配器；其次讲解了迭代器的概念，以及五种基本的迭代器；然后讲解了几种常用的STL算法。最后，通过一个阶段案例加深读者对容器的理解。关于STL，还有很多内容要学习，本章只是带读者初步认识STL，要深入掌握，还需要读者在实践中多多应用和学习。
一、填空题
1.STL框架的核心组成部分由___、___、___、适配器、空间配置器、仿函数六个部分组成。
2.STL中的序列容器包括___、___、___等。
3.STL中的容器适配器包括___、___、___三种。
4.STL中的五种迭代器类型分别是___、___、___、___、___。
5.STL中的___算法用于对指定区间的元素执行同一种操作。
二、判断题
1.STL是由微软开发出来的。（ ）
2.STL中的容器可以存储不同类型的数据。（ ）
3.multim ap容器可以存储重复键值的元素。（ ）
4.array容器等同于数组，不支持迭代器操作。（ ）
5. 使用sort()算法对容器排序时，可以指定排序规则。（ ）
三、选择题
1. 下列选项中，不属于vector容器操作方法的是（ ）。
A.em place_back
B.pop_back
C.insert
D.push_front
2. 关于array容器，下列描述错误的是（ ）。
A.array容器初始化后，大小固定，不可修改
B.array容器中的元素不可以修改
C.array容器和数组类型一样不进行边界检查
D.array容器可以调用fill()函数进行初始化
3. 关于queue容器适配器，下列描述正确的是（ ）。
A.queue具有先入后出的特点
B.queue可以一次删除多个元素
C.queue不支持迭代器操作
D.queue不支持pop()方法
4. 关于迭代器，下列说法错误的是（ ）。
A.删除容器中的元素，可能会使原有迭代器失效
B.反向迭代器可以从容器尾部向容器首部进行迭代
C.vector容器的iterator迭代器是随机迭代器
D.迭代器就是指针
5. 下列选项中，属于可变序列算法的是（ ）。
A.for_each()
B.sort()
C.accumulate()
D.find()
四、简答题
1. 简述STL中迭代器和C++指针的异同。
2. 简述顺序容器vector、list、deque的结构特点。
3. 简述四种关联容器的特点。
五、编程题
1. 定义vector容器，对数字0～9进行插入、删除和遍历操作。
2. 使用m ap容器对数字0～25映射英文单词A～Z，并在控制台输出。