【C++】第10章标准模板库_c++标准模板库-程序员宅基地

C++的标准模板库（Standard Template Library，STL）是泛型程序设计最成功应用的实例。STL是一些常用数据结构（如链表、可变长数组、排序二叉树）和算法（如排序、查找）的模板的集合，主要由 Alex Stepanov 主持开发，于 1998 年被加人C++标准。有了 STL，程序员就不必编写大多数常用的数据的数据结构和算法。而且 STL 是经过精心设计的，运行效率很高，比水平一般的程序员编写的同类代码速度更快。

有一种说法，C++是用来编写大程序的，如果只是编写几十上百行的行的小程序，用C语言就可以，没有必要用C++。这个说法是不准确的。可以说，写小程序没必要用面向对象的方法，但是用C++还是能够带来很大方便的，因为C++中有 STL。哪怕编写只有十几行的程序，也可能会用到 STL 中提供的数据结构和算法。例如对数组排序，用 STL 中的 sort 算法往往只需要一条语句就能解决，而不用像调用C语言库函数 qsort 那样还要编写比较函数。

10.1 STL 中的基本概念

STL中有以下几个基本概念。

容器（container）：用于存放数据的类模板。可变长数组、链表、平衡二叉树等数据结构在 STL 中都被实现为容器。

迭代器（iterator）：用于存取容器中存放的元素的工具。迭代器是一个变量，作用类似于指针。访问容器中的元素需要通过迭代器，迭代器相当于一个中介。

算法（algorithm）：用来操作容器中元素的函数模板。例如，可以用排序算法 sort 对可变长数组容器 vector 中的元素进行排序，也可以用查找算法 find 搜索链表容器 list 中的元素。这些算法（函数模板）是泛型的,可以在不同数据类型的简单数组和复杂容器上使用。

例如，在 STL 的概念中，int array[100] 这个数组就是一个容器,而 int* 类型的指针变量可以作为迭代器。使用 sort 算法就可以对这个容器进行排序:

sort(array, array +100);

10.1.1 容器模板

容器是用于存放数据的类模板。程序员使用容器时，即将容将容器类模板实例化为容器类时，会指明容器中存放的元素是什么类型的。容器中可以存放基本类型的变量，也可以存放对象。对象或基本类型的变量被插人容器中时，实际插人的是对象或变量的一个复制品。STL 中的许多算法（即函数模板），如排序、查找等算法，在执行过程中会对容器中的元素进行比较。这些算法在比较元素是否相等时通常用 “==” 运算符进行，比较大小通常用 “<” 运算符进行，因此，被放入容器的对象所属的类最好重载 “==” 和 “<” 运算符，以使得两个对象用 “==” 和 "<" 进行比较是有定义的。

容器分为两大类。

（1）顺序容器。顺序容器有以下三种：可变长动态数组 vector、双端队列 deque、双向链表list。它们之所以被称为顺序容器，是因为元素在容器中的位置同元素的值无关，即容器不是排序的。将元素插入容器时，指定在什么位置（尾部、头部或中间某处）插人，元素就会位于什么位置。

（2）关联容器。关联容器有以下四种：set、multiset、 map、multimap。关联容器内的元素是排序的。插人元素时，容器会按一定的排序规则将元素放到适当的位置上，因此插人元素时不能指定位置。默认情况下，关联容器中的元素是从小到大排序（或按关键字从小到大排序）的，而且用 “<” 运算符比较元素或关键字大小。因为是排好序的，所以关联容器在查找时具有非常好的性能。

除了以上两类容器外，STL 还在两类容器的基础上屏蔽一部分功能，突出或增加另一部分功能，实现了三种容器适配器：栈 stack、队列 queue、优先级队列 priority_queue。

为称呼方便起见，本书后面将容器和容器适配器统称为容器。

容器都是类模板。它们实例化后就成为容器类。用容器类定义的对象称为容器对象。例如，“vector<int>” 是一个容器类的名字，“vector<int> a;” 就定义了一个容器对象a,，a 代表一个长度可变的数组，数组中的每个元素都是 int 类型的变量。“vector<double> b;” 定义了另一个容器对象b， a和b的类型是不同的。本书后文所说的 “容器”，有时也指 “容器对象”，读者需要根据上下文自行判别。

任何两个容器对象，只要它们的类型相同，就可以用 <、<=、>、>=、==、!= 进行词典式的比较运算。假设 a、b是两个类型相同的容器对象，这些运算符的运算规则如下。

a == b：若a和b中的元素个数相同，且对应元素均相等，则 “a == b” 的值为 true，否则值为 false。元素是否相等是用 “==” 运算符进行判断的。

a < b：规则类似于词典中两个单词比较大小，从头到尾依次比较每个元素，如果发生 a 中的元素小于 b 中的元素的情况，则 “a < b” 的值为 true;；如果没有发生 b 中的元素小于 a 中的元素的情况，且 a 中的元素个数比 b 少，“a < b” 的值也为 true；其他情况下值为 false。元素比较大小是通过 “<” 运算符进行的。

a != b：等价于! ( a == b )。

a > b：等价于b < a。

a <= b：等价于! (b < a)。

a >= b：等价于! (a < b)。

所有容器都有以下两个

int size()：返回容器对象中元素的个数。

bool empty()：判断容器对象是否为空。

顺序容器和关联容器还有以下成员函数：

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

end()：返回指向容器中最后一个元素后面的位置的迭代器。

rbegin()：返回指向容器中最后一个元素的反向迭代器。

rend()：返回指向容器中第一个元素前面的位置的反向迭代器。

erase (…)：从容器中删除一个或几个元素。该函数参数较复杂，此处省略。

clear()：从容器中删除所有元素。

如果一个容容器是空的，则 begin() 和 end() 的返回值相等。rbegin() 和 rend() 的返回值也相等。

顺序容器还有以下常用成员函数：

front()：返回容器中第一个元素的引用。

back()：返回容器中最后一个元素的引用。

push_back()：在容器末尾增加新元素。

pop back()：删除容器末尾的元素。

insert(…)：插人一个或多个元素。该函数参数较复杂，此处省略。

10.1.2 迭代器

要访问顺序容器和关联容器中的元素，需要通过 “迭代器“ 进行。迭代器是一个变量，相当于容器和操纵容器的算法之间的中介。迭代器可以指向容器中的某个元素，通过迭代器就可以读写它指向的元素。从这一点上看，迭代器和指针类似。迭代器按照定义方式分成以下四种。

（1）正向迭代器，定义方法如下：

容器类名::iterator 迭代器名;

（2）常量正向迭代器，定义方法如下：

容器类名::const_iterator 迭代器名;

（3）反向迭代器，定义方法如下：

容器类名::reverse_iterator 迭代器名;

（4）常量反向迭代器，定义方法如下：

容器类名::const_reverse_iterator 迭代器名;

1. 迭代器用法示例

通过迭代器可以读取它指向的元素，“*迭代器名” 就表示迭代器指向的元素。通过非常量迭代器还能修改其指向的元素。迭代器都可以进行 “++” 操作。反向迭代器和正向迭代器的区别在于：对正向迭代器进行 “++” 操作时，迭代器会指向容器中的后一个元素；而对反向迭代器进行 “++” 操作时，迭代器会指向容器中的前一个元素。下面的程序演示了如何通过迭代器遍历一个 vector 容器中的所有元素。

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> v;
	for(int n = 0; n < 5; ++n)
		v.push_back(n);
	vector<int>::iterator i;		//定义正向迭代器
	for(i = v.begin(); i != v.end(); ++i){
		cout << *i << " ";
		*i *= 2;
	}
	cout << endl;
	//用反向迭代器遍历容器
	for(vector<int>::reverse_iterator j = v.rbegin(); j != v.rend(); ++j)
		cout << *j << " ";
	return 0;
}

程序的输出结果是：

0 1 2 3 4
8 6 4 2 0

第 6 行，vector 容器有多个构造函数，如果用无参构造函数初始化，则容器一开始是空的。

第 10 行，begin 成员函数返回指向容器中第一个元素的迭代器。++i使得 i 指向容器中的下一个元素。end 成员函数返回的不是指向最后一个元素的迭代器，而是指向最后一个元素后面的位置的迭代器，因此循环的终止条件是 “i != v.end()”。

第 16 行定义了反向迭代器用以遍历容器。反向迭代器进行 “++” 操作后，会指向容器中的上一个元素。rbegin 成员函数返回指向容器中最后一个元素的迭代器，rend 成员函数返回指向容器中第一个元素前面的位置的迭代器，因此本循环实际上是从后往前遍历整个数组。

如果迭代器指向了容器中最后一个元素的后面或第一个元素的前面，在通过该迭代器访问元素，就有可能导致程序崩溃，这和访问 NULL 或未初始化的指针指向的地方类似。

第 10 行和第 16 行，写 “++i”、“++j” 相比于写 “i++”、“j++”，程序的执行速度更快。回顾 “++” 被重载成前置和后置运算符的例子如下：

CDemo CDemo::operator ++()

{//前置++

++n;

return *this;

}

CDemo CDemo::operator ++(int k)

{//后置++

CDemo tmp(*this);

n++;

return tmo;

}

后置 “++” 要多生成一个局部对象 tmp，因此执行速度比前置的慢。同理，迭代器是一个对象，STL 在重载迭代器的 “++” 运算符时，后执行时也比前置形式慢。在次数很多的循环中，“++i” 和 “i++” 可能就会造成运行时间上客观的差别了。因此，本书在前面特别提到，对循环控制变量 i，要养成写 “++i”、不写 “i++” 的习惯。

注意，容器适配器 stack、queue、priority_queue 没有迭代器，容器适配器有一些成员函数，可以用来对元素进行访问。

2. 迭代器的功能分类

不同容器的迭代器，其功能强弱有所不同。容器的迭代器的功能强弱，决定了该容器是否支持 STL 中的某种算法。例如，排序算法需要通过随机访问迭代器来访问容器中的元素，因此有点容器就不支持排序算法。常用的迭代器按功能强弱分为输入、输出、正向、双向、随机访问五种，这里指介绍常用的三种。

（1）正向迭代器。假设 p 是一个正向迭代器，则 p 支持以下操作：++p，p++，*p。此外，两个正向迭代器可以互相赋值，还可以用 “==” 和 “!=” 运算符进行比较。

（2）双向迭代器。双向迭代器具有正向迭代器的全部功能。除此之外，若 p 是一个双向迭代器，则 “- - p” 和 “p - -” 都是有定义的。“- - p” 使得 p 朝和 “++p” 相反的方向移动。

若 p 和 p1 都是双向迭代器，则可对 p、p1 进行以下操作：

++p，p++	使 p 指向容器中下一个元素
- - p，p - -	使 p 指向容器中上一个元素
* p	取 p 指向的元素
p = p1	赋值
p == p1，p != p1	判断是否相等、不等

（3）随机访问迭代器。随机访问迭代器具有双向迭代器的全部功能。若 p 是一个随机访问迭代器，i 是一个整型变量或常量，则 p 还支持以下操作：

若 p 和 p1 都是随机访问迭代器，则可对 p、p1 进行以下操作：

双向迭代器的所有操作
p += i	将 p 向后移动 i 个元素
p -= i	将 p 向前移动 i 个元素
p + i	值为：指向 p 后面的第i个元素的迭代器
p - i	值为：指向 p 前面的第i个元素的迭代器
p [ i ]	值为：p 后面的第i个元素的引用
p < p1，p <= p1，p > p1，p >= p1
p - p1	p1 和 p 之间的元素个数

此外，两个随机访问迭代器 p1、p2还可以用 “<”，“>”，“<=”，“>=” 运算符进行比较。“p1 < p2” 的含义是：p1 经过若干次（至少一次）“++” 操作后，就会等于 p2。其他比较方式的含义与此类似。

对于两个随机访问迭代器 p1、p2，表达式 “p2 - p1” 也是有定义的，其返回值是 p2 所指向的元素和 p1 所指向元素的序号之差（也可以说是 p2 和 p1 之间的元素个数减一）。

表 10.1 所示为不同容器的迭代器的功能。

表10.1 不同容器的迭代器的功能
容器	迭代器功能
vector	随机访问
deque	随机访问
list	双向
set / multiset	双向
map / multimap	双向
stack	不支持迭代器
queue	不支持迭代器
priority_queue	不支持迭代器

例如，vector 的迭代器是随机迭代器，因此遍历 vector 容器有以下几种做法，下面的程序中，每个循环演示了一种做法。

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> v(100); //v被初始化成有100个元素
	for(int i = 0;i < v.size() ; ++i) //size返回元素个数
		cout << v[i]; //像普通数组一样使用vector容器
	vector<int>::iterator i;
	for(i = v.begin(); i != v.end (); ++i) //用 != 比较两个迭代器
		cout << * i;
	for(i = v.begin(); i < v.end ();++i) //用 < 比较两个迭代器
		cout << * i;
	i = v.begin();
	while(i < v.end()) { //间隔一个输出
		cout << * i;
		i += 2; // 随机访问迭代器支持 "+= 整数"  的操作
	}
}

list 容器的迭代器是双向迭代器。假设 v 和 i 的定义如下：

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 < size(); ++i)

cout << v[i];

因为 list 不支持随机访问迭代器的容器，也不支持用下标随机访问其元素。

在C++中，数组也是容器。数组的迭代器就是指针，而且是随机访问迭代器。例如，对于数组 int a[10]，int* 类型的指针就是其迭代器。则 a、a+1、a+2 都是 a 的迭代器。

3. 迭代器的辅助函数

STL 中有用于操作迭代器的三个函数模板，它们是：

（1）advance(p, n)：使迭代器 p 向前或向后移动 n 个元素。

（2）distance(p, q)：计算两个迭代器之间的距离，即迭代器 p 经过多少次 ++ 操作后和迭代器 q 相等。如果调用时 p 已经指向 q 的后面，则这个函数会陷入死循环。

（3）iter_swap(p, q)：用于交换两个迭代器 p、q 指向的值。

要使用上述模板，需要包含头文件 algorithm。下面的程序演示了这三个函数模板的用法。

#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);
	cout << "1)" << *p << endl;
	advance(p, -1);
	cout << "2)" << *p << endl;
	list<int>::iterator q = lst.end();
	q--;
	cout << "3)" << distance(p, q) << endl;
	iter_swap(p, q);
	cout << "4)";
	for(p = lst.begin(); p != lst.end(); ++p)
		cout << *p << " ";
	return 0;
}

程序的输出结果是：

1)3

2)2

3)3

4)1 5 3 4 2

10.1.3 算法

STL 提供能在各种容器中通用的算法（大约有70种），如插入、删除、查找、排序等。算法就是函数模板。算法通过迭代器来操纵容器中的元素。许多算法操作的是容器上的一个区间（也可以是整个容器），因此需要两个参数，一个是区间起点元素的迭代器，另一个是区间终点的元素的后面一个元素的迭代器。例如，排序和查找算法都需要这两个参数来指明待排序或待查找的区间。

有的算法返回一个迭代器。例如，find 算法在容器中查找一个元素，并返回一个指向该元素的迭代器。

算法可以处理容器，也可以处理普通的数组。

有的算法会改变其所作用的容器。例如：

copy：将一个容器的内容复制到另一个容器。

remove：在容器中删除一个元素。

random_shuffle：随机打乱容器中的元素。

fill：用某个值填充容器。

有的算法不会改变其所作用的容器。例如：

find：在容器中查找元素。

count_if：统计容器中符合某种条件的元素的个数。

STL 中的大部分常用算法都在头文件 algorithm 中定义。此外，头文件 numeric 中也有一些算法。

下面介绍一个常用算法 find，以便对算法是什么、怎么用有一个基本的概念。find 算法和其他算法一样都是函数模板。find 模板的原型如下：

template<class InIt, class T>

InIt find(InIt first, InIt last, const T& val);

其功能可以是在迭代器 first、last 指定的容器的一个区间 [ first, last) 中，按顺序查找和 val 相等的元素。如果找到，就返回该元素的迭代器；如果找不到，就返回 last。[ first, last) 这个区间是一个左闭右开的区间，即 last 指向的元素其实不在此区间内。find 模板使用 “==” 运算符判断元素是否相等。因此，如果 [ first, last) 区间中存放的是对象，则 “==” 运算符应当被适当重载，使得两个对象可以用 “==” 运算符比较。

注意：上一段话说的是 “其功能可以是”，而不是 “其功能就是”。这是因为模板只是一种代码形式，这种代码形式具体能完成什么功能，取决于程序员对该模板写法的了解及其想象力。按照语法，调用 find 模板时，first 和 last 只要类型相同就可以，不一定必须是迭代器。

演示 find 用法的程序如下：

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main()  {
	int a[10] = {10,20,30,40};
	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 << "not found " << 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 << "not found" << endl;
	else
		cout << "3) " <<* pp << endl;
}

程序的输出结果是：

1) 3

not found

2) 4

3) 20

第 11 行，要查找的区间是 [ v.begin(), v.end() )，v.end() 不在查找范围内，因此没有问题。本行的查找会成功，因此 p 指向找到的元素 3。

第 17 行，因为要查找的区间是 [ v.begin()+1, v.end()-1 )，这个区间中只有 2、3 这两个元素，因此查找会失败，p 的值变为 v.end()-1，因此 p 正好指向 4 这个元素。

第 19 行，数据 a 是一个容器。数组名 a 的类型是 int*，可以做迭代器使用，表达式 “a+4” 的类型也是 int*，因此也能做迭代器。本次调用 find，查找区间是 [a, a+4)，即数组 a 的前四个元素。如果查找失败，find 就会返回 a+4。

STL 中还有一个常用的算法 sort，用于对容器排序，其原型为：

template <class_RandIt>

void sort(_RandIt first, _RandIt last);

该算法可以用来对区间 [first, last) 从小到大进行排序。下面两行程序就能对数组 a 排序：

int a[4] = {3,4,2,1};

sort(a, a+4);

10.1.4 STL 中 “大”、“小” 和 “相等” 的概念

STL 中关联容器内部的元素是排序的。STL 中的许多算法也涉及排序、查找。这些容器和算法都需要对元素进行比较，有点比较是否相等，有的比较元素大小。在 STL 中，默认情况下，比较大小是通过 “<” 运算符进行的，和 “>” 运算符无关。在 STL 中提到 “大”、“小” 的概念时，以下三个说法是等价的：

（1）x 比 y 小。

（2）表达式 “x<y” 为真。

（3）y 比 x 大。

一定要注意，“y 比 x 大” 意味着 “x<y 为真”，而不是 “y>x 为真”。“y>x” 的结果如何并不重要，甚至 “y>x” 是没定义的都没有关系。

在 STL 中，“x 和 y 相等” 也往往不等价于 “x==y 为真”。对于在未排序的区间上进行的算法，如顺序查找算法 find，查找过程中比较两个元素是否相等用的是 “==” 运算符；但是对于在排好序的区间上进行查找、合并等操作的算法（如折半查找算法 binary_search，关联容器自身的成员函数 find）来说，“x 和 y 相等” 是与 “x<y 和 y<x 同时为假” 等价的，与 “==” 运算符无关。看上去 “x<y 和 y<x 同时为假” 就应该和 “x==y 为真” 等价，其实不然。例如下面的 class A：

class A{

int v;

public:

bool operator < (const A & a)const {return false};

可以看到，对任意两个类 A 的对象 x、y，“x<y” 和 “y<x” 都是为假的。也就是说，对 STL 的关联容器和许多算法来说，任意两个类 A 的对象都是相等的，这与 “==” 运算符的行为无关。

综上所述，使用 STL 中的关联容器和许多算法时，往往需要对 “<” 运算符进行适当的重载，使得这些容器和算法可以用 “<” 运算符对所操作的元素进行比较。最好将 “<” 运算符重载为全局函数，因为在重载为成员函数时，有些编译器上会出错（由其 STL 源代码的写法导致）。

10.2 顺序容器

10.2.1 动态数组 vector

vector 是可变长的动态数组，支持随机访问迭代器，所有 STL 算法都能对 vector 进行操作。要使用 vector，需要包含头文件 vector。

在 vector 容器中，根据下标随机访问某个元素的时间是常数，在尾部添加一个元素的时间大多数情况下也是常数，总体来说速度很快。在中间插入或删除元素时，因为要移动多个元素，因此速度较慢，平均花费的时间和容器中的元素个数成正比。

在 vector 容器中，用一个动态分配的数组来存放元素，因此根据下标访问某个元素的时间固定，与元素个数无关。vector 容器在实现时，动态分配的存储空间一般都大于存放元素所需的空间。例如，哪怕容器中只有一个元素，也会分配 32 个元素的存储空间。这样做的好处是，在尾部添加一个新元素时不必重新分配空间，直接将新元素写入适当位置即可。在这种情况下，添加新元素的时间也是常数。但是，如果不断添加新元素，多出来的空间就会用完，此时再添加新元素，就不得不重新分配内存空间，把原有内容复制过去后再添加新的元素。碰到这种情况，添加新元素所花的时间就不是常数，而是和数组中的元素个数成正比。至于在中间插入或删除元素，必然涉及元素的移动，因此时间不是固定的，而是和元素个数有关。

vector 有很多成员函数，常用的如表 10.2 所示。

表10.2 vector 中常用的成员函数
成员函数	作用
vector()	无参构造函数，将容器初始化为空
vector(int n)	将容器初始化为有 n 个元素
vector(int n, const T & val)	假定元素的类型是 T，此构造函数将容器初始化为有 n 个元素，每个元素的值都是 val
vector(iterator first, iterator last)	first 和 last 可以是其他容器的迭代器。一般来说，本构造函数初始化的结果就是将 vector 容器的内存变成与其他容器上的区间 [first, last) 一致
void clear()	删除所有元素
bool empty()	判断容器是否为空
void pop_back()	删除容器末尾的元素
void push_back(const T & val)	将 val 添加到容器末尾
int size()	返回容器中的元素的个数
T & front()	返回容器中第一个元素的引用
T & back()	返回容器中最后一个元素的引用
iterator insert(iterator i, const T & val)	将 val 插入迭代器 i 指向的位置，返回 i
iterator insert(iterator i, iterator first, iterator last)	将其他容器上的区间 [first, last) 中的元素插入迭代器 i 指向的位置
iterator erase(iterator i)	删除迭代器 i 指向的元素，返回值是被删元素后面的元素的迭代器
iterator erase(iterator first, iterator last)	删除容器中的区间 [first, last)
void swap(vector<T> & v)	将容器自身的内容和另一个同类型的容器 v 互换

下面的程序演示了 vector 的基本用法。

#include <iostream>
#include <vector>
using namespace std;
template <class T>
void PrintVector(const vector<T> & v)
{
	typename vector<T>::const_iterator i;
	for(i = v.begin(); i != v.end(); ++i)
		cout << *i << " ";
	cout << endl;
}
int main()
{
	int a[5] = {1,2,3,4,5};
	vector<int> v(a, a+5);
	cout << "1)" << v.end()-v.begin() << endl;
	cout << "2)"; PrintVector(v);
	v.insert(v.begin()+2 ,13);
	cout << "3)"; PrintVector(v);
	v.erase(v.begin()+2);
	cout << "4)"; PrintVector(v);
	vector<int> v2(4, 100);
	v2.insert(v2.begin(), v.begin()+1,v.begin()+3);
	cout << "5)v2:"; PrintVector(v2);
	v.erase(v.begin()+1, v.begin()+3);
	cout << "6)"; PrintVector(v);
	return 0;
}

程序的输出结果是：

1)5

2)1 2 3 4 5

3)1 2 13 3 4 5

4)1 2 3 4 5

5)v2:2 3 100 100 100 100

6)1 4 5

思考题：程序中的 PrintVector 模板演示了将容器的引用作为函数参数的用法。就完成输出整个容器内容这个功能来说，写成 PrintVector 模板这样是比较笨拙的，该模板的适用范围太窄。有没有更好的写法？（暂未想到）

vector 还可以嵌套以形成可变长的二维数组。例如：

#include <iostream>
#include <vector>
using namespace std;
int main()
{	
	vector<vector<int> > v(3); //v有3个元素，每个元素都是vector<int> 容器
	for(int i = 0;i < v.size(); ++i)
		for(int j = 0; j < 4; ++j)
			v[i].push_back(j);
	for(int i = 0;i < v.size(); ++i) {
		for(int j = 0; j < v[i].size(); ++j)
			cout << v[i][j] << " ";
		cout << endl;
	}
	return 0;
}

程序的输出结果是：

0 1 2 3

“vector<vector<int> > v(3);” 定义了一个 vector 容器，该容器中的每个元素都是一个 vector<int> 容器。即可认为，v 是一个二维数组，一共 3 行，每行都是一个可变长的一维数组。在 Dev C++ 中，上面写法中 int 后面的两个 “>” 之间需要有空格，否则有的编译器会把它们当做 “>>” 运算符，编译会出错。

10.2.2 双向链表 list

list 是一个双向链表。使用 list 需要包含头文件 list。双向链表的每个元素中都有一个指针指向后一个元素，也有一个指针指向前一个元素，如图 10.1 所示。

在 list 容器中，在已经定位到要增删元素的位置的情况下，增删元素能在常数时间内完成。如图 10.2 所示，在 a[i] 和 a[i+1] 之间插入一个元素，只需要修改 a[i] 和 a[i+1] 中的指针即可。

list 容器不支持根据下标随机存取元素。

list 的构造函数和许多成员函数的用法都与 vector 类似，此处不再列举（见表 10.2）。除了顺序容器都有的成员函数外，list容器还独有如表 10.3 所示的成员函数（此表不包含全部成员函数，且有些函数的参数较为复杂，表中值列出函数名）。

表10.3 list 的成员函数
成员函数或成员函数模板	作用
void push_front(const T & val)	将 val 插入链表最前面
void pop_front()	删除链表最前面的元素
void sort()	将链表从小到大排序
void remove(const T & val)	删除和 val 相等的元素
remove_if	删除符合某种条件的元素
void unique()	删除所有和前一个元素相等的元素
void merge(list<T> & x)	将链表 x 合并进来并清空 x。要求链表自身和 x 都是有序的
void splic(iterator i, list<T> & x, iterator first, iterator last)	在位置 i 前面插入链表 x 中的区间 [first, last)，并在链表 x 中删除该区间。链表自身和链表 x 可以是同一个链表，只要 i 不再 [first, last) 中即可

表 10.3 中列出的成员函数有些事重载的，如 unique、merge、splice 成员函数都不止一个，这里不再意义列举并解释。后面对于其他容器以及算法的介绍，对于有重载的情况也不再指出。要详细了解 STL，还需要查阅专门的 STL 手册，或查看编译器提供的联机帮助。

STL 中的算法 sort 可以用来对 vector 和 deque 排序，它需要随机访问迭代器的支持。因为 list 不支持随机访问迭代器，所以不能用算符 sort 对 list 容器排序。因此，list 容器引入了 sort 成员函数以完成排序。

list 的示例程序如下：

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
class A{
	private:
		int n;
	public:
		A(int n_) {n = n_;}
		friend bool operator < (const A & a1, const A & a2);
		friend bool operator == (const A & a1, const A & a2);
		friend ostream & operator << (ostream & o, const A & a);
};
bool operator < (const A & a1, const A & a2){
	return a1.n < a2.n;
}
bool operator == (const A & a1, const A & a2){
	return a1.n == a2.n;
}
ostream & operator << (ostream & o, const A & a){
	o << a.n;
	return o;
}
template <class T>
void Print(T first, T last)
{
	for(; first != last; ++first)
		cout << *first << " ";
	cout << endl;
}
int main()
{
	A a[5] = {1,3,2,4,2};
	A b[7] = {10,30,20,30,30,40,40};
	list<A> lst1(a, a+5), lst2(b, b+7);
	lst1.sort();
	cout << "1)"; Print(lst1.begin(), lst1.end());
	lst1.remove(2);
	cout << "2)"; Print(lst1.begin(), lst1.end());
	lst2.pop_front();
	cout << "3)"; Print(lst2.begin(), lst2.end());
	lst2.unique();
	cout << "4)"; Print(lst2.begin(), lst2.end());
	lst2.sort();
	lst1.merge(lst2);
	cout << "5)"; Print(lst1.begin(), lst1.end());
	cout << "6)"; Print(lst2.begin(), lst2.end());
	lst1.reverse();
	cout << "7)"; Print(lst1.begin(), lst1.end());
	lst2.insert(lst2.begin(), a+1, a+4);
	list<A>::iterator p1, p2, p3;
	p1 = find(lst1.begin(), lst1.end(), 30);
	p2 = find(lst2.begin(), lst2.end(), 2);
	p3 = find(lst2.begin(), lst2.end(), 4);
	lst1.splice(p1, lst2, p2, p3);
	cout << "8)"; Print(lst1.begin(), lst1.end());
	cout << "9)"; Print(lst2.begin(), lst2.end());
	return 0;
}

程序的输出结果是：

1)1 2 2 3 4

2)1 3 4

3)30 20 30 30 40 40

4)30 20 30 40

5)1 3 4 20 30 30 40

7)40 30 30 20 4 3 1

8)40 2 30 30 20 4 3 1

9)3 4

分析略。

例题：用 list 解决约瑟夫问题。约瑟夫问题是：有 n 只猴子，按顺时针方向围成一圈选大王（编号为 1~n），从第 1 号开始报数，一直数到 m，数到 m 的猴子退到圈外，剩下的猴子再接着从 1 开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王。编程求输入 n、m 后，输出最后猴王的编号。

输入数据：每行是用空格分开的两个整数，第一个是 n，第二个是 m（0 < m，n <= 1 000 000）。最后一行是：

0 0

输出要求：对于每行输入数据（最后一行除外），输出数据也是一行，即最后猴王的编号。

输入样例：

6 2

12 4

8 3

0 0

输出样例：

示例程序如下：

#include <list>
#include <iostream>
using namespace std;
int main()
{
	list<int> monkeys;
	int n,m;
	while(true) {
		cin >> n >> m ;
		if(n == 0 && m == 0)
			break;
		monkeys.clear();  //清空list容器
		for(int i = 1;i <= n; ++i)  //将猴子的编号放入list
			monkeys.push_back(i);
		list<int>::iterator it = monkeys.begin ();
		while(monkeys.size() > 1) { //只要还有不止一只猴子，就要找一只猴子让其出列
			for(int i = 1; i < m ; ++i) { //报数
				++it;
				if(it == monkeys.end())
					it = monkeys.begin ();
			}
			it = monkeys.erase(it); //删除元素后，迭代器失效，
								 //要重新让迭代器指向被删元素的后面
			if(it == monkeys.end())
				it = monkeys.begin();
		}
		cout << monkeys.front() << endl; //front返回第一个元素的引用
	}
	return 0;
}

erase 成员函数返回被删除元素后面那个元素的迭代器。如果被删除的是最后一个元素，则返回 end()。

这个程序也可以用 vector 实现，但是执行速度要慢很多。因为 vector 的 erase 操作牵涉元素的移动，不能在常数时间内完成，所花费的时间和容器中的元素个数有关；而 list 的 erase 操作只是修改几个指针而已，可以在常数时间内完成。当 n 很大（数十万）时，两种写法在速度上会有明显区别。

10.2.3 双向队列 deque

deque 也是一个可变长数组。要使用 deque，需要包含头文件 deque。所有适用于 vector 的操作都适用于 deque。在 deque 中，随机存取任何元素都能在常数时间内完成（但慢于 vector）。它相比于 vector 的优点是，vector 在头部删除或添加元素的速度很慢，在尾部添加元素的性能较好，而 deque 在头尾增删元素都具有较好的性能（大多数情况下都能在常数时间内完成）。它有两种 vector 没有的成员函数。

void push_front(const T & val); //将 val 插入容器的头部

void pop_front(); //删除容器头部的元素

思考题：猜想一下，deque 是如何实现它相比 vector 的优势的？

答：建议在系统学习完数据结构后回答。

10.3 函数对象

10.3.1 函数对象的概念

在详细学习关联容器和算法之前，需要先了解函数对象的概念。

如果一个类将 “( )” 运算符重载为成员函数，这个类就称为函数对象类，这个类的对象就是函数对象。函数对象是一个对象，但是使用的形式看起来像函数调用，实际上也执行了函数调用，因而得名。下面是一个函数对象的例子。

#include <iostream>
using namespace std;
class CAverage{
	public:
		double operator () (int a1, int a2, int a3)
		{
			return (double)(a1+a2+a3)/3;
		}
};
int main()
{
	CAverage average;
	cout << average(3, 2, 3);
	return 0;
}

程序的输出结果是：
2.66667

“( )” 是目数不限的运算符，因此重载为成员函数时，有多少个参数都可以。

average 是一个对象，average(3,2,3) 实际上就是 average.operator(3,2,3)，这使得 average 看上去像函数的名字，故称其为函数对象。

10.3.2 函数对象应用实例 1：在 accumulate 算法中的应用

STL 中有以下实现 “累加” 功能的算法（函数模板）：

template <class InIt, class T, class Pred>

T accumulate(InIt first, InIt last, T val, Pred op);

该模板的功能是对 [first, last) 中的每个迭代器 I 执行 val = op(val, *I)，返回最终的 val。

在 Dev C++ 中，numeric 头文件中 accumulate 的源代码如下：

template <class InIt, class T, class Pred>

T accumulate(InIt first, InIt last, T val, Pred op)

{

for(; first != last; ++first)

init = op(init, *first);

return init;

}

此模板被实例化后，“op(init, *first)” 必须要有定义，则 op 只能是函数指针或者函数对象。因此调用该 accumulate 模板时，形参 op 对应的实参只能是函数名、函数指针或者函数对象。

下面的程序通过 accumulate 模板求一个 vector 中元素的平方和，其中用到了函数对象。

#include <iostream>
#include <vector>
#include <numeric> //accumulate 在此头文件定义
using namespace std;
template <class T>
void PrintInterval(T first, T last)
{ //输出区间[first,last)中的元素
	for(; first != last; ++ first)
		cout << * first << " ";
	cout << endl;
}
int SumSquares(int total, int value)
{
	return total + value * value;
}
template<class T>
class SumPowers
{
	private:
		int power;
	public:
		SumPowers(int p):power(p) { }
		const T operator() ( const T & total, const T & value)
		{ //计算 value的power次方，加到total上
		 	T v = value;
			for(int i = 0;i < power - 1; ++ i)
				v = v * value;
	 		return total + v;
		}
};
int main()
{
	const int SIZE = 10;	
	int a1[] = { 1,2,3,4,5,6,7,8,9,10 };
	vector<int> v(a1,a1+SIZE);
	cout << "1) "; PrintInterval(v.begin(),v.end());
	int result = accumulate(v.begin(),v.end(),0,SumSquares);
	cout << "2) 平方和：" << result << endl;
	result = accumulate(v.begin(),v.end(),0,SumPowers<int>(3));
	cout << "3) 立方和：" << result << endl;
	result = accumulate(v.begin(),v.end(),0,SumPowers<int>(4));
	cout << "4) 4次方和：" << result;
	return 0;
}

程序的输出结果是：

1) 1 2 3 4 5 6 7 8 9 10

2) 平方和：385

3) 立方和：3025

4) 4次方和：25333

第 37 行，第四个参数是 SumSquares 函数的名字。函数名字的类型是函数指针，因此本行将 accumulate 模板实例化后得到的模板函数定义如下：

int accumulate(vector<int>::iterator first, vector<int>::iterator last, int init,

int (*op)(int, int))

{

for(; first != last; ++first)

init = op(init, *first);

return init;

}

形参 op 是一个函数指针，而 “op(init, *first);” 就调用了指针 op 指向的函数，在第 37 行的情况下就是函数 SumSquares。

第 39 行，第四个仓鼠是 SumPowers<int>(3)。SumPowers 是类模板的名字，SumPowers<int>(3) 就是一个 SumPowers<int> 类的临时对象。编译器在编译此行时，会将 accumulate 模板实例化成以下函数：

int accumulate(vector<int>::iterator first, vector<int>::iterator last, int init,

SumPowers<int> op)

{

for(; first != last; ++first)

init = op(init, *first);

return init;

}

形参 op 是一个函数对象，而 “op(init, *first);” 等价于：
op.operator()(init, *first);

即调用了 SumPowers<int> 类的 operator() 成员函数。

对比 SumPowers 和 SumSquares 可以发现，函数对象的 operator() 成员函数可以根据对象内部的不同状态执行不同操作，而普通函数就无法做到这一点。因此函数对象的功能比普通函数更强大。

10.3.3 函数对象应用实例 2：在 sort 算法中的应用

STL 中的排序模板 sort 能将区间从小到大排序。sort 算法有两个版本。第一个版本的原型如下：

template <class_RandIt>

void sort(_RandIt first, _RandIt last);

该模板可以用来将区间 [first, last) 中的元素从小到大排序，要求 first、last 是随机访问迭代器。元素比较大小是用 “<” 进行的。如果表达式 “a<b” 的值为 true，则 a 排在 b 前面；如果 “a<b” 的值为 false，则 b 未必排在 a 的前面，还要看 “b<a” 是否成立，成立的话 b 才排在 a 前面。要使用这个版本的 sort 算法，待排序的对象必须能用 “<” 运算符进行比较。

sort 算法第二个版本的原型如下：

template <class_RandIt, class Pred>

void sort(_RandIt first, _RandIt last, Pred op);

这个版本和第一个版本的差别在于，元素 a、b 比较大小是通过表达式 “op(a, b)” 进行的。如果该表达式的值为 true，则 a 比 b 小；如果该表达式的值为 false，也不能认为 b 比 a 小，还要看 “op(b, a)” 的值。总之，op 定义了元素比较大小的规则。下面是一个使用 sort 算法的例子。

#include <iostream>
#include <algorithm>
using namespace std;
template <class T>
void PrintInterval(T first, T last)
{
	for(; first != last; ++first)
		cout << *first << " ";
	cout << endl;
}
class A{
	public:
		int v;
		A(int n):v(n) {}
};
bool operator < (const A & a1, const A & a2)
{//重载为 A 的 const 成员函数也可以，重载为非 const 成员函数在某些编译器上会出错
	return a1.v < a2.v;
}
bool GreaterA(const A & a1, const A & a2)
{//v 值大的元素作为较小的数
	return a1.v > a2.v;
}
struct LessA
{
	bool operator() (const A & a1, const A & a2)
	{//v 的个位数小的元素作为较小的数
		return (a1.v % 10) < (a2.v % 10);
	}
};
ostream & operator << (ostream & o, const A & a)
{
	o << a.v;
	return o;
}
int main()
{
	int a1[4] = {5,2,4,1};
	A a2[5] = {13,12,9,8,16};
	sort(a1, a1+4);
	cout << "1)"; PrintInterval(a1, a1+4);
	sort(a2, a2+5);
	cout << "2)"; PrintInterval(a2, a2+5);
	sort(a2, a2+5, GreaterA);
	cout << "3)"; PrintInterval(a2, a2+5);
	sort(a2, a2+5, LessA());
	cout << "4)"; PrintInterval(a2, a2+5);
	return 0;
}

程序的输出结果是：

1)1 2 4 5

2)8 9 12 13 16

3)16 13 12 9 8

4)12 13 16 8 9

编译到第 45 行时，编译器将 sort 实例化得到的函数原型如下：

void sort(A* first, A* last, bool (*op)(const A &, const A &));

该函数在执行过程中，当要比较两个元素a、b的大小时，就是看 op(a,b) 和 op(b,a) 的返回值。本程序中 op 指向 GreaterA，因此就用 GreaterA 定义的规则来比较大小。

编译至第 47 行时，编译器将 sort 实例化得到的函数原型如下：

void sort(A* first, A* last, LessA op);

该函数在执行过程中，当要比较两个元素 a、b 的大小时，就是看 op(a,b) 和 op(b,a) 的返回值。本程序中，op(a,b) 等价于 operator(a,b)，因此就用 LessA 定义的规则来比较大小。

STL 中定义了一些函数对象类模板，都位于头文件 funtional 中。例如，greater 模板的源代码如下：

template <class T>

struct greater

{

bool operator() (const T& x, const T& y)const{

return x>y;

}

};

假设有以下数组：

int a[4] = {3,5,34,8};

要将该数组从大到小排序，则只需写：

sort(a, a+4, greater<int>());

要使用 greater 模板，须确保 “>” 运算符本来就有定义，或经过了适当的重载。

list 容器的 sort 成员能将元素从小到大排序。它也有两个版本：一个是没有参数的函数，比较大小用 “<” 运算符；另一个是函数模板，原型如下：

template <class Pred>

void sort(Pred op);

sort 函数允许自定义比较大小的规则，即 op(x,y) 为真就认为 x 比 y 小。例如，假设有：

list<int> lst;

如果希望将 lst 中的元素按其整数数值从大到小排序，只需写：

list.sort(greater<int>());

在使用关联容器和许多算法时，都可以用函数对象来定义比较大小的规则，以及其他一些规则和操作。

10.3.4 STL 中的函数对象类模板

STL 中有一些函数对象类模板，如表 10.4 所示。

表10.4 STL 中的函数对象类模板
函数对象类模板	成员函数 T operator (const T & x, const T & y) 的功能
plus<T>	return x+y;
minus<T>	return x-y;
multplies<T>	return x*y;
divides<T>	return x/y;
modulus<T>	return x%y;
	成员函数 bool operator(const T & x, const T & y) 的功能
equal_to<T>	return x==y;
not_equal_to<T>	return x!=y;
greater<T>	return x>y;
less<T>	return x<y;
gerater_equal<T>	return x>=y;
less_equal<T>	return x<=y;
logcal_and<T>	return x && y;
logical_or<T>	return x \|\| y;
	成员函数 T operator(const T & x) 的功能
negate<T>	return -x;
	成员函数 bool operator(const T & x) 的功能
logical_not<T>	return !x

例如，如果要求两个 double 型变量 x、y 的成绩，可以写：

multiplies<double> () (x,y)

less 是 STL 中最常用的函数对象类模板，其定义如下：

template <class_Tp>

struct less

{

bool operator() (const _Tp&_x, const _Tp&_y)const

{ return _x<_y; }

};

要判断两个 int 变量 x、y 中 x 是否比 y小，可以写：

if(less<int> () (x,y)) { ... }

10.3.5 引入函数对象后 STL 中的 “大”、“小” 和 “相等” 概念

前面提到过，默认情况下，STL 中的容器和算法比较元素的大小是通过 “<” 运算符进行的。通过 10.3.4 节可知，sort 和 list::sort 都可以通过一个函数对象或者函数自定义比较元素大小的规则。例如以下的 sort 版本：

template <class_RandIt, class Pred>

void sort(_RandIt first, _RandIt last, Pred op);

实际调用 sort 时，和 op 对应的实参可以是一个函数对象或者函数的名字。sort 在执行过程中用 op(x,y) 比较 x 和 y 的大小，因此可以将 op 称为自定义的 “比较器”。

关联容器中的元素是从小到大排序的。使用关联容器时，也可以用自定义的比较器取代 “<” 运算符，以规定元素之间的大小关系。STL 中还有许多算法都可以自定义比较器。在自定义比较器 op 的情况下，以下三种说法是等价的：

（1）x 小于 y。

（2）op(x,y) 的返回值为 true。

（3）y 大于 x。

同样地，对关联容器的 find 和 count 成员函数以及其他一些在有序区间上的 STL 算法而言，在自定义比较器 op 的情况下，“x 和 y 相等” 与 “op(x,y) 和 op(y,x) 都为假” 是等价的。

10.4 关联容器

关联容器内部的元素都是排好序的，有以下四种。

set：排好序的集合，不允许有相同元素。

multiset：排好序的集合，允许有相同的元素。

map：每个元素都分为关键字和值两部分，容器中的元素是按关键字排序的。不允许有多个元素的关键字相同。

multimap：和 map 类似，差别在于元素的关键字可以相同。

不能修改 set 或 multiset 容器中元素的值。因为元素被修改后，容器并不会自动重新调整顺序，于是容器的有序性就会被破坏，再在其上进行查找等操作就会得到错误的结果。因此，如果要修改 set 或 multiset 容器中某个元素的值，正确的做法是先删除该元素，再插入新元素。同理，也不能修改 map 和 multimap 容器中元素的关键字。

关联容器内部的元素或关键字之间比较大小可以用 “<” 运算符，也可以用自定义的比较器。因为有序，所以在关联容器上进行查找的速度较快。使用关联容器的目的也就在于快速查找。当一个元素被插入关联容器时，该元素会和已有的元素进行比较，最终被插入一个合适的位置。在关联容器中查找元素和插入元素的时间复杂度都是 O(log(n))。从 begin() 到 end() 遍历整个关联容器，就是从小到大遍历整个容器。

在排好序的 vector 和 deque 上进行折半查找，时间复杂度也可以是 O(log(n))。但是，对于插入、删除和查询交替进行的情况，使用 vector 和 deque 的效率不高。因为tm上面的插入和删除操作会引起元素的移动，时间复杂度是 O(n)。

关联容器一般是用平衡二叉树实现的。平衡二叉树的原理属于 “数据结构” 课程的内容，本书不做介绍。时间复杂度是衡量算法好坏的两大标准之一，具体介绍见 “数据结构与算法” 专栏的文章，简单了解可参考：什么是时间复杂度？_残雪飞扬的博客-程序员宅基地。

除了所有容器共有的成员函数外，关联容器还具有以下成员函数：

find：查找某个值。

lowe_bound：查找某个下界。

upper_bound：查找某个上界。

equal_range：同时查找上界和下界。

count：计算等于某个值的元素个数。

insert：插入一个元素或一个区间。

10.4.1 预备知识：pair 类模板

在学习关联容器之前，首先要了解 STL 中的 pair 类模板，因为关联容器的一些成员函数的返回值是 pair 对象，而且 map 和 multimap 容器中的元素都是 pair 对象。pair 的定义如下：

template <class _T1, class_T2>

struct pair

{

_T1 first;

_T2 second;

pair():first(), second() { } //无参构造函数初始化

pair(const _T1 &_a, const _T2 &_b):first(_a), second(_b) { }

template <class_U1, class_U2>

pair(const pair<_U1, _U2> &__p):first(__p.first), second(__p.second) { }

};

pair 实例化出来的类都有两个成员变量，一个是 first，一个是 second。

STL 中还有一个函数模板 make_pair，其功能是生成一个 pair 模板类对象。make_pair 的源代码如下：

template <class T1, class T2>

pair<T1, T2> make_pair(T1 x, T2 y)

{

return (pair<T1, T2> (x, y) );

}

下面的程序演示了 pair 和 make_pair 的用法。

#include <iostream>
using namespace std;
int main()
{
	pair<int,double> p1;
	cout << p1.first << "," << p1.second << endl; //输出  0,0	
	pair<string,int> p2("this",20);
	cout << p2.first << "," << p2.second << endl; //输出  this,20
	pair<int,int> p3(pair<char,char>('a','b'));
	cout << p3.first << "," << p3.second << endl; //输出  97,98
	pair<int,string> p4 = make_pair(200,"hello");
	cout << p4.first << "," << p4.second << endl; //输出  200,hello
	return 0;
}

pair 模板中的第三个构造函数就是函数模板，参数必须是一个 pair 模板类对象的引用。程序中第 9 行的 p3 就是用这个构造函数初始化的。

10.4.2 multiset

使用 multiset 必须包含头文件 set。multiset 类模板的定义如下：

template <class Key, class Pred = less<Key>, class B = allocator<Key> >

class multiset{

...

};

该模板有三个类型参数：Key、Pred 和 B。类型参数可以有默认值，默认值就是某种类型。例如，Pred 类型参数的默认值就是 less<Key> 类型，B的默认值就是 allocator<Key> 类型。第三个类型参数极少用到，一般都用默认值，因此这里不做介绍。

第一个类型参数说明 multiset 容器中的每个元素都是 Key 类型的。第二个类型参数 Pred 用于指明容器中元素的排序规则，在被实例化后，Pred 可以是函数对象类，也可以是函数指针类型。multiset 内部在排序时定义了一个变量 “Pred op”，根据表达式 “op(x, y)” 来比较两个元素 x、y的大小。该表达式的值为 true，则说明 x 比 y 小。Pred 的默认值是 less<Key>，less 是 STL 中的函数对象类模板，其定义如下：

template <class_Tp>

struct less

{

bool operator () (const _Tp &__x, const _Tp & __y)const

{ return __x < __y; }

};

这说明，在默认情况下，multiset 容器中的元素是用 “<” 运算符比较大小的。例如，假设 A 是一个类的名字，可以定义一个如下的容器对象：

multiset<A> s;

由于 multiset 的类型参数可以使用默认值，因此上面的语句等价于：

multiset<int, less<A>, allpcator<A> > s;

模板类 multiset<int, less<A>, allpcator<A> > 的 insert 成员函数可以用来插入一个元素，插入过程中需要进行元素之间的比较，可以认为 insert 成员函数中定义了一个变量 less<A> op，用 op(x, y) 来比较元素 x、y 的大小。归根到底，还是用 “<” 运算符比较 x、y 的大小。因此，“<” 运算符必须经过适当重载，才可以向 multiset<A> 容器中插入元素。下面的程序会编译出错：

#include <set>

using namespace std;

class A{ };

int main() {

multiset<A> a;

a.insert(A()); //编译出错，因为不能用 “<” 运算符比较两个 A 对象

}

multiset 常用的成员函数如表 10.5 所示。有的成员函数有不止一个版本，这里不一一列出。

表10.5 multiset 的成员函数
成员函数或成员函数模板	作用
iterator find(const T & val);	在容器中查找值为 val 的元素，返回其迭代器。如果找不到，返回 end()
iterator insert(const T & val);	将 val 插入容器中并返回其迭代器
void insert(iterator first, iterator last);	将区间 [first, last) 中的元素插入容器
int count(const T & val);	统计有多少个元素的值和 val 相等
iterator lower_bound(const T & val);	查找一个最大的位置 it，使得 [begin(), it) 中所有的元素都比 val 小
iterator upper_bound(const T & val);	查找一个最大的位置 it，使得 [begin(), it) 中所有的元素都比 val 大
pair<iterator, iterator> equal_range (const T & val);	同时求得 lower_bound 和 upper_bound
iterator erase(iterator it);	删除 it 指向的元素，返回其后面的元素的迭代器（Visual Studio 2010 中如此，但是在 C++ 标准和 Dev C++ 中，返回值不是这样）
iterator erase(iterator first, iterator last);	删除区间 [first, last)，返回 last（Visual Studio 2010 中如此，但是在 C++ 标准和 Dev C++ 中，返回值不是这样）

multiset 及 set 中的 find 和 count 并不是用 “==” 运算符比较元素是否和待查找的值相等的。它们进行比较的原则是：如果 “x 比 y 小” 和 “y 比 x 小” 同时为假，就认为 x 和 y 相等。

下面通过一个例子说明 multiset 的用法。

#include <iostream>
#include <set>
using namespace std;
template <class T>
void Print(T first, T last)
{
	for(; first != last; ++first)
		cout << *first << " ";
	cout << endl;
}
class A{
	private:
		int n;
	public:
		A(int n_) {n = n_;}
		friend bool operator < (const A & a1, const A & a2)
		{return a1.n < a2.n;}
		friend ostream & operator << (ostream & o, const A & a2)
		{o << a2.n;	return o;}
		friend class MyLess;
};
class MyLess{
	public:
		bool operator () (const A & a1, const A & a2)
		{return (a1.n%10) < (a2.n%10);}
};
typedef multiset<A> MSET1;
typedef multiset<A, MyLess> MSET2;
int main()
{
	const int SIZE = 6;
	A a[SIZE] = {4,22,19,8,33,40};
	MSET1 m1;
	m1.insert(a, a+SIZE);
	m1.insert(22);
	cout << "1)" << m1.count(22) << endl;
	cout << "2)"; Print(m1.begin(), m1.end());
	MSET1::iterator pp = m1.find(19);
	if(pp != m1.end())
		cout << "found" << endl;
	cout << "3)"; cout << *m1.lower_bound(22) << "," << *m1.upper_bound(22) << endl;
	pp = m1.erase(m1.lower_bound(22), m1.upper_bound(22));
	cout << "4)"; Print(m1.begin(), m1.end());
	cout << "5)"; cout << *pp << endl;
	MSET2 m2;
	m2.insert(a, a+SIZE);
	cout << "6)"; Print(m2.begin(), m2.end());
	return 0;
}

程序的输出结果是：

1)2

2)4 8 19 22 22 33 40

found

3)22,33

4)4 8 19 33 40

5)33

6)40 22 33 4 8 19

第 30 行，MSET2 类的排序规则和 MSET1 不同。MSET2 用 MyLess 定义排序规则，即 n 的个位数小的元素排在前面。

第 43、44 行，lower_bound 返回的迭代器指向第一个 22，upper_bound 返回的迭代器指向 33,。

第 45 行，删除所有值为 22 的元素。erase 成员函数删除一个元素后，返回下一个元素的迭代器应该是很合理的，但是 C++ 标准委员会认为，返回下一个元素的迭代器也是需要时间开销的，如果程序员不想要这个返回值，那么这个开销就是浪费的——因此在遵循 C++ 标准的 Dev C++ 中，本行无法编译通过。但是微软公司认为应该对这一点做出改进，因此 Visual Studio 2010 将 erase 成员函数处理成返回被删元素的下一个元素的迭代器。

不论在哪种编译器中，用 erase 成员函数删除迭代器 i 指向的元素后，迭代器 i 即告失效，此时不能指望 ++i 后 i 会指向被删除元素的下一个元素；相反，++i 可能立即导致出错。如果想要得到被删除元素后面那个元素的迭代器，可以在删除前获取其迭代器并保存起来（这同样适用于 set、map、multimap 的 erase 成员函数）。事实上，如果得到了某关联容器的迭代器，则该迭代器并不会因为容器中元素的插入以及其他元素的删除而失效。只要该迭代器指向的元素没有被删除，就可以一直使用它。

10.4.3 set

使用 set 必须包含头文件 set。set 的定义如下：

template <class Key, class Pred = less<Key>, class A = allocator<Key> >

class set { ... }

set 和 multiset 类似，它和 multiset 的差别在于 set 中不能有重复的元素。multiset 的成员函数 set 中也有。由于不能有重复元素，所以 set 中插入单个元素的 insert 成员函数与 multiset 中有所不同，其原型如下：

pair<iterator, bool> insert (const T & val);

如果 set 的 insert 成员函数的返回值是 pair 模板类对象 x，如果 x.second 为 true，则说明插入成功，此时 x.first 就是指向被插入元素的迭代器；如果 x.second 为 false，则说明要插入的元素已在容器中，此时 x.first 就是指向原有那个元素的迭代器。

关联容器的 equal_range 成员函数的返回值也是 pair 模板类对象，其原型如下：

pair<iterator, iterator> equal_range(const T & val);

返回值对象中的 first 就是lower_bound 的值，second 就是 upper_bound 的值。

下面的程序演示了 set 的用法。

#include <iostream>
#include <set>  //使用set须包含此文件
using namespace std;
int main()
{
	typedef set<int>::iterator IT;
	int a[5] = { 3,4,6,1,2 };
	set<int> st(a,a+5);    // st里是 1 2 3 4 6
	pair< IT,bool> result;
	result = st.insert(5); // st变成  1 2 3 4 5 6
	if(result.second)    //插入成功则输出被插入元素
		cout << * result.first  << " inserted" << endl; //输出: 5 inserted
	if(st.insert(5).second)
		cout << * result.first  << endl;
	else
		cout << * result.first << " already exists" << endl;
	//输出 5 already exists
	pair<IT,IT> bounds = st.equal_range(4);
	cout << * bounds.first << "," << * bounds.second ;  //输出：4,5
	return 0;
}

程序的输出结果是：

5 inserted

5 already exists

4,5

10.4.4 multimap

使用 multimap 必须包含头文件 map。multimap 的定义如下：

template<class Key, class T, class Pred = less<Key>, class A = allocator<Key> >

class multimap

{

...

typedef pair<const Key, T> value_type;

...

};

multimap 中的元素都是 pair 模板类的对象。元素的 first 成员变量也叫 “关键字”， second 成员变量也叫 “值”。multimap 容器中的元素是按关键字从小到大排序的。默认情况下，元素的关键字之间用 less<Key> 比较大小，也就是用 “<” 运算符比较大小。multimap 匀速多个元素的关键字相同。

multimap 中的 value_type 实际上就表示容器中元素的类型。C++ 允许在类的内部定义类型。

multimap 的成员函数（未列出每个函数的所有版本）如表 10.6 所示。

表10.6 multimap 的成员函数
成员函数或成员函数模板	作用
iterator find(const Key & val);	在容器中查找关键字等于 val 的元素，返回其迭代器；如果找不到，返回 end()
iterator insert(pair<Key, T> const & p);	将 pair 对象 p 插入容器中并返回其迭代器
void insert(iterator first, iterator last);	将区间 [first, last) 插入容器
int count(const Key & val);	统计有多少个元素的关键字和 val 相等
iterator lower_bound(const Key & val);	查找一个最大的位置 it，使得 [begin(), it) 中所有的元素的关键字都比 val 小
iterator upper_bound(const Key & val);	查找一个最小的位置 it，使得 [it, end() ) 中所有的元素的关键字都比 val 大
pair<iterator, iterator>equal_range (const Key & val);	同时求得 lower_bound 和 upper_bound
iterator erase(iterator it);	删除 it 指向的元素，返回其后面的元素的迭代器（Visual Studio 2010 中如此，但是在 C++ 标准和 Dev C++ 中，返回值不是这样的）
iterator erase(iterator first, iterator last);	删除区间 [first, last)，返回 last（Visual Studio 2010 中如此，但是在 C++ 标准和 Dev C++ 中，返回值不是这样的）

multimap 及 map 中的 find 和 count 不用 “==” 运算符比较两个关键字是否相等。如果 “x 比 y 小” 和 “y 比 x 小” 同时为假，就认为 x 和 y 相等。

例题：一个学生成绩录入和查询系统接受以下两种输入：

1) Add name id score

2) Query score

name 是一个字符串，其中不包含空格，表示学生姓名。id 是一个整数，表示学号。score 是一个整数，表示分数。学号不会重复，分数和姓名都可能重复。

两种输入交替出现。第一种输入表示要添加一个学生的信息，碰到这种输入，就记下学生的姓名、id 和分数。第二种输入表示要查询分数为 score 的学生的信息，碰到这种输入，就输出已有记录中分数比查询分数低的最高分获得者的姓名、学号和分数。如果有多个学生满足条件，则输出学号最大的学生的信息。如果找不到满足条件的学生，则输出 “Nobody”。

输入样例：

Add Jack 12 78

Query 78

Query 81

Add Percy 9 81

Add Marry 8 81

Query 82

Add Tom 11 79

Query 80

Query 81

输出结果样例：

Nobody

Jack 12 78

Percy 9 81

Tom 11 79

此题如果用 vector 存放所有学生的信息，然后进行顺序查找的话，在学生数量很大和查询很多的情况下非常费时，因为顺序查找的时间复杂度是 O(n)。将 vector 排序后在查找也不行，因为会不断插入新元素，每次插入新元素就要进行元素的移动，而这一步骤的时间复杂度是 O(n)，这会导致效率低下。

下面程序的思路是用 multimap 存放学生信息，使学生信息按照分数排序。要添加学生时，就用 insert 成员函数插入学生记录，这步操作的时间复杂度是 O(log(n) )。输入一个要查询的分数 score 时，就用 lower_bound 求得该分数对应的下界——迭代器 p（这一步的时间复杂度是 O(log(n) ) ）。*p 这个元素的分数是大于或等于 score 的，往前再找一个元素，其分数就是低于 score 的最高分了。继续往前遍历所有等于该分数的元素，找出 id 最大的元素输出即可。解题程序如下：

#include <iostream>
#include <map>
#include <string>
using namespace std;
class CStudent{
	public:
		struct CInfo{
			int id;
			string name;
		};
		int score;
		CInfo info;
};
typedef multimap<int, CStudent::CInfo> MAP_STD;
int main()
{
	MAP_STD mp;
	CStudent st;
	string cmd;
	while(cin >> cmd){
		if(cmd == "Add"){
			cin >> st.info.name >> st.info.id >> st.score;
			mp.insert(MAP_STD::value_type(st.score, st.info));
		}
		else if(cmd == "Query"){
			int score;
			cin >> score;
			MAP_STD::iterator p = mp.lower_bound(score);
			if(p != mp.begin()){
				--p;
				score = p->first;	//比要查询分数低的最高分
				MAP_STD::iterator maxp = p;
				int maxId = p->second.id;
				for(; p != mp.begin() && p->first == score; --p){
					//遍历所有成绩和 score 相同的学生
					if(p->second.id > maxId){
						maxp = p;
						maxId = p->second.id;
					}
				}
				if(p->first == score){	//如果上面的循环因为 p == mp.begin()
										//而终止，则 p 指向的元素还要处理
					if(p->second.id > maxId){
						maxp = p;
						maxId = p->second.id;
					}
				}
				cout << maxp->second.name << " " << maxp->second.id <<" "
					 << maxp->first << endl;
			}
			else	//lower_bound 的结果就是 begin，说明没有分数比查询分数低
				cout << "Nobody" << endl;
		}
	}
	return 0;
}

multimap 容器中的元素必须是 pair 类模板对象。本体需要用 multimap 来存放学生信息，然而学生信息由三部分组成：姓名、学号、分数，解决的办法就是将用于排序的 score 作为一个成员变量，而且把其他部分一起作为一个 CInfo 对象，这样，第 16 行实例化出来的类 multimap<int, CStudent::CInfo> 中的元素就会是如下 pair 类模板：

class pair<int, CStudent::CInfo?

{

int first;

CStudent::CInfo second;

};

第 26 行如下：

mp.insert（MAP_STD::value_type(st.name, st.info）);

参考 multimap 的定义，MAP_STD::value_type 就是容器中元素的类型，该类型是 pair<int, CStudent::CInfo>。类型名后面跟构造函数的参数表就代表一个对象。因此，此条语句生成了一个 pair<int, CStudent::CInfo> 对象并将其插入 multimap 容器中。该对象内部存放的信息和 st 相同，first 对应于 st.score，second 对应于 st.info。（关于 “value_type” 详细可参考：C++ 10.3 关联容器map定义以及value_type、key_type、mapped_type_c++ value_type_普通网友的博客-程序员宅基地）

第 31 行，lower_bound 的返回结果 p 满足以下条件：[begin(), p) 中的分数都比查询分数低，但是 *p 的分数不比查询分数低。所以执行 - - p 操作之后，*p 的分数就是低于查询分数的最高分了。

10.4.5 map

要使用 map，必须包含头文件 mao。map 的定义如下：

template<class Key, class T, class Pred = less<Key>, class A = allocator<T> >

class map{

...

typedef pair<const Key, T> value_type;

...

};

map 和 multimap 十分类似，区别在于 map 容器中的元素的关键字不能重复。multimap 有的成员函数，map 都有。此外，map 还有成员函数 operator[ ]：

T & operator[ ] (Key k);

该成员函数返回 first 值为 k 的元素的 second 部分的引用。如果容器中没有元素的 first 值等于 k，则自动添加一个 first 值为 k 的元素。如果该元素的 second 成员变量是一个对象，则用无参构造函数对其初始化。

下面的程序演示了 map 的用法。

#include <iostream>
#include <map>  //使用map需要包含此头文件
using namespace std;
template <class T1,class T2>
ostream & operator <<(ostream & o,const pair<T1,T2> & p)
{ //将pair对象输出为 (first,second)形式
	o << "(" << p.first  << "," << p.second << ")";
	return o;
}
template<class T>
void Print(T first,T last)
{//打印区间[first,last)
	for( ; first != last; ++ first)
		cout <<  * first << " ";
	cout << endl;
}
typedef map<int,double,greater<int> > MYMAP; //此容器关键字是整型，
                                            //元素按关键字从大到小排序
int main()
{
	MYMAP mp;
	mp.insert(MYMAP::value_type(15,2.7));
	pair<MYMAP::iterator,bool> p = mp.insert(make_pair(15,99.3));
	if(!p.second)
		cout << * (p.first) << " already exists" << endl; //会输出
	cout << "1) " << mp.count(15) << endl; //输出 1) 1
	mp.insert(make_pair(20,9.3));
	cout << "2) " << mp[40] << endl;//如果没有关键字为40的元素，则插入一个
	cout << "3) ";Print(mp.begin(),mp.end());//输出：3) (40,0)(20,9.3)(15,2.7)
	mp[15] = 6.28; //把关键字为15的元素值改成6.28
	mp[17] = 3.14; //插入关键字为17的元素，并将其值设为3.14
	cout << "4) ";Print(mp.begin(),mp.end());
	return 0;
}

程序的输出结果如下：

(15,2.7) already exists

1) 1

2) 0

3) (40,0) (20,9.3) (15,2.7)

4) (40,0) (20,9.3) (17,3.14) (15,6.28)

第 17 行的 “greater<int> >” 最右边的两个 “>” 之间要有空格，否则 Dev C++ 会将它们当做右移运算符，导致编译出错。在 Visual Studio 2010 中无此问题。

第 22 行用 STL 中的函数模板 make_pair 生成一个 pair 模板类对象插入 mp 中。

第 23 行，如果插入成功，p.second 的值会是 true。显然这里不能成功，因为 map 不允许关键字重复。因为关键字重复而插入失败时，p.first 就指向容器中关键字相同的那个元素。

第 27 行要访问关键字为 40 的元素。在没有这个元素的情况下，一个关键字为 40、值为 0 的元素被自动插入容器。mp[40] 等价于 “mp.operator[ ](40);”，其返回值是关键字为 40 的那个元素（不论是原有的还是新插入的）的 second 成员变量的引用。第 29 行和第 30 行的道理与此类似。

10.5 容器适配器

STL 中的容器适配器有 stack、queue、priority_queue 三种。它们都是在顺序容器的基础上实现的，屏蔽了顺序容器的一部分功能，突出或增加了另外一些功能。容器适配器都有以下三个成员函数：
push：添加一个元素。

top：返回顶部（对 stack 而言）或队头（对 queue、priority_queue 而言）的元素的引用。

pop：删除一个元素。

容器适配器是没有迭代器的，因此 STL 中的各种排序、查找、变序等算法都不适用于容器适配器。

10.5.1 stack

要使用 stack，必须包含头文件 stack。stack 就是 “栈”。栈是一种后进先出的元素序列，访问和删除都只能对栈顶的元素（即最后一个被加入栈的元素）进行，并且元素也只能被添加到栈顶。栈内的元素不能访问。如果一定要访问栈内元素，只能将其上方的元素全部从栈中删除，使之变成栈顶元素才可以。

stack 的定义如下：

template<class T, Cont = deque<T> >

class stack{

...

};

第二个参数表明，在默认情况下，stack 就是用 deque 实现的。当然们也可以指定用 vector 或 list 实现。虽然 stack 使用顺序容器实现，但它不能提供顺序容器具有的成员函数。除了 size、empty 这两个所有容器都有的成员函数外，stack 还有以下三个成员函数，如表 10.7 所示。

表10.7 stack 的成员函数
成员函数	功能
void pop();	弹出（即删除）栈顶元素
T & top();	返回栈顶元素的引用。通过此函数可以读取栈顶元素的值，也可以修改栈顶元素
void push(const T & x);	将 x 压入栈顶

例题：编写程序，输入一个十进制数 n 和进制 k（k <= 10），输出 n 对应的 k 进制数。

#include <iostream>
#include <stack>
using namespace std;
int main()
{
	int n, k;
	stack<int> stk;
	cin >> n >> k;
	if(n == 0){
		cout << 0;
		return 0;
	}
	while(n){
		stk.push(n % k);
		n /= k;
	}
	while(!stk.empty()){
		cout << stk.top();
		stk.pop();
	}
	return 0;
}

10.5.2 queue

要使用 queue，必须包含头文件 queue。queue 就是 “队列”。队列是先进先出的，和排队类似。队头的访问和删除操作只能在队头进行，添加操作只能在队尾进行。不能访问队列中间的元素。queue 可以用 list 和 deque 实现，默认情况下用 deque 实现。queue 的定义如下：

template<class T, Cont = deque<T> >

class queue{

...

};

queue 同样也有和 stack 类似的 push、pop、top 函数。区别在于，queue 的 push 发生在队尾，pop 和 top 发生在队头。

10.5.3 priority_queue

使用 priority_queue，必须包含头文件 queue。priority_queue是 “优先队列”。它和普通队列的区别在于，优先队列的UI头元素总是最大的——即执行 pop 操作时，删除的总是最大的元素；执行 top 操作时，返回的是最大元素的引用。priority_queue 可以用 vector 和 deque 实现，默认情况下用 vector 实现，priority_queue 默认的元素比较器是 less<T>。也就是说，在默认情况下，要放入 priority_queue 的元素必须是能用 “<” 运算符进行比较的，而且 priority_queue 保证以下条件总是成立：对于队头的元素 x 和任意非队头的元素 y，表达式 “x < y” 必为 false。

priority_queue 定义如下：

template<class T, Container = vector<T>, class Compare = less<T> >

class priority_queue{

...

};

priority_queue 的第三个类型参数可以用来指定排序规则。

和 set / multiset 不同，priority_queue 是使用 “堆排序” 技术实现的，其内部并非完全有序，但却能确保最大元素总在队头。因此，priority_queue 特别适用于 “不停地在一堆元素中取走最大的元素” 这种情况。priority_queue 插入和删除元素的复杂度都是 O(log(n))。虽然用 set / multiset 也能完成此项工作，但是 priority_queue 比它们略快一些。

priority_queue 队头的元素只能被查看或者修改，不能被删除。

priority_queue 的用法示例如下。

#include <queue>
#include <iostream>
using namespace std;
int main()
{
	priority_queue<double> pq1;
	pq1.push(3.2); pq1.push(9.8); pq1.push(9.8); pq1.push(5.4);
	while(!pq1.empty()) {
		cout << pq1.top() << " ";
		pq1.pop();
	} //上面输出 9.8 9.8 5.4 3.2
	cout << endl;
	priority_queue<double,vector<double>,greater<double> > pq2;
	pq2.push(3.2); pq2.push(9.8); pq2.push(9.8); pq2.push(5.4);
	while(!pq2.empty()) {
		cout << pq2.top() << " ";
		pq2.pop();
	}
	//上面输出 3.2 5.4 9.8 9.8
	return 0;
}

程序的输出结果是：

9.8 9.8 5.4 3.2

3.2 5.4 9.8 9.8

pq2 的排序规则和 pq1 相反，因此元素出队的顺序也相反。

10.6 STL 算法分类

在 STL 中，算法就是函数模板。STL 中的算法大多数是用来对容器进行操作的，如排序、查找等。大部分算法都是在头文件 algorithm 中定义的，还有些算法用于数值处理，定义在头文件 numeric 中。

不同的书籍对 STL 中的算法有不同的分类方法。本书将算法分为以下七类：

（1）不变序列算法。

（2）变值算法。

（3）删除算法。

（4）变序算法。

（5）排序算法。

（6）有序区间算法。

（7）数值算法。

本书介绍前六类算法。第七类算法共有三个，除了前面已经介绍过的 accumulate 以外，另外两个算法既不常用，讲解起来有比较繁琐，本书就不介绍了，有需要的读者可自行查阅相关资料。（可参考：c++数值算法_fkvnin的博客-程序员宅基地）

许多算法都是重载的，有不止一个版本。篇幅所限，本书往往只能列出其中一个版本。有些算法也不给出原型，直接通过程序来演示其用法。

实际上，大多数重载的算法都有两个版本，其中一个用 “==” 判断元素是否相等，或用 “<” 比较大小；而另一个版本多出来一个类型参数 Pred 以及函数形参 Pred op，该版本通过表达式 “op(x, y)” 的返回值是 true 还是 false 来判断 x 是否 “等于” y 或者 “小于” y。例如，10.3.3 节 “函数对象应用实例 2” 中提到的 sort，再如下面有两个版本的 min_element：

iterator min_element(iterator first, iterator last);

iterator min_element(iterator first, iterator last, Pred op);

min_element 返回区间中最小的元素。第一个版本用 “<” 比较大小，而第二个版本用自定义的比较器 op 来比较大小，op(x, y) 的值为 true，则说明 x 比 y 小。

类似 sort 和 min_element 这样有可自定义比较器版本的算法，在后文的表格中列出时，将加注 “（可自定义比较器）”

10.7 不变序列算法

此类算法不会修改算法所作用的容器或对象，适用于所有容器。它们的时间复杂度都是 O(n)的。表 10.8 列出了此类算法。

表10.8 不变序列算法
算法名称	功能
min	求两个对象中较小的（可自定义比较器）
max	求两个对象中较大的（可自定义比较器）
min_element	求区间中的最小值（可自定义比较器）
max_element	求区间中的最大值（可自定义比较器）
for_each	对区间中的每个元素都做某种操作
count	计算区间中等于某值的元素个数
count_if	计算区间中符合某种条件的元素个数
find	在区间中查找等于某值的元素
find_if	在区间中查找符合某条件的元素
find_end	在区间中查找另一个区间最后一次出现的位置（可自定义比较器）
find_first_of	在区间中查找第一个出现在另一个区间中的元素（可自定义比较器）
adjacent_find	在区间中寻找第一次出现连续两个相等元素的位置（可自定义比较器）
search	在区间中查找另一个区间第一次出现的位置（可自定义比较器）
search_n	在区间中查找第一次出现等于某值的连续 n 个元素（可自定义比较器）
equal	判断两区间是否相等（可自定义比较器）
mismatch	逐个比较两个区间的元素，返回第一次发生不相等的两个元素的位置（可自定义比较器）
lexicographical_compare	按字典序比较两个区间的大小（可自定义比较器）

上述算法的原型如下（未列出所有版本，本书后面也一样）。

min

原型：const T & min(const T & x, const T & y);

功能：返回 x，y 中较小的元素。

max

原型：const T & max(const T & x, const T & y);

功能：返回 x，y 中较大的元素。

min_element

原型：iterator min_element(iterator first, iterator last);

功能：返回 [first, last) 中最小元素的迭代器。

max_element

原型：iterator max_element(iterator first, iterator last);

功能：返回 [first, last) 中最大元素的迭代器。

for_each

原型：Pred for_each(iterator first, iterator last);

功能：对区间 [first, last) 中的每个元素 x 都执行 op(x)。

count

原型：int count(iterator first, iterator last, const T & val);

功能：计算区间 [first, last) 中等于 val 的元素个数。

count_if

原型：count_if(iterator first, iterator last, Pred op);

功能：计算区间 [first, last) 中使得 op(x) 为 true 的 x 的个数。

find

原型：iterator find(iterator first, iterator last, const T & val);

功能：返回 [first, last) 中等于 val 的元素的迭代器。

find_if

原型：iterator find_if(iterator first, iterator last, Pred op);

功能：返回 [first, last) 中使得 op(x) 为 true 的元素 x 的迭代器。

find_end

原型：iterator find_end(iterator firs1t, iterator last1, iterator first2, iterator last2);

功能：返回 [first1, last1) 中最后出现序列 [first2, last2) 的位置。

find_first_of

原型：iterator find_first_of(iterator first1, iterator last1, iterator first2, iterator last2);

功能：返回 [first2, last2) 中的元素（随便哪个都行）在 [first1, last1) 中最早出现的位置。

adjacent_find

原型：iterator adjacent_find(iterator first, iterator last);

功能：返回最先出现连续两个元素相等的位置。

search

原型：iterator search(iterator first1, iterator last1, iterator first2, iterator last2);

功能：返回 [first1, last1) 中第一次出现 [first2, last2) 的位置。

search_n

原型：iterator search_n(iterator first, iterator last, T1 count, const T2 & val);

功能：返回 [first, last) 中最早出现的连续 count 个 val 的位置。

equal

原型：bool equal(iterator first1, iterator last1, iterator first2);

功能：判断 [first, last) 是否和以 first2 为起点的等长区间中的每个元素都相等。

mismatch

原型：pair<iterator, iterator> mismatch(iterator first1, iterator last1, iterator first2);

功能：逐个比较 [first1, last1) 和以 first2 为起点的等长区间中的元素，返回第一次发生不相等时的两个元素的迭代器。

lexicographical_compare

原型：bool lexicographical_compare(iterator first1, iterator last1, iterator first2, iterator last2);

功能：按字典序比较法比较区间 [first1, last1) 和 [first2, last2)，如果前者更小，则返回 true，否则返回 false。

下面的程序演示了上面所列算法的应用。

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
using namespace std;
void Print(int v)
{
	cout << "<" << v << ">";
}
bool LessThen4(int n)
{
	return n < 4;
}
int main()
{
	cout << "1)" << min(3, 4) << "," << max(2.5, 8.3) << endl;
	int a[9] = {1,2,3,4,5,3,4,4,4};
	cout << "2)" << *min_element(a, a+9) << "," << *max_element(a, a+9) << endl;
	cout << "3)" << count(a, a+9, 4) << endl;
	cout << "4)" << count_if(a, a+9, LessThen4) << endl;
	list<int> lst(a, a+9);
	int b[2] = {4, 3};
	vector<int> v(b, b+2);
	list<int>::iterator p;
	p = find_first_of(lst.begin(), lst.end(), b, b+2);			//找 4，3 中任意一元素
	cout << "5)" << distance(lst.begin(), p) << endl;
	reverse(v.begin(), v.end());								//算法 reverse 能前后颠倒区间
	int* ptr = find_end(a, a+9, v.begin(), v.end());			//找序列 "3 4" 在数组 a 中最后出现的位置
	cout << "6)" << distance(a, ptr) << endl;
	p = adjacent_find(lst.begin(), lst.end());					//找 lst 中连续两个相同的元素
	cout << "7)" << *p << "," << distance(lst.begin(), p) << endl;
	p = search(lst.begin(), lst.end(), v.begin(), v.end());		//找序列 "3 4"
	cout << "8)" << distance(lst.begin(), p) << endl;
	ptr = search_n(a, a+9, 2, 4);								//找连续两个 4 出现的位置
	cout << "9)" << distance(a, ptr) << endl;
	cout << boolalpha;											//将 true，false 以字符串形式出书
	cout << "10)" << equal(v.begin(), v.end(), a+2) << endl;	//比较 v 和 a+2 开始的两个元素，相等
	int c[6] = {1,2,3,9,7,8};
	pair<int*, int*> result;
	result = mismatch(c, c+6, a);
	cout << "11)" << *result.first << "," << *result.second << endl;
	cout << "12)" << lexicographical_compare(a, a+9, c, c+6) << endl;
	for_each(a, a+3, Print);	//以 [a, a+3) 中的每个元素为参数，调用 Print，输出 < 1 > < 2 > < 3 >
	return 0;
}

程序的输出结果是：

1)3,8.3

2)1,5

3)4

4)4

5)2

6)5

7)4,6

8)2

9)6

10)true

11)9,4

12)true

<1><2><3>

第 27 行，在 lst 中寻找 4,3 这两个元素任意一个最早出现的位置，结果是 p 指向找到的元素 3。第 28 行输出了 p 到 lst.begin() 的距离2.

第 30 行，查找序列 “3 4” 在数组 a 中最后出现的位置。

第 44 行，逐个比较 [c, c+6) 和 [a, a+6)，比到下标为 3 的元素时，c 中是9，a 中是 4，不相等。result.first 就是指向 9 的迭代器，result.second 就是指向 4 的迭代器。

10.8 变值算法

此类算法会修改元区间或目标区间中元素的值。值被修改的区间不应该属于关联容器，否则会破坏关联容器的有序性。此类算法如表 10.9 所示。

表10.9 变值算法
算法名称	功能
for_each	对区间中的每个元素都做某种操作
copy	复制一个区间到别处
copy_backward	复制一个区间到别处，但目标区间是从后往前被修改的
transform	讲一个区间的元素变形后复制到另一个区间
swap_ranges	交换两个区间的内容
fill	用某个值填充区间
fill_n	用某个值替换区间中的 n 个元素
generate	用某个操作的结果填充区间
generate_n	用某个操作的结果填充区间中的 n 个元素
replace	将区间中的某个值替换为另一个值
replace_if	将区间中符合某种条件的值替换成另一个值
replace_copy	将一个区间复制到另一个区间，复制时某个值要换成新值
replace_copy_if	讲一个区间复制到另一个区间，复制时符合某条件的值要换成新值

上述算法的原型如下（没有列出所有版本）。对于返回值一般没用的算法，不再交代其返回值。

for_each

原型：for_each(iterator first, iterator last, Pred op);

功能：对区间 [first, last) 中的每个元素 x 都执行 op(x)。此算法可以是不变序列算法，也可是变值算法，取决于调用时的 op 是什么样子的。如果 op 的参数是传引用的，则 for_each 可能会修改区间中元素的值。

copy

原型：iterator copy(iterator first, iterator last, iterator dest);

功能：将 [first, last) 复制到从 dest 开始的地方。程序员要确保从 dest 开始有足够的空间存放复制过来的元素。返回值是迭代器 dest + (last - first)。注意，dest + (last - first) 的写法只是为了便于说明返回值到底指向哪里，并不意味着 copy 算法要求迭代器必须是支持 “+” “ - ” 操作的随机访问迭代器（下同）。

copy_backward

原型：iterator copy_backward(iterator first, iterator last, iterator dest);

功能：将 [first, last) 复制到 [dest - (last - first), dest)。程序员要确保从 dest 开始有足够的空间存放复制过来的元素。复制从后往前进行。此算法主要是为了弥补 copy 算法的不足。copy 算法是从前往后复制的，如果源区间和目标区间发生了重叠，且 dest 位于 [first, last) 区间之中，则从前往后复制会导致结果不正确，copy_backward 从后往前复制可以解决这个问题，返回值是迭代器 dest - (last - first)。

transform

原型：transform(iterator first, iterator last, iterator dest, Pred op);

功能：对于 [first, last) 中的每个元素 x，将 op(x) 的返回值放入从 dest 开始的地方。程序员要确保从 dest 开始有足够的空间存放元素。

swap_ranges

原型：swap_ranges(iterator first1, iterator last1, iterator first2);

功能：交换 [first1, last1) 和从 first2 开始的等长区间的内容。

fill

原型：void fill(iterator first, iterator last, count T & val);

功能：用 val 填充区间 [first, last)。

fill_n

原型：fill_n(iterator first, Diff cound, count T & val);

功能：用 val 替换从 first 开始的 count 个元素。

generate

原型：void generate(iterator first, iterator last, Pred op);

功能：用 op() 的返回值填充 [first, last)。

generate_n

原型：generate_n(iterator first, Diff count, Pred op);

功能：用 op() 的返回值替换从 first 开始的 count 个元素。

replace

原型：void replace(iterator first, iterator last, const T & oldVal, const T & newVal);

功能：用 newVal 替换区间 [first, last) 中的 oldVal。

replace_if

原型：void replace_if(iterator first, iterator last, Pred op, const T & val);

功能：对于区间 [first, last) 中使得 op(x) 为 true 的每个 x，用 val 进行替换。

replace_copy

原型：replace_copy(iterator first, iterator last, iteartor dest, const T & oldVal. const T & newVal);

功能：将区间 [first, last) 复制到从 dest 开始的地方。复制过程中，若碰到源区间中的 oldVal，则不复制 oldVal，而是将 newVal 复制到目标区间。程序员要确保从 dest 开始有足够的空间存放复制过来的元素。

replace_copy_if

原型：replace_copy_if(iterator first, iterator last, iterator dest, Pred op, const T & newVal);

功能：将区间 [first, last) 复制到从 dest 开始的地方。复制过程中，若碰到源区间中的 x，使得 op(x) 为 true，则不复制 x，而将 newVal 复制到目标区间。程序员要确保从 dest 开始有足够的空间存放复制过来的元素。

上面这些算法，涉及一个区间的，时间复杂度都是 O(n)。如果涉及两个区间，假设一个区间长 m，一个区间长 n，则时间复杂度是 O(n+m)。下面的程序演示了上面所列算法的应用。

#include <iostream>
#include <iterator>  //使用ostream_iterator需要包含此文件
#include <list>
#include <algorithm>
using namespace std;
void Modify(int & lst) { lst *= lst; }
int Square(int n) { return n * n; }
int Zero() { return 0; }
int One() { return 1; }
bool Even(int n) { return !(n % 2); } //判断n是否是偶数
int main()
{
	int a[6] = { 1,2,3,4,5,6};
	int b[6];
	copy(a,a+6,b);
	ostream_iterator<int> oit(cout,",");//定义用于输出的迭代器
	cout << "1) "; copy(b,b+6,oit); cout << endl;
		//输出 1) 1,2,3,4,5,6,
	copy_backward(b,b+4,b+5); //拷贝[b,b+4)到[b+1,b+5)
	cout << "2) "; copy(b,b+6,oit); cout << endl;
		//输出 2) 1,1,2,3,4,6,
	list<int> lst(5); //lst要有足够空间以支持后面的拷贝
	transform(a,a+5,lst.begin(),Square);
		//将a中元素的平方拷贝到lst，a中的元素不会改变
	cout << "3) "; copy(lst.begin(),lst.end(),oit); cout << endl;
		//输出 3) 1,4,9,16,25,
	cout << "4) "; copy(a,a+6,oit); cout << endl;
		//输出4) 1,2,3,4,5,6, 说明a中元素没变
	swap_ranges(lst.begin(),lst.end(),b);//交换lst和b的内容
	cout << "5) ";copy(lst.begin(),lst.end(),oit); cout << endl;
		//输出 5) 1,1,2,3,4,
	fill(b,b+6,0); //b变成 0 0 0 0 0 0
	fill_n(b+2,3,1); //b变成 0 0 1 1 1 0
	cout << "6) ";copy(b,b+6,oit); cout << endl;
		//输出 6) 0,0,1,1,1,0,
	copy(a,a+6,b); //b 变成 1 2 3 4 5 6
	generate(b,b+6,Zero); //b变成 0 0 0 0 0 0
	generate_n(b+1,3,One); //b变成 0 1 1 1 0 0
	cout << "7) "; copy(b,b+6,oit); cout << endl;
		//输出 7) 0,1,1,1,0,0,
	replace(b,b+6,1,3); //将b中的1都替换成3
	cout << "8) "; copy(b,b+6,oit); cout << endl;
		//输出 8) 0,3,3,3,0,0,
	replace_if(b,b+6,Even,11); //将b中的偶数都替换成11
	cout << "9) "; copy(b,b+6,oit); cout << endl;
		//输出 9) 11,3,3,3,11,11,
	replace_copy(a,a+6,b,3,30);
		//拷贝a到b,但是拷贝过程中会将3替换成30,a不变
	cout << "10) "; copy(b,b+6,oit); cout << endl;
		//输出 10) 1,2,30,4,5,6,
	replace_copy_if(a,a+6,b,Even,7);
		//拷贝a到b,但是拷贝过程中偶数都被替换成7，a不变
	cout << "11) "; copy(b,b+6,oit); cout << endl;
		//输出 11) 1,7,3,7,5,7,
	return 0;
}

程序的输出结果是：

1) 1,2,3,4,5,6,

2) 1,1,2,3,4,6,

3) 1,4,9,16,25,

4) 1,2,3,4,5,6,

5) 1,1,2,3,4,

6) 0,0,1,1,1,0,

7) 0,1,1,1,0,0,

8) 0,3,3,3,0,0,

9) 11,3,3,3,11,11,

10) 1,2,30,4,5,6,

11) 1,7,3,7,5,7,

第 16 行用到了 STL 中的一个类模板 ostream_iterator。此类模板的对象可以与 copy 算法一起使用，用于输出容器的内容。“ostream_iterator<int>oit(cout, ",")” 表示要交给 oit 输出的每一项都是 int 类型，这些项最终交给 cout 输出，输出两项之间用 “,” 分隔。因此，第 17 行的 “copy(b, b+6, oit)” 就会输出 “1,2,3,4,5,6”。copy 算法的功能本来是将一个区间复制到另一个区间，此处为什么能完成输出的功能呢，取决于程序员如何使用这些模板和程序员的想象力。这一点稍后还会解释。

第 19 行要复制 [b, b+4) 到 [b+1, b+5)，源区间和目标区间有重叠，如果用 copy 算法进行从前到后的复制，结果肯定不正确，因为 *(b+1) 的值还没有被复制到后面，就已经被 *b 覆盖了。因此要用 copy_backward 算法从后往前复制，*(b+3) 先被复制到 *(b+4)，然后 *(b+2) 被复制到 *(b+3)……最后 *b 被复制到 *(b+1)。

第 22 行，要先为 lst 分配足够的空间，否则第 23 行的复制操作执行时会出错。

ostream_iterator 是在头文件 iterator 中定义的一个类模板。为什么 copy 和 ostream_iterator 模板类对象一起使用就能够输出容器的内容呢？要弄清楚这个问题，最好的办法莫过于自己编写一个类似于 ostream_iterator 的类模板，不妨命名为 My_ostream_iterator，使得下面的程序能够向屏幕和 test.txt 文件都输出 “1* 2* 3* 4”。程序代码如下：

#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <iterator>
using namespace std;
int main()
{
	int a[4] = {1,2,3,4};
	My_ostream_iterator<int>oit(cout, "* ");
	copy(a, a+4, oit);
	ostream oFile("test.txt", ios::out);
	My_ostream_iterator<int>oitf(oFile, "* ");
	copy(a, a+4, oitf);
	oFile.close();
	return 0;
}

要写出 My_ostream_iterator，先要知道 copy 的工作原理。copy 的源代码如下：

template<class _II, class _OI>_Oi copy(_II _F, _II _L, _OI _X)

{

for(; _F != _L; ++_X, ++_F)

*_X = *_F;

return (_X);

}

因此，上面程序中的调用语句 “copy(a, a+4, oit)” 实例化后得到的 copy 如下：

My_ostream_iterator copy(int* _F, int* _L, My_ostream_iterator _X)

{

for(; _F != _L; ++_X, ++_F)

*_X = *_F;

return (_X);

}

要使得实例化后得到的 copy 编译不出错，++_X、*_X 和 *_X = *_F 都必须有定义。而 _X 是 My_ostream_iterator对象，因此 My_ostream_iterator 类应该重载 “++” 和 “*” 运算符，“=” 运算符也应该被重载。要输出的元素是 *_F。因此输出工作应该是在被重载的 “=” 运算符中进行的。再根据定义 oit 时的构造函数，分析出 My_ostream_iterator 可以如下编写：

template<class T>
class My_ostream_iterator{
	private:
		string sep;		//分隔符
		ostream & os;
	public:
		My_ostream_iterator(ostream & o, string s):sep(s), os(o) { }
		void operator ++ () { }		//++ 只需要有定义即可，不需要执行具体操作
		My_ostream_iterator & operator * ()
		{return *this;}
		My_ostream_iterator & operator = (const T & val)
		{os << val << sep;	return *this;}
};

前面的 copy 的源代码来自 Dev C++，是符合 C++ 标准的。在 Vistual Studio 中，copy 的写法略有不同，因此 My_ostream_iterator 也要做如下修改。不过，对此可以不必深究。

                template<class T, class T2 = void>
                class My_ostream_iterator:public iterator<T2, T>{
...
                };

“{ }” 中的代码不变。

从上面的例子可以看到，运算符重载的作用决不仅仅是方便使用和符合习惯。运算符重载是 STL 的基础。由此还能看到，C++ 有强大的扩展能力。要成为高级的 C++ 程序员，对 STL 中模板的具体实现也需要有所了解，这样才能写出富有想象力的程序。

（关于输入输出迭代器，可参考：C++输入输出迭代器_乌鸦_在飞的博客-程序员宅基地）

10.9 删除算法

删除算法会删除一个容器中的某些元素。这里所说的 “删除” 并不会使容器中的元素减少，其工作过程是：将所有应该被删除的元素看做空位，将剩余的元素从后往前移动，依次去填充这些空位。元素向前移动后，它原来的位置也成为空位，也应由后面剩余的元素来填充。最后，没有被填充的空位维持其原来的值不变。删除算法不应作用于关联容器。下面以 remove 为例说明删除算法的工作原理：

remove

原型：iterator remove(iterator first, iterator last, const T & val);

功能：删除 [first, last) 中等于 val 的元素。返回值是一个迭代器。如果有 n 个元素被删除，则返回值就是 last - n。示例程序如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
int main()
{
	int a[5] = {1,2,3,2,5};
	int b[6] = {1,2,3,2,5,6};
	ostream_iterator<int>oit(cout,",");
	int* p = remove(a, a+5, 2);
	cout << "1)"; copy(a, a+5, oit); cout << endl;
	cout << "2)" << p-a << endl;
	vector<int> v(b, b+6);
	remove(v.begin(), v.end(), 2);
	cout << "3)"; copy(v.begin(), v.end(), oit); cout << endl;
	cout << "4)"; cout << v.size() << endl;		//v 中的元素没有减少
	return 0;
}

程序的输出结果是：

1)1,3,5,2,5,

2)3

3)1,3,5,6,5,6,

4)6

第 11 行，在 [a, a+5) 中删除 2 的过程如下（加括号的数字代表 “空位”）：

（1）标出空位：1（2）3（2）5。

（2）3 向前移动，填充第一个空位，3 原来的位置成为空位。区间变为：1 3（3) (2） 5。

（3）5 向前移动，填充新的第一个空位，5 原来的位置成为空位。区间变为：1 3 5 (2) (5)。

（4）剩下的两个空位没有元素可以移过来填充，则维持原来的值，删除结束。最终区间变为：1 3 5 2 5.

自行分析第 15 行 remove 的工作过程。

表 10.10 列出了删除算法，此类算法的复杂度都是 O(n)。。

表10.10 删除算法
算法	功能
remove	删除区间中等于某个值的元素
remove_if	删除区间中满足某种条件的元素
remove_copy	复制区间到另一个区间，等于某个值的元素不复制
remove_copy_if	复制区间到另一个区间，符合某种条件的元素不复制
unique	删除区间中连续相等的元素，只留下一个（可自定义比较器）
unique_copy	复制区间到领一个区间。连续相等的元素，只复制第一个到目标区间（可自定义比较器）

上述算法的原型如下：

remove_if

原型：iterator remove_if(iterator first, iterator last, Pred op);

功能：删除 [first, last) 中所有使得 op(x) 为真的 x。如果有 n 个元素被删除，则返回值就是 last -n。

remove_copy

原型：iterator remove_copy(iterator first, iterator last, iterator dest, const T & val);

功能：将 [first, last) 复制到 dest 开始的地方，等于 val 的元素不复制。程序员要确保从 dest 开始有足够的空间存放复制过来的元素。假设有 n 个元素被复制，返回值就是迭代器 dest +n。

remove_copy_if

原型：iterator remove_copy(iterator first, iterator last, iterator dest, Pred op);

功能：将 [first, last) 复制到 dest 开始的地方，使得 op(x) 为真的元素 x 不复制。程序员要确保从 dest 开始有足够的空间存放复制过来的元素。假设有 n 个元素被复制，返回值就是迭代器 dest +n。

unique

原型：iterator unique(iterator first, iterator last);

功能：对 [first, last) 中连续相等的元素，只留下第一个，删除其他元素。如果删除了 n 个元素，返回值就是迭代器 last - n。

unique_copy

原型：iterator unique_copy(iterator first, iterator last, iterator dest);

功能：将 [first, last) 复制到 dest 开始的地方，对 [first, last) 中连续相等的元素，只复制第一个到目标区间。程序员要确保从 dest 开始有足够的空间存放复制过来的元素。假设有 n 个元素被复制，返回值就是迭代器 dest +n。

下面的程序演示了删除算法的应用。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring> // memset函数在此声明
#include <iterator>
using namespace std;
bool LessThan4( int n) { return n < 4; }
int main()
{
	int a[5] = { 1,2,3,2,5};
	int b[6] = { 1,2,5,2,5,6};
	int c[6] = { 0,0,0,0,0,0};
	ostream_iterator<int> oit(cout,",");
	remove_if(b,b+6,LessThan4);//删除小于4的元素
	cout << "1) "; copy(b,b+6,oit); cout << endl; 	//输出 1) 5,5,6,2,5,6,
	int * p = remove_copy(a,a+5,c,2); //等于2的元素不拷贝
	cout << "2) " << p - c << endl; 		         //输出 2) 3
	cout << "3) "; copy(c,c+6,oit); cout << endl; //输出 3) 1,3,5,0,0,0,
	cout << "4) "; copy(a,a+5,oit); cout << endl; //输出 4) 1,2,3,2,5,
	                                              //说明remove_copy不改变源区间
	memset(c,0,sizeof(c)); //把 c 置为全0
	remove_copy_if(a,a+5,c,LessThan4); //小于4的元素不拷贝
	cout << "5) "; copy(c,c+6,oit); cout << endl; //输出 5) 5,0,0,0,0,0
	int d[7] = { 1,2,2,2,3,3,4 };
	vector<int> v;
	v.insert(v.begin(),d,d+7);
	unique(d,d+7);
	cout << "6) "; copy(d,d+7,oit); cout << endl;	
	//输出 6) 1,2,3,4,3,3,4,
	memset(d,0,sizeof(d));
	unique_copy(v.begin(),v.end(),d);
	cout << "7) ";copy( d,d+7,oit);		        //输出 7) 1,2,3,4,0,0,0,
	return 0;
}

第 14 行的执行过程如下（开始时 b 是 1 2 5 2 5 6）：

（1）把该删除的元素标记为空位：(1) (2) 5 (2) 5 6。

（2）第一个 5 填充空位：5 (2) (5) (2) 5 6。

（3）第二个 5 填充空位：5 5 (5) (2) (5) 6。

（4）6 填充空位：5 5 (5) (2) (5) 6。

（5）后面的空位没有元素可以填充，维持原来的值，最终结果是：5 5 6 2 5 6。

第 31 行的执行过程如下（开始 d 是 1 2 2 2 3 3 4）

（1）把该删除的元素标记为空位：1 2 (2) (2) 3 (3) 4。

（2）3 填充空位：1 2 3 (2) (3) (3) 4。

（3）4 填充空位：1 2 3 4 (3) (3) (4)。

（4）后面的空位没有元素可以填充，维持原来的值，最终结果是：1 2 3 4 3 3 4。

10.10 变序算法

变序算法改变容器中元素的顺序，但是不改变元素的值。变序算法不适用于关联容器。此类算法复杂度都是 O(n)。变序算法如表 10.11 所示。

表10.11 变序算法
算法	功能
reverse	颠倒区间的前后次序
reverse_copy	把一个区间颠倒后的结果复制到另一个区间，源区间不变
rotate	将区间进行循环左移
rotate_copy	将区间以首尾相接的形式进行旋转后的结果复制到另一个区间，源区间不变
next_permutation	将区间改为下一个排列（可自定义比较器）
prev_permutation	将区间改为上一个排列（可自定义比较器）
random_shuffle	随机打乱区间内元素的顺序
partition	把区间内满足某个条件的元素移到前面，不满足该条件的移到后面
stable_patition	把区间内满足某个条件的元素移到前面，不满足该条件的移到后面。而且对于这两部分元素，分别保持它们原来的先后次序不变

上述算法的原型如下：

reverse

原型：void reverse(iterator first, iterator last);

功能：颠倒区间 [first, last) 的次序。

reverse_copy

原型：iterator reverse_copy(iterator first, iterator last, iterator dest);

功能：将颠倒次序的 [first, last) 的内容复制到 dest 开始处，[first, last) 不变。程序要要确保 dest 开始处有足够的空间存放复制过来的元素。返回值是 dest + (last - first)。

rotate

原型：void rotate(iterator first, iterator newFirst, iterator last);

功能：将区间 [first, last) 进行循环左移，即左侧移出去的元素填充右侧。左移后，原 *newFirst 称为新的区间起点，原 *first 则被移动到原来 first + (last - newFirst) 的位置。

rotate_copy

原型：iterator rotate_copy(iterator first, iterator newFirst, iterator last, iterator dest);

功能：将区间 [first, last) 循环左移后的结果复制到 dest 开始处，[first, last) 不变。程序员要确保 dest 开始处有足够的空间存放复制过来的元素。

next_permutation

原型：bool next_permutation(iterator first, iterator last);

功能：将区间 [first, last) 改为下一个排列。这里所说的 “排列”，是 “排列组合” 这个数学概念中的 “排列”。n 个元素最多有 n！种排列（有可能有重复元素，所以不一定有 n！种排列），把这些排列按字典方式排序后，“上一个排列” 或 “下一个排列” 的说法就是有意义的。例如，“12354” 的下一个排列就是 “12435”，上一个排列是 “12345”，而 “12345” ，没有上一个排列，它已经是最小的排列了。如果存在符合要求的排列，该函数返回 true；否则返回 false。

该函数还有一个版本，可以自定义元素之间比较大小的规则。元素之间比较大小的规则决定了两个排列之间比较大小的规则。

prev_permutation

原型：bool perv_permutation(iterator first, iterator last);

功能：将区间 [first, last) 改为上一个排列。如果存在符合要求的排列，该函数返回 true；否则返回 false。该函数同样存在自定义元素之间比较大小规则的版本。

random_shuffle

原型：void random_shuffle(iterator first, iterator last);

功能：将区间 [first, last) 内元素的顺序随机打乱，类似于洗牌。注意，调用本算法前，还需要调用随机数发生函数 srand 以设置随机种子，否则每次程序运行时得到的结果一样，就不够随机了。

partition

原型：iterator partition(iterator first, iteartor last, Pred op);

功能：将区间 [first, last) 中满足 op(x) 为 true 的 x 移动到区间前部，返回值为第一个使得 op(x) 为 false 的 x 的迭代器。

stable_patition

原型：iterator stable_partition(iterator first, iterator last, Pred op);

功能：将区间 [first, last) 中满足 op(x) 为真的 x 移动到区间前部，返回值为第一个使得 op(x) 为假的 x 的迭代器。它和 partition 的区别在于，对于使得 op(x) 为真的元素和使得 op(x) 为假的元素，此算法分别保持它们原先的相对次序。

下面的程序演示了以上的变序算法。

#include <iostream>
#include <algorithm>
#include <ctime>
#include <iterator>
using namespace std;
bool LessThan4(int n) {return n < 4;}
int main()
{
	ostream_iterator<int> oit(cout, ",");
	int a[5] = {1,2,3,4,5};
	reverse(a, a+5);
	cout << "1)"; copy(a, a+5, oit); cout << endl;
	int b[5] = {0,0,0,0,0};
	reverse_copy(a, a+5, b);
	cout << "2)"; copy(b, b+5, oit); cout << endl;
	cout << "3)"; copy(a, a+5, oit); cout << endl;
	bool result = prev_permutation(a, a+5);
	cout << "4)"; copy(a, a+5, oit); cout << endl;
	result = next_permutation(a, a+5);
	cout << "5)"; copy(a, a+5,oit); cout << endl;
	result = next_permutation(a, a+5);
	cout << "6)" << result << endl;
	srand(time(0));		//设置随机种子
	random_shuffle(a, a+5);
	cout << "7)"; copy(a, a+5, oit); cout << endl;
	partition(a, a+5, LessThan4);
	cout << "8)"; copy(a, a+5, oit); cout << endl;
	random_shuffle(a, a+5);
	cout << "9)"; copy(a, a+5, oit); cout << endl;
	stable_partition(a, a+5, LessThan4);
	cout << "10)"; copy(a, a+5, oit); cout << endl;
	return 0;
}

程序的输出结果是：

1)5,4,3,2,1,

2)1,2,3,4,5,

3)5,4,3,2,1,

4)5,4,3,1,2,

5)5,4,3,2,1,

6)0

7)2,4,3,5,1,

8)2,1,3,5,4,

9)2,1,4,3,5,

10)2,1,3,4,5,

本程序每次运行时，第 24 行以后的输出都有可能不同个，因为第 24 行随机打乱了 a 的次序。

第 23 行，srand(time(0)) 设置了随机数发生器的种子。random_shuffle 执行过程中要产生随机数序列，根据此序列来打乱其所操作的区间的顺序。void srand(unsigned int seed) 是产生随机种子的库函数，seed 决定了random_shuffle 被调用时产生的随机数序列是什么样的（计算机无法产生真正的、不可预测的随机数序列）。为了使程序每次运行时 random_shuffle 产生的结果都不一样，不能用固定的 seed，故此处用 time(0) 作为 seed。time 是在 ctime 头文件中定义的获取当前时间的函数，time(0) 能产生一个和当前系统时间相关的值，该值在程序每次运行时都不相同，因此 random_shuffle 产生的打乱次序的效果也就不同了。

第 30 行，把小于 4 的元素都排在前面，还要保持元素原先的次序。结果就是小于 4 的元素被排到前面，它们之间的先后次序与原来一样；大于或等于 4 的元素被排到后面，它们的先后次序也保持不变。

next_permutation 常用于枚举，例如下面的例题。

例题：用 next_permutation 解 n 皇后问题。即在一个 n 行 n 列的国际象棋棋盘上摆放 n 个皇后，使得它们不会相互攻击。两个皇后在同一行、同一列或同一斜线上，即为互相攻击。输入 n，输出 n 皇后问题的所有解法。

解题思路：反复调用 next_permutation 就可以枚举所有皇后的摆法（两个或多个皇后在同一列的摆法除外）。程序如下：

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
bool Valid(int rows,const vector<int> & pos) //前rows行皇后是否冲突
{ //pos是各行皇后的位置，位置从0开始算
	for(int i = 0; i < rows; ++ i)
		for(int j = 0; j < i; ++ j )
			if(pos[i] == pos[j] || abs(i-j) == abs(pos[i]-pos[j]))
				return false; //冲突
	return true; //不冲突
}
int main()
{
	int n;
	cin >> n; //n个皇后
	vector<int> pos(n);  // n个皇后摆放的位置,行列都从0开始算
	for(int i = 0;i < n; ++ i) //算出最小的排列012…… n-1，已知其不是解
		pos[i] = i;
	while(next_permutation(pos.begin(),pos.end())) {
		if(Valid(n,pos)) {
			for( int k = 0; k < n; ++k)
				cout << pos[k] << " ";
			cout << endl;
		}
	}
	return 0;
}

这个解法写起来比较方便，但是没有必要地穷举了几乎所有的摆法，所以执行速度较慢。

10.11 排序算法

排序算法比变序算法复杂度更高，一般是 O(n * log(n))。排序算法需要随机访问迭代器的支持，因而不适用于关联容器和 list。每个排序算法都有两个版本，一个用 “<” 作为比较器，从小到大排序；另一个可以自定义比较器。排序算法及其功能如表 10.12 所示。

表10.12 排序算法
算法名称	功能
sort	将区间从小到大排序（可自定义比较器）
stable_sort	将区间从小到大排序，并保持相等元素间的相对次序（可自定义比较器）
partial_sort	对区间部分排序，知道最小的 n 个元素就位（可自定义比较器）
partial_sort_copy	将区间前 n 个元素的排序结果复制到别处，源区间不变（可自定义比较器）
nth_element	对区间部分排序，使得第 n 小的元素（n 从 0 开始）就位，而且比它小的元素都在它前面，比它大的元素都在它后面（可自定义比较器）
make_heap	使区间成为一个 “堆”（可自定义比较器）
push_heap	将元素加入一个 “堆” 区间（可自定义比较器）
pop_heap	从 “堆” 区间删除堆顶元素（可自定义比较器）
sort_heap	对一个 “堆” 区间进行排序，排序结束后，该区间就是普通的有序区间，不再是 “堆” 了（可自定义比较器）

以下是各个算法的详细解释，每种算法只列出一个版本。

sort

原型： void sort(iterator first, iterator last);

功能：将区间 [first, last) 排序。一般用快速排序算法实现，平均时间复杂度为 O(n * log(n))；最坏情况下，时间复杂度是 O( $n^{^{2}}$ )。此算法的详细用法在 “函数对象” 一节已有讲解。

stable_sort

原型：void stable_sort(iterator first, iterator last);

功能：将区间 [first, last) 排序，并保持相等元素的先后次序。一般用归并排序算法实现，最坏情况下时间复杂度也是 O(n * log(n))，但平均来说比 sort 慢。

partial_sort

原型：void partial_sort(iterator first, iterator mid, iterator last);

功能：将区间 [first, last) 部分排序，排序的结果是 [first, mid) 成为有序，并且其中的任一元素都不比 [mid, last) 中的任一元素大，但 [mid, last) 可能无序。换句话说，就是使 [first, last) 中最小的 mid - first 个元素就位。一般用堆排序算法实现，最坏情况下时间复杂度也是 O(n * log(n))。

partial_sort_copy

原型：iterator partial_sort_copy(iterator first1, iterator last1, iterator first2, iterator last2);

功能：这个算法并不是 partial_sort 再加 copy。设 x = min{last1 - first1, last2 - first2}，则本算法将区间 [first1, last1) 的排序结果复制到 first2 开始处，且只复制排序结果的前 x 个元素；[first1, last1) 保持不变。返回值是 first2+x。

nth_element

原型：void nth_element(iterator first, iterator mid, iterator last);

功能：对 [first, last) 进行部分排序，排序后，mid 位置的元素 x 满足以下条件：比 x 小的都在 x 的前面，比 x 大的都在 x 后面。

make_heap、push_heap、pop_heap、sort_heap 都是和 “堆” 有关的算法。“堆” 是数据结构可成中的概念，这里只做简要介绍：

n 个元素的序列 { $k_{0}$ , $k_{1}$ , $k_{2}$ ,..., $k_{n-1}$ }，如果满足 $k_{i}\geqslant k_{2i+1}$ 且 $k_{i}\geqslant k_{2i+2}$ （其中 i = 0,1,...），则称该序列构成一个 “堆”。例如下面两个序列都是堆：

96 83 27 38 11 9

y r p d f b k a c

make_heap

原型：void make_heap(iterator first, iteartor last);

功能：将区间 [first, last) 做称一个堆。时间复杂度为 O(n)。

push_heap

原型：void push_heap(iterator first, iteartor last);

功能：在 [first, last - 1) 已经是堆的情况下，该算法能将 [first, last) 变成堆，时间复杂度为 O(long(n))。向已经是堆的容器中添加元素，可以在每次 push_back 一个元素后，再调用 push_back 算法，使得容器依然是一个堆。

pop_heap

原型：void pop_heap(iterator first, iteartor last);

功能：在 [first, last) 已经是堆的情况下，将堆中的最大元素，即 *first，移动到 last - 1的位置，原 *(last - 1) 元素则被移动到前面某个位置，并且移动后 [first, last - 1) 仍然是一个堆。算法的时间复杂度为 O(log(n))。

sort_heap

原型：void sort_heap(iterator first, iteartor last);

功能：在 [first, last) 已经是堆的情况下，对 [first, last) 进行排序。排序结束后，[first, last) 成为普通有序区间，不再是堆。

下面的程序演示了排序算法的应用。sort 的用法前面已经出现多次，stable_sort 的用法和 sort 一模一样，就不在程序中演示了。

#include <iostream>
#include <iterator>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int main()
{
	ostream_iterator<int> oit(cout, ",");
	int a[5] = {4,5,3,1,2};
	int b[5];
	memcpy(b, a, sizeof(a));						//复制 a 到 b
	partial_sort(b, b+3, b+5);						//使前三个元素就位
	cout << "1)"; copy(b, b+5, oit); cout << endl;
	memset(b, 0, sizeof(b));						//把 b 变成全 0
	partial_sort_copy(a, a+4, b, b+3);				//把 [a, a+4) 排序结果的前三个复制到 b
	cout << "2)"; copy(a, a+5, oit); cout << endl;
	cout << "3)"; copy(b, b+5, oit); cout << endl;
	int c[8] = {4,1,2,6,5,3,7,0};
	nth_element(c, c+3, c+8);
	cout << "4)"; copy(c, c+8, oit); cout << endl;
	memcpy(b, a, sizeof(a));
	make_heap(b, b+5);								//把 b 变成一个堆
	cout << "5)"; copy(b, b+5, oit); cout << endl;
	vector<int> v(b, b+5);							//因为 b 是堆，所以 v 也是堆
	v.push_back(9);									//往堆 v 中添加一个元素后，v 可能就不是堆了
	push_heap(v.begin(), v.end());					//将 v 恢复成堆
	cout << "6)"; copy(v.begin(), v.end(), oit); cout << endl;
	pop_heap(v.begin(), v.end());
	cout << "7)"; copy(v.begin(), v.end(), oit); cout << endl;
	sort_heap(v.begin(), v.end()-1);
	cout << "8)"; copy(v.begin(), v.end()-1, oit); cout << endl;
	return 0;
}

程序的输出结果是：

1)1,2,3,5,4,

2)4,5,3,1,2,

3)1,3,4,0,0,

4)1,0,2,3,4,5,7,6,

5)5,4,3,1,2,

6)9,4,5,1,2,3,

7)5,4,3,1,2,9,

8)1,2,3,4,5,

第 13 行，“partial_sort(b, b+3, b+5)” 使得 [b, b+5) 中最小的三个元素就位，排序后，1、2、3 这三个元素就应该排在前三个位置，后面两个元素可以无序。

第 16 行，“partial_sort_copy(a, a+4, b, b+3)” 把 [a, a+4) 排序结果的前三个复制到 b。[a, a+4) 就是 “4 5 3 1 ”，排序后是 “1 3 4 5”，只复制前三个到 b，于是就复制了 “1 3 4”。

第 20 行，“nth_element(c, c+3, c+8)” 使得排序后 c+3 这个位置的元素 x 应该满足以下条件：比 x 小的都在 x 的前面，比 x 大的都在 x 的后面。排序后，这个位置的元素应该是 3。在元素个数较少（如少于 32 个）时，Visual Studio 的 nth_element 算法执行的是完全的排序。

10.12 有序区间算法

有序区间算法要求所操作的区间是已经从小到大排好序的，而且需要随机访问迭代器的支持，因此有序区间算法不能用于关联容器和 list。有序区间算法都有两个版本，一个用 “<” 运算符比较元素的大小，另一个用自定义比较器比较元素的大小。有序区间算法不用 “==” 运算符比较 x 和 y 是否相等，而是在当且仅当 “x 小于 y” 和 “y 小于 x” 都不成立时，认为 x 和 y 相等。

有序区间算法在对区间操作时比较大小的规则，必须和该区间在排序时比较大小的规则一致。

STL 中的有序区间算法如表 10.13 所示，它们全部都可以自定义比较器。

表10.13 有序区间算法
算法名称	功能
binary_search	判断区间中是否包含某个元素
includes	判断是否一个区间中的每一个元素都在另一个区间中
lower_bound	查找最后一个不小于某值的元素的位置
upper_bound	查找第一个大于某值的元素的位置
equal_range	同时获取 lower_bound 和 upper_bound
merge	合并两个有序区间到第三个区间
set_union	将两个有序区间的并复制到第三个区间
set_intersection	将两个有序区间的交复制到第三个区间
set_difference	将两个有序区间的差复制到第三个区间
set_symmetric_difference	将两个有序区间的对称差复制到第三个区间
inplace_merge	将两个连续的有序区间原地合并为一个有序区间

有序区间算法的原型和功能如下。

binary_search

原型：bool binary_search(iterator first, iterator last, const T & val);

功能：判断区间 [first, last) 是否包含 val。因为 [first, last) 是有序的，所以查找的过程不必像 find 那样顺序查找，而采用折半查找，因此时间复杂度是 O(log(n))。所谓 [first, last) 包含 val，指的是 [first, last) 中存在 x，使得 “x < val” 和 “val < x” 同时为假。

includes

原型：bool binary_search(iterator first, iterator last, const T & val, Pred op);

功能：这个版本要求 [first, last) 本来就是按照 op 所规定的比较规则排序的。而且对于 val 和元素 x，如果 op(x, val) 和 op(val, x) 同时为假，则认为 x 和 val 相等，亦即 [first, last) 中包含 val。

lower_bound

原型：iterator lower_bound(iterator first, iterator last, const T & val);

功能：返回一个最大的迭代器 it，使得 [first, it) 中的元素都比 val 小。如果 [first, last) 中的元素都不比 val 小，则返回 first。时间复杂度为 O(log(n))。

upper_bound

原型：iterator upper_bound(iterator first, iterator last, const T & val);

功能：返回一个最小的迭代器 it，使得 [it, last) 中的元素都比 val 大。如果 [first, last) 中的元素都不比 val 大，则返回 last。时间复杂度为 O(log(n))。

equal_range

原型：pair<iterator, iterator> equal_range(iterator first, iterator last, const T & val);

功能：同时计算 lower_bound 和 upper_bound。返回值 p 是一个 pair 模板类对象，p.first 存放 lower_bound 的返回值，p.second 存放 upper_bound 的返回值。时间复杂度为 O(log(n))。

下面从 merge 到 set_symmetric_difference 的五个算法将两个源区间的一些内容复制到从 dest 开始的地方，要求两个源区间 [first1, last1) 和 [first2, last2) 是有序的。程序员要确保 dest 处有足够的空间存放复制过去的内容。最终复制过去的内容也会是排好序的，源区间的内容不会被改变。这五个算法的时间复杂度都是线性的。

merge

原型：iterator merge(iterator first1, iterator last1, iteartor first2, iterator last2, iterator dest);

功能：将 [first1, last1) 和 [first2, last2) 的全部内容复制到 dest。返回值是 dest + (last1 - first1) + (last2 - first2)。

set_union

原型：iterator set_union(iterator first1, iterator last1, iteartor first2, iterator last2, iterator dest);

功能：将 [first1, last1) 和 [first2, last2) 的并复制到 dest。并的规则是：若元素 e 在 [first1, last1) 中出现 n1 次，在 [first2, last2) 中出现 n2 次，则 e 在目标区间出现 max(n1, n2) 次。假设有 n 个元素被复制到目标区间，则返回值是 dest+n。

set_intersection

原型：iterator set_intersection(iterator first1, iterator last1, iteartor first2, iterator last2, iterator dest);

功能：将 [first1, last1) 和 [first2, last2) 的交复制到 dest。交的规则是：若元素 e 在 [first1, last1) 中出现 n1 次，在 [first2, last2) 中出现 n2 次，则 e 在目标区间出现 min(n1, n2) 次。假设有 n 个元素被复制到目标区间，则返回值是 dest+n。

set_difference

原型：iterator set_difference(iterator first1, iterator last1, iteartor first2, iterator last2, iterator dest);

功能：将 [first1, last1) 和 [first2, last2) 的差复制到 dest。差的规则是：若元素 e 在 [first1, last1) 中出现 n1 次，在 [first2, last2) 中出现 n2 次，则 e 在目标区间出现 max(0, n1 - n2) 次。假设有 n 个元素被复制到目标区间，则返回值是 dest+n。

set_symmetric_difference

原型：iterator set_symmetric_difference(iterator first1, iterator last1, iteartor first2, iterator last2, iterator dest);

功能：将 [first1, last1) 和 [first2, last2) 的对称差复制到 dest。对称差的规则是：若元素 e 在 [first1, last1) 中出现 n1 次，在 [first2, last2) 中出现 n2 次，则 e 在目标区间出现 $\left | n1-n2 \right |$ 次。假设有 n 个元素被复制到目标区间，则返回值是 dest+n。

inplace_merge

原型：void inplace_merge(iterator first, iterator mid, iterator last

功能：将有序区间 [first, mid) 和 [mid, last) 合并。合并后的区间 [first, last) 也是有序的。

下面的程序演示了有序区间算法的应用。

#include <iostream>
#include <iterator>
#include <algorithm>
#include <cstring>
using namespace std;
class A
{
	public:
		int v;
		A(int n):v(n) { }
		A(){ v = 0;};
};
bool operator< ( const A & a1, const A & a2)
{
	return a1.v < a2.v;
}
ostream & operator <<( ostream & o, const A & a)
{
	cout << a.v;
	return o;
}
int main()
{
	ostream_iterator<A> oit(cout,",");
	A a[7] = { 1,2,2,3,3,5,6 };
	A b[3] = { 3,4,6};
	A c[20];
	A d[4] = { 2,2,2,3 };
	A e[6] = { 2,2,2,3,7,7 };
	cout << "1) " << binary_search(a,a+7,A(3)) << endl;//输出 1) 1
	cout << "2) " << binary_search(a,a+7,A(100)) << endl; //输出 2) 0
	cout << "3) " << includes(a,a+6,b,b+3) << endl; //输出 3) 0
	A * p = lower_bound(a,a+7,3);
	cout << "4) " << p - a << endl; 			 //输出 4) 3
	p = upper_bound(a,a+7,3);
	cout << "5) " << p - a << endl; 			 //输出 5) 5
	pair<A * ,A *> pi = equal_range(a,a+7,3);
	cout << "6) " << pi.first - a << "," << pi.second - a << endl;
	//输出 6) 3,5
	p = merge(a,a+7,b,b+3,c);
	cout << "7) "; copy(c,p,oit); cout << endl;
	//输出 7) 1,2,2,3,3,3,4,5,6,6,
	memset(c,0,sizeof(c)); //把c变成全0
	p = set_union(a,a+7,b,b+3,c);
	cout << "8) "; copy(c,p,oit); cout << endl; //输出 8) 1,2,2,3,3,4,5,6,
	memset(c,0,sizeof(c));
	p = set_intersection(a,a+7,d,d+4,c);
	cout << "9) "; copy(c,p,oit); cout << endl; //输出 9) 2,2,3,
	memset(c,0,sizeof(c));
	p = set_difference(a,a+7,d,d+4,c);
	cout << "10) "; copy(c,p,oit); cout << endl; //输出 10) 1,3,5,6,
	p = set_symmetric_difference(a,a+7,e,e+6,c);
	cout << "11) "; copy(c,p,oit); cout << endl; //输出 11) 1,2,3,5,6,7,7,
	A f[8] = { 2,4,6,8,1,3,5,7};
	inplace_merge(f,f+4,f+8);
	cout << "12) "; copy(f,f+8,oit); cout << endl;
	//输出 12) 1,2,3,4,5,6,7,8,
	return 0;
}

关于 STL 算法总结：STL 算法多，要求程序员全部记住反而是一个负担。而且其中一些算法在实际编写代码的过程中也可以用几个循环解决，对算法的使用没有刚性需求，所以除去一些常用的算法（如 sort、unique、binary_search、reverse、random_shuffle、next_permutation、prev_permutation）最好熟练掌握之外，对其他算法有个基本印象即可，实在要用的时候再查也不迟。

10.13 string 类详解

string 类是 STL 中 basic_string 模板实例化得到的模板类。其定义如下：

typedef basic_string<char> string;

basic_string 此处可以不必深究。

string 类的成员函数很多，同一个名字的函数，也常会有五六个重载的版本。篇幅所限，不能一一列出原型并加以解释。这里仅对常用成员函数按功能进行分类，并直接给出应用的例子，通过例子读者可以基本学会这些成员函数的用法。要想更深入了解 string 类，还是要看 C++ 的参考手册或编译器带的联机资料。对于一部分在前面介绍过的字符串中提到过的内容，这里就不再说明了。

1. 构造函数

string类有多个构造函数,用法示例如下：

                string s1();                           //s1 = ""
                string s2("Hello");           //s2 ="Hello"
                string s3(4, 'K');                  //s3="KKKK”
                string s4("12345",1,3); /ls4 ="234",即"12345"的从下标1开始,长度为3的子串

为称呼方便，本书后文将从字符串下标n开始的，长度为 m 的子串，称为 “子串(n,m)”。

string类没有接收一个整型参数或一个字符型参数的构造函数。下面的两种写法是错误的：

string s1('K');
string s2( 123);

2. 对string对象赋值

可以用 char*类型的变量、常量，以及 char 类型的变量、常量对 string 对象进行赋值，例如：

                string s1;
                s1 = "Hello";        //s1 .= "He1lo"
                s2= 'K'; //s2=“K"

string 类还有 assign 成员函数，可以用来对 string 对象赋值。assign 成员函数返回对象自身的引用：

                string s1("12345"), s2;
                s3.assign(s1);      //s3 =s1
                s2.assign(s1,1,2);    //s2 = "23"，即s1的子串(1,2)
                s2. assign(4, 'K');                //s2 ="KKKK"
                s2.assign( "abcde" ,2,3);        //s2 = "cde"，即 "abcde" 的子串(2,3)

3. 求字符串的长度

int length() const 成员函数返回字符串的长度。int size() const成员函数完成同样的功能。

4. string对象中字符串的连接

除了可以使用 “＋” 和 “+=” 对 string 对象执行字符串的连接操作外， string 类还有 append 成员函数，可以用来往字符串后面添加内容。append 成员函数返回对象自身的引用：

                string s1("123"),s2("abc");
                s1.append(s2); //s1 = "123abc"
                s1 . append(s2,1,2); //s1 = "123abcbc"
                s1.append(3, 'K');         //s1 = "123abcbcKKK"
                s1 .append( "ABCDE",2,3);        //s1 = "123abcbcKKKCDE”,添加"ABCDE"的子串(2,3)

5. string对象的比较

除了可以用 “<”、“<=”、“==”、“!=”、“>=”、“>” 互相比较外，string 类还有 compare 成员函数，可用于比较字符串。compare 函数的返回值，小于 0 表示自身的字符串小；等于0表示两串相等；大于0表示另一个字符串小：

                string s1( "hello"),s2( "he1lo, world");
                int n= s1.compare( s2);
                n= s1.compare(1,2,s2,0,3);   //比较s1的子串(1,2)和s3的子串(0,3)
                n=s1.compare(0,2,s2);                   //比较s1的子串(0,2)和s3
                n= s1.compare("Hello");
                n = s1.compare(1,2, "Hello"); //比较s1的子串(1,2)和"Hello"
                n = s1.compare(1,2,"Hello",1,2);        //比较s1的子串(1,2)和"Eello"的子串(1,2)

6. string对象求子串

substr 成员函数可以求子串(n,m):

string substr( int n =0,int m= string::npos) const;

调用时，如果 m 默认或超过了字符串长度，则求出来的子串就是从下标 n 开始一直到字符串结束。例如：

                string s1 = "this is ok";
                string s2 =s1.substr(2,4); //s2 := "is i"
                s2 = s1. substr(2);                        //s2 = "is is ok"

7. 交换两个string对象内容

swap 成员函数可以交换两个 string 对象的内容。

string s1("West"),s2("East");
s1.swap(s2); //s1 = "East” , s2= "West"

8. 查找子串和字符

string 类有一些查找子串和查找字符的成员函数，它们的返回值都是子串或字符在 string 对象字符串中的位置（即下标）。如果查不到，则返回 string::npos。string::npos 是 string 类中定义的一个静态常量。这些函数如下：

find：从前向后查找子串或字符出现的位置。

rfind：从后往前查找子串或字符出现的位置。

find_first_of：从前向后查找，何处出现了另一个字符串中包含的字符。例如：

s1.find_first_of("abe"); //查找s1中第一次出现 "abc" 中任一字符的位置

find_last_of：从后往前查找，何处出现了另一个字符串中包含的字符。

find_first_not_of：从前向后查找，何处出现了另一个字符串中没有包含的字符。
find_last_not_of：从后往前查找，何处出现了另一个字符串中没有包含的字符。下面是查找成员函数的示例程序：

#include <iostream>
#include <string>
using namespace std;
int main()
{
	string s1 ("Source Code");
	int n;
	if((n = s1.find('u')) != string:: npos)						//查找u出现的位置
	cout << "1)" << n << "," << s1.substr(n) << endl;			//输出1)2,urce Code
	if((n = s1.find("Source",3)) == string::npos )				//从下标3开始查找"Source",找不到
	cout << "2)" << "Not Found" << endl;						//输出2)Not Found
	if((n = s1.find("co")) != string::npos)						//查找子串Co",能找到,返回"Co"位置
	cout << "3)" << n << "," << s1.substr(n) << endl;			//输出3)7,Code
	if((n = s1.find_first_of( "ceo")) != string::npos)			//查找第一次出现了'c'或'e'或'o'的位置
	cout << "4)" << n << "," << s1.substr(n) << endl;			//输出4)1,ource Code
	if((n= s1.find_last_of('e')) != string::npos)				//查找最后一个'e'的位置
	cout << "5)" << n << "," << s1.substr(n) << endl;			//输出5)10,e
	if((n = s1.find_first_not_of("eou",1)) != string::npos)		//从下标1开始查找第一次出现非'e'.非'o'、非'u'字符的位置
	cout << "6)" << n << "," << s1.substr(n) << endl;				//输出6)3, rce Code
	return 0;
}

9．替换子串

replace 成员函数可以对 string 对象中的子串进行替换，返回对象自身的引用：

                string s1( "Real Steel");
                s1.replace(1,3,"123456"，2,4);        //用"123456"的子串(2,4)替换s1的子串(1,3)
                cout<<s1<< endl;          //输出 R3456 Steel
                string s2("Harry Potter" );
                s2.replace(2,3,5,'0');           //用5个 '0 '替换子串(2,3)
                cout<<B2<<endl;          //输出Ha00000 Potter
                int n = s2.find( "oo00o");             //找子串"00000"的位置,n= 2
                s2 . replace(n, 5, "XXX");                //将子串(n,5)替换为"XXX"
                cout << s2<< endl;           //输出 HaXXX Potter

10．删除子串

erase 成员函数可以删除 string 对象中的子串，返回对象自身的引用。

                string s1("Real Steel" );
                s1 .erase(1,3);                        //删除子串(1,3),此后s1= "R Steel"
                s1.erase(5); //删除下标5及其后所有字符,此后s1="R Ste"

11．插入字符串

insert成员函数可以在string对象中插入另一个字符串，返回对象自身的引用。

                string s1("Limitless"),s2("00");
                s1.insert(2, "123"); //在下标2处插人字符串"123",s1= "Li123mitless"
                s1.insert(3,s2);                        //在下标2处插人s2,s1="Li10023mitless"
                s1.insert(3,5,'X');                      //在下标3处插人5个'x',s1 ="Li1XXXXX0023mitless"

12. string对象作为流处理

使用流对象 istringstream 和 ostringstream，可以将 string 对象当做一个流，进行输入和输出。使用这两个类需要包含头文件 sstream。示例程序如下：

#include <iostream>
#include <sstream>
#include <string>
using namespace std;
int main()
{
   string src("Avatar 123 5.2 Titanic K");
   istringstream istrStream(src); //建立src到istrStream的联系
   string s1, s2;
   int n;  double d;  char c;
   istrStream >> s1 >> n >> d >> s2 >> c; //把src的内容当做输入流进行读取
   ostringstream ostrStream;
   ostrStream << s1 << endl << s2 << endl << n << endl << d << endl << c <<endl;
   cout << ostrStream.str();
   return 0;
}

程序的输出结果：

                Avatar
                Titanic
                123
                5.2
                K

第11行，从输入流 istrStream 进行读取，过程和从 cin 读取一样，只不过输入的来源由键盘变成了 string 对象 src。因此 “Avatar” 被读取到 s1，123 被读取到 n，5.2 被读取到 d，“Titannic”被读取到 s2，‘K’ 被读取到 c。

第12行输出到流 ostrStream。输出结果不会出现在屏幕上，而是被保存在 ostrStream 对象管理的某处。用 ostringstream 的 string str() const 成员函数。就能将输出到 ostringstream 对象中的内容提取出来。

13. 用 STL 算法操作string对象

string 对象也可以看做一个顺序容器，它支持随机访问迭代器，也有 begin 和 end 等成员函数。STL 中许多算法也适用于 string 对象。下面是用 STL 算法操作 string 对象的程序示例：

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
	string s("afgcbed");
	string::iterator p = find(s.begin(), s.end(), 'c');
	if(p != s.end())
	cout<< p-s.begin() << endl;	//输出3
	sort(s.begin(), s.end());
	cout<< s << endl;			//输出abcdefg
	next_permutation(s.begin(),s.end());
	cout<< s << endl;			//输出abcdegf
	return 0;
}

10.14 bitset 对象

bitset 对象由若干个位（bit）组成，它提供一些成员函数，使程序员不必通过位运算就能很方便地访问。修改其中的任意一位。bitset 模板在头文件 bitset 中定义如下：

template<size_t N>

class bitset

{

...

}

size_t 可看作 unsigned int。将 bitset 实例化时，N 必须是一个整型常数。例如：

bitset<40> bst;

则 bst 是一个由 40 个位组成的对象，用 bitset 的成员函数可以方便地访问其中任意一位。bitset 中的位从 0 开始编号，第 0 位是最右边的位。

bitset 有许多成员函数，有些成员函数执行的就是类似于位运算的操作。bitset 成员函数列表如下：

bitset<N>& operator &= (const bitset<N>& rhs);	//和另一个 bitset 对象进行与操作
bitset<N>& operator |= (const bitset<N>& rhs);	//和另一个 bitset 对象进行或操作
bitset<N>& operator ^= (const bitset<N>& rhs);	//和另一个 bitset 对象进行异或操作
bitset<N>& operator <<= (size_t num);			//左移 num 位
bitset<N>& operator >>= (size_t num);			//右移 num 位
bitset<N>& set();								//将所有位全部设成 1
bitset<N>& set(size_t pos, bool val = true);	//将第 pos 位设为 val
bitset<N>& reset();								//将所有位全部设成 0
bitset<N>& reset(size_t pos);					//将第 pos 位设为 0
bitset<N>& flip();								//将所有位翻转（0 变成 1, 1 变成 0）
bitset<N>& flip(size_t pos);					//翻转第 pos 位
reference operator [] (size_t pos);				//返回对第 pos 位的引用
bool operator [] (size_t pos)const;				//返回第 pos 位的值
reference at(size_t pos);						//返回对第 pos 位的引用
bool at(size_t pos)const;						//返回第 pos 位的值
unsigned long to_ulong()const;					//将对象中的 0、1 串转换成整数
string to_string()const;						//将对象中的 0、1 串转换成字符串
												//（Visual Studio 支持，Dec C++ 不支持）
size_t count()const;							//计算 1 的个数
size_t size()const;								//返回总位数
bool operator == (const bitset<N>& rhs)const;
bool operator != (const bitset<N>& rhs)const;
bool test(size_t pos)const;						//测试第 pos 位是否为 1
bool any()const;								//判断是否有某位为 1
bool none()const;								//判断是否全部为 0
bitset<N>operator << (size_t pos)const;			//返回左移 pos 位后的结果
bitset<N>operator >> (size_t pos)const;			//返回右移 pos 位后的结果
bitset<N>operator ~ ();							//返回取反后的结果
bitset<N>operator & (const bitset<N>& rhs)const;//返回和另一个 bitset 对象 rhs 进行与运算的结果
bitset<N>operator | (const bitset<N>& rhs)const;//返回和另一个 bitset 对象 rhs 进行或运算的结果
bitset<N>operator ^ (const bitset<N>& rhs)const;//返回和另一个 bitset 对象 rhs 进行异或运算的结果

下面的程序演示了 bitset 的用法。

#include <iostream>
#include <bitset>
#include <string>
using namespace std;
int main()
{
	bitset<7> bst1;
	bitset<7> bst2;
	cout << "1) " << bst1 << endl; //输出 1) 0000000
	bst1.set(0,1);//将第0位变成1，bst1变为 0000001
	cout << "2) " << bst1 << endl; //输出 2) 0000001
	bst1 <<= 4; //左移4位，变为 0010000
	cout << "3) " << bst1 << endl; //输出 3) 0010000
	bst2.set(2);//第二位设置为1，bst2变成  0000100
	bst2 |=bst1; // bst2变成  0010100
	cout << "4) " << bst2 << endl; //输出 4) 0010100
	cout << "5) " << bst2.to_ulong () << endl; //输出 5) 20
	bst2.flip(); //每一位都取反，bst2变成 1101011
	bst1.set(3); //bst1变成  0011000
	bst2.flip(6); //bst2变成 0101011
	bitset<7> bst3 = bst2^ bst1;//bst3 变成 0110011
	cout << "6) " << bst3 << endl; //输出 6) 0110011
	cout << "7) " << bst3[3] << "," << bst3[4] << endl; //输出 7) 0,1
	return 0;
}

本章对各方面介绍较为简洁，主要目的在于使学习者有初步理解并会运用，更多细致的知识还需要进一步学习，详细可参考以下文章或者查询 C++ 手册。

value_type：C++ 10.3 关联容器map定义以及value_type、key_type、mapped_type_c++ value_type_普通网友的博客-程序员宅基地

typedef：typedef常见用法和函数指针用法_vex_sx的博客-程序员宅基地

数据结构：(1条消息) 数据结构_UniqueUnit的博客-程序员宅基地

输入输出迭代器：C++输入输出迭代器_乌鸦_在飞的博客-程序员宅基地

string 类成员函数：C++-string常用函数整理（建议收藏）_c++string类函数_翟天保Steven的博客-程序员宅基地

本文链接：https://blog.csdn.net/m0_74105426/article/details/131605381

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Eclipse中配置WebMagic(已配置好Maven)_使用eclipse搭建webmagic工程-程序员宅基地

文章浏览阅读364次。1.WebMagicWebMagic是一个简单灵活的Java爬虫框架。基于WebMagic，你可以快速开发出一个高效、易维护的爬虫。2.在Eclipse中配置WebMagic1.首先需要下载WebMagic的压缩包官网地址为：WebMagic官网最新版本为：WebMagic-0.7.3，找到对应版本，打开下载界面，注意，下载要选择Source code(zip)版本，随便下载到哪里都可以；2.下载好的压缩包需要解压，此时解压到的位置即为后续新建的Eclipse的project位置，比如我的Ecli_使用eclipse搭建webmagic工程

linux启动mysql_linux如何启动mysql服务_linux启动mysql服务命令是什么－系统城-程序员宅基地

文章浏览阅读1.9k次。mysql数据库是一种开放源代码的关系型数据库管理系统，有很多朋友都在使用。一些在linux系统上安装了mysql数据库的朋友，却不知道该如何对mysql数据库进行配置。那么linux该如何启动mysql服务呢？接下来小编就给大家带来linux启动mysql服务的命令教程。具体步骤如下：1、首先，我们需要修改mysql的配置文件，一般文件存放在/etc下面，文件名为my.cnf。2、对于mysql..._linux中 mysql 启动服务命令

php实现在线oj,详解OJ(Online Judge)中PHP代码的提交方法及要点-程序员宅基地

文章浏览阅读537次。详解OJ(Online Judge)中PHP代码的提交方法及要点Introduction of How to submit PHP code to Online Judge SystemsIntroduction of How to commit submission in PHP to Online Judge Systems在目前常用的在线oj中，codeforces、spoj、uva、zoj..._while(fscanf(stdin, "%d %d", $a, $b) == 2)

java快捷键调字体_设置MyEclipse编码、补全快捷键、字体大小-程序员宅基地

文章浏览阅读534次。一、设置MyEclipse编码(1)修改工作空间的编码方式：Window-->Preferences-->General-->Workspace-->Text file encoding(2)修改一类文件的编码方式：Window-->Preferences-->General-->content Types-->修改default Encoding(..._java修改快捷缩写内容

解析蓝牙原理_蓝牙原理图详解-程序员宅基地

文章浏览阅读1.4w次，点赞19次，收藏76次。1.前言市面上关于Android的技术书籍很多，几乎每本书也都会涉及到蓝牙开发，但均是上层应用级别的，而且篇幅也普遍短小。对于手机行业的开发者，要进行蓝牙模块的维护，就必须从Android系统底层，至少框架层开始，了解蓝牙的结构和代码实现原理。这方面的文档、网上的各个论坛的相关资料却少之又少。分析原因，大概因为虽然蓝牙协议是完整的，但是并没有具体的实现。蓝牙芯片公司只负责提供最底层的API_蓝牙原理图详解

从未在一起更让人遗憾_“从未在一起和最终没有在一起哪个更遗憾”-程序员宅基地

文章浏览阅读7.7k次。图/源于网络文/曲尚菇凉1.今天早上出门去逛街，在那家冰雪融城店里等待冰淇淋的时候，听到旁边两个女生在讨论很久之前的一期《奇葩说》。那期节目主持人给的辩论题是“从未在一起和最终没有在一起哪个更遗憾”，旁边其中一个女生说，她记得当时印象最深的是有个女孩子说了这样一句话。她说:“如果我喜欢一个人呢，我就从第一眼到最后一眼，把这个人爱够，把我的感觉用光，我只希望那些年让我成长的人是他，之后的那些年他喝过..._从未在一起更遗憾

随便推点

Spring Cloud Alibaba 介绍_sprngcloud alba-程序员宅基地

文章浏览阅读175次。Spring Cloud Alibaba 介绍Sping体系Spring 以 Bean（对象）为中心，提供 IOC、AOP 等功能。Spring Boot 以 Application（应用）为中心，提供自动配置、监控等功能。Spring Cloud 以 Service（服务）为中心，提供服务的注册与发现、服务的调用与负载均衡等功能。Sping Cloud介绍官方介绍 Tools for building common patterns in distributed systems_sprngcloud alba

测试数据类型的一些测试点和经验_基础字段的测试点-程序员宅基地

文章浏览阅读3.2k次，点赞4次，收藏21次。我这里是根据之前在测试数据类项目过程中的一些总结经验和掉过个坑，记录一下，可以给其他人做个参考，没什么高深的东西，但是如果不注意这些细节点，后期也许会陷入无尽的扯皮当中。1 需求实现的准确度根据产品需求文档描述发现不明确不详细的或者存在歧义的地方一定要确认，例如数据表中的一些字段，与开发和产品确认一遍，如有第三方相关的，要和第三方确认，数据类项目需要的是细心，哪怕数据库中的一个字段如果没有提前对清楚，后期再重新补充，会投入更大的精力。2 数据的合理性根据业务场景/常识推理，提..._基础字段的测试点

一文看懂：行业分析怎么做？_码工小熊-程序员宅基地

文章浏览阅读491次。大家好，我是爱学习的小xiong熊妹。在工作和面试中，很多小伙伴会遇到“对XX行业进行分析”的要求。一听“行业分析”四个字，好多人会觉得特别高大上，不知道该怎么做。今天给大家一个懒人攻略，小伙伴们可以快速上手哦。一、什么是行业？在做数据分析的时候，“行业”两个字，一般指的是：围绕一个商品，从生产到销售相关的全部企业。以化妆品为例，站在消费者角度，就是简简单单的从商店里买了一支唇膏回去。可站在行业角度，从生产到销售，有相当多的企业在参与工作（如下图）在行业中，每个企业常常扮._码工小熊

LLaMA 简介：一个基础的、650 亿参数的大型语言模型_llma-程序员宅基地

文章浏览阅读1.6w次，点赞2次，收藏2次。还需要做更多的研究来解决大型语言模型中的偏见、有毒评论和幻觉的风险。我们在数万亿个令牌上训练我们的模型，并表明可以仅使用公开可用的数据集来训练最先进的模型，而无需诉诸专有和不可访问的数据集。在大型语言模型空间中训练像 LLaMA 这样的小型基础模型是可取的，因为它需要更少的计算能力和资源来测试新方法、验证他人的工作和探索新的用例。作为 Meta 对开放科学承诺的一部分，今天我们公开发布 LLaMA（大型语言模型元 AI），这是一种最先进的基础大型语言模型，旨在帮助研究人员推进他们在 AI 子领域的工作。_llma

强化学习在制造业领域的应用：智能制造的未来-程序员宅基地

文章浏览阅读223次，点赞3次，收藏5次。1.背景介绍制造业是国家经济发展的重要引擎，其产能和质量对于国家经济的稳定和发展具有重要意义。随着工业技术的不断发展，制造业的生产方式也不断发生变化。传统的制造业通常依赖于人工操作和手工艺，这种方式的缺点是低效率、低产量和不稳定的质量。随着信息化、智能化和网络化等新技术的出现，制造业开始向智能制造迈出了第一步。智能制造的核心是通过大数据、人工智能、计算机视觉等技术，实现制造过程的智能化、自动化...

ansible--安装与使用_pip安装ansible-程序员宅基地

文章浏览阅读938次。系列文章目录文章目录系列文章目录前言一、ansible是什么？二、使用步骤 1.引入库 2.读入数据总结前言菜鸟一只，刚开始使用，仅作以后参考使用。边学习，边记录，介绍一下最基础的使用，可能会有理解不到位的地方，可以共同交流，废话不多说，走起。一、ansible 简介？ansible是自动化运维工具的一种，基于Python开发，可以实现批量系统配置，批量程序部署，批量运行命令，ansible是基于模块工作的，它本身没有批量部署的能力，真正.._pip安装ansible