10、STL实用技术专题

超、凢脫俗 2022-05-19 00:21 137阅读 0赞

# **10、STL实用技术专题** #

## **10.1STL(标准模板库)理论基础** ##

### **10.1.1基本概念** ###

#include <iostream>
 #include <vector>
 #include <algorithm>
 
 using namespace std;
 
 //容器中 装 基础数据类型变量
 void main01()
 {
 	vector<int> v1; //容器：把你的元素拷贝到容器中
 
 	v1.push_back(-1);
 	v1.push_back(1);
 	v1.push_back(3);
 	v1.push_back(5);
 	v1.push_back(3);
 
 	// 1 3 5
 	//▲
 	//2迭代器: 相当于一个指针 分类
 	for (vector<int>::iterator it = v1.begin(); it !=v1.end(); it++)
 	{
 		cout << "*it" << *it << " ";
 	}
 
 	//3 算法 算法和迭代器 进行无缝的连接
 	int num1 = count(v1.begin(),v1.end(),3);
 	cout << "num1:" << num1 << endl;
 
 	system("pause");
 }
 
 class Teacher
 {
 public:
 	int age;
 	char name[64];
 public:
 	void printT()
 	{
 		cout << "age: " << age << endl;
 	}
 };
 //容器中 装 元素
 void main()
 {
 	Teacher t1, t2, t3;
 	t1.age = 31;
 	t2.age = 32;
 	t3.age = 33;
 
 	vector<Teacher> v2; 
 	// 1容器: 把你的元素copy到容器中 //容器实现了 数据类型 和算法的有效分离
 	v2.push_back(t1);
 	v2.push_back(t2);
 	v2.push_back(t3);
 	for (vector<Teacher>::iterator it = v2.begin(); it != v2.end(); it++)
 	{
 		cout << it->age << " ";
 	}
 
 	Teacher *p1, *p2, *p3;
 	p1 = &t1;
 	p2 = &t2;
 	p3 = &t3;
 
 	// 1容器: 把t1 t2 t3内存首地址 放入到了容器
 	vector<Teacher *> v1;
 	v1.push_back(p1);
 	v1.push_back(p2);
 	v1.push_back(p3);
 
 	// p1 p2 p3
 	// ▲
 	//2迭代器: 相当于一个指针 分类
 
 	for (vector<Teacher *>::iterator it =v1.begin(); it!=v1.end(); it++)
 	{
 		cout << (*it)->age << endl;
 	}
 	system("pause");
 }

STL（Standard Template Library，标准模板库)是惠普实验室开发的一系列软件的统称。现然主要出现在C++中，但在被引入C++之前该技术就已经存在了很长的一段时间。

STL的从广义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器），容器和算法通过迭代器可以进行无缝地连接。几乎所有的代码都采用了模板类和模板函数的方式，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。在C++标准中，STL被组织为下面的13个头文件：<algorithm>、<deque>、<functional>、<iterator>、<vector>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack>和<utility>。

![70][]

STL详细的说六大组件

*   *  容器（Container）
     *  算法（Algorithm）
     *  迭代器（Iterator）
     *  仿函数（Function object）
     *  适配器（Adaptor）
     *  空间配制器（allocator）

**使用****STL****的好处**

1）STL是C++的一部分，因此不用额外安装什么，它被内建在你的编译器之内。

2）***STL的一个重要特点是数据结构和算法的分离***。尽管这是个简单的概念，但是这种分离确实使得STL变得非常通用。

例如，在STL的vector容器中，可以放入元素、基础数据类型变量、元素的地址；

***STL的sort()函数可以用来操作vector,list等容器。***

1.  程序员可以不用思考STL具体的实现过程，只要能够熟使用STL就OK了。这样他们就可以把精力放在程序开发的别的方面。
2.  STL具有高可重用性，高性能，高移植性，跨平台的优点。

高可重用性：STL中几乎所有的代码都采用了模板类和模版函数的方式实现，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。关于模板的知识，已经给大家介绍了。

高性能：如map可以高效地从十万条记录里面查找出指定的记录，**因为map是采用红黑树的变体实现的**。(红黑树是平横二叉树的一种)

高移植性：如在项目A上用STL编写的模块，可以直接移植到项目B上。

跨平台：如用windows的Visual Studio编写的代码可以在Mac OS的XCode上直接编译。

1.  程序员可以不用思考STL具体的实现过程，只要能够熟练使用STL就OK了。这样他们就可以把精力放在程序开发的别的方面。
2.  了解到STL的这些好处，我们知道STL无疑是最值得C++程序员骄傲的一部分。每一个C＋＋程序员都应该好好学习STL。只有能够熟练使用STL的程序员，才是好的C++程序员。
3.  总之：招聘工作中，经常遇到C++程序员对STL不是非常了解。大多是有一个大致的映像，而对于在什么情况下应该使用哪个容器和算法都感到比较茫然。**STL****是****C++****程序员的一项不可或缺的基本技能**，掌握它对提升C++编程大有裨益。

### **10.1.2容器** ###

在实际的开发过程中，数据结构本身的重要性不会逊于操作于数据结构的算法的重要性，当程序中存在着对时间要求很高的部分时，数据结构的选择就显得更加重要。

经典的数据结构数量有限，但是我们常常重复着一些为了实现向量、链表等结构而编写的代码，这些代码都十分相似，只是为了适应不同数据的变化而在 细节上有所出入。STL容器就为我们提供了这样的方便，它允许我们重复利用已有的实现构造自己的特定类型下的数据结构，通过设置一些模板，STL容器对最常用的数据结构提供了支持，这些模板的参数允许我们指定容器中元素的数据类型，可以将我们许多重复而乏味的工作简化。

容器部分主要由头文 件<vector>,<list>,<deque>,<set>,<map>,<stack> 和<queue>组成。对于常用的一些容器和容器适配器（可以看作由其它容器实现的容器），可以通过下表总结一下它们和相应头文件的对应关系。

**10.1.2.1容器的概念**

用来管理一组元素

![70 1][]

**10.1.2.2容器的分类**

序列式容器（Sequence containers）

每个元素都有固定位置－－取决于插入时机和地点，和元素值无关。

*vector**、deque、list*

关联式容器（Associated containers）

元素位置取决于特定的排序准则，和插入顺序无关

*set**、multiset、map、multimap*

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;width:106.8pt;"> 数据结构 </td> 
 <td style="vertical-align:top;width:231.75pt;"> 描述 </td> 
 <td style="vertical-align:top;width:87.55pt;"> 实现头文件 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.8pt;"> 向量(vector) </td> 
 <td style="vertical-align:top;width:231.75pt;"> 连续存储的元素 </td> 
 <td style="vertical-align:top;width:87.55pt;"> &lt;vector&gt; </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.8pt;"> 列表(list) </td> 
 <td style="vertical-align:top;width:231.75pt;"> 由节点组成的双向链表，每个结点包含着一个元素 </td> 
 <td style="vertical-align:top;width:87.55pt;"> &lt;list&gt; </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.8pt;"> 双队列(deque) </td> 
 <td style="vertical-align:top;width:231.75pt;"> 连续存储的指向不同元素的指针所组成的数组 </td> 
 <td style="vertical-align:top;width:87.55pt;"> &lt;deque&gt; </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.8pt;"> 集合(set) </td> 
 <td style="vertical-align:top;width:231.75pt;"> 由节点组成的红黑树，每个节点都包含着一个元素，节点之间以某种作用于元素对的谓词排列，没有两个不同的元素能够拥有相同的次序 </td> 
 <td style="vertical-align:top;width:87.55pt;"> &lt;set&gt; </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.8pt;"> 多重集合(multiset) </td> 
 <td style="vertical-align:top;width:231.75pt;"> 允许存在两个次序相等的元素的集合 </td> 
 <td style="vertical-align:top;width:87.55pt;"> &lt;set&gt; </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.8pt;"> 栈(stack) </td> 
 <td style="vertical-align:top;width:231.75pt;"> 后进先出的值的排列 </td> 
 <td style="vertical-align:top;width:87.55pt;"> &lt;stack&gt; </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.8pt;"> 队列(queue) </td> 
 <td style="vertical-align:top;width:231.75pt;"> 先进先出的值的排列 </td> 
 <td style="vertical-align:top;width:87.55pt;"> &lt;queue&gt; </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.8pt;"> 优先队列(priority_queue) </td> 
 <td style="vertical-align:top;width:231.75pt;"> 元素的次序是由作用于所存储的值对上的某种谓词决定的的一种队列 </td> 
 <td style="vertical-align:top;width:87.55pt;"> &lt;queue&gt; </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.8pt;"> 映射(map) </td> 
 <td style="vertical-align:top;width:231.75pt;"> 由{键，值}对组成的集合，以某种作用于键对上的谓词排列 </td> 
 <td style="vertical-align:top;width:87.55pt;"> &lt;map&gt; </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.8pt;"> 多重映射(multimap) </td> 
 <td style="vertical-align:top;width:231.75pt;"> 允许键对有相等的次序的映射 </td> 
 <td style="vertical-align:top;width:87.55pt;"> &lt;map&gt; </td> 
 </tr> 
 </tbody> 
</table>

### **10.1.3迭代器** ###

迭代器从作用上来说是最基本的部分，可是理解起来比前两者都要费力一些。软件设计有一个基本原则，所有的问题都可以通过引进一个间接层来简化，这种简化在STL中就是用迭代器来完成的。概括来说，迭代器在STL中用来将算法和容器联系起来，起着一种黏和剂的作用。几乎STL提供的所有算法都是通过迭代器存取元素序列进行工作的，每一个容器都定义了其本身所专有的迭代器，用以存取容器中的元素。

迭代器部分主要由头文件<utility>,<iterator>和<memory>组成。<utility>是一个很小的头文件，它包括了贯穿使用在STL中的几个模板的声明，<iterator>中提供了迭代器使用的许多方法，而对于<memory>的描述则十分的困难，它以不同寻常的方式为容器中的元素分配存储空间，同时也为某些算法执行期间产生的临时对象提供机制,<memory>中的主要部分是模板类allocator，它负责产生所有容器中的默认分配器。

### **10.1.4算法** ###

函数库对数据类型的选择对其可重用性起着至关重要的作用。举例来说，一个求方根的函数，在使用浮点数作为其参数类型的情况下的可重用性肯定比使用整型作为它的参数类性要高。而C++通过模板的机制允许推迟对某些类型的选择，直到真正想使用模板或者说对模板进行特化的时候，STL就利用了这一点提供了相当多的有用算法。它是在一个有效的框架中完成这些算法的——可以将所有的类型划分为少数的几类，然后就可以在模版的参数中使用一种类型替换掉同一种类中的其他类型。

STL提供了大约100个实现算法的模版函数，比如算法for\_each将为指定序列中的每一个元素调用指定的函数，stable\_sort以你所指定的规则对序列进行稳定性排序等等。这样一来，只要熟悉了STL之后，许多代码可以被大大的化简，只需要通过调用一两个算法模板，就可以完成所需要的功能并大大地提升效率。

算法部分主要由头文件<algorithm>，<numeric>和<functional>组成。<algorithm>是所有STL头文件中最大的一个（尽管它很好理解），它是由一大堆模版函数组成的，可以认为每个函数在很大程度上都是独立的，其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、移除、反转、排序、合并等等。<numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。<functional>中则定义了一些模板类，用以声明函数对象。

### **10.1.5C++标准库** ###

C++强大的功能来源于其丰富的类库及库函数资源。C++标准库的内容总共在50个标准头文件中定义。在C++开发中，要尽可能地利用标准库完成。这样做的直接好处包括：（1）成本：已经作为标准提供，何苦再花费时间、人力重新开发呢；（2）质量：标准库的都是经过严格测试的，正确性有保证；（3）效率：关于人的效率已经体现在成本中了，关于代码的执行效率要相信实现标准库的大牛们的水平；（4）良好的编程风格：采用行业中普遍的做法进行开发。

在C++程序设计课程中，尤其是作为第一门程序设计课程，我们注重了语法、语言的机制等方面的内容。程序设计能力的培养有个过程，跨过基本的原理性知识直接进入到工程中的普遍做法，由于跨度决定了其难度。再者，在掌握了基本原理的基础上，在认识标准库的问题上完全可以凭借实践，逐步地掌握。标准库的学习不需要认认真真地读书，需要的是在了解概貌的情况下，在实践中深入。

这个任务就是要知道C++程序设计课程中不讲的，但对程序设计又很重要的这部分内容。至少我们要能先回答出“有什么”的问题。

C++标准库的内容分为10类，分别是（建议在阅读中，将你已经用过或听说过的头文件划出来）：

C1. 标准库中与语言支持功能相关的头文件

<table> 
 <thead> 
 <tr> 
 <td style="vertical-align:top;"> 头文件 </td> 
 <td style="vertical-align:top;"> 描&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 述 </td> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> &lt;cstddef&gt; </td> 
 <td style="vertical-align:top;"> 定义宏NULL和offsetof，以及其他标准类型size_t和ptrdiff_t。与对应的标准C头文件的区别是，NULL是C++空指针常量的补充定义，宏offsetof接受结构或者联合类型参数，只要他们没有成员指针类型的非静态成员即可。 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;limits&gt; </td> 
 <td style="vertical-align:top;"> 提供与基本数据类型相关的定义。例如，对于每个数值数据类型，它定义了可以表示出来的最大值和最小值以及二进制数字的位数。 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;climits&gt; </td> 
 <td style="vertical-align:top;"> 提供与基本整数数据类型相关的C样式定义。这些信息的C++样式定义在&lt;limits&gt;中 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;cfloat&gt; </td> 
 <td style="vertical-align:top;"> 提供与基本浮点型数据类型相关的C样式定义。这些信息的C++样式定义在&lt;limits&gt;中 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;cstdlib&gt; </td> 
 <td style="vertical-align:top;"> 提供支持程序启动和终止的宏和函数。这个头文件还声明了许多其他杂项函数，例如搜索和排序函数，从字符串转换为数值等函数。它与对应的标准C头文件 stdlib.h不同，定义了abort(void)。abort()函数还有额外的功能，它不为静态或自动对象调用析构函数，也不调用传给 atexit()函数的函数。它还定义了exit()函数的额外功能，可以释放静态对象，以注册的逆序调用用atexit()注册的函数。清除并关闭所有 打开的C流，把控制权返回给主机环境。 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;new&gt; </td> 
 <td style="vertical-align:top;"> 支持动态内存分配 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;typeinfo&gt; </td> 
 <td style="vertical-align:top;"> 支持变量在运行期间的类型标识 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;exception&gt; </td> 
 <td style="vertical-align:top;"> 支持异常处理，这是处理程序中可能发生的错误的一种方式 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;cstdarg&gt; </td> 
 <td style="vertical-align:top;"> 支持接受数量可变的参数的函数。即在调用函数时，可以给函数传送数量不等的数据项。它定义了宏va_arg、va_end、va_start以及va_list类型 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;csetjmp&gt; </td> 
 <td style="vertical-align:top;"> 为C样式的非本地跳跃提供函数。这些函数在C++中不常用 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;csignal&gt; </td> 
 <td style="vertical-align:top;"> 为中断处理提供C样式支持 </td> 
 </tr> 
 </tbody> 
</table>

C2. 支持流输入/输出的头文件

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> 头文件 </td> 
 <td style="vertical-align:top;"> 描&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 述 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;iostream&gt; </td> 
 <td style="vertical-align:top;"> 支持标准流cin、cout、cerr和clog的输入和输出，它还支持多字节字符标准流wcin、wcout、wcerr和wclog。 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;iomanip&gt; </td> 
 <td style="vertical-align:top;"> 提供操纵程序，允许改变流的状态，从而改变输出的格式。 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;ios&gt; </td> 
 <td style="vertical-align:top;"> 定义iostream的基类 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;istream&gt; </td> 
 <td style="vertical-align:top;"> 为管理输出流缓存区的输入定义模板类 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;ostream&gt; </td> 
 <td style="vertical-align:top;"> 为管理输出流缓存区的输出定义模板类 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;sstream&gt; </td> 
 <td style="vertical-align:top;"> 支持字符串的流输入输出 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;fstream&gt; </td> 
 <td style="vertical-align:top;"> 支持文件的流输入输出 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;iosfwd&gt; </td> 
 <td style="vertical-align:top;"> 为输入输出对象提供向前的声明 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;streambuf&gt; </td> 
 <td style="vertical-align:top;"> 支持流输入和输出的缓存 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;cstdio&gt; </td> 
 <td style="vertical-align:top;"> 为标准流提供C样式的输入和输出 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;cwchar&gt; </td> 
 <td style="vertical-align:top;"> 支持多字节字符的C样式输入输出 </td> 
 </tr> 
 </tbody> 
</table>

C3. 与诊断功能相关的头文件

C4. 定义工具函数的头文件

C5. 支持字符串处理的头文件

<table style="width:472.25pt;"> 
 <thead> 
 <tr> 
 <td style="vertical-align:top;"> 头文件 </td> 
 <td style="vertical-align:top;"> 描&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 述 </td> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> &lt;string&gt; </td> 
 <td style="vertical-align:top;"> 为字符串类型提供支持和定义，包括单字节字符串(由char组成)的string和多字节字符串(由wchar_t组成) </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;cctype&gt; </td> 
 <td style="vertical-align:top;"> 单字节字符类别 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;cwctype&gt; </td> 
 <td style="vertical-align:top;"> 多字节字符类别 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;cstring&gt; </td> 
 <td style="vertical-align:top;"> 为处理非空字节序列和内存块提供函数。这不同于对应的标准C库头文件，几个C样式字符串的一般C库函数被返回值为const和非const的函数对替代了 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;cwchar&gt; </td> 
 <td style="vertical-align:top;"> 为处理、执行I/O和转换多字节字符序列提供函数，这不同于对应的标准C库头文件，几个多字节C样式字符串操作的一般C库函数被返回值为const和非const的函数对替代了。 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;cstdlib&gt; </td> 
 <td style="vertical-align:top;"> 为把单字节字符串转换为数值、在多字节字符和多字节字符串之间转换提供函数 </td> 
 </tr> 
 </tbody> 
</table>

C6. 定义容器类的模板的头文件

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;"> &lt;vector&gt; </td> 
 <td style="vertical-align:top;"> 定义vector序列模板，这是一个大小可以重新设置的数组类型，比普通数组更安全、更灵活 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;list&gt; </td> 
 <td style="vertical-align:top;"> 定义list序列模板，这是一个序列的链表，常常在任意位置插入和删除元素 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;deque&gt; </td> 
 <td style="vertical-align:top;"> 定义deque序列模板，支持在开始和结尾的高效插入和删除操作 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;queue&gt; </td> 
 <td style="vertical-align:top;"> 为队列(先进先出)数据结构定义序列适配器queue和priority_queue </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;stack&gt; </td> 
 <td style="vertical-align:top;"> 为堆栈(后进先出)数据结构定义序列适配器stack </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;map&gt; </td> 
 <td style="vertical-align:top;"> map是一个关联容器类型，允许根据键值是唯一的，且按照升序存储。multimap类似于map，但键不是唯一的。 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;set&gt; </td> 
 <td style="vertical-align:top;"> set是一个关联容器类型，用于以升序方式存储唯一值。multiset类似于set，但是值不必是唯一的。 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;"> &lt;bitset&gt; </td> 
 <td style="vertical-align:top;"> 为固定长度的位序列定义bitset模板，它可以看作固定长度的紧凑型bool数组 </td> 
 </tr> 
 </tbody> 
</table>

C7. 支持迭代器的头文件

C8. 有关算法的头文件

C9. 有关数值操作的头文件

C10. 有关本地化的头文件

C++标准库的所有头文件都没有扩展名。C++标准库以<cname>形式的标准头文件提供。在<cname>形式标准的头文件中，与宏相关的名称在全局作用域中定义，其他名称在std命名空间中声明。在C++中还可以使用name.h 形式的标准C库头文件名

### **10.1.6模板简要回顾** ###

*  模板是实现代码重用机制的一种工具，实质就是实现类型参数化，即把类型定义为参数。
 *  C++提供两种模板：函数模板，类模板

函数模板的简介

*  函数模板就是建立一个通用的函数，其函数返回类型和形参类型不具体指定，而是用虚拟的类型来代表。
 *  凡是函数体相同的函数都可以用函数模板来代替，不必定义多个函数，只需在模板中定义一次即可。
 *  在调用函数时系统会根据实参的类型来取代模板中的虚拟类型，从而实现了不同函数的功能。

类模板的简介

*  我们先来看一下下面这个类，求最大值的类
 *  和函数模板一样，类模板就是建立一个通用类，其数据成员的类型、成员函数的返回类型和参数类形都可以不具体指定，而用虚拟的类型来代表。
 *  当使用类模板建立对象时，系统会根据实参的类型取代类模板中的虚拟类型，从而实现不同类的功能。

### 10.2.2Vector容器 ###

1Vector容器简介

*  vector是将元素置于一个动态数组中加以管理的容器。
 *  vector可以随机存取元素（支持索引值直接存取，用\[\]操作符或at()方法，这个等下会详讲）。

**vector尾部添加或移除元素非常快速。但是在中部或头部插入元素或移除元素比较费时**

2vector对象的默认构造

***vector采用模板类实现，vector对象的默认构造形式***

***vector<T> vecT;***

**vector<int> vecInt; **         //一个存放int的vector容器。

vector<float> vecFloat;     //一个存放float的vector容器。

vector<string> vecString;     //一个存放string的vector容器。

...                                     //尖括号内还可以设置指针类型或自定义类型。

Class CA\{\};

vector<CA\*> vecpCA;               //用于存放CA对象的指针的vector容器。

vector<CA> vecCA;             //用于存放CA对象的vector容器。**由于容器元素的存放是按值复制的方式**进行的，所以此时CA必须提供CA的拷贝构造函数，以保证CA对象间拷贝正常。

3vector对象的带参数构造

理论知识

*  vector(beg,end);    //构造函数将\[beg, end)区间中的元素拷贝给本身。注意该区间是**左闭右开的区间。**
 *  vector(n,elem);   //构造函数将n个elem拷贝给本身。
 *  vector(const vector &vec);  //拷贝构造函数

int  iArray\[\] = \{0,1,2,3,4\};

vector<int>  vecIntA( iArray,  iArray+5 );

vector<int> vecIntB (  vecIntA.begin() , vecIntA.end()  );   //用构造函数初始化容器vecIntB

vector<int> vecIntB (  vecIntA.begin() , vecIntA.begin()+3  );

vector<int> vecIntC(3,9); //此代码运行后，容器vecIntB就存放3个元素，每个元素的值是9。

vector<int> vecIntD(vecIntA);

**4vector的赋值**

理论知识

*  vector.assign(beg,end);    //将\[beg, end)区间中的数据拷贝赋值给本身。注意该区间是左闭右开的区间。
 *  vector.assign(n,elem);  //将n个elem拷贝赋值给本身。
 *  vector& operator=(const vector  &vec);          //重载等号操作符
 *  vector.swap(vec);  // 将vec与本身的元素互换。

vector<int> vecIntA,vecIntB,vecIntC,vecIntD;

int  iArray\[\] = \{0,1,2,3,4\};

vecIntA.assign(iArray,iArray+5);

vecIntB.assign( vecIntA.begin(),  vecIntA.end() );    //用其它容器的迭代器作参数。

vecIntC.assign(3,9);

vector<int> vecIntD;

vecIntD = vecIntA;

vecIntA.swap(vecIntD);

5vector的大小

理论知识

*  vector.size();         //返回容器中元素的个数
 *  vector.empty();     //判断容器是否为空
 *  vector.resize(num);   //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
 *  vector.resize(num, elem);  //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

例如   vecInt是vector<int>声明的容器，现已包含1,2,3元素。

int iSize = vecInt.size();             //iSize == 3;

bool bEmpty = vecInt.empty();         // bEmpty == false;

执行vecInt.resize(5);  //此时里面包含1,2,3,0,0元素。

再执行vecInt.resize(8,3);  //此时里面包含1,2,3,0,0,3,3,3元素。

再执行vecInt.resize(2);  //此时里面包含1,2元素。

**6vector末尾的添加移除操作**

vector<int> vecInt;

**vecInt.push\_back(1);  //在容器尾部加入一个元素**

vecInt.push\_back(3);  //移除容器中最后一个元素

vecInt.push\_back(5);

vecInt.push\_back(7);

vecInt.push\_back(9);

vecInt.pop\_back();

//\{5 ,7 ,9\}

**7vector的数据存取**

**理论知识**

**vec.at(idx); **   //返回索引idx所指的数据，如果idx越界，抛出out\_of\_range异常。

vec\[idx\];          //返回索引idx所指的数据，越界时，运行直接报错

vector<int> vecInt;    //假设包含1 ,3 ,5 ,7 ,9

vecInt.at(2) == vecInt\[2\] ;                 //5

vecInt.at(2) = 8;  或  vecInt\[2\] = 8;

vecInt 就包含 1, 3, 8, 7, 9值

int iF = vector.front();       //iF==1  vector头部元素

int iB = vector.back();       //iB==9 尾部元素

vector.front() = 11;  //vecInt包含\{11,3,8,7,9\}

vector.back() = 19;   //vecInt包含\{11,3,8,7,19\}

**8迭代器基本原理**

*  迭代器是一个“可遍历STL容器内全部或部分元素”的对象。
 *  迭代器指出容器中的一个特定位置。
 *  迭代器就如同一个指针。
 *  迭代器提供对一个容器中的对象的访问方法，并且可以定义了容器中对象的范围。
 *  这里大概介绍一下迭代器的类别。

**输入迭代器**：也有叫法称之为“只读迭代器”，它从容器中读取元素，只能一次读入一个元素向前移动，只支持一遍算法，同一个输入迭代器不能两遍遍历一个序列。

**输出迭代器**：也有叫法称之为“只写迭代器”，它往容器中写入元素，只能一次写入一个元素向前移动，只支持一遍算法，同一个输出迭代器不能两遍遍历一个序列。

**正向迭代器**：组合输入迭代器和输出迭代器的功能，还可以多次解析一个迭代器指定的位置，可以对一个值进行多次读/写。

**双向迭代器**：组合正向迭代器的功能，还可以通过--操作符向后移动位置。

随机访问迭代器：组合双向迭代器的功能，还可以向前向后跳过任意个位置，可以直接访问容器中任何位置的元素。

*  目前本系列教程所用到的容器，都支持双向迭代器或随机访问迭代器，下面将会详细介绍这两个类别的迭代器。

9双向迭代器与随机访问迭代器

双向迭代器支持的操作：

it++,  ++it,    it--,   --it，\*it， itA = itB，

itA == itB，itA != itB

其中list,set,multiset,map,multimap支持双向迭代器。

随机访问迭代器支持的操作：

在双向迭代器的操作基础上添加

it+=i， it-=i， it+i(或it=it+i)，it\[i\],

itA<itB,   itA<=itB,  itA>itB,  itA>=itB  的功能。

其中vector，deque支持随机访问迭代器。

10vector与迭代器的配合使用

![70 2][]

vector<int>  vecInt; //假设包含1,3,5,7,9元素

vector<int>::iterator it;            //声明容器vector<int>的迭代器。

it = vecInt.begin();    // \*it == 1

\++it;                             //或者it++;  \*it == 3  ，前++的效率比后++的效率高，前++返回引用，后++返回值。

it += 2;               //\*it == 7

it = it+1;            //\*it == 9

\++it;                             // it == vecInt.end();  此时不能再执行\*it,会出错!

正向遍历：

for(vector<int>::iterator it=vecInt.begin(); it!=vecInt.end(); ++it)

int iItem = \*it;

cout << iItem;    //或直接使用  cout << \*it;

这样子便打印出1 3 5 7 9

逆向遍历：

for(vector<int>::reverse\_iterator rit=vecInt.rbegin(); rit!=vecInt.rend(); ++rit)    //注意，小括号内仍是++rit

int iItem  = \*rit;

cout << iItem;      //或直接使用cout << \*rit;

此时将打印出9,7,5,3,1

注意，这里迭代器的声明采用vector<int>::reverse\_iterator，而非vector<int>::iterator。

迭代器还有其它两种声明方法：

vector<int>::const\_iterator 与vector<int>::const\_reverse\_iterator

以上两种分别是vector<int>::iterator 与vector<int>::reverse\_iterator 的只读形式，使用这两种迭代器时，不会修改到容器中的值。

备注：不过容器中的insert和erase方法仅接受这四种类型中的iterator，其它三种不支持。《Effective STL》建议我们尽量使用iterator取代const\_iterator、reverse\_iterator和const\_reverse\_iterator。

11vector的插入

理论知识

*  vector.insert(pos,elem);   //在pos位置插入一个elem元素的拷贝，返回新数据的位置。
 *  vector.insert(pos,n,elem);   //在pos位置插入n个elem数据，无返回值。
 *  vector.insert(pos,beg,end);   //在pos位置插入\[beg,end)区间的数据，无返回值

简单案例

vector<int> vecA;

vector<int> vecB;

vecA.push\_back(1);

vecA.push\_back(3);

vecA.push\_back(5);

vecA.push\_back(7);

vecA.push\_back(9);

vecB.push\_back(2);

vecB.push\_back(4);

vecB.push\_back(6);

vecB.push\_back(8);

vecA.insert(vecA.begin(), 11);                   //\{11, 1, 3, 5, 7, 9\}

vecA.insert(vecA.begin()+1,2,33);           //\{11,33,33,1,3,5,7,9\}

vecA.insert(vecA.begin() , vecB.begin() , vecB.end() );   //\{2,4,6,8,11,33,33,1,3,5,7,9\}

12vector的删除

理论知识

*  vector.clear();    //移除容器的所有数据
 *  vec.erase(beg,end);  //删除\[beg,end)区间的数据，返回下一个数据的位置。
 *  vec.erase(pos);    //删除pos位置的数据，返回下一个数据的位置。

简单案例:

删除区间内的元素

vecInt是用vector<int>声明的容器，现已包含按顺序的1,3,5,6,9元素。

vector<int>::iterator itBegin=vecInt.begin()+1;

vector<int>::iterator itEnd=vecInt.begin()+2;

vecInt.erase(itBegin,itEnd);

//此时容器vecInt包含按顺序的1,6,9三个元素。

假设 vecInt 包含1,3,2,3,3,3,4,3,5,3，删除容器中等于3的元素

for(vector<int>::iterator it=vecInt.being(); it!=vecInt.end(); )    //小括号里不需写  ++it

if(\*it == 3)

it  =  vecInt.erase(it);       //以迭代器为参数，删除元素3，并把数据删除后的下一个元素位置返回给迭代器。

//此时，不执行  ++it；

else

++it;

//删除vecInt的所有元素

vecInt.clear();                    //容器为空

13vector小结

这一讲，主要讲解如下要点：

容器的简介，容器的分类，各个容器的数据结构

vector,deque,list,set,multiset,map,multimap

容器vector的具体用法（包括迭代器的具体用法）。

vertor简介，vector使用之前的准备，vector对象的默认构造，vector末尾的添加移除操作，vector的数据存取，迭代器的简介，双向迭代器与随机访问迭代器

vector与迭代器的配合使用，vector对象的带参数构造，vector的赋值，vector的大小，vector的插入，vector的删除。

#include <iostream>
 using namespace std;
 #include "string"
 #include "algorithm"
 
 //string的初始化
 void main01()
 {
 	string s1 = "aaaa";
 	string s2("bbbb");
 	string s3 = s2; //通过拷贝构造函数 来初始化对象s3
 	string s4(10, 'a');
 
 	cout << "s1:" << s1 << endl;
 	cout << "s2:" << s2 << endl;
 	cout << "s3:" << s3 << endl;
 	cout << "s4:" << s4 << endl;
 }
 
 //string的 遍历
 void main02()
 {
 	string s1 = "abcdefg";
 	//int length() const; //返回当前字符串的长度。长度不包括字符串结尾的'\0'。
 	//1 数组方式
 	for (int i = 0; i<s1.length(); i++)
 	{
 		cout << s1[i] << " ";
 	}
 	cout << endl;
 
 	//2 迭代器
 	for (string::iterator it = s1.begin(); it != s1.end(); it++)
 	{
 		cout << *it << " ";
 	}
 	cout << endl;
 	//	operator[]和at()均返回当前字符串中第n个字符，但二者是有区别的。
 	//	主要区别在于at()在越界时会抛出异常，[]在刚好越界时会返回(char)0，再继续越界时，编译器直接出错。如果你的程序希望可以通过try, catch捕获异常，建议采用at()
 	try
 	{
 		for (int i = 0; i<s1.length() + 3; i++)
 		{
 			cout << s1.at(i) << " "; //抛出异常
 		}
 	}
 	catch (...)
 	{
 		cout << "发生异常\n";
 	}
 
 	cout << "at之后" << endl;
 	
 	try
 	{
 		for (int i=0; i<s1.length() + 3; i++)
 		{
 			cout << s1[i] << " "; //出现错误 不向外面抛出异常 引起程序的中断
 		}
 	}
 	catch ( ... )
 	{
 	cout << "发生异常\n" ;
 	}
 	
 
 }
 
 //字符指针和string的转换
 void main03()
 {
 	string s1 = "aaabbbb";
 	//const char *c_str() const; //返回一个以'\0'结尾的字符串的首地址
 	//1 s1===>char *
 	printf("s1:%s \n", s1.c_str());
 
 	//2 char *====>sting 
 
 	//	int copy(char *s, int n, int pos = 0) const;
 	//把当前串中以pos开始的n个字符拷贝到以s为起始位置的字符数组中，返回实际拷贝的数目。注意要保证s所指向的空间足够大以容纳当前字符串，不然会越界
 
 	//3 s1的内容 copy buf中
 	char buf1[128] = {0};
 	s1.copy(buf1, 3, 0); //注意 只给你copy3个字符 不会变成C风格的字符串
 	cout << "buf1:" << buf1 << endl; 
 }
 
 //字符串的 连接
 void main04()
 {
 	string s1 = "aaa";
 	string s2 = "bbb";
 	s1 = s1 + s2;
 	cout << "s1:" << s1 << endl;
 
 	string s3 = "333";
 	string s4 = "444";
 	//string &append(const char *s); //把字符串s连接到当前字符串结尾
 	s3.append(s4);
 	cout << "s3:" << s3 << endl;
 	
 	system("pause");
 }

#include <iostream>
 using namespace std;
 #include "string"
 #include "algorithm"
 
 
 //字符串的查找和替换
 void main05()
 {
 	string s1 = "wbm hello wbm 111 wbm 222 wbm 333 ";
 	//			 ▲
 	//第一次 出现wbm index
 	//查找
 	//	int find(char c, int pos = 0) const; //从pos开始查找字符c在当前字符串的位置
 	//int find(const char *s, int pos = 0) const; //从pos开始查找字符串s在当前字符串的位置
 	//int find(const string &s, int pos = 0) const; //从pos开始查找字符串s在当前字符串中的位置
 	//find函数如果查找不到，就返回 - 1
 
 	int index = s1.find("wbm", 0); //位置下标 从0开始
 	cout << "index: " << index << endl;
 
 	//案例1 求wbm出现的次数 每一次出现的数组下标
 	int offindex = s1.find("wbm", 0);
 	while (offindex != string::npos)
 	{
 		cout << "offindex:" << offindex << endl;
 		offindex = offindex + 1;
 		offindex = s1.find("wbm", offindex); //wang bao ming 
 	}
 
 	//案例2 把小写wbm===>WBM
 	//替换
 	//string &replace(int pos, int n, const char *s);//删除从pos开始的n个字符，然后在pos处插入串s
 	//string &replace(int pos, int n, const string &s); //删除从pos开始的n个字符，然后在pos处插入串s
 
 	string s3 = "aaa bbb ccc";
 	s3.replace(0, 3, "AAA");
 	cout << "s3" << s3 << endl;
 	//string::npos作为string的成员函数的一个长度参数时，表示“直到字符串结束
 	offindex = s1.find("wbm", 0);
 	while (offindex != string::npos)
 	{
 		cout << "offindex:" << offindex << endl;
 		s1.replace(offindex, 3, "WBM");
 		offindex = offindex + 1;
 		offindex = s1.find("wbm", offindex); //
 	}
 
 	cout << "s1替换后的结果: " << s1 << endl;
 
 	cout << "hello..." << endl;
 	system("pause");
 	return;
 }
 
 
 //截断（区间删除）和插入
 void main06()
 {
 	string s1 = "hello1 hello2 hello1";
 	//_InIt find(_InIt _First, _InIt _Last, const _Ty& _Val)
 	string::iterator it = find(s1.begin(), s1.end(), 'l');
 	if (it != s1.end())
 	{
 		s1.erase(it);//string &erase(int pos=0, int n=npos); //删除pos开始的n个字符，返回修改后的字符串
 	}
 	cout << "s1删除l以后的结果:" << s1 << endl;
 
 	s1.erase(s1.begin(), s1.end());
 	cout << "s1全部删除:" << s1 << endl;
 	cout << "s1长度 " << s1.length() << endl;
 
 	string s2 = "BBB";
 	//string &insert(int pos, const char *s);
 	//string &insert(int pos, const string &s);
 	//前两个函数在pos位置插入字符串s
 	//string &insert(int pos, int n, char c); //在pos位置插入n个字符c
 
 	s2.insert(0, "AAA"); // 头插法
 	s2.insert(s2.length(), "CCC");
 
 	cout << s2 << endl;
 }
 
 void main()
 {
 	string s1 = "AAAbbb";
 	//1函数的入口地址 2函数对象 3预定义的函数对象
 	transform(s1.begin(), s1.end(), s1.begin(), toupper);
 	cout << "s1" << s1 << endl;
 
 	string s2 = "AAAbbb";
 	transform(s2.begin(), s2.end(), s2.begin(), tolower);
 	cout << "s2:" << s2 << endl;
 
 }

#include <iostream>
 using namespace std;
 #include <vector>
 
 //数组元素的 添加与删除
 void main01()
 {
 	vector<int> v1;
 	cout << "length:" << v1.size() << endl;
 	v1.push_back(1);
 	v1.push_back(3);
 	v1.push_back(5);
 	cout << "lenth:" << v1.size() << endl;
 
 	cout << "头部元素" << v1.front() << endl;
 
 
 	//修改 头部元素
 	//函数返回值当左值 应该返回一个引用
 	v1.front() = 11;
 	v1.back() = 55;
 
 	while (v1.size() > 0)
 	{
 		cout << "尾部元素:" << v1.back() << endl;
 		v1.pop_back();//删除尾部元素
 	}
 
 
 
 	system("pause");
 }
 //vector初始化
 void main02()
 {
 	vector<int> v1;
 	v1.push_back(1);
 	v1.push_back(3);
 	v1.push_back(5);
 	v1.push_back(7);
 	//对象初始化
 	vector<int> v2 = v1;
 	vector<int> v3(v1.begin(),v1.end()+2);
 
 }
 
 void printV(vector<int> &v)
 {
 	for (int i = 0; i<v.size(); i++)
 	{
 		cout << v[i] << " ";
 	}
 }
 
 //vector的遍历 通过数组的方式 
 void main03()
 {
 	vector<int> v1(10); //提前把内存准备好
 
 	for (int i = 0; i<10; i++)
 	{
 		v1[i] = i + 1;
 	}
 
 	// 	for (int i=0; i<10; i++)
 	// 	{
 	// 		printf("%d ", v1[i]);
 	// 	}
 
 	printV(v1);
 
 }
 
 //push_back的强化记忆
 void main04()
 {
 	vector<int> v1(10); //提前把内存准备好
 	v1.push_back(100);//尾部添加元素
 	v1.push_back(200);
 	cout << "size: " << v1.size() << endl;
 	printV(v1);
 
 	system("pause");
 }
 
 //1迭代器 end()的理解 
 // 1	3	5
 //	 ▲	
 //	 ▲
 //当 it == v1.end()的时候 说明这个容器已经遍历完毕了...
 //end()的位置 应该是 5的后面
 
 void main05()
 {
 	vector<int> v1(10);
 	for (int i = 0; i<10; i++)
 	{
 		v1[i] = i + 1;
 	}
 
 	//正向遍历
 	for (vector<int>::iterator it = v1.begin(); it != v1.end(); it++)
 	{
 		cout << *it << " ";
 	}
 
 	//逆序遍历
 	for (vector<int>::reverse_iterator rit = v1.rbegin(); rit != v1.rend(); rit++)
 	{
 		cout << *rit << " ";
 	}
 
 }
 
 
 //vector 删除
 void main()
 {
 	vector<int> v1(10);
 	for (int i = 0; i<10; i++)
 	{
 		v1[i] = i + 1;
 	}
 
 	//区间删除
 	v1.erase(v1.begin(), v1.begin() + 3);
 	printV(v1);
 
 	//根据元素的位置 指定位置删除
 	v1.erase(v1.begin()); //在头部删除一个元素
 	printV(v1);
 
 	cout << endl;
 
 	//根据元素的值 
 	v1[1] = 2;
 	v1[3] = 2;
 	printV(v1);
 
 	for (vector<int>::iterator it = v1.begin(); it != v1.end();)
 	{
 		if (*it == 2)
 		{
 			it = v1.erase(it); //当 删除迭代器所指向的元素的时候,erase删除函数会让it自动下移动
 		}
 		else
 		{
 			it++;
 		}
 	}
 	printV(v1);
 
 	cout << endl;
 	v1.insert(v1.begin(), 100);
 	v1.insert(v1.end(), 200);
 	printV(v1);
 
 }

### 10.2.3Deque容器 ###

Deque简介

* deque是“double-ended queue”的缩写，和vector一样都是STL的容器，deque是双端数组，而vector是单端的。
 * deque在接口上和vector非常相似，在许多操作的地方可以直接替换。
 * deque可以随机存取元素（支持索引值直接存取，用\[\]操作符或at()方法，这个等下会详讲）。
 * deque头部和尾部添加或移除元素都非常快速。但是在中部安插元素或移除元素比较费时。
 * \#include <deque>

deque对象的默认构造

deque采用模板类实现，deque对象的默认构造形式：deque<T> deqT;

deque <int> deqInt;            //一个存放int的deque容器。

deque <float> deq Float;     //一个存放float的deque容器。

deque <string> deq String;     //一个存放string的deque容器。

...

//尖括号内还可以设置指针类型或自定义类型。

deque末尾的添加移除操作

理论知识:

*  deque.push\_back(elem);   //在容器尾部添加一个数据
 *  deque.push\_front(elem);  //在容器头部插入一个数据
 *  deque.pop\_back();                  //删除容器最后一个数据
 *  deque.pop\_front();              //删除容器第一个数据

deque<int> deqInt;

deqInt.push\_back(1);

deqInt.push\_back(3);

deqInt.push\_back(5);

deqInt.push\_back(7);

deqInt.push\_back(9);

deqInt.pop\_front();

deqInt.push\_front(11);

deqInt.push\_front(13);

deqInt.pop\_back();

//deqInt  \{ 13,11,5\}

deque的数据存取

理论知识:

*  **deque.at(idx);  //返回索引idx所指的数据，如果idx越界，抛出out\_of\_range。**
 *  deque\[idx\];  //返回索引idx所指的数据，如果idx越界，不抛出异常，直接出错。
 *  ***deque.front();   //返回第一个数据。***
 *  ***deque.back();  //返回最后一个数据***

deque<int> deqInt;

deqInt.push\_back(1);

deqInt.push\_back(3);

deqInt.push\_back(5);

deqInt.push\_back(7);

deqInt.push\_back(9);

int iA = deqInt.at(0);                  //1

int iB = deqInt\[1\];                       //3

deqInt.at(0) = 99;                       //99

deqInt\[1\] = 88;                            //88

int iFront = deqInt.front();        //99

int iBack = deqInt.back();         //9

deqInt.front() = 77;                    //77

deqInt.back() = 66;                     //66

deque与迭代器

理论知识

*  **deque.begin();  //返回容器中第一个元素的迭代器。**
 *  **deque.end();  //返回容器中最后一个元素之后的迭代器。**
 *  **deque.rbegin();  //返回容器中倒数第一个元素的迭代器。**
 *  **deque.rend();   //返回容器中倒数最后一个元素之后的迭代器。**

deque<int> deqInt;

deqInt.push\_back(1);

deqInt.push\_back(3);

deqInt.push\_back(5);

deqInt.push\_back(7);

deqInt.push\_back(9);

for (deque<int>::iterator it=deqInt.begin(); it!=deqInt.end(); ++it)

cout << \*it;

cout << "";

// 1 3 5 7 9

for (deque<int>::reverse\_iterator rit=deqInt.rbegin(); rit!=deqInt.rend(); ++rit)

cout << \*rit;

cout << "";

//9 7 5 3 1

deque对象的带参数构造

理论知识

*  **deque(beg,end);    //构造函数将\[beg, end)区间中的元素拷贝给本身。注意该区间是左闭右开的区间。**
 *  **deque(n,elem);   //构造函数将n个elem拷贝给本身。**
 *  **deque(const deque  &deq);  //拷贝构造函数。**

deque<int> deqIntA;

deqIntA.push\_back(1);

deqIntA.push\_back(3);

deqIntA.push\_back(5);

deqIntA.push\_back(7);

deqIntA.push\_back(9);

deque<int> deqIntB(deqIntA.begin(),deqIntA.end());              //1 3 5 7 9

deque<int> deqIntC(5,8);                                                                 //8 8 8 8 8

deque<int> deqIntD(deqIntA);                                                       //1 3 5 7 9

deque的赋值

理论知识

*  **deque.assign(beg,end);    //将\[beg, end)区间中的数据拷贝赋值给本身。注意该区间是左闭右开的区间。**
 *  **deque.assign(n,elem);  //将n个elem拷贝赋值给本身。**
 *  **deque& operator=(const deque &deq);    //重载等号操作符**
 *  **deque.swap(deq);  // 将vec与本身的元素互换**

deque<int> deqIntA,deqIntB,deqIntC,deqIntD;

deqIntA.push\_back(1);

deqIntA.push\_back(3);

deqIntA.push\_back(5);

deqIntA.push\_back(7);

deqIntA.push\_back(9);

deqIntB.assign(deqIntA.begin(),deqIntA.end());    // 1 3 5 7 9

deqIntC.assign(5,8);                                                       //8 8 8 8 8

deqIntD = deqIntA;                                                         //1 3 5 7 9

deqIntC.swap(deqIntD);                                                //互换

deque的大小

理论知识

*  **deque.size();         //返回容器中元素的个数**
 *  **deque.empty();     //判断容器是否为空**
 *  **deque.resize(num);   //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。**
 *  **deque.resize(num, elem);  //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。**

deque<int> deqIntA;

deqIntA.push\_back(1);

deqIntA.push\_back(3);

deqIntA.push\_back(5);

int iSize = deqIntA.size();  //3

if (!deqIntA.empty())

deqIntA.resize(5);             //1 3 5 0 0

deqIntA.resize(7,1);         //1 3 5 0 0 1 1

deqIntA.resize(2);             //1 3

deque的插入

理论知识

*  **deque.insert(pos,elem);   //在pos位置插入一个elem元素的拷贝，返回新数据的位置。**
 *  **deque.insert(pos,n,elem);   //在pos位置插入n个elem数据，无返回值。**
 *  **deque.insert(pos,beg,end);   //在pos位置插入\[beg,end)区间的数据，无返回值。**

deque<int> deqA;

deque<int> deqB;

deqA.push\_back(1);

deqA.push\_back(3);

deqA.push\_back(5);

deqA.push\_back(7);

deqA.push\_back(9);

deqB.push\_back(2);

deqB.push\_back(4);

deqB.push\_back(6);

deqB.push\_back(8);

deqA.insert(deqA.begin(), 11);                  //\{11, 1, 3, 5, 7, 9\}

deqA.insert(deqA.begin()+1,2,33);          //\{11,33,33,1,3,5,7,9\}

deqA.insert(deqA.begin() , deqB.begin() , deqB.end() );          //\{2,4,6,8,11,33,33,1,3,5,7,9\}

deque的删除

理论知识

*  **deque.clear();    //移除容器的所有数据**
 *  **deque.erase(beg,end);  //删除\[beg,end)区间的数据，返回下一个数据的位置。**
 *  **deque.erase(pos);    //删除pos位置的数据，返回下一个数据的位置。**

删除区间内的元素

deqInt是用deque<int>声明的容器，现已包含按顺序的1,3,5,6,9元素。

deque<int>::iterator itBegin=deqInt.begin()+1;

deque<int>::iterator itEnd=deqInt.begin()+3;

deqInt.erase(itBegin,itEnd);

//此时容器deqInt包含按顺序的1,6,9三个元素。

假设 deqInt 包含1,3,2,3,3,3,4,3,5,3，删除容器中等于3的元素

for(deque<int>::iterator it=deqInt.being(); it!=deqInt.end(); )    //小括号里不需写  ++it

if(\*it == 3)

it  =  deqInt.erase(it);       //以迭代器为参数，删除元素3，并把数据删除后的下一个元素位置返回给迭代器。

//此时，不执行  ++it；

else

++it;

//删除deqInt的所有元素

deqInt.clear();                    //容器为空

#include <iostream>
 #include <algorithm>
 #include <deque>
 
 using namespace std;
 
 void printD(deque<int> &d)
 {
 	for (deque<int>::iterator it = d.begin(); it !=d.end();it++)
 	{
 		cout << *it << " ";
 	}
 }
 void main()
 {
 	//deque.push_back(elem);	//在容器尾部添加一个数据
 	deque<int> d1;
 	d1.push_back(1);
 	d1.push_back(3);
 	d1.push_back(5);
 	//deque.push_front(elem);	//在容器头部插入一个数据
 	d1.push_front(-11);
 	d1.push_front(-33);
 	d1.push_front(-55);
 	//deque.front(); //返回第一个数据
 	//deque.back(); //返回最后一个数据
 	cout << "头部元素:" << d1.front() << endl;
 	cout << "尾部元素:" << d1.back() << endl;
 	printD(d1);
 	//deque.pop_back(); 		//删除容器最后一个数据
 	//deque.pop_front();		//删除容器第一个数据
 	d1.pop_front();
 	d1.pop_back();
 	printD(d1);
 	cout << endl;
 	//查找 -33 在数组下标的值
 	deque<int>::iterator it = find(d1.begin(),d1.end(),-33);
 	if (it!=d1.end())
 	{
 		cout << "-33数组下标是" << distance(d1.begin(), it) << endl;
 	}
 	else
 	{
 		cout << "没有找到值为-33的元素" << endl;
 	}
 	cout << "hello..." << endl;
 	system("pause");
 	return;
 }

### 10.2.4stack容器 ###

Stack简介

* **stack是堆栈容器，是一种“先进后出”的容器。**
 * stack是简单地装饰deque容器而成为另外的一种容器。
 * \#include <stack>

stack对象的默认构造

stack采用模板类实现， stack对象的默认构造形式： stack <T> stkT;

stack <int> stkInt;            //一个存放int的stack容器。

stack <float> stkFloat;     //一个存放float的stack容器。

stack <string> stkString;     //一个存放string的stack容器。

//尖括号内还可以设置指针类型或自定义类型。

stack的push()与pop()方法

**stack.push(elem);   //往栈头添加元素**

**stack.pop();   //从栈头移除第一个元素**

stack<int> stkInt;

stkInt.push(1);stkInt.push(3);stkInt.pop();

stkInt.push(5);stkInt.push(7);

stkInt.push(9);stkInt.pop();

stkInt.pop();

此时stkInt存放的元素是1,5

stack对象的拷贝构造与赋值

stack(const stack &stk);                //拷贝构造函数

stack& operator=(const stack &stk);      //重载等号操作符

stack<int> stkIntA;

stkIntA.push(1);

stkIntA.push(3);

stkIntA.push(5);

stkIntA.push(7);

stkIntA.push(9);

stack<int> stkIntB(stkIntA);             //拷贝构造

stack<int> stkIntC;

stkIntC = stkIntA;                                //赋值

stack的数据存取

*  **stack.top();           //返回最后一个压入栈元素**

stack<int> stkIntA;

stkIntA.push(1);

stkIntA.push(3);

stkIntA.push(5);

stkIntA.push(7);

stkIntA.push(9);

int iTop = stkIntA.top();             //9

stkIntA.top() = 19;                      //19

stack的大小

*  **stack.empty();   //判断堆栈是否为空**
 *  **stack.size();            //返回堆栈的大小**

stack<int> stkIntA;

stkIntA.push(1);

stkIntA.push(3);

stkIntA.push(5);

stkIntA.push(7);

stkIntA.push(9);

if (!stkIntA.empty())

int iSize = stkIntA.size();           //5

#include <iostream>
 #include <stack>
 
 using namespace std;
 
 //栈模型 
 //栈的算法 和 数据类型的分离
 //1.入栈：如s.push(x);
 //2.出栈:如 s.pop().注意：出栈操作只是删除栈顶的元素，并不返回该元素。
 //3.访问栈顶：如s.top();
 //4.判断栈空：如s.empty().当栈空时返回true。
 //5.访问栈中的元素个数，如s.size（）;
 void main01()
 {
 	stack<int> s;
 	//入栈
 	for (int i = 0; i < 10; i++)
 	{
 		s.push(i+1);
 	}
 	cout << "栈的大小" << s.size() << endl;
 	//出栈
 	while (!s.empty())
 	{
 		int tmp = s.top();//获取栈顶元素
 		cout << tmp << " ";
 		s.pop();//弹出栈顶元素
 	}
 
 	cout << "hello..." << endl;
 	system("pause");
 	return;
 }
 
 //Teacher结点
 class Teacher
 {
 public:
 	int age;
 	char name[32];
 public:
 	void printT()
 	{
 		cout << "age:" << age << endl;
 	}
 private:
 
 };
 //装 元素
 void main02()
 {
 	Teacher t1, t2, t3;
 	t1.age = 31;
 	t2.age = 32;
 	t3.age = 33;
 
 	stack<Teacher> s;
 	s.push(t1);
 	s.push(t2);
 	s.push(t3);
 
 	while (!s.empty())
 	{
 		Teacher tmp = s.top();//获取栈顶元素
 		tmp.printT();
 		s.pop();
 	}
 
 	cout << "hello..." << endl;
 	system("pause");
 	return;
 }
 //装 元素地址
 void main()
 {
 	Teacher t1, t2, t3;
 	t1.age = 31;
 	t2.age = 32;
 	t3.age = 33;
 
 	stack<Teacher *> s;
 	s.push(&t1);
 	s.push(&t2);
 	s.push(&t3);
 
 	while (!s.empty())
 	{
 		Teacher *tmp = s.top();//获取栈顶元素
 		tmp->printT();
 		s.pop();//弹出栈顶元素
 	}
 
 
 	cout << "hello..." << endl;
 	system("pause");
 	return;
 }

### 10.2.5Queue容器 ###

Queue简介

* **queue是队列容器，是一种“先进先出”的容器。**
 * **queue是简单地装饰deque容器而成为另外的一种容器。**
 * **\#include <queue>**

queue对象的默认构造

queue采用模板类实现，queue对象的默认构造形式：queue<T> queT;  如：

queue<int> queInt;            //一个存放int的queue容器。

queue<float> queFloat;     //一个存放float的queue容器。

queue<string> queString;     //一个存放string的queue容器。

//尖括号内还可以设置指针类型或自定义类型。

queue的push()与pop()方法

**queue.push(elem);   //往队尾添加元素**

**queue.pop();   //从队头移除第一个元素**

queue<int> queInt;

queInt.push(1);queInt.push(3);

queInt.push(5);queInt.push(7);

queInt.push(9);queInt.pop();

queInt.pop();

此时queInt存放的元素是5,7,9

queue对象的拷贝构造与赋值

queue(const queue &que);                    //拷贝构造函数

queue& operator=(const queue &que); //重载等号操作符

queue<int> queIntA;

queIntA.push(1);

queIntA.push(3);

queIntA.push(5);

queIntA.push(7);

queIntA.push(9);

queue<int> queIntB(queIntA);         //拷贝构造

queue<int> queIntC;

queIntC = queIntA;                              //赋值

**queue的数据存取**

*  **queue.back();   //返回最后一个元素**
 *  **queue.front();   //返回第一个元素**

queue<int> queIntA;

queIntA.push(1);

queIntA.push(3);

queIntA.push(5);

queIntA.push(7);

queIntA.push(9);

int iFront = queIntA.front();              //1

int iBack = queIntA.back();                //9

queIntA.front() = 11;                           //11

queIntA.back() = 19;                           //19

**queue的大小**

*  **queue.empty();   //判断队列是否为空**
 *  **queue.size();          //返回队列的大小**

queue<int> queIntA;

queIntA.push(1);

queIntA.push(3);

queIntA.push(5);

queIntA.push(7);

queIntA.push(9);

if (!queIntA.empty())

int iSize = queIntA.size();                   //5

#include <iostream>
 #include <queue>
 
 
 using namespace std;
 
 
 void main01()
 {
 	queue<int> q;
 	q.push(1);
 	q.push(2);
 	q.push(3);
 
 	cout << "队头元素:" << q.front() << endl;
 	cout << "队列的大小" << q.size() << endl;
 	//queue.back(); //返回最后一个元素
 	//queue.front(); //返回第一个元素
 
 	while (!q.empty())
 	{
 		int tmp = q.front();
 		cout << tmp << " " << endl;
 		q.pop();
 	}
 	cout << "hello..." << endl;
 	system("pause");
 	return;
 }
 
 //teacher结点
 class Teacher
 {
 public:
 	int		age;
 	char	name[32];
 public:
 	void printT()
 	{
 		cout << "age:" << age << endl;
 	}
 };
 
 
 void main02()
 {
 	Teacher t1, t2, t3;
 	t1.age = 31;
 	t2.age = 32;
 	t3.age = 33;
 	//queue.push(elem); //往队尾添加元素
 	queue<Teacher> q;
 	q.push(t1);
 	q.push(t2);
 	q.push(t3);
 
 	while (!q.empty())
 	{
 		Teacher tmp = q.front();
 		tmp.printT();
 		q.pop();
 	}
 }
 
 void main()
 {
 	Teacher t1, t2, t3;
 	t1.age = 31;
 	t2.age = 32;
 	t3.age = 33;
 
 	queue<Teacher *> q;
 	q.push(&t1);
 	q.push(&t2);
 	q.push(&t3);
 	//queue.pop(); //从队头移除第一个元素
 	while (!q.empty())
 	{
 		Teacher *tmp = q.front();
 		tmp->printT();
 		q.pop();
 	}
 
 
 }

### 10.2.6List容器 ###

List简介

* **list是一个双向链表容器，可高效地进行插入删除元素。**
 * **list不可以随机存取元素，所以不支持at.(pos)函数与\[\]操作符。It++(ok) it+5(err)**
 * \#include <list>

list对象的默认构造

list采用采用模板类实现,对象的默认构造形式：list<T> lstT;  如：

list<int> lstInt;            //定义一个存放int的list容器。

list<float> lstFloat;     //定义一个存放float的list容器。

list<string> lstString;     //定义一个存放string的list容器。

//尖括号内还可以设置指针类型或自定义类型。

**list头尾的添加移除操作**

*  **list.push\_back(elem);            //在容器尾部加入一个元素**
 *  **list.pop\_back();              //删除容器中最后一个元素**
 *  **list.push\_front(elem);     //在容器开头插入一个元素**
 *  **list.pop\_front();              //从容器开头移除第一个元素**

list<int> lstInt;

lstInt.push\_back(1);

lstInt.push\_back(3);

lstInt.push\_back(5);

lstInt.push\_back(7);

lstInt.push\_back(9);

lstInt.pop\_front();

lstInt.push\_front(11);

lstInt.push\_front(13);

lstInt.pop\_back();

// lstInt    \{13,11,5\}

**list的数据存取**

*  **list.front();   //返回第一个元素。**
 *  **list.back();  //返回最后一个元素。**

list<int> lstInt;

lstInt.push\_back(1);

lstInt.push\_back(3);

lstInt.push\_back(5);

lstInt.push\_back(7);

lstInt.push\_back(9);

int iFront = lstInt.front(); //1

int iBack = lstInt.back();            //9

lstInt.front() = 11;                      //11

lstInt.back() = 19;                       //19

**list与迭代器**

*  **list.begin();                     //返回容器中第一个元素的迭代器。**
 *  **list.end();                       //返回容器中最后一个元素之后的迭代器。**
 *  **list.rbegin();         //返回容器中倒数第一个元素的迭代器。**
 *  **list.rend();         //返回容器中倒数最后一个元素的后面的迭代器。**

list<int> lstInt;

lstInt.push\_back(1);

lstInt.push\_back(3);

lstInt.push\_back(5);

lstInt.push\_back(7);

lstInt.push\_back(9);

for (list<int>::iterator it=lstInt.begin(); it!=lstInt.end(); ++it)

cout << \*it;

cout << " ";

for (list<int>::reverse\_iterator rit=lstInt.rbegin(); rit!=lstInt.rend(); ++rit)

cout << \*rit;

cout << " ";

**list对象的带参数构造**

*  **list(beg,end);    //构造函数将\[beg, end)区间中的元素拷贝给本身。注意该区间是左闭右开的区间。**
 *  **list(n,elem);   //构造函数将n个elem拷贝给本身。**
 *  **list(const list &lst);  //拷贝构造函数。**

list<int> lstIntA;

lstIntA.push\_back(1);

lstIntA.push\_back(3);

lstIntA.push\_back(5);

lstIntA.push\_back(7);

lstIntA.push\_back(9);

list<int> lstIntB(lstIntA.begin(),lstIntA.end());                  //1 3 5 7 9

list<int> lstIntC(5,8);                                                                //8 8 8 8 8

list<int> lstIntD(lstIntA);                                               //1 3 5 7 9

**list的赋值**

*  **list.assign(beg,end);    //将\[beg, end)区间中的数据拷贝赋值给本身。注意该区间是左闭右开的区间。**
 *  **list.assign(n,elem);  //将n个elem拷贝赋值给本身。**
 *  **list& operator=(const list &lst);         //重载等号操作符**
 *  **list.swap(lst);  // 将lst与本身的元素互换。**

list<int> lstIntA,lstIntB,lstIntC,lstIntD;

lstIntA.push\_back(1);

lstIntA.push\_back(3);

lstIntA.push\_back(5);

lstIntA.push\_back(7);

lstIntA.push\_back(9);

lstIntB.assign(lstIntA.begin(),lstIntA.end());           //1 3 5 7 9

lstIntC.assign(5,8);                                                         //8 8 8 8 8

lstIntD = lstIntA;                                                              //1 3 5 7 9

lstIntC.swap(lstIntD);                                                    //互换

**list的大小**

*  **list.size();      //返回容器中元素的个数**
 *  **list.empty();           //判断容器是否为空**
 *  **list.resize(num);   //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。**
 *  **list.resize(num, elem);  //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。**

list<int> lstIntA;

lstIntA.push\_back(1);

lstIntA.push\_back(3);

lstIntA.push\_back(5);

if (!lstIntA.empty())

int iSize = lstIntA.size();            //3

lstIntA.resize(5);                        //1 3 5 0 0

lstIntA.resize(7,1);                     //1 3 5 0 0 1 1

lstIntA.resize(2);                        //1 3

**list的插入**

*  **list.insert(pos,elem);   //在pos位置插入一个elem元素的拷贝，返回新数据的位置。**
 *  **list.insert(pos,n,elem);   //在pos位置插入n个elem数据，无返回值。**
 *  **list.insert(pos,beg,end);   //在pos位置插入\[beg,end)区间的数据，无返回值。**

list<int> lstA;

list<int> lstB;

lstA.push\_back(1);

lstA.push\_back(3);

lstA.push\_back(5);

lstA.push\_back(7);

lstA.push\_back(9);

lstB.push\_back(2);

lstB.push\_back(4);

lstB.push\_back(6);

lstB.push\_back(8);

lstA.insert(lstA.begin(), 11);             //\{11, 1, 3, 5, 7, 9\}

lstA.insert(++lstA.begin(),2,33);               //\{11,33,33,1,3,5,7,9\}

lstA.insert(lstA.begin() , lstB.begin() , lstB.end() );          //\{2,4,6,8,11,33,33,1,3,5,7,9\}

**list的删除**

*  **list.clear();          //移除容器的所有数据**
 *  **list.erase(beg,end);  //删除\[beg,end)区间的数据，返回下一个数据的位置。**
 *  **list.erase(pos);    //删除pos位置的数据，返回下一个数据的位置。**
 *  **lst.remove(elem);   //删除容器中所有与elem值匹配的元素。**

删除区间内的元素

lstInt是用list<int>声明的容器，现已包含按顺序的1,3,5,6,9元素。

list<int>::iterator itBegin=lstInt.begin();

\++itBegin;

list<int>::iterator itEnd=lstInt.begin();

\++itEnd;

lstInt.erase(itBegin,itEnd);

//此时容器lstInt包含按顺序的1,6,9三个元素。

假设 lstInt 包含1,3,2,3,3,3,4,3,5,3，删除容器中等于3的元素的方法一

for(list<int>::iterator it=lstInt.being(); it!=lstInt.end(); )    //小括号里不需写  ++it

if(\*it == 3)

it  =  lstInt.erase(it);       //以迭代器为参数，删除元素3，并把数据删除后的下一个元素位置返回给迭代器。

//此时，不执行  ++it；

else

++it;

删除容器中等于3的元素的方法二

lstInt.remove(3);

删除lstInt的所有元素

lstInt.clear();                      //容器为空

**list的反序排列**

*  **lst.reverse();     //反转链表，比如lst包含1,3,5元素，运行此方法后，lst就包含5,3,1元素。**

list<int> lstA;

lstA.push\_back(1);

lstA.push\_back(3);

lstA.push\_back(5);

lstA.push\_back(7);

lstA.push\_back(9);

lstA.reverse();                    //9 7 5 3 1

**小结:**

*  **一、容器deque的使用方法**

**         适合         在头尾添加移除元素。使用方法与vector类似。**

*  **二、容器queue,stack的使用方法**

**         适合队列，堆栈的操作方式。**

*  **三、容器list的使用方法**

**         适合在任意位置快速插入移除元素**

//list.push_back(elem);            //在容器尾部加入一个元素
 //list.pop_back();              //删除容器中最后一个元素
 //list.push_front(elem);     //在容器开头插入一个元素
 //list.pop_front();              //从容器开头移除第一个元素
 
 //list的数据存取
 //list.front();   //返回第一个元素。
 //list.back();  //返回最后一个元素。
 
 //list与迭代器
 //list.begin();                     //返回容器中第一个元素的迭代器。
 //list.end();                       //返回容器中最后一个元素之后的迭代器。
 //list.rbegin();         //返回容器中倒数第一个元素的迭代器。
 //list.rend();         //返回容器中倒数最后一个元素的后面的迭代器。
 
 //list对象的带参数构造
 //list(beg, end);    //构造函数将[beg, end)区间中的元素拷贝给本身。注意该区间是左闭右开的区间。
 //list(n, elem);   //构造函数将n个elem拷贝给本身。
 //list(const list &lst);  //拷贝构造函数。
 
 //list的赋值
 //list.assign(beg, end);    //将[beg, end)区间中的数据拷贝赋值给本身。注意该区间是左闭右开的区间。
 //list.assign(n, elem);  //将n个elem拷贝赋值给本身。
 //list& operator=(const list &lst);         //重载等号操作符
 //list.swap(lst);  // 将lst与本身的元素互换。
 
 //list的大
 //list.size();      //返回容器中元素的个数
 //list.empty();           //判断容器是否为空
 //list.resize(num);   //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
 //list.resize(num, elem);  //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
 
 //list的插入
 //list.insert(pos, elem);   //在pos位置插入一个elem元素的拷贝，返回新数据的位置。
 //list.insert(pos, n, elem);   //在pos位置插入n个elem数据，无返回值。
 //list.insert(pos, beg, end);   //在pos位置插入[beg,end)区间的数据，无返回值
 
 //list的删除
 //list.clear();          //移除容器的所有数据
 //list.erase(beg, end);  //删除[beg,end)区间的数据，返回下一个数据的位置。
 //list.erase(pos);    //删除pos位置的数据，返回下一个数据的位置。
 //lst.remove(elem);   //删除容器中所有与elem值匹配的元素
 
 //list的反序排列
 //lst.reverse();     //反转链表，比如lst包含1,3,5元素，运行此方法后，lst就包含5,3,1元素
 #include <iostream>
 #include <list>
 using namespace std;
 
 //list的基本操作
 void main01()
 {
 	list<int> lis;
 	cout << "list的大小:" << lis.size() << endl;
 	for (int i = 0; i < 10; i++)
 	{
 		lis.push_back(i);//尾部插入元素 尾插法
 	}
 	cout << "list的大小:" << lis.size() << endl;
 
 	list<int>::iterator it = lis.begin();
 	while (it!=lis.end())
 	{
 		cout << *it << " ";
 		it++;
 	}
 	cout << endl;
 
 	//list不能随机访问
 	it = lis.begin();
 	it++;
 	it++;
 	it++;
 	//it = it + 5; //不支持随机的访问容器
 	lis.insert(it,100);//请问100插入的位置
 	for (list<int>::iterator it = lis.begin(); it != lis.end();it++)
 	{
 		cout << *it << " ";
 	}
 	//结论1 链表的结点index 序号是从0号位置开始
 	//在3号位置插入元素, 让原来的3号位置变成4号位置 原来的4号位置变成5号位置
 
 
 
 	system("pause");
 }
 
 
 //list 删除
 void main()
 {
 	list<int> lis;
 	cout << "list的大小:" << lis.size() << endl;
 	for (int i = 0; i < 10; i++)
 	{
 		lis.push_back(i);//尾部插入元素 尾插法
 	}
 	cout << "list的大小:" << lis.size() << endl;
 	for (list<int>::iterator it = lis.begin(); it != lis.end();it++)
 	{
 		cout << *it << " ";
 	}
 	cout << endl;
 	//0	 1	2	3	4	5
 	// ▲
 	list<int>::iterator it1 = lis.begin();
 	list<int>::iterator it2 = lis.begin();
 	it2++;
 	it2++;
 	it2++;
 	//list.erase(beg, end);  
 	//删除[beg,end)区间的数据，返回下一个数据的位置。
 	lis.erase(it1,it2);
 	for (list<int>::iterator it = lis.begin(); it != lis.end();it++)
 	{
 		cout << *it << " ";
 	}
 	cout << endl;
 
 	lis.insert(lis.begin(),100);
 	for (list<int>::iterator it = lis.begin(); it != lis.end(); it++)
 	{
 		cout << *it << " ";
 	}
 	cout << endl;
 	//list的删除
 	//list.clear();          //移除容器的所有数据
 	//list.erase(beg, end);  //删除[beg,end)区间的数据，返回下一个数据的位置。
 	//list.erase(pos);    //删除pos位置的数据，返回下一个数据的位置。
 	//lst.remove(elem);   //删除容器中所有与elem值匹配的元素
 	
 	//list.erase(pos);    //删除pos位置的数据，返回下一个数据的位置。
 	lis.erase(lis.begin());
 	for (list<int>::iterator it = lis.begin(); it != lis.end(); it++)
 	{
 		cout << *it << " ";
 	}
 	lis.remove(100);
 
 
 	system("pause");
 }

### 10.2.7优先级队列priority\_queue ###

1.  最大值优先级队列、最小值优先级队列
2.  优先级队列适配器STL priority\_queue
3.  用来开发一些特殊的应用,请对stl的类库,多做扩展性学习

priority\_queue<int, deque<int>>    pq;

priority\_queue<int, vector<int>>    pq;

pq.empty()

pq.size()

pq.top()

pq.pop()

pq.push(item)

\#include <iostream>

using namespace std;

\#include "queue"

void main81()

priority\_queue<int> p1; //默认是最大值优先级队列

**//priority\_queue<int, vector<int>, less<int>> p1**; //相当于这样写

priority\_queue<int, vector<int>, greater<int>> p2; //最小值优先级队列

p1.push(33);

p1.push(11);

p1.push(55);

p1.push(22);

cout <<"队列大小" << p1.size() << endl;

cout <<"队头" << p1.top() << endl;

while (p1.size() > 0)

cout << p1.top() << " ";

p1.pop();

cout << endl;

cout << "测试最小值优先级队列" << endl;

p2.push(33);

p2.push(11);

p2.push(55);

p2.push(22);

while (p2.size() > 0)

cout << p2.top() << " ";

p2.pop();

#include <functional>//一定要包含这个文件
 #include <iostream>
 using namespace std;
 #include <queue>
 
 
 void main()
 {
 	//从大到小
 	priority_queue<int> p1; //默认是 最大值优先级队列 
 	//priority_queue<int, vector<int>, less<int> > p1; //相当于这样写
 
 
 	p1.push(33);
 	p1.push(11);
 	p1.push(55);
 	p1.push(22);
 	cout << "队列大小" << p1.size() << endl;
 	cout << "队头" << p1.top() << endl;
 
 	while (p1.size() > 0)
 	{
 		cout << p1.top() << " ";
 		p1.pop();
 	}
 	cout << endl;
 
 	cout << "测试 最小值优先级队列" << endl;
 	//从小到大
 	priority_queue<int, vector<int>, greater<int> > q;
 	q.push(11);
 	q.push(15);
 	q.push(7);
 	q.push(58);
 	cout << "队列大小" << q.size() << endl;
 	cout << "队头" << q.top() << endl;
 
 	while (q.size() > 0)
 	{
 		cout << q.top() << " ";
 		q.pop();
 	}
 
 
 	cout << "hello..." << endl;
 	system("pause");
 	return;
 }

### 10.2.8Set和multiset容器 ###

set/multiset的简介

* set是一个**集合**容器，其中所包含的元素是**唯一**的，**集合中的元素按一定的顺序排列**。**元素插入过程是按排序规则插入**，所以不能指定插入位置。
 * set采用**红黑树**变体的数据结构实现，红黑树属于平衡二叉树。**在插入操作和删除操作上比vector快。**
 * **set不可以直接存取元素。（不可以使用at.(pos)与\[\]操作符）。**
 * **multiset与set的区别**：**set支持唯一键值，每个元素值只能出现一次**；而multiset中**同一值可以出现多次**。
 * 不可以直接修改set或multiset容器中的元素值，因为该类容器是自动排序的。如果希望修改一个元素值，必须先删除原有的元素，再插入新的元素。
 * \#include <set>

![70 3][]

set/multiset对象的默认构造

set<int> setInt;            //一个存放int的set容器。

set<float> setFloat;     //一个存放float的set容器。

set<string> setString;     //一个存放string的set容器。

multiset<int> mulsetInt;            //一个存放int的multi set容器。

multi set<float> multisetFloat;     //一个存放float的multi set容器。

multi set<string> multisetString;     //一个存放string的multi set容器。

**set的插入与迭代器**

*  **set.insert(elem);     //在容器中插入元素。**
 *  **set.begin();  //返回容器中第一个数据的迭代器。**
 *  **set.end();  //返回容器中最后一个数据之后的迭代器。**
 *  **set.rbegin();  //返回容器中倒数第一个元素的迭代器。**
 *  **set.rend();   //返回容器中倒数最后一个元素的后面的迭代器。**

set<int> setInt;

setInt.insert(3); setInt.insert(1);setInt.insert(5);setInt.insert(2);

for(set<int>::iterator it=setInt.begin(); it!=setInt.end(); ++it)

int iItem = \*it;

cout << iItem;    //或直接使用cout << \*it

//这样子便顺序输出  1 2 3 5。

set.rbegin()与set.rend()。略。

**Set集合的元素排序**

* **set<int,less<int>>  setIntA;  //该容器是按升序方式排列元素。从小到大**
 * **set<int,greater<int>> setIntB;   //该容器是按降序方式排列元素。从大到小**
 * **set<int>相当于 set<int,less<int>>。**
 * **less<int>与greater<int>中的int可以改成其它类型，该类型主要要跟set容纳的数据类型一致。**
 * 疑问1：less<>与greater<>是什么？
 * 疑问2：如果set<>不包含int类型，而是包含自定义类型，set容器如何排序？
 * 要解决如上两个问题，需要了解容器的函数对象，也叫伪函数，英文名叫functor。
 * 下面将讲解什么是functor，functor的用法。

使用stl提供的函数对象

set<int,greater<int>> setIntB;

setIntB.insert(3);

setIntB.insert(1);

setIntB.insert(5);

setIntB.insert(2);

此时容器setIntB就包含了按顺序的5,3,2,1元素

函数对象functor的用法

* 尽管函数指针被广泛用于实现函数回调，但C++还提供了一个重要的实现回调函数的方法，那就是函数对象。
 * functor，翻译成函数对象，伪函数，算符，是重载了“()”操作符的普通类对象。从语法上讲，它与普通函数行为类似。
 * greater<>与less<>就是函数对象。
 * 下面举出greater<int>的简易实现原理。

下面举出greater<int>的简易实现原理。

struct greater

bool operator() (const int& iLeft, const int& iRight)

return (iLeft>iRight);//如果是实现less<int>的话，这边是写return (iLeft<iRight);

容器就是调用函数对象的operator()方法去比较两个值的大小。

题目：学生包含学号，姓名属性，现要求任意插入几个学生对象到set容器中，使得容器中的学生按学号的升序排序。

解：

//学生类

class CStudent

public:

CStudent(int iID, string strName)

m\_iID = iID;

m\_strName = strName;

int m\_iID;                //学号

string m\_strName;       //姓名

//为保持主题鲜明，本类不写拷贝构造函数，不类也不需要写拷贝构造函数。但大家仍要有考虑拷贝构造函数的习惯。

//函数对象

struct StuFunctor

bool operator()  (const CStudent &stu1, const CStudent &stu2)

return (stu1.m\_iID<stu2.m\_iID);

//main函数

void main()

set<CStudent, StuFunctor> setStu;

setStu.insert(CStudent(3,"小张"));

setStu.insert(CStudent(1,"小李"));

setStu.insert(CStudent(5,"小王"));

setStu.insert(CStudent(2,"小刘"));

//此时容器setStu包含了四个学生对象，分别是按姓名顺序的“小李”，“小刘”，“小张”，“小王”

set对象的拷贝构造与赋值

set(const set &st);                //拷贝构造函数

set& operator=(const set &st);       //重载等号操作符

set.swap(st);                               //交换两个集合容器

set<int> setIntA;

setIntA.insert(3);

setIntA.insert(1);

setIntA.insert(7);

setIntA.insert(5);

setIntA.insert(9);

set<int> setIntB(setIntA);  //1 3 5 7 9

set<int> setIntC;

setIntC = setIntA;             //1 3 5 7 9

setIntC.insert(6);

setIntC.swap(setIntA);     //交换

**set的大小**

*  **set.size();   //返回容器中元素的数目**
 *  **set.empty();//判断容器是否为**

set<int> setIntA;

setIntA.insert(3);

setIntA.insert(1);

setIntA.insert(7);

setIntA.insert(5);

setIntA.insert(9);

if (!setIntA.empty())

int iSize = setIntA.size();           //5

**set的删除**

*  **set.clear();          //清除所有元素**
 *  **set.erase(pos);  //删除pos迭代器所指的元素，返回下一个元素的迭代器。**
 *  **set.erase(beg,end);       //删除区间\[beg,end)的所有元素  ，返回下一个元素的迭代器。**
 *  **set.erase(elem);     //删除容器中值为elem的元素。**

删除区间内的元素

setInt是用set<int>声明的容器，现已包含按顺序的1,3,5,6,9,11元素。

set<int>::iterator itBegin=setInt.begin();

\++itBegin;

set<int>::iterator itEnd=setInt.begin();

\++itEnd;

setInt.erase(itBegin,itEnd);

//此时容器setInt包含按顺序的1,6,9,11四个元素。

删除容器中第一个元素

setInt.erase(setInt.begin());            //6,9,11

删除容器中值为9的元素

set.erase(9);

删除setInt的所有元素

setInt.clear();                     //容器为空

**set的查找**

*  **set.find(elem);   //查找elem元素，返回指向elem元素的迭代器。**
 *  **set.count(elem);   //返回容器中值为elem的元素个数。对set来说，要么是0，要么是1。对multiset来说，值可能大于1。**
 *  **set.lower\_bound(elem);  //返回第一个>=elem元素的迭代器。**
 *  **set.upper\_bound(elem);       //  返回第一个>elem元素的迭代器。**
 *  **set.equal\_range(elem);              //返回容器中与elem相等的上下限的两个迭代器。上限是闭区间，下限是开区间，如\[beg,end)。**
 *   
 *  以上函数返回两个迭代器，而这两个迭代器被封装在pair中。
 *  以下讲解pair的含义与使用方法。

set<int> setInt;

setInt.insert(3);

setInt.insert(1);

setInt.insert(7);

setInt.insert(5);

setInt.insert(9);

set<int>::iterator itA = setInt.find(5);

int iA = \*itA;              //iA == 5

int iCount = setInt.count(5);    //iCount == 1

set<int>::iterator itB = setInt.lower\_bound(5);

set<int>::iterator itC = setInt.upper\_bound(5);

int iB = \*itB;     //iB == 5

int iC = \*itC; //iC == 7

pair< set<int>::iterator, set<int>::iterator >pairIt = setInt.equal\_range(5);  //pair是什么？

**pair的使用**

* **pair译为对组，可以将两个值视为一个单元。**
 * **pair<T1,T2>存放的两个值的类型，可以不一样，如T1为int，T2为float。T1,T2也可以是自定义类型。**
 * **pair.first是pair里面的第一个值，是T1类型。**
 * **pair.second是pair里面的第二个值，是T2类型。**

set<int> setInt;

...  //往setInt容器插入元素1,3,5,7,9

pair< set<int>::iterator , set<int>::iterator > pairIt = setInt.equal\_range(5);

set<int>::iterator itBeg = pairIt.first;

set<int>::iterator itEnd = pairIt.second;

//此时 \*itBeg==5  而  \*itEnd == 7

**小结**

*  **一、容器set/multiset的使用方法；**

**                            红黑树的变体，查找效率高，插入不能指定位置，插入时自动排序。**

*  **二、functor的使用方法；**

**类似于函数的功能，可用来自定义一些规则，如元素比较规则。**

*  **三、pair的使用方法。**

**         对组，一个整体的单元，存放两个类型(T1,T2，T1可与T2一样)的两个元素。**

案例:

int x;

scanf("%ld",&x);

multiset<int> h;//建立一个multiset类型，变量名是h，h序列里面存的是int类型,初始h为空

while(x!=0)\{

h.insert(x);//将x插入h中

scanf("%ld",&x);

pair< multiset<int>::iterator , multiset<int>::iterator > pairIt = h.equal\_range(22);

multiset<int>::iterator itBeg = pairIt.first;

multiset<int>::iterator itEnd = pairIt.second;

int nBeg = \*itBeg;

int nEnd = \*itEnd;

while(!h.empty())\{// 序列非空h.empty()==true时表示h已经空了

multiset<int>::iterator c = h.begin();//c指向h序列中第一个元素的地址，第一个元素是最小的元素

printf("%ld ",\*c);//将地址c存的数据输出

h.erase(c);//从h序列中将c指向的元素删除

#define _CRT_SECURE_NO_WARNINGS
 #include <functional>
 #include <iostream>
 using namespace std;
 #include <set>
 
 //集合 有序(默认从小到大) 唯一(红黑二叉树 这种数据结构的变体)
 void main01()
 { 
 	set<int> set1;
 	for (int i = 0; i < 5; i++)
 	{
 		int tmp = rand();
 		set1.insert(tmp);
 	}
 	set1.insert(100);
 	set1.insert(100);
 	set1.insert(100);
 
 	//打印输出
 	for (set<int>::iterator it = set1.begin(); it != set1.end();it++)
 	{
 		cout << *it << " ";
 	}
 
 	//删除集合
 	cout << "\n删除集合";
 	while (!set1.empty())
 	{
 		set<int>::iterator it = set1.begin();
 		printf("%d ",*it);
 		set1.erase(set1.begin());
 	}
 
 	cout << "hello..." << endl;
 	system("pause");
 	return;
 }
 //2 集合 从小到大 
 void main02()
 { //从大到小
 	set<int, greater<int>> set1;
 	for (int i = 0; i < 5; i++)
 	{
 		int tmp = rand();
 		set1.insert(tmp);
 	}
 	set1.insert(100);
 
 	for (set<int, greater<int>>::iterator it = set1.begin(); it != set1.end();it++)
 	{
 		cout << *it << " ";
 	}
 	cout << endl;
 
 	//删除集合
 	cout << "\n删除集合";
 	while (!set1.empty())
 	{
 		set<int, greater<int>>::iterator it = set1.begin();
 		printf("%d ",*it);
 		set1.erase(set1.begin());
 	}
 	cout << "hello..." << endl;
 	system("pause");
 	return;
 }
 //3 自定义数据类型 排序
 //03 仿函数 函数对象 重载() 操作 进行比较大小
 //题目：学生包含学号，姓名属性，现要求任意插入几个学生对象到set容器中，
 //使得容器中的学生按学号的升序排序
 class Student
 {
 public:
 	Student(char *name, int age)
 	{
 		strcpy(this->name,name);
 		this->age = age;
 	}
 
 public:
 	char name[64];
 	int age;
 };
 //函数对象
 //如果是实现less<int>的话，这边是写return (iLeft<iRight);升序
 struct StuFunctor
 {
 	bool operator()(const Student &left, const Student &right)
 	{
 		return (left.age < right.age);
 	}
 };
 
 
 void main03()
 {
 	set<Student, StuFunctor> set1;
 	Student s1("张1", 32);
 	//multiset与set的区别：set支持唯一键值，每个元素值只能出现一次；而multiset中同一值可以出现多次。
 	set1.insert(s1);
 	set1.insert(Student("张2", 32));
 	set1.insert(Student("张3", 53));
 	set1.insert(Student("张4", 34));
 
 	//打印输出
 	for (set<Student, StuFunctor>::iterator it = set1.begin(); it != set1.end();it++)
 	{
 		cout << (*it).name << " ";
 	}
 
 
 	cout << "hello..." << endl;
 	system("pause");
 	return;
 }
 //04演示：set集合查找功能
 void main()
 {
 	int		i = 0;
 	set<int> set1;
 
 	for (i = 1; i<10; i++)
 	{
 		set1.insert(i);
 	}
 	//打印输出
 	for (set<int>::iterator it = set1.begin(); it != set1.end(); it++)
 	{
 		cout << *it << " ";
 	}
 	cout << endl;
 
 	set<int>::iterator it1 = set1.lower_bound(5); //大于等于5迭代器
 	set<int>::iterator it2 = set1.upper_bound(5); //大于5的迭代器
 
 	//通过迭代器进行元素的操作
 	cout << "it1 " << *it1 << " " << "it2 " << *it2 << endl;
 
 	//set.equal_range(elem);//返回容器中与elem相等的上下限的两个迭代器，上限是闭区间，下限是开区间
 	pair <set<int>::iterator, set<int>::iterator> pairIt = set1.equal_range(5);
 
 	set<int>::iterator it3 = pairIt.first; //获取第一个
 	set<int>::iterator it4 = pairIt.second; //获取第二个
 
 	// 5 6
 	cout << "it3 " << *it3 << " " << "it4 " << *it4 << endl;
 	cout << "hello..." << endl;
 	system("pause");
 	return;
 }

#define _CRT_SECURE_NO_WARNINGS
 #include <functional>
 #include <iostream>
 using namespace std;
 #include <set>
 
 //集合 有序(默认从小到大) 唯一(红黑二叉树 这种数据结构的变体)
 void main01()
 { 
 	set<int> set1;
 	for (int i = 0; i < 5; i++)
 	{
 		int tmp = rand();
 		set1.insert(tmp);
 	}
 	set1.insert(100);
 	set1.insert(100);
 	set1.insert(100);
 
 	//打印输出
 	for (set<int>::iterator it = set1.begin(); it != set1.end();it++)
 	{
 		cout << *it << " ";
 	}
 
 	//删除集合
 	cout << "\n删除集合";
 	while (!set1.empty())
 	{
 		set<int>::iterator it = set1.begin();
 		printf("%d ",*it);
 		set1.erase(set1.begin());
 	}
 
 	cout << "hello..." << endl;
 	system("pause");
 	return;
 }
 //2 集合 从小到大 
 void main02()
 { //从大到小
 	set<int, greater<int>> set1;
 	for (int i = 0; i < 5; i++)
 	{
 		int tmp = rand();
 		set1.insert(tmp);
 	}
 	set1.insert(100);
 
 	for (set<int, greater<int>>::iterator it = set1.begin(); it != set1.end();it++)
 	{
 		cout << *it << " ";
 	}
 	cout << endl;
 
 	//删除集合
 	cout << "\n删除集合";
 	while (!set1.empty())
 	{
 		set<int, greater<int>>::iterator it = set1.begin();
 		printf("%d ",*it);
 		set1.erase(set1.begin());
 	}
 	cout << "hello..." << endl;
 	system("pause");
 	return;
 }
 //3 自定义数据类型 排序
 //03 仿函数 函数对象 重载() 操作 进行比较大小
 //题目：学生包含学号，姓名属性，现要求任意插入几个学生对象到set容器中，
 //使得容器中的学生按学号的升序排序
 class Student
 {
 public:
 	Student(char *name, int age)
 	{
 		strcpy(this->name,name);
 		this->age = age;
 	}
 
 public:
 	char name[64];
 	int age;
 };
 //函数对象
 //如果是实现less<int>的话，这边是写return (iLeft<iRight);升序
 struct StuFunctor
 {
 	bool operator()(const Student &left, const Student &right)
 	{
 
 		return (left.age < right.age);
 	}
 };
 
 
 void main03()
 {
 	set<Student, StuFunctor> set1;
 	Student s1("张1", 32);
 	//multiset与set的区别：set支持唯一键值，每个元素值只能出现一次；而multiset中同一值可以出现多次。
 	set1.insert(s1);
 	set1.insert(Student("张2", 32));
 	set1.insert(Student("张3", 53));
 	set1.insert(Student("张4", 34));
 
 	//打印输出
 	for (set<Student, StuFunctor>::iterator it = set1.begin(); it != set1.end();it++)
 	{
 		cout << (*it).name << " ";
 	}
 
 
 	cout << "hello..." << endl;
 	system("pause");
 	return;
 }
 //04演示：set集合查找功能
 //typedef pair<iterator, bool> _Pairib;
 //4 如何判断 set1.insert函数的返回值
 //Pair的用法 
 void main()
 {
 	int		i = 0;
 	set<int> set1;
 
 	for (i = 1; i<10; i++)
 	{
 		set1.insert(i);
 	}
 	//打印输出
 	for (set<int>::iterator it = set1.begin(); it != set1.end(); it++)
 	{
 		cout << *it << " ";
 	}
 	cout << endl;
 
 	set<int>::iterator it1 = set1.lower_bound(5); //大于等于5迭代器
 	set<int>::iterator it2 = set1.upper_bound(5); //大于5的迭代器
 
 	//通过迭代器进行元素的操作
 	cout << "it1 " << *it1 << " " << "it2 " << *it2 << endl;
 
 	//set.equal_range(elem);//返回容器中与elem相等的上下限的两个迭代器，上限是闭区间，下限是开区间
 	pair <set<int>::iterator, set<int>::iterator> pairIt = set1.equal_range(5);
 
 	set<int>::iterator it3 = pairIt.first; //获取第一个
 	set<int>::iterator it4 = pairIt.second; //获取第二个
 
 	// 5 6
 	cout << "it3 " << *it3 << " " << "it4 " << *it4 << endl;
 	Student s1("s1", 31);
 	Student s5("s5", 31);
 	set<Student, StuFunctor> set2;
 	//	multiset与set的区别：set支持唯一键值，每个元素值只能出现一次；而multiset中同一值可以出现多次。
 	pair<set<Student, StuFunctor>::iterator, bool> pair1 = set2.insert(s1);
 	if (pair1.second == true)
 	{
 		cout << "插入s1成功" << endl;
 	}
 	else
 	{
 		cout << "插入s1失败" << endl;
 	}
 
 	pair<set<Student, StuFunctor>::iterator, bool> pair2 = set2.insert(s5);
 	if (pair2.second == true)
 	{
 		cout << "插入s5成功" << endl;
 	}
 	else
 	{
 		cout << "插入s5失败" << endl;
 	}
 	for (set<Student, StuFunctor>::iterator it = set2.begin(); it != set2.end(); it++)
 	{
 		cout << it->age << "\t" << it->name << endl;
 	}
 	cout << "hello..." << endl;
 	system("pause");
 	return;
 }

#define _CRT_SECURE_NO_WARNINGS
 #include <functional>
 #include <iostream>
 using namespace std;
 #include <set>
 
 //multiset与set的区别：set支持唯一键值，每个元素值只能出现一次；而multiset中同一值可以出现多次。
 void main01()
 {
 	multiset<int> set1;
 	int tmp = 0;
 	printf("请输入multiset集合的值:");
 	scanf("%d", &tmp);
 
 	while (tmp!=0)
 	{
 		set1.insert(tmp);
 		printf("请输入multiset集合的值:");
 		scanf("%d", &tmp);
 	}
 
 	//遍历
 	for (multiset<int>::iterator it = set1.begin(); it != set1.end(); it++)
 	{
 		cout << *it << " ";
 	}
 	cout << endl;
 
 	while (!set1.empty())
 	{
 		multiset<int>::iterator it = set1.begin();
 		cout << *it << " ";
 		set1.erase(it);
 	}
 
 
 	cout << "hello..." << endl;
 	system("pause");
 	return;
 }

### 10.2.9Map和multimap容器 ###

map/multimap的简介

* map是标准的**关联式**容器，一个map是一个键值对序列，即(key,value)对。它提供基于key的快速检索能力。
 * map中**key****值是唯一的**。集合中的元素按一定的**顺序**排列。元素插入过程是按排序规则插入，所以不能指定插入位置。
 * map的具体实现采用红黑树变体的平衡二叉树的数据结构。在插入操作和删除操作上比vector快。
 * map可以直接存取key所对应的value，支持\[\]操作符，如map\[key\]=value。
 * multimap与map的区别：map支持唯一键值，每个键只能出现一次；而multimap中相同键可以出现多次。multimap不支持\[\]操作符。
 * \#include <map>

![70 4][]

**map/multimap****对象的默认构造**

map/multimap采用模板类实现，对象的默认构造形式：

map<T1,T2> mapTT;

multimap<T1,T2>  multimapTT;

如：

map<int, char> mapA;

map<string,float> mapB;

//其中T1,T2还可以用各种指针类型或自定义类型

**map****的插入与迭代器**

* map.insert(...);    //往容器插入元素，返回pair<iterator,bool>
 * 在map中插入元素的三种方式：

假设  map<int, string> mapStu;

*  一、通过pair的方式插入对象

mapStu.insert(  pair<int,string>(3,"小张")  );

*  二、通过pair的方式插入对象

mapStu.inset(make\_pair(-1, “校长-1”));

*  三、通过value\_type的方式插入对象

mapStu.insert(  map<int,string>::value\_type(1,"小李")  );

*  四、通过数组的方式插入值

mapStu\[3\] = “小刘";

mapStu\[5\] = “小王"；

* 前三种方法，采用的是insert()方法，该方法**返回值为****pair<iterator,bool>**

*  第四种方法非常直观，但存在一个性能的问题。插入3时，先在mapStu中查找主键为3的项，若没发现，则将一个键为3，值为初始化值的对组插入到mapStu中，然后再将值**修改**成“小刘”。若发现已存在3这个键，则修改这个键对应的value。
 *  string strName = mapStu\[2\];   //取操作或插入操作
 *  只有当mapStu存在2这个键时才是正确的取操作，否则会自动插入一个实例，键为2，值为初始化值。

假设  map<int, string>mapA;

pair< map<int,string>::iterator, bool > pairResult = mapA.insert(pair<int,string>(3,"小张"));                       //插入方式一

int iFirstFirst = (pairResult.first)->first;            //iFirst == 3;

string strFirstSecond = (pairResult.first)->second;          //strFirstSecond为"小张"

bool bSecond = pairResult.second;                                                         //bSecond == true;

mapA.insert(map<int,string>::value\_type(1,"小李"));                     //插入方式二

mapA\[3\] = "小刘";                     //修改value

mapA\[5\] = "小王";                     //插入方式三

string str1 = mapA\[2\];                        //执行插入 string() 操作，返回的str1的字符串内容为空。

string str2 = mapA\[3\];                        //取得value，str2为"小刘"

//迭代器遍历

for (map<int,string>::iterator it=mapA.begin(); it!=mapA.end(); ++it)

pair<int, string> pr = \*it;

int iKey = pr.first;

string strValue = pr.second;

**map.rbegin()与map.rend()  略。**

* **map<T1,T2,less<T1>>  mapA;  //该容器是按键的升序方式排列元素。未指定函数对象，默认采用less<T1>函数对象。**
 * **map<T1,T2,greater<T1>> mapB;   //该容器是按键的降序方式排列元素。**
 * **less<T1>与greater<T1>可以替换成其它的函数对象functor。**
 * **可编写自定义函数对象以进行自定义类型的比较，使用方法与set构造时所用的函数对象一样。**
 * **map.begin();  //返回容器中第一个数据的迭代器。**
 * **map.end();  //返回容器中最后一个数据之后的迭代器。**
 * **map.rbegin();  //返回容器中倒数第一个元素的迭代器。**
 * **map.rend();   //返回容器中倒数最后一个元素的后面的迭代器。**

map对象的拷贝构造与赋值

map(const map &mp);                   //拷贝构造函数

map& operator=(const map &mp);         //重载等号操作符

map.swap(mp);                                    //交换两个集合容器

例如:

map<int, string> mapA;

mapA.insert(pair<int,string>(3,"小张"));

mapA.insert(pair<int,string>(1,"小杨"));

mapA.insert(pair<int,string>(7,"小赵"));

mapA.insert(pair<int,string>(5,"小王"));

map<int ,string> mapB(mapA);                          //拷贝构造

map<int, string> mapC;

mapC = mapA;                                                                           //赋值

mapC\[3\] = "老张";

mapC.swap(mapA);                            //交换

**map的大小**

*  **map.size();          //返回容器中元素的数目**
 *  **map.empty();//判断容器是否为空**

map<int, string> mapA;

mapA.insert(pair<int,string>(3,"小张"));

mapA.insert(pair<int,string>(1,"小杨"));

mapA.insert(pair<int,string>(7,"小赵"));

mapA.insert(pair<int,string>(5,"小王"));

if (mapA.empty())

int iSize = mapA.size();              //iSize == 4

**map的删除**

*  **map.clear();                 //删除所有元素**
 *  **map.erase(pos);         //删除pos迭代器所指的元素，返回下一个元素的迭代器。**
 *  **map.erase(beg,end);              //删除区间\[beg,end)的所有元素  ，返回下一个元素的迭代器。**
 *  **map.erase(keyElem);     //删除容器中key为keyElem的对组。**

map<int, string> mapA;

mapA.insert(pair<int,string>(3,"小张"));

mapA.insert(pair<int,string>(1,"小杨"));

mapA.insert(pair<int,string>(7,"小赵"));

mapA.insert(pair<int,string>(5,"小王"));

//删除区间内的元素

map<int,string>::iterator itBegin=mapA.begin();

++ itBegin;

map<int,string>::iterator itEnd=mapA.end();

mapA.erase(itBegin,itEnd);                       //此时容器mapA包含按顺序的\{1,"小杨"\}\{3,"小张"\}两个元素。

mapA.insert(pair<int,string>(7,"小赵"));

mapA.insert(pair<int,string>(5,"小王"));

//删除容器中第一个元素

mapA.erase(mapA.begin());             //此时容器mapA包含了按顺序的\{3,"小张"\}\{5,"小王"\}\{7,"小赵"\}三个元素

//删除容器中key为5的元素

mapA.erase(5);

//删除mapA的所有元素

mapA.clear();                     //容器为空

**map的查找**

*  **map.find(key);   查找键key是否存在，若存在，返回该键的元素的迭代器；若不存在，返回map.end();**
 *  **map.count(keyElem);   //返回容器中key为keyElem的对组个数。对map来说，要么是0，要么是1。对multimap来说，值可能大于1。**

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;width:426.1pt;"> map&lt;int,string&gt;::iterator it=mapStu.find(3); if(it == mapStu.end()) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; //没找到 } else { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; //找到了 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; pair&lt;int, string&gt; pairStu = *it; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; int iID = pairStu.first;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; //或&nbsp;&nbsp; int&nbsp; iID = it-&gt;first; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; string strName = pairStu.second;&nbsp;&nbsp; //或&nbsp;&nbsp; string strName = it-&gt;second; } </td> 
 </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;width:426.1pt;"> 
 <ul> 
 <li>map.lower_bound(keyElem);&nbsp; //返回第一个key&gt;=keyElem元素的迭代器。</li> 
 <li>map.upper_bound(keyElem);&nbsp;&nbsp;&nbsp; &nbsp;&nbsp; //&nbsp; 返回第一个key&gt;keyElem元素的迭代器。</li> 
 </ul>例如：&nbsp; mapStu是用map&lt;int,string&gt;声明的容器，已包含{1,"小李"}{3,"小张"}{5,"小王"}{7,"小赵"}{9,"小陈"}元素。map&lt;int,string&gt;::iterator it; it = mapStu.lower_bound(5);&nbsp; //it-&gt;first==5&nbsp;&nbsp;&nbsp; it-&gt;second=="小王" it = mapStu.upper_bound(5);&nbsp;&nbsp; //it-&gt;first==7&nbsp;&nbsp; it-&gt;second=="小赵" it = mapStu.lower_bound(6);&nbsp; //it-&gt;first==7&nbsp;&nbsp;&nbsp; it-&gt;second=="小赵" it = mapStu.upper_bound(6);&nbsp;&nbsp;&nbsp; //it-&gt;first==7&nbsp;&nbsp; it-&gt;second=="小赵" &nbsp; </td> 
 </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;width:426.1pt;"> 
 <ul> 
 <li>map.equal_range(keyElem);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; //返回容器中key与keyElem相等的上下限的两个迭代器。上限是闭区间，下限是开区间，如[beg,end)。</li> 
 </ul>&nbsp; 以上函数返回两个迭代器，而这两个迭代器被封装在pair中。 &nbsp; 例如 map&lt;int,string&gt; mapStu; ...&nbsp; //往mapStu容器插入元素{1,"小李"}{3,"小张"}{5,"小王"}{7,"小赵"}{9,"小陈"} pair&lt; map&lt;int,string&gt;::iterator , map&lt;int,string&gt;::iterator &gt; pairIt = mapStu.equal_range(5); map&lt;int, string&gt;::iterator itBeg = pairIt.first; map&lt;int, string&gt;::iterator itEnd = pairIt.second; //此时 itBeg-&gt;first==5&nbsp; ,&nbsp; itEnd-&gt;first == 7, itBeg-&gt;second=="小王", itEnd-&gt;second=="小赵" &nbsp; </td> 
 </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;width:426.1pt;"> Multimap案例: //1个key值可以对应多个valude=è分组 //公司有销售部 sale （员工2名）、技术研发部 development （1人）、财务部 Financial （2人） //人员信息有：姓名，年龄，电话、工资等组成 //通过 multimap进行信息的插入、保存、显示 //分部门显示员工信息 &nbsp; </td> 
 </tr> 
 </tbody> 
</table>

#define _CRT_SECURE_NO_WARNINGS
 #include <functional>
 #include <iostream>
 using namespace std;
 #include <map>
 #include <string>
 
 
 //map元素的添加/遍历/删除基本操作
 void main01()
 {
 	map<int, string> map1;
 	//方法1
 	map1.insert(pair<int,string>(1,"teacher01"));
 	map1.insert(pair<int,string>(2,"teacher02"));
 
 	//方法2
 	map1.insert(make_pair(3,"teacher03"));
 	map1.insert(make_pair(4, "teacher04"));
 
 	//方法3
 	map1.insert(map<int,string>::value_type(5,"teacher05"));
 	map1.insert(map<int, string>::value_type(6, "teacher06"));
 
 	//方法4
 	map1[7] = "teacher07";
 	map1[8] = "teacher08";
 	//容器的遍历
 	for (map<int, string>::iterator it = map1.begin(); it != map1.end(); it++)
 	{
 		cout << it->first << "\t" << it->second << endl;
 	}
 	cout << "遍历结束" << endl;
 
 	//容器元素的删除
 	while (!map1.empty())
 	{
 		map<int, string>::iterator it = map1.begin();
 		cout << it->first << "\t" << it->second << endl;
 		map1.erase(it);
 	}
 
 	cout << "hello..." << endl;
 	system("pause");
 	return;
 }
 //插入的四种方法 异同
 //前三种方法 返回值为pair<iterator,bool>	若key已经存在 则报错
 //	方法四									若key已经存在,则修改		
 void main02()
 {
 	map<int, string> map1;
 	//方法1
 	pair<map<int, string>::iterator, bool> mypair1 = map1.insert(pair<int, string>(1, "teacher01"));
 	map1.insert(pair<int, string>(2, "teacher02"));
 	//方法2
 	pair<map<int, string>::iterator, bool> mypair2 = map1.insert(make_pair(2,"teacher03"));
 	map1.insert(make_pair(4, "teacher05"));
 
 	//方法3
 	pair<map<int, string>::iterator, bool> mypair3 = map1.insert(map<int,string>::value_type(5,"teacher05"));
 	if (mypair3.second !=true)
 	{
 		cout << "key 5 插入失败" << endl;
 	}
 	else
 	{
 		cout << mypair3.first->first << "\t" << mypair3.first->second << endl;
 	}
 	pair<map<int, string>::iterator, bool> mypair4 = map1.insert(map<int, string>::value_type(5, "teacher55"));
 	if (mypair4.second != true)
 	{
 		cout << "key 5 插入失败" << endl;
 	}
 	else
 	{
 		cout << mypair4.first->first << "\t" << mypair4.first->second << endl;
 	}
 	//方法4
 	map1[7] = "teacher07";
 	map1[7] = "teacher77";
 
 	//容器的遍历
 	for (map<int, string>::iterator it = map1.begin(); it != map1.end(); it++)
 	{
 		cout << it->first << "\t" << it->second << endl;
 	}
 	cout << "遍历结束" << endl;
 
 }
 
 void main()
 {
 	map<int, string> map1;
 	//方法1
 	map1.insert(pair<int, string>(1, "teacher01"));
 	map1.insert(pair<int, string>(2, "teacher02"));
 
 	//方法2 
 	map1.insert(make_pair(3, "teacher04"));
 	map1.insert(make_pair(4, "teacher05"));
 
 	//方法3 
 	map1.insert(map<int, string>::value_type(5, "teacher05"));
 	map1.insert(map<int, string>::value_type(6, "teacher06"));
 
 	//方法4
 	map1[7] = "teacher07";
 	map1[8] = "teacher08";
 
 	//容器的遍历
 	for (map<int, string>::iterator it = map1.begin(); it != map1.end(); it++)
 	{
 		cout << it->first << " " << it->second << endl;
 	}
 	cout << "遍历结束" << endl;
 
 	//map的查找
 	//异常处理
 	map<int, string>::iterator it2 = map1.find(100);
 	if (it2 == map1.end())
 	{
 		cout << "key 100 的值 不存在" << endl;
 	}
 	else
 	{
 		cout << it2->first << "\t" << it2->second << endl;
 	}
 
 	//equal_range //异常处理
 	pair<map<int, string>::iterator, map<int, string>::iterator> mypair = map1.equal_range(5); //返回两个迭代器 形成一个 pair
 	//第一个迭代器 >= 5的 位置 
 	//第一个迭代器 = 5的 位置 
 
 	if (mypair.first ==map1.end())
 	{
 		cout << "第一个迭代器 >= 5的 位置 不存在" << endl;
 	}
 	else
 	{
 		cout << mypair.second->first << "\t" << mypair.second->second << endl;
 	}
 }

#define _CRT_SECURE_NO_WARNINGS
 #include <functional>
 #include <iostream>
 using namespace std;
 #include <map>
 #include <string>
 
 
 //Multimap 案例:
 //1个key值可以对应多个valude =分组 
 //公司有销售部 sale （员工2名）、技术研发部 development （2人）、财务部 Financial （1人） 
 //人员信息有：姓名，年龄，电话、工资等组成
 //通过 multimap进行 信息的插入、保存、显示
 //分部门显示员工信息 
 
 class Person
 {
 public:
 	string	name;
 	int		age;
 	string	tel;
 	double	saly;
 
 private:
 
 };
 
 void main01()
 {
 	Person p1, p2, p3, p4, p5;
 	p1.name = "王1";
 	p1.age = 300;
 
 	p2.name = "王2";
 	p2.age = 32;
 
 	p3.name = "张3";
 	p3.age = 33;
 
 	p4.name = "张4";
 	p4.age = 34;
 
 	p5.name = "赵5";
 	p5.age = 35;
 
 	multimap<string, Person> map2;
 	//Sale部门
 	map2.insert(make_pair("sale",p1));
 	map2.insert(make_pair("sale", p2));
 
 	//development 部门
 	map2.insert(make_pair("development", p3));
 	map2.insert(make_pair("development", p4));
 
 	//Financial 部门
 	map2.insert(make_pair("Financial", p5));
 
 	//遍历 分部门显示员工信息
 	for (multimap<string, Person>::iterator it = map2.begin(); it != map2.end(); it++)
 	{
 		cout << it->first << " " << it->second.name << endl;
 	}
 	cout << "遍历结束" << endl;
 
 	int num2 = map2.count("development");
 	cout << "development部门人数==>" << num2 << endl;
 
 	cout << "development部门员工信息" << endl;
 	multimap<string, Person>::iterator it2 = map2.find("development");
 
 	int tag = 0;
 	cout << "development部门员工具体信息" << endl;
 	while (it2 != map2.end() && tag < num2)
 	{
 		cout << it2->first << "\t" << it2->second.name << endl;
 		it2++;
 		tag++;
 	}
 	system("pause");
 }
 
 //age = 32修改成 name32
 void main()
 {
 	Person p1, p2, p3, p4, p5;
 
 	p1.name = "王1";
 	p1.age = 31;
 
 	p2.name = "王2";
 	p2.age = 32;
 
 	p3.name = "张3";
 	p3.age = 33;
 
 	p4.name = "张4";
 	p4.age = 34;
 
 	p5.name = "赵5";
 	p5.age = 35;
 
 	multimap<string, Person> map2;
 	//sale部门
 	map2.insert(make_pair("sale",p1));
 	map2.insert(make_pair("sale",p2));
 
 	//development 部门
 	map2.insert(make_pair("development",p3));
 	map2.insert(make_pair("development",p4));
 
 	//Financial 部门
 	map2.insert(make_pair("Financial", p5));
 
 
 	cout << "\n按照条件 检索数据 进行修改 " << endl;
 	for (multimap<string, Person>::iterator it = map2.begin(); it != map2.end(); it++)
 	{
 		if (it->second.age == 32)
 		{
 			it->second.name = "name32";
 		}
 	}
 	for (multimap<string, Person>::iterator it = map2.begin(); it != map2.end(); it++)
 	{
 		cout << it->first << "\t" << it->second.name << endl;
 	}
 
 	system("pause");
 }

### 10.2.10容器共性机制研究 ###

10.2.9.1容器的共通能力

C++模板是容器的概念。

**理论提高：**所有容器提供的都是值（value）语意，而非引用（reference）语意。**容器执行插入元素的操作时，内部实施拷贝动作。**所以STL容器内存储的元素必须**能够被拷贝**（必须提供拷贝构造函数）。

* 除了queue与stack外，每个容器都提供可返回迭代器的函数，运用返回的迭代器就可以访问元素。
 * 通常STL不会丢出异常。要求使用者确保传入正确的参数。
 * 每个容器都提供了一个默认构造函数跟一个默认拷贝构造函数。
 * 如已有容器vecIntA。
 * vector<int> vecIntB(vecIntA);  //调用拷贝构造函数，复制vecIntA到vecIntB中。
 * 与大小相关的操作方法(c代表容器)：

c.size();   //返回容器中元素的个数

c.empty();   //判断容器是否为空

*  比较操作(c1,c2代表容器)：

c1 == c2     判断c1是否等于c2

c1 != c2      判断c1是否不等于c2

c1 = c2        把c2的所有元素指派给c1

![70 5][]

10.2.9.2各个容器的使用时机

*  **Vector的使用场景：比如软件历史操作记录的存储，我们经常要查看历史记录，比如上一次的记录，上上次的记录，但却不会去删除记录，因为记录是事实的描述。**
 *  ** deque的使用场景：比如排队购票系统，对排队者的存储可以采用deque，支持头端的快速移除，尾端的快速添加。如果采用vector，则头端移除时，会移动大量的数据，速度慢。**
 *  **vector与deque的比较：**
 *  **一：vector.at()比deque.at()效率高，比如vector.at(0)是固定的，deque的开始位置却是不固定的。**
 *  **二：如果有大量释放操作的话，vector花的时间更少，这跟二者的内部实现有关。**
 *  **三：deque支持头部的快速插入与快速移除，这是deque的优点。**
 *  **list的使用场景：比如公交车乘客的存储，随时可能有乘客下车，支持频繁的不确实位置元素的移除插入。**
 *  **set的使用场景：比如对手机游戏的个人得分记录的存储，存储要求从高分到低分的顺序排列。 **
 *  **map的使用场景：比如按ID号存储十万个用户，想要快速要通过ID查找对应的用户。二叉树的查找效率，这时就体现出来了。如果是vector容器，最坏的情况下可能要遍历完整个容器才能找到该用户。**

### 10.2.11其他 ###

#define _CRT_SECURE_NO_WARNINGS
 #include <functional>
 #include <iostream>
 #include <vector>
 using namespace std;
 
 class Teacher
 {
 public:
 	Teacher(char *name, int age)
 	{
 		m_pname = new char[strlen(name) + 1];
 		strcpy(m_pname, name);
 		m_age = age;
 	}
 
 	~Teacher()
 	{
 		if (m_pname != NULL)
 		{
 			delete[] m_pname;
 			m_pname = NULL;
 			m_age = 0;
 		}
 	}
 
 	//Teacher t2 = t1;
 	//拷贝构造函数
 	Teacher(const Teacher &obj)
 	{
 		m_pname = new char[strlen(obj.m_pname) + 1];
 		strcpy(m_pname,obj.m_pname);
 		m_age = obj.m_age;
 	}
 
 	//重载 =号操作符
 	//t3 = t2 = t1
 	Teacher& operator=(const Teacher &obj)
 	{
 		//1 先把旧的内存释放掉
 		if (m_pname != NULL)
 		{
 			delete[] m_pname;
 			m_pname = NULL;
 			m_age = 0;
 		}
 
 		//2 根据obj的大小分配内存
 		m_pname = new char[strlen(obj.m_pname) + 1];
 
 		//3 拷贝数据
 		strcpy(m_pname,obj.m_pname);
 		m_age = obj.m_age;
 
 		return *this;
 	}
 public:
 	void printT()
 	{
 		cout << m_pname << "\t" << m_age << endl;
 	}
 private:
 	char	*m_pname;
 	int		m_age;
 };
 
 
 
 void main()
 {
 	Teacher t1("t1",31);
 	t1.printT();
 
 	vector<Teacher> v1;
 	v1.push_back(t1); //把t1拷贝了一份 存入到容器中了....
 	system("pause");
 }

## 10.3算法 ##

### 10.3.1算法基础 ###

10.3.1.1算法概述

* 算法部分主要由头文件<algorithm>，<numeric>和<functional>组成。
 * <algorithm>是所有STL头文件中最大的一个，其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、反转、排序、合并等等。
 * <numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。
 * <functional>中则定义了一些模板类，用以声明函数对象。
 * STL提供了大量实现算法的模版函数，只要我们熟悉了STL之后，许多代码可以被大大的化简，只需要通过调用一两个算法模板，就可以完成所需要的功能，从而大大地提升效率。
 * \#include <algorithm>
 * \#include <numeric>
 * \#include <functional>

10.3.1.2 STL中算法分类

*  操作对象
    
     *  直接改变容器的内容
     *  将原容器的内容复制一份,修改其副本,然后传回该副本
 *  功能:
    
     *  非可变序列算法 指不直接修改其所操作的容器内容的算法
        
         *  计数算法        count、count\_if
         *  搜索算法        search、find、find\_if、find\_first\_of、…
         *  比较算法        equal、mismatch、lexicographical\_compare
     *  可变序列算法 指可以修改它们所操作的容器内容的算法
        
         *  删除算法        remove、remove\_if、remove\_copy、…
         *  修改算法        for\_each、transform
         *  排序算法        sort、stable\_sort、partial\_sort、
     *  排序算法 包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作
     *  数值算法 对容器内容进行数值计算

10.3.1.3查找算法(13个)：判断容器中是否包含某个值

<table> 
 <tbody> 
 <tr> 
 <td style="background-color:#182448;width:50.4pt;"> 函数名 </td> 
 <td style="background-color:#182448;width:41pt;"> 头文件 </td> 
 <td style="background-color:#182448;width:323.9pt;"> 函数功能 </td> 
 </tr> 
 <tr> 
 <td style="width:50.4pt;"> adjacent_find </td> 
 <td style="width:41pt;"> &lt;algorithm&gt; </td> 
 <td style="width:323.9pt;"> 在iterator对标识元素范围内,查找一对相邻重复元素,找到则返回指向这对元素的第一个元素的ForwardIterator&nbsp;.否则返回last.重载版本使用输入的二元操作符代替相等的判断 </td> 
 </tr> 
 <tr> 
 <td style="width:41pt;"> 函数原形 </td> 
 <td style="width:323.9pt;"> template&lt;class&nbsp;FwdIt&gt; FwdIt&nbsp;adjacent_find(FwdIt&nbsp;first,&nbsp;FwdIt&nbsp;last); </td> 
 </tr> 
 <tr> 
 <td style="width:323.9pt;"> template&lt;class&nbsp;FwdIt,&nbsp;class&nbsp;Pred&gt; FwdIt&nbsp;adjacent_find(FwdIt&nbsp;first,&nbsp;FwdIt&nbsp;last,&nbsp;Pred&nbsp;pr); </td> 
 </tr> 
 <tr> 
 <td style="width:50.4pt;"> binary_search </td> 
 <td style="width:41pt;"> &lt;algorithm&gt; </td> 
 <td style="width:323.9pt;"> 在有序序列中查找value,找到返回true.重载的版本实用指定的比较函数对象或函数指针来判断相等 </td> 
 </tr> 
 <tr> 
 <td style="width:41pt;"> 函数原形 </td> 
 <td style="width:323.9pt;"> template&lt;class&nbsp;FwdIt,&nbsp;class&nbsp;T&gt; bool&nbsp;binary_search(FwdIt&nbsp;first,&nbsp;FwdIt&nbsp;last,&nbsp;const&nbsp;T&amp;&nbsp;val); </td> 
 </tr> 
 <tr> 
 <td style="width:323.9pt;"> template&lt;class&nbsp;FwdIt,&nbsp;class&nbsp;T,&nbsp;class&nbsp;Pred&gt; bool&nbsp;binary_search(FwdIt&nbsp;first,&nbsp;FwdIt&nbsp;last,&nbsp;const&nbsp;T&amp;&nbsp;val,Pred&nbsp;pr); </td> 
 </tr> 
 <tr> 
 <td style="width:50.4pt;"> count </td> 
 <td style="width:41pt;"> &lt;algorithm&gt; </td> 
 <td style="width:323.9pt;"> 利用等于操作符,把标志范围内的元素与输入值比较,返回相等元素个数 </td> 
 </tr> 
 <tr> 
 <td style="width:41pt;"> 函数原形 </td> 
 <td style="width:323.9pt;"> template&lt;class&nbsp;InIt,&nbsp;class&nbsp;Dist&gt; size_t&nbsp;count(InIt&nbsp;first,&nbsp;InIt&nbsp;last,const&nbsp;T&amp;&nbsp;val,&nbsp;Dist&amp;&nbsp;n); </td> 
 </tr> 
 <tr> 
 <td style="width:50.4pt;"> count_if </td> 
 <td style="width:41pt;"> &lt;algorithm&gt; </td> 
 <td style="width:323.9pt;"> 利用输入的操作符,对标志范围内的元素进行操作,返回结果为true的个数 </td> 
 </tr> 
 <tr> 
 <td style="width:41pt;"> 函数原形 </td> 
 <td style="width:323.9pt;"> template&lt;class&nbsp;InIt,&nbsp;class&nbsp;Pred,&nbsp;class&nbsp;Dist&gt; size_t&nbsp;count_if(InIt&nbsp;first,&nbsp;InIt&nbsp;last,&nbsp;Pred&nbsp;pr); </td> 
 </tr> 
 <tr> 
 <td style="width:50.4pt;"> equal_range </td> 
 <td style="width:41pt;"> &lt;algorithm&gt; </td> 
 <td style="width:323.9pt;"> 功能类似equal，返回一对iterator，第一个表示lower_bound，第二个表示upper_bound </td> 
 </tr> 
 <tr> 
 <td style="width:41pt;"> 函数原形 </td> 
 <td style="width:323.9pt;"> template&lt;class&nbsp;FwdIt,&nbsp;class&nbsp;T&gt; pair&lt;FwdIt,&nbsp;FwdIt&gt;&nbsp;equal_range(FwdIt&nbsp;first,&nbsp;FwdIt&nbsp;last,const&nbsp;T&amp;&nbsp;val); </td> 
 </tr> 
 <tr> 
 <td style="width:323.9pt;"> template&lt;class&nbsp;FwdIt,&nbsp;class&nbsp;T,&nbsp;class&nbsp;Pred&gt; pair&lt;FwdIt,&nbsp;FwdIt&gt;&nbsp;equal_range(FwdIt&nbsp;first,&nbsp;FwdIt&nbsp;last,const&nbsp;T&amp;&nbsp;val,&nbsp;Pred&nbsp;pr); </td> 
 </tr> 
 <tr> 
 <td style="width:50.4pt;"> find </td> 
 <td style="width:41pt;"> &lt;algorithm&gt; </td> 
 <td style="width:323.9pt;"> 利用底层元素的等于操作符,对指定范围内的元素与输入值进行比较.当匹配时,结束搜索,返回该元素的一个InputIterator </td> 
 </tr> 
 <tr> 
 <td style="width:41pt;"> 函数原形 </td> 
 <td style="width:323.9pt;"> template&lt;class&nbsp;InIt,&nbsp;class&nbsp;T&gt; InIt&nbsp;find(InIt&nbsp;first,&nbsp;InIt&nbsp;last,&nbsp;const&nbsp;T&amp;&nbsp;val); </td> 
 </tr> 
 <tr> 
 <td style="width:50.4pt;"> find_end </td> 
 <td style="width:41pt;"> &lt;algorithm&gt; </td> 
 <td style="width:323.9pt;"> 在指定范围内查找"由输入的另外一对iterator标志的第二个序列"的最后一次出现.找到则返回最后一对的第一个ForwardIterator,否则返回输入的"另外一对"的第一个ForwardIterator.重载版本使用用户输入的操作符代替等于操作 </td> 
 </tr> 
 <tr> 
 <td style="width:41pt;"> 函数原形 </td> 
 <td style="width:323.9pt;"> template&lt;class&nbsp;FwdIt1,&nbsp;class&nbsp;FwdIt2&gt;FwdIt1&nbsp;find_end(FwdIt1&nbsp;first1,&nbsp;FwdIt1&nbsp;last1,FwdIt2&nbsp;first2,&nbsp;FwdIt2&nbsp;last2); </td> 
 </tr> 
 <tr> 
 <td style="width:323.9pt;"> template&lt;class&nbsp;FwdIt1,&nbsp;class&nbsp;FwdIt2,&nbsp;class&nbsp;Pred&gt; FwdIt1&nbsp;find_end(FwdIt1&nbsp;first1,&nbsp;FwdIt1&nbsp;last1,FwdIt2&nbsp;first2,&nbsp;FwdIt2&nbsp;last2,&nbsp;Pred&nbsp;pr); </td> 
 </tr> 
 <tr> 
 <td style="width:50.4pt;"> find_first_of </td> 
 <td style="width:41pt;"> &lt;algorithm&gt; </td> 
 <td style="width:323.9pt;"> 在指定范围内查找"由输入的另外一对iterator标志的第二个序列"中任意一个元素的第一次出现。重载版本中使用了用户自定义操作符 </td> 
 </tr> 
 <tr> 
 <td style="width:41pt;"> 函数原形 </td> 
 <td style="width:323.9pt;"> template&lt;class&nbsp;FwdIt1,&nbsp;class&nbsp;FwdIt2&gt; FwdIt1&nbsp;find_first_of(FwdIt1&nbsp;first1,&nbsp;FwdIt1&nbsp;last1,FwdIt2&nbsp;first2,&nbsp;FwdIt2&nbsp;last2); </td> 
 </tr> 
 <tr> 
 <td style="width:323.9pt;"> template&lt;class&nbsp;FwdIt1,&nbsp;class&nbsp;FwdIt2,&nbsp;class&nbsp;Pred&gt; FwdIt1&nbsp;find_first_of(FwdIt1&nbsp;first1,&nbsp;FwdIt1&nbsp;last1,FwdIt2&nbsp;first2,&nbsp;FwdIt2&nbsp;last2,&nbsp;Pred&nbsp;pr); </td> 
 </tr> 
 <tr> 
 <td style="width:50.4pt;"> find_if </td> 
 <td style="width:41pt;"> &lt;algorithm&gt; </td> 
 <td style="width:323.9pt;"> 使用输入的函数代替等于操作符执行find </td> 
 </tr> 
 <tr> 
 <td style="width:41pt;"> &nbsp; </td> 
 <td style="width:323.9pt;"> template&lt;class&nbsp;InIt,&nbsp;class&nbsp;Pred&gt; InIt&nbsp;find_if(InIt&nbsp;first,&nbsp;InIt&nbsp;last,&nbsp;Pred&nbsp;pr); </td> 
 </tr> 
 <tr> 
 <td style="width:50.4pt;"> lower_bound </td> 
 <td style="width:41pt;"> &lt;algorithm&gt; </td> 
 <td style="width:323.9pt;"> 返回一个ForwardIterator，指向在有序序列范围内的可以插入指定值而不破坏容器顺序的第一个位置.重载函数使用自定义比较操作 </td> 
 </tr> 
 <tr> 
 <td style="width:41pt;"> 函数原形 </td> 
 <td style="width:323.9pt;"> template&lt;class&nbsp;FwdIt,&nbsp;class&nbsp;T&gt; FwdIt&nbsp;lower_bound(FwdIt&nbsp;first,&nbsp;FwdIt&nbsp;last,&nbsp;const&nbsp;T&amp;&nbsp;val); </td> 
 </tr> 
 <tr> 
 <td style="width:323.9pt;"> template&lt;class&nbsp;FwdIt,&nbsp;class&nbsp;T,&nbsp;class&nbsp;Pred&gt; FwdIt&nbsp;lower_bound(FwdIt&nbsp;first,&nbsp;FwdIt&nbsp;last,&nbsp;const&nbsp;T&amp;&nbsp;val,&nbsp;Pred&nbsp;pr); </td> 
 </tr> 
 <tr> 
 <td style="width:50.4pt;"> upper_bound </td> 
 <td style="width:41pt;"> &lt;algorithm&gt; </td> 
 <td style="width:323.9pt;"> 返回一个ForwardIterator,指向在有序序列范围内插入value而不破坏容器顺序的最后一个位置，该位置标志一个大于value的值.重载函数使用自定义比较操作 </td> 
 </tr> 
 <tr> 
 <td style="width:41pt;"> 函数原形 </td> 
 <td style="width:323.9pt;"> template&lt;class&nbsp;FwdIt,&nbsp;class&nbsp;T&gt; FwdIt&nbsp;upper_bound(FwdIt&nbsp;first,&nbsp;FwdIt&nbsp;last,&nbsp;const&nbsp;T&amp;&nbsp;val); </td> 
 </tr> 
 <tr> 
 <td style="width:323.9pt;"> template&lt;class&nbsp;FwdIt,&nbsp;class&nbsp;T,&nbsp;class&nbsp;Pred&gt; FwdIt&nbsp;upper_bound(FwdIt&nbsp;first,&nbsp;FwdIt&nbsp;last,&nbsp;const&nbsp;T&amp;&nbsp;val,&nbsp;Pred&nbsp;pr); </td> 
 </tr> 
 <tr> 
 <td style="width:50.4pt;"> search </td> 
 <td style="width:41pt;"> &lt;algorithm&gt; </td> 
 <td style="width:323.9pt;"> 给出两个范围，返回一个ForwardIterator,查找成功指向第一个范围内第一次出现子序列(第二个范围)的位置，查找失败指向last1,重载版本使用自定义的比较操作 </td> 
 </tr> 
 <tr> 
 <td style="width:41pt;"> 函数原形 </td> 
 <td style="width:323.9pt;"> template&lt;class&nbsp;FwdIt1,&nbsp;class&nbsp;FwdIt2&gt; FwdIt1&nbsp;search(FwdIt1&nbsp;first1,&nbsp;FwdIt1&nbsp;last1,FwdIt2&nbsp;first2,&nbsp;FwdIt2&nbsp;last2); </td> 
 </tr> 
 <tr> 
 <td style="width:323.9pt;"> template&lt;class&nbsp;FwdIt1,&nbsp;class&nbsp;FwdIt2,&nbsp;class&nbsp;Pred&gt; FwdIt1&nbsp;search(FwdIt1&nbsp;first1,&nbsp;FwdIt1&nbsp;last1,&nbsp;FwdIt2&nbsp;first2,&nbsp;FwdIt2&nbsp;last2,&nbsp;Pred&nbsp;pr); </td> 
 </tr> 
 <tr> 
 <td style="width:50.4pt;"> search_n </td> 
 <td style="width:41pt;"> &lt;algorithm&gt; </td> 
 <td style="width:323.9pt;"> 在指定范围内查找val出现n次的子序列。重载版本使用自定义的比较操作 </td> 
 </tr> 
 <tr> 
 <td style="width:41pt;"> 函数原形 </td> 
 <td style="width:323.9pt;"> template&lt;class&nbsp;FwdIt,&nbsp;class&nbsp;Dist,&nbsp;class&nbsp;T&gt; FwdIt&nbsp;search_n(FwdIt&nbsp;first,&nbsp;FwdIt&nbsp;last,Dist&nbsp;n,&nbsp;const&nbsp;T&amp;&nbsp;val); </td> 
 </tr> 
 <tr> 
 <td style="width:323.9pt;"> template&lt;class&nbsp;FwdIt,&nbsp;class&nbsp;Dist,&nbsp;class&nbsp;T,&nbsp;class&nbsp;Pred&gt; FwdIt&nbsp;search_n(FwdIt&nbsp;first,&nbsp;FwdIt&nbsp;last,Dist&nbsp;n,&nbsp;const&nbsp;T&amp;&nbsp;val,&nbsp;Pred&nbsp;pr); </td> 
 </tr> 
 </tbody> 
</table>

10.3.1.4堆算法(4个)

--------------------

10.3.1.5关系算法(8个)

10.3.1.6集合算法(4个)

10.3.1.6列组合算法(2个)

提供计算给定集合按一定顺序的所有可能排列组合

--------------------

10.3.1.7排序和通用算法(14个)：提供元素排序策略

<table> 
 <tbody> 
 <tr> 
 <td style="background-color:#182448;"> 函数名 </td> 
 <td style="background-color:#182448;"> 头文件 </td> 
 <td style="background-color:#182448;"> 函数功能 </td> 
 </tr> 
 <tr> 
 <td> inplace_merge </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 合并两个有序序列，结果序列覆盖两端范围。重载版本使用输入的操作进行排序 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;BidIt&gt; void&nbsp;inplace_merge(BidIt&nbsp;first,&nbsp;BidIt&nbsp;middle,&nbsp;BidIt&nbsp;last); </td> 
 </tr> 
 <tr> 
 <td> template&lt;class&nbsp;BidIt,&nbsp;class&nbsp;Pred&gt; void&nbsp;inplace_merge(BidIt&nbsp;first,&nbsp;BidIt&nbsp;middle,&nbsp;BidIt&nbsp;last,&nbsp;Pred&nbsp;pr); </td> 
 </tr> 
 <tr> 
 <td> merge </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 合并两个有序序列，存放到另一个序列。重载版本使用自定义的比较 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;InIt1,&nbsp;class&nbsp;InIt2,&nbsp;class&nbsp;OutIt&gt;OutIt&nbsp;merge(InIt1&nbsp;first1,&nbsp;InIt1&nbsp;last1,InIt2&nbsp;first2,&nbsp;InIt2&nbsp;last2,&nbsp;OutIt&nbsp;x); </td> 
 </tr> 
 <tr> 
 <td> template&lt;class&nbsp;InIt1,&nbsp;class&nbsp;InIt2,&nbsp;class&nbsp;OutIt,&nbsp;class&nbsp;Pred&gt; OutIt&nbsp;merge(InIt1&nbsp;first1,&nbsp;InIt1&nbsp;last1,InIt2&nbsp;first2,&nbsp;InIt2&nbsp;last2,&nbsp;OutIt&nbsp;x,&nbsp;Pred&nbsp;pr); </td> 
 </tr> 
 <tr> 
 <td> nth_element </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 将范围内的序列重新排序，使所有小于第n个元素的元素都出现在它前面，而大于它的都出现在后面。重载版本使用自定义的比较操作 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;RanIt&gt; void&nbsp;nth_element(RanIt&nbsp;first,&nbsp;RanIt&nbsp;nth,&nbsp;RanIt&nbsp;last); </td> 
 </tr> 
 <tr> 
 <td> template&lt;class&nbsp;RanIt,&nbsp;class&nbsp;Pred&gt; void&nbsp;nth_element(RanIt&nbsp;first,&nbsp;RanIt&nbsp;nth,&nbsp;RanIt&nbsp;last,&nbsp;Pred&nbsp;pr); </td> 
 </tr> 
 <tr> 
 <td> partial_sort </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 对序列做部分排序，被排序元素个数正好可以被放到范围内。重载版本使用自定义的比较操作 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;RanIt&gt; void&nbsp;partial_sort(RanIt&nbsp;first,&nbsp;RanIt&nbsp;middle,&nbsp;RanIt&nbsp;last); </td> 
 </tr> 
 <tr> 
 <td> template&lt;class&nbsp;RanIt,&nbsp;class&nbsp;Pred&gt; void&nbsp;partial_sort(RanIt&nbsp;first,&nbsp;RanIt&nbsp;middle,&nbsp;RanIt&nbsp;last,&nbsp;Pred&nbsp;pr); </td> 
 </tr> 
 <tr> 
 <td> partial_sort_copy </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 与partial_sort类似，不过将经过排序的序列复制到另一个容器 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;InIt,&nbsp;class&nbsp;RanIt&gt; RanIt&nbsp;partial_sort_copy(InIt&nbsp;first1,&nbsp;InIt&nbsp;last1,RanIt&nbsp;first2,&nbsp;RanIt&nbsp;last2); </td> 
 </tr> 
 <tr> 
 <td> template&lt;class&nbsp;InIt,&nbsp;class&nbsp;RanIt,&nbsp;class&nbsp;Pred&gt; RanIt&nbsp;partial_sort_copy(InIt&nbsp;first1,&nbsp;InIt&nbsp;last1,RanIt&nbsp;first2,&nbsp;RanIt&nbsp;last2,&nbsp;Pred&nbsp;pr); </td> 
 </tr> 
 <tr> 
 <td> partition </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 对指定范围内元素重新排序，使用输入的函数，把结果为true的元素放在结果为false的元素之前 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;BidIt,&nbsp;class&nbsp;Pred&gt; BidIt&nbsp;partition(BidIt&nbsp;first,&nbsp;BidIt&nbsp;last,&nbsp;Pred&nbsp;pr); </td> 
 </tr> 
 <tr> 
 <td> random_shuffle </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 对指定范围内的元素随机调整次序。重载版本输入一个随机数产生操作 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;RanIt&gt; void&nbsp;random_shuffle(RanIt&nbsp;first,&nbsp;RanIt&nbsp;last); </td> 
 </tr> 
 <tr> 
 <td> template&lt;class&nbsp;RanIt,&nbsp;class&nbsp;Fun&gt; void&nbsp;random_shuffle(RanIt&nbsp;first,&nbsp;RanIt&nbsp;last,&nbsp;Fun&amp;&nbsp;f); </td> 
 </tr> 
 <tr> 
 <td> reverse </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 将指定范围内元素重新反序排序 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;BidIt&gt; void&nbsp;reverse(BidIt&nbsp;first,&nbsp;BidIt&nbsp;last); </td> 
 </tr> 
 <tr> 
 <td> reverse_copy </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 与reverse类似，不过将结果写入另一个容器 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;BidIt,&nbsp;class&nbsp;OutIt&gt; OutIt&nbsp;reverse_copy(BidIt&nbsp;first,&nbsp;BidIt&nbsp;last,&nbsp;OutIt&nbsp;x); </td> 
 </tr> 
 <tr> 
 <td> rotate </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 将指定范围内元素移到容器末尾，由middle指向的元素成为容器第一个元素 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;FwdIt&gt; void&nbsp;rotate(FwdIt&nbsp;first,&nbsp;FwdIt&nbsp;middle,&nbsp;FwdIt&nbsp;last); </td> 
 </tr> 
 <tr> 
 <td> rotate_copy </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 与rotate类似，不过将结果写入另一个容器 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;FwdIt,&nbsp;class&nbsp;OutIt&gt; OutIt&nbsp;rotate_copy(FwdIt&nbsp;first,&nbsp;FwdIt&nbsp;middle,&nbsp;FwdIt&nbsp;last,&nbsp;OutIt&nbsp;x); </td> 
 </tr> 
 <tr> 
 <td> sort </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 以升序重新排列指定范围内的元素。重载版本使用自定义的比较操作 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;RanIt&gt; void&nbsp;sort(RanIt&nbsp;first,&nbsp;RanIt&nbsp;last); </td> 
 </tr> 
 <tr> 
 <td> template&lt;class&nbsp;RanIt,&nbsp;class&nbsp;Pred&gt; void&nbsp;sort(RanIt&nbsp;first,&nbsp;RanIt&nbsp;last,&nbsp;Pred&nbsp;pr); </td> 
 </tr> 
 <tr> 
 <td> stable_sort </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 与sort类似，不过保留相等元素之间的顺序关系 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;BidIt&gt; void&nbsp;stable_sort(BidIt&nbsp;first,&nbsp;BidIt&nbsp;last); </td> 
 </tr> 
 <tr> 
 <td> template&lt;class&nbsp;BidIt,&nbsp;class&nbsp;Pred&gt; void&nbsp;stable_sort(BidIt&nbsp;first,&nbsp;BidIt&nbsp;last,&nbsp;Pred&nbsp;pr); </td> 
 </tr> 
 <tr> 
 <td> stable_partition </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 与partition类似，不过不保证保留容器中的相对顺序 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;FwdIt,&nbsp;class&nbsp;Pred&gt; FwdIt&nbsp;stable_partition(FwdIt&nbsp;first,&nbsp;FwdIt&nbsp;last,&nbsp;Pred&nbsp;pr); </td> 
 </tr> 
 </tbody> 
</table>

10.3.1.8删除和替换算法(15个)

<table> 
 <tbody> 
 <tr> 
 <td style="background-color:#182448;"> 函数名 </td> 
 <td style="background-color:#182448;"> 头文件 </td> 
 <td style="background-color:#182448;"> 函数功能 </td> 
 </tr> 
 <tr> 
 <td> copy </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 复制序列 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;InIt,&nbsp;class&nbsp;OutIt&gt; OutIt&nbsp;copy(InIt&nbsp;first,&nbsp;InIt&nbsp;last,&nbsp;OutIt&nbsp;x); </td> 
 </tr> 
 <tr> 
 <td> copy_backward </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 与copy相同，不过元素是以相反顺序被拷贝 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;BidIt1,&nbsp;class&nbsp;BidIt2&gt; BidIt2&nbsp;copy_backward(BidIt1&nbsp;first,&nbsp;BidIt1&nbsp;last,&nbsp;BidIt2&nbsp;x); </td> 
 </tr> 
 <tr> 
 <td> iter_swap </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 交换两个ForwardIterator的值 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;FwdIt1,&nbsp;class&nbsp;FwdIt2&gt; void&nbsp;iter_swap(FwdIt1&nbsp;x,&nbsp;FwdIt2&nbsp;y); </td> 
 </tr> 
 <tr> 
 <td> remove </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 删除指定范围内所有等于指定元素的元素。注意，该函数不是真正删除函数。内置函数不适合使用remove和remove_if函数 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;FwdIt,&nbsp;class&nbsp;T&gt; FwdIt&nbsp;remove(FwdIt&nbsp;first,&nbsp;FwdIt&nbsp;last,&nbsp;const&nbsp;T&amp;&nbsp;val); </td> 
 </tr> 
 <tr> 
 <td> remove_copy </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 将所有不匹配元素复制到一个制定容器，返回OutputIterator指向被拷贝的末元素的下一个位置 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;InIt,&nbsp;class&nbsp;OutIt,&nbsp;class&nbsp;T&gt; OutIt&nbsp;remove_copy(InIt&nbsp;first,&nbsp;InIt&nbsp;last,&nbsp;OutIt&nbsp;x,&nbsp;const&nbsp;T&amp;&nbsp;val); </td> 
 </tr> 
 <tr> 
 <td> remove_if </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 删除指定范围内输入操作结果为true的所有元素 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;FwdIt,&nbsp;class&nbsp;Pred&gt; FwdIt&nbsp;remove_if(FwdIt&nbsp;first,&nbsp;FwdIt&nbsp;last,&nbsp;Pred&nbsp;pr); </td> 
 </tr> 
 <tr> 
 <td> remove_copy_if </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 将所有不匹配元素拷贝到一个指定容器 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;InIt,&nbsp;class&nbsp;OutIt,&nbsp;class&nbsp;Pred&gt; OutIt&nbsp;remove_copy_if(InIt&nbsp;first,&nbsp;InIt&nbsp;last,&nbsp;OutIt&nbsp;x,&nbsp;Pred&nbsp;pr); </td> 
 </tr> 
 <tr> 
 <td> replace </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 将指定范围内所有等于vold的元素都用vnew代替 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;FwdIt,&nbsp;class&nbsp;T&gt; void&nbsp;replace(FwdIt&nbsp;first,&nbsp;FwdIt&nbsp;last,const&nbsp;T&amp;&nbsp;vold,&nbsp;const&nbsp;T&amp;&nbsp;vnew); </td> 
 </tr> 
 <tr> 
 <td> replace_copy </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 与replace类似，不过将结果写入另一个容器 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;InIt,&nbsp;class&nbsp;OutIt,&nbsp;class&nbsp;T&gt; OutIt&nbsp;replace_copy(InIt&nbsp;first,&nbsp;InIt&nbsp;last,&nbsp;OutIt&nbsp;x,const&nbsp;T&amp;&nbsp;vold,&nbsp;const&nbsp;T&amp;&nbsp;vnew); </td> 
 </tr> 
 <tr> 
 <td> replace_if </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 将指定范围内所有操作结果为true的元素用新值代替 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;FwdIt,&nbsp;class&nbsp;Pred,&nbsp;class&nbsp;T&gt; void&nbsp;replace_if(FwdIt&nbsp;first,&nbsp;FwdIt&nbsp;last,Pred&nbsp;pr,&nbsp;const&nbsp;T&amp;&nbsp;val); </td> 
 </tr> 
 <tr> 
 <td> replace_copy_if </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 与replace_if，不过将结果写入另一个容器 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;InIt,&nbsp;class&nbsp;OutIt,&nbsp;class&nbsp;Pred,&nbsp;class&nbsp;T&gt; OutIt&nbsp;replace_copy_if(InIt&nbsp;first,&nbsp;InIt&nbsp;last,&nbsp;OutIt&nbsp;x,&nbsp;Pred&nbsp;pr,&nbsp;const&nbsp;T&amp;&nbsp;val); </td> 
 </tr> 
 <tr> 
 <td> swap </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 交换存储在两个对象中的值 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;T&gt; void&nbsp;swap(T&amp;&nbsp;x,&nbsp;T&amp;&nbsp;y); </td> 
 </tr> 
 <tr> 
 <td> swap_range </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 将指定范围内的元素与另一个序列元素值进行交换 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;FwdIt1,&nbsp;class&nbsp;FwdIt2&gt; FwdIt2&nbsp;swap_ranges(FwdIt1&nbsp;first,&nbsp;FwdIt1&nbsp;last,&nbsp;FwdIt2&nbsp;x); </td> 
 </tr> 
 <tr> 
 <td> unique </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 清除序列中重复元素，和remove类似，它也不能真正删除元素。重载版本使用自定义比较操作 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;FwdIt&gt; FwdIt&nbsp;unique(FwdIt&nbsp;first,&nbsp;FwdIt&nbsp;last); </td> 
 </tr> 
 <tr> 
 <td> template&lt;class&nbsp;FwdIt,&nbsp;class&nbsp;Pred&gt; FwdIt&nbsp;unique(FwdIt&nbsp;first,&nbsp;FwdIt&nbsp;last,&nbsp;Pred&nbsp;pr); </td> 
 </tr> 
 <tr> 
 <td> unique_copy </td> 
 <td> &lt;algorithm&gt; </td> 
 <td> 与unique类似，不过把结果输出到另一个容器 </td> 
 </tr> 
 <tr> 
 <td> 函数原形 </td> 
 <td> template&lt;class&nbsp;InIt,&nbsp;class&nbsp;OutIt&gt; OutIt&nbsp;unique_copy(InIt&nbsp;first,&nbsp;InIt&nbsp;last,&nbsp;OutIt&nbsp;x); </td> 
 </tr> 
 <tr> 
 <td> template&lt;class&nbsp;InIt,&nbsp;class&nbsp;OutIt,&nbsp;class&nbsp;Pred&gt; OutIt&nbsp;unique_copy(InIt&nbsp;first,&nbsp;InIt&nbsp;last,&nbsp;OutIt&nbsp;x,&nbsp;Pred&nbsp;pr); </td> 
 </tr> 
 </tbody> 
</table>

10.3.1.9生成和变异算法(6个)

--------------------

10.3.1.10算数算法(4个)

10.3.1.11常用算法汇总

*  常用的查找算法：

adjacent\_find()（ adjacent 是邻近的意思）,binary\_search(),count(),

count\_if(),equal\_range(),find(),find\_if()。

*  常用的排序算法：

merge(),sort(),random\_shuffle()（shuffle是洗牌的意思） ,reverse()。

*  常用的拷贝和替换算法：

copy(), replace(),

replace\_if(),swap()

*  常用的算术和生成算法：

accumulate()（ accumulate 是求和的意思）,fill(),。

*  常用的集合算法：

set\_union(),set\_intersection(),

set\_difference()。

*  常用的遍历算法：

for\_each(), transform()（ transform 是变换的意思）

### 10.3.2STL算法中函数对象和谓词 ###

10.3.2.1函数对象和谓词定义

**函数对象：**

重载函数调用操作符的类，其对象常称为函数对象（function object），即它们是行为类似函数的对象。一个类对象，表现出一个函数的特征，就是通过“对象名+([参数列表][Link 1])”的方式使用一个类对象，如果没有上下文，完全可以把它看作一个函数对待。

这是通过[重载][Link 2]类的operator()来实现的。

“在标准库中，函数对象被广泛地使用以获得弹性”，标准库中的很多算法都可以使用函数对象或者函数来作为自定的回调行为；

**谓词：**

一元函数对象：函数参数1个；

二元函数对象：函数参数2个；

一元谓词函数参数1个，函数返回值是bool类型，可以作为一个判断式

谓词可以使一个仿函数，也可以是一个回调函数。

二元谓词函数参数2个，函数返回值是bool类型

一元谓词函数举例如下

1，判断给出的string对象的长度是否小于6

bool GT6(const string &s)

return s.size() >= 6;

2,判断给出的int是否在3到8之间

bool Compare( int i )

return ( i >= 3 && i <= 8 );

二元谓词举例如下

1，比较两个string对象，返回一个bool值，指出第一个string是否比第二个短

bool isShorter(const string &s1, const string &s2)

return s1.size() < s2.size();

10.3.2.2一元函数对象案例

//1普通类重载函数调用操作符

template <typename T>

void FuncShowElemt(T &t)  //普通函数不能像仿函数那样记录状态

cout << t << " ";

\};

void showChar(char &t)

cout << t << " ";

//函数模板重载函数调用操作符

template <typename T>

class ShowElemt

public:

ShowElemt()

n = 0;

void operator()(T &t)

n++;

cout << t << " ";

void printCount()

cout << n << endl;

public:

int n;

\};

//1 函数对象基本使用

void main11()

int a = 100;

FuncShowElemt<int>(a); //普通的函数调用

ShowElemt<int> showElemt; //函数对象

showElemt(a); //函数对象调用

10.3.2.3一元谓词案例

//1元谓词例子

template <typename T>

class Isdiv

public:

Isdiv(const T &divisor) //

this->divisor = divisor;

bool operator()(T &t)

return (t%divisor == 0);

protected:

private:

T divisor;

\};

void main13()

vector<int> v2;

for (int i=10; i<33; i++)

v2.push\_back(i);

vector<int>::iterator it;

int a = 4;

Isdiv<int> mydiv(a);

// \_InIt find\_if(\_InIt \_First, \_InIt \_Last, \_Pr \_Pred)   //返回的是迭代器

it = find\_if(v2.begin(), v2.end(), Isdiv<int>(4));

if (it != v2.end())

cout << "第一个被4整除的数是：" << \*it << endl;

10.3.2.4二元函数对象案例

template <typename T>

struct SumAdd

T operator()(T &t1, T &t2)

return t1 + t2;

\};

template <typename T>

void printE(T &t)

for (vector<int>::iterator it = t.begin(); it!=t.end(); it++ )

cout << \*it << " ";

void printVector(vector<int>&v)

for (vector<int>::iterator it = v.begin(); it!=v.end(); it++ )

cout << \*it << " ";

void  main14()

vector<int> v1, v2 ;

vector<int> v3;

v1.push\_back(1);

v1.push\_back(2);

v1.push\_back(3);

v2.push\_back(4);

v2.push\_back(5);

v2.push\_back(6);

v3.resize(10);

//transform(v1.begin(), v1.end(), v2.begin(),v3.begin(), SumAdd<int>());

/\*

template<class \_InIt1,

class \_InIt2,

class \_OutIt,

class \_Fn2> inline

\_OutIt transform(\_InIt1 \_First1, \_InIt1 \_Last1,

\_InIt2 \_First2, \_OutIt \_Dest, \_Fn2 \_Func)

\*/

vector<int>::iterator it = transform(v1.begin(), v1.end(), v2.begin(),v3.begin(), SumAdd<int>());

cout << \*it << endl;

printE(v3);

10.3.2.5二元谓词案例

void current(int &v)

cout << v << " ";

bool MyCompare(const int &a, const int &b)

return a < b;

void main15()

vector<int> v(10);

for (int i=0; i<10; i++)

v\[i\] = rand() % 100;

for\_each(v.begin(), v.end(), current);

printf("\\n");

sort(v.begin(), v.end(), MyCompare );

printf("\\n");

for (int i=0; i<10; i++)

printf("%d ", v\[i\]);

printf("\\n");

#define _CRT_SECURE_NO_WARNINGS
 #include <functional>
 #include <iostream>
 #include <algorithm>
 #include <vector>
 #include <list>
 #include <string>
 #include <set>
 using namespace std;
 
 //函数对象 类重载()
 template <typename T>
 class ShowElemt
 {
 public:
 	ShowElemt()
 	{
 		n = 0;
 	}
 	void operator()(T &t)
 	{
 		n++;
 		cout << t << " " << "ShowElemt operator()" << endl;
 	}
 	void printN()
 	{
 		cout << "n:" << n << endl;
 	}
 
 private:
 	int n;
 };
 
 //函数模板 ==函数
 template <typename T>
 void FuncShowElemt(T &t)
 {
 	cout << t << " " << "FuncShowElemt" << endl;
 }
 
 //普通函数
 void FuncShowElemt2(int &t)
 {
 	cout << t << " " << " FuncShowElemt2" << endl;
 }
 
 //函数对象 定义 ; 函数对象和普通函数的异同 
 
 void main01()
 {
 	int a = 10;
 	ShowElemt<int> showElemt;
 	showElemt(a);//函数对象的()的执行 很像一个函数 //仿函数
 
 	FuncShowElemt<int>(a);
 	FuncShowElemt2(a);
 
 	system("pause");
 }
 //函数对象是属于类对象,能突破函数的概念,能保持调用状态信息
 //函数对象的好处
 // for_each算法中, 函数对象做函数参数
 // for_each算法中, 函数对象当返回值
 //函数对象的好处 函数对象做函数参数 函数对象做返回值
 void main02()
 {
 	vector<int> v1;
 	v1.push_back(1);
 	v1.push_back(3);
 	v1.push_back(5);
 	//匿名函数对象 匿名仿函数
 	for_each(v1.begin(),v1.end(),ShowElemt<int>());
 	cout << endl;
 	//	for_each: 用指定函数依次对指定范围内所有元素进行迭代访问。该函数不得修改序列中的元素
 	//通过回调函数 谁使用for_each 谁去填写回调函数的入口地址
 	//	_Fn1 for_each(_InIt _First, _InIt _Last, _Fn1 _Func)
 	for_each(v1.begin(),v1.end(),FuncShowElemt2);
 
 	//函数对象 做函数参数 
 	ShowElemt<int> show1;
 	/*
 	template<class _InIt,
 	class _Fn1> inline
 	_Fn1 for_each(_InIt _First, _InIt _Last, _Fn1 _Func)
 	{	// perform function for each element
 	_DEBUG_RANGE(_First, _Last);
 	_DEBUG_POINTER(_Func);
 	return (_For_each(_Unchecked(_First), _Unchecked(_Last), _Func));
 	}
 	*/
 	//1 for_each算法的 函数对象的传递 是元素值传递 ,不是引用传递
 	for_each(v1.begin(), v1.end(), show1);
 	show1.printN();
 
 	cout << "通过for_each算法的返回值看调用的次数" << endl;
 	show1 = for_each(v1.begin(), v1.end(), show1);
 	show1.printN();//说明调用了三次
 	//结论 要点: 分清楚 stl算法返回的值是迭代器 还是 谓词（函数对象） 是stl算法入门的重要点
 
 	system("pause");
 }
 
 template <typename T>
 class IsDiv
 {
 public:
 	IsDiv(const T &divisor)
 	{
 		this->divisor = divisor;
 	}
 
 	bool operator()(T &t)
 	{
 		return (t % divisor == 0);
 	}
 
 private:
 	T divisor;
 };
 //一元谓词
 void main03()
 {
 	vector<int> v1;
 	for (int i = 0; i < 33; i++)
 	{
 		v1.push_back(i);
 	}
 	int a = 4;
 	IsDiv<int> myDiv(a);
 	/*
 	template<class _InIt,
 	class _Pr> inline
 		_InIt find_if(_InIt _First, _InIt _Last, _Pr _Pred)
 	{	// find first satisfying _Pred
 		_DEBUG_RANGE(_First, _Last);
 		_DEBUG_POINTER(_Pred);
 		return (_Rechecked(_First,
 			_Find_if(_Unchecked(_First), _Unchecked(_Last), _Pred)));
 	}
 	*/
 	//find_if返回值是一个迭代器 
 	//要点: 分清楚 stl算法返回的值是迭代器 还是 谓词（函数对象） 是stl算法入门的重要点
 
 	//find_if(v1.begin(), v1.end(), myDiv );
 	vector<int>::iterator it;
 	it = find_if(v1.begin(), v1.end(), IsDiv<int>(a));
 	if (it == v1.end())
 	{
 		cout << "容器中没有被4整除的元素" << endl;
 	}
 	else
 	{
 		cout << "第一个是被4整除的元素是:" << *it << endl;
 	}
 
 	system("pause");
 }
 //二元函数对象
 template <typename T>
 class SumAdd
 {
 public:
 	T operator()(T t1, T t2)
 	{
 		return t1 + t2;
 	}
 
 private:
 
 };
 //二元函数对象 和二元谓词
 void main04()
 {
 	vector<int>	v1, v2;
 	vector<int> v3;
 	v1.push_back(1);
 	v1.push_back(3);
 	v1.push_back(5);
 
 	v2.push_back(2);
 	v2.push_back(4);
 	v2.push_back(6);
 
 	v3.resize(10);
 	/*
 	template<class _InIt1,
 	class _InIt2,
 	class _OutIt,
 	class _Fn2> inline
 	_OutIt transform(_InIt1 _First1, _InIt1 _Last1,
 	_InIt2 _First2, _OutIt _Dest, _Fn2 _Func)
 	{	// transform [_First1, _Last1) and [_First2, ...) with _Func
 	_DEBUG_RANGE(_First1, _Last1);
 	_DEBUG_POINTER(_Dest);
 	_DEBUG_POINTER(_Func);
 	if (_First1 != _Last1)
 	return (_Transform2(_Unchecked(_First1), _Unchecked(_Last1),
 	_First2, _Dest, _Func,
 	_Is_checked(_Dest)));
 	return (_Dest);
 	}
 	*/
 	//transform 把运算结果的 迭代器的开始位置 返回出来
 //_OutIt transform(_InIt1 _First1, _InIt1 _Last1_InIt2 _First2, _OutIt _Dest, _Fn2 _Func)
 	transform(v1.begin(), v1.end(), v2.begin(), v3.begin(), SumAdd<int>());
 	for (vector<int>::iterator it = v3.begin(); it != v3.end(); it++)
 	{
 		cout << *it << " ";
 	}
 	cout << endl;
 
 	system("pause");
 }
 //二元函数对象 和二元谓词
 bool MyCompare(const int &a, const int &b)
 {
 	return a < b; //从小到大
 }
 
 void main05()
 {
 	vector<int> v1(10);
 
 	for (int i = 0; i<10; i++)
 	{
 		int tmp = rand() % 100;
 		v1[i] = tmp;
 	}
 
 	for (vector<int>::iterator it = v1.begin(); it != v1.end(); it++)
 	{
 		cout << *it << " ";
 	}
 	cout << endl;
 	for_each(v1.begin(), v1.end(), FuncShowElemt2);
 	cout << endl;
 	//从小到大进行排序
 	sort(v1.begin(), v1.end(), MyCompare);
 	for_each(v1.begin(), v1.end(), FuncShowElemt2);
 	cout << endl;
 }
 //二元谓词在set集合中的应用
 //二元谓词函数参数2个，函数返回值是bool类型
 class CompareNoCase//类似less
 {
 public:
 	bool operator()(const string &str1, const string &str2)
 	{
 		string mystring1;
 		mystring1.resize(str1.size());
 		//预定义函数对象 
 		transform(str1.begin(),str1.end(),mystring1.begin(),tolower);
 
 		string mystring2;
 		mystring2.resize(str2.size());
 		transform(str2.begin(), str2.end(), mystring2.begin(), tolower); //预定义函数对象 
 
 		return (mystring1 < mystring2); // 从小到大进行排序
 	}
 
 private:
 
 };
 //二元谓词在set集合中的应用
 void main()
 {
 	set<string> set1;
 	set1.insert("aaa");
 	set1.insert("bbb");
 	set1.insert("ccc");
 	set<string>::iterator it = set1.find("aAa"); //find函数 默认 区分大小写
 	if (it == set1.end())
 	{
 		cout << " 没有 查找到 aaa " << endl;
 	}
 	else
 	{
 		cout << " 查找到 aaa " << endl;
 	}
 	set<string, CompareNoCase> set2;
 	set2.insert("bbb");
 	set2.insert("aaa");
 	set2.insert("ccc");
 	set<string, CompareNoCase>::iterator it2 = set2.find("aAa");
 	if (it2 == set2.end())
 	{
 		cout << " 没有 查找到 aaa " << endl;
 	}
 	else
 	{
 		cout << " 不区分大小的的查找 查找到 aaa " << endl;
 	}
 }

10.3.2.6预定义函数对象和函数适配器

**1****）预定义函数对象基本概念：标准模板库STL****提前定义了很多预定义函数对象，**\#include <functional>必须包含。

//1使用预定义函数对象：

//类模板plus<>的实现了：不同类型的数据进行加法运算

void main41()

plus<int> intAdd;

int x = 10;

int y = 20;

int z = intAdd(x, y); //等价于 x + y

cout << z << endl;

plus<string> stringAdd;

string myc = stringAdd("aaa", "bbb");

cout << myc << endl;

vector<string> v1;

v1.push\_back("bbb");

v1.push\_back("aaa");

v1.push\_back("ccc");

v1.push\_back("zzzz");

//缺省情况下，sort()用底层元素类型的小于操作符以升序排列容器的元素。

//为了降序，可以传递预定义的类模板greater,它调用底层元素类型的大于操作符：

cout << "sort()函数排序" << endl;;

sort(v1.begin(), v1.end(), greater<string>() ); //从大到小

for (vector<string>::iterator it=v1.begin(); it!=v1.end(); it++ )

cout << \*it << endl;

**2****）算术函数对象**

预定义的函数对象支持加、减、乘、除、求余和取反。调用的操作符是与type相关联的实例

加法：plus<Types>

plus<string> stringAdd;

sres = stringAdd(sva1,sva2);

减法：minus<Types>

乘法：multiplies<Types>

除法divides<Tpye>

求余：modulus<Tpye>

取反：negate<Type>

negate<int> intNegate;

ires = intNegate(ires);

Ires= UnaryFunc(negate<int>(),Ival1);

**3****）关系函数对象**

等于equal\_to<Tpye>

equal\_to<string> stringEqual;

sres = stringEqual(sval1,sval2);

不等于not\_equal\_to<Type>

大于 greater<Type>

大于等于greater\_equal<Type>

小于 less<Type>

小于等于less\_equal<Type>

void main42()

vector<string> v1;

v1.push\_back("bbb");

v1.push\_back("aaa");

v1.push\_back("ccc");

v1.push\_back("zzzz");

v1.push\_back("ccc");

string s1 = "ccc";

//int num = count\_if(v1.begin(),v1.end(), equal\_to<string>(),s1);

int num = count\_if(v1.begin(),v1.end(),bind2nd(equal\_to<string>(), s1));

cout << num << endl;

**4****）逻辑函数对象**

逻辑与 logical\_and<Type>

logical\_and<int> indAnd;

ires = intAnd(ival1,ival2);

dres=BinaryFunc( logical\_and<double>(),dval1,dval2);

逻辑或logical\_or<Type>

逻辑非logical\_not<Type>

logical\_not<int> IntNot;

Ires = IntNot(ival1);

Dres=UnaryFunc( logical\_not<double>,dval1);

10.3.2.7函数适配器

**1****）函数适配器的理论知识**

![70 6][]

![70 7][]

![70 8][]

![70 9][]

**2）常用函数函数适配器**

标准库提供一组函数适配器，用来特殊化或者扩展一元和二元函数对象。常用适配器是：

1绑定器（binder）: binder通过把二元函数对象的一个实参绑定到一个特殊的值上，将其转换成一元函数对象。C＋＋标准库提供两种预定义的binder适配器：bind1st和bind2nd，前者把值绑定到二元函数对象的第一个实参上，后者绑定在第二个实参上。

2取反器(negator) : negator是一个将函数对象的值翻转的函数适配器。标准库提供两个预定义的ngeator适配器：not1翻转一元预定义函数对象的真值,而not2翻转二元谓词函数的真值。

常用函数适配器列表如下：

bind1st(op, value)

bind2nd(op, value)

not1(op)

not2(op)

mem\_fun\_ref(op)

mem\_fun(op)

ptr\_fun(op)

**3****）常用函数适配器案例**

class IsGreat

public:

IsGreat(int i)

m\_num = i;

bool operator()(int &num)

if (num > m\_num)

return true;

return false;

protected:

private:

int m\_num;

\};

void main43()

vector<int>  v1;

for (int i=0; i<5; i++)

v1.push\_back(i+1);

for (vector<int>::iterator it = v1.begin(); it!=v1.end(); it ++)

cout << \*it << " " ;

int num1 = count(v1.begin(), v1.end(), 3);

cout << "num1:" << num1 << endl;

//通过谓词求大于2的个数

int num2 = count\_if(v1.begin(), v1.end(), IsGreat(2));

cout << "num2:" << num2 << endl;

//通过预定义函数对象求大于2的个数   greater<int>() 有2个参数

//                                                                                                             param > 2

int num3 = count\_if(v1.begin(), v1.end(), bind2nd(greater<int>(), 2 ) );

cout << "num3:" << num3 << endl;

//取模能被2整除的数求奇数

int num4 = count\_if(v1.begin(), v1.end(), bind2nd(modulus <int>(), 2 ) );

cout << "奇数num4:" << num4 << endl;

int num5 = count\_if(v1.begin(), v1.end(), not1( bind2nd(modulus <int>(), 2 ) ) );

cout << "偶数num5:" << num5 << endl;

return ;

**10.3.2.8 STL的容器算法迭代器的设计理念**

#define _CRT_SECURE_NO_WARNINGS
 #include <functional>
 #include <iostream>
 #include <algorithm>
 #include <vector>
 #include <list>
 #include <string>
 #include <set>
 using namespace std;
 
 //二元函数对象
 template <typename T>
 class SumAdd
 {
 public:
 	T operator()(T t1, T t2)
 	{
 		return t1 + t2;
 	}
 };
 
 int mysum(int &t1, int &t2)
 {
 	return t1 + t2;
 }
 
 void main()
 {
 	//v1 v2 ==> v3
 	vector<int> v1, v2;
 	vector<int> v3;
 	v1.push_back(1);
 	v1.push_back(3);
 	v1.push_back(5);
 
 	v2.push_back(2);
 	v2.push_back(4);
 	v2.push_back(6);
 
 	v3.resize(10);
 	/*
 	template<class _InIt1,
 	class _InIt2,
 	class _OutIt,
 	class _Fn2> inline
 	_OutIt transform(_InIt1 _First1, _InIt1 _Last1,
 	_InIt2 _First2, _OutIt _Dest, _Fn2 _Func)
 	{	// transform [_First1, _Last1) and [_First2, ...) with _Func
 	_DEBUG_RANGE(_First1, _Last1);
 	_DEBUG_POINTER(_Dest);
 	_DEBUG_POINTER(_Func);
 	if (_First1 != _Last1)
 	return (_Transform2(_Unchecked(_First1), _Unchecked(_Last1),
 	_First2, _Dest, _Func,
 	_Is_checked(_Dest)));
 	return (_Dest);
 	}
 	*/
 	transform(v1.begin(), v1.end(), v2.begin(), v3.begin(),SumAdd<int>());
 	//transform(v1.begin(), v1.end(), v2.begin(), v3.begin(), mysum );
 	for (vector<int>::iterator it = v3.begin(); it != v3.end();it++)
 	{
 		cout << *it << " ";
 	}
 	cout << endl;
 
 }

![70 10][]

1.  STL的容器通过**类模板**技术，实现数据类型和容器模型的分离。
2.  STL的迭代器技术实现了遍历容器的统一方法；也为STL的算法提供了统一性
3.  STL的函数对象实现了自定义数据类型的算法运算。（算法和）
4.  具体例子：transform算法的输入，通过迭代器first和last指向的元算作为输入；通过result作为输出；通过函数对象来做自定义数据类型的运算。

#define _CRT_SECURE_NO_WARNINGS
 #include <functional>
 #include <iostream>
 #include <algorithm>
 #include <vector>
 #include <list>
 #include <string>
 #include <set>
 using namespace std;
 
 
 //plus<int> 预定义好的函数对象 能实现不同类型的数据的 + 运算
 //实现了 数据类型 和算法的分离 ===》通过函数对象技术实现的。。。。
 
 //思考：怎么样知道 plus<type> 是两个参数
 
 //1使用预定义函数对象：
 //类模板plus<>的实现了：不同类型的数据进行加法运算
 
 void main01()
 {
 	/*
 	template<class _Ty>
 	struct plus
 	: public binary_function<_Ty, _Ty, _Ty>
 	{	// functor for operator+
 	_Ty operator()(const _Ty& _Left, const _Ty& _Right) const
 	{	// apply operator+ to operands
 	return (_Left + _Right);
 	}
 	};
 	*/
 	plus<int> intAdd;
 	int x = 10;
 	int y = 20;
 	int z = intAdd(x,y);
 
 	cout << "z:" << z << endl;
 	plus<string> stringAdd;
 
 	string s1 = "aaa";
 	string s2 = "bbb";
 	string s3 = stringAdd(s1, s2);
 
 	cout << "s3:" << s3 << endl;
 
 	vector<string> v1;
 	v1.push_back("bbb");
 	v1.push_back("aaa");
 	v1.push_back("ccc");
 	v1.push_back("zzz");
 	v1.push_back("ccc");
 	v1.push_back("ccc");
 	/*
 	template<class _Ty>
 	struct greater
 	: public binary_function<_Ty, _Ty, bool>
 	{	// functor for operator>
 	bool operator()(const _Ty& _Left, const _Ty& _Right) const
 	{	// apply operator> to operands
 	return (_Left > _Right);
 	}
 	};
 	*/
 	sort(v1.begin(),v1.end(),greater<string>());
 
 	for (vector<string>::iterator it = v1.begin(); it != v1.end();it++)
 	{
 		cout << *it << endl;
 	}
 
 	//求ccc出现的个数
 	string sc = "ccc";
 
 	//equal_to<string>() 有两个参数 left参数来自容器，right参数来自sc
 	//int num = count_if(v1.begin(), v1.end(),equal_to<string>(),sc);//报错
 
 	//bind2nd函数适配器 ：把预定义函数对象 和 第二个参数进行绑定
 	int num = count_if(v1.begin(), v1.end(), bind2nd(equal_to<string>(), sc));
 
 	cout << "num: " << num << endl;
 
 	system("pause");
 
 
 }
 
 
 class IsGreat
 {
 public:
 	IsGreat(int i)
 	{
 		m_num = i;
 	}
 
 	bool operator()(int &num)
 	{
 		if (num > m_num)
 		{
 			return true;
 		}
 		return false;
 	}
 
 private:
 	int m_num;
 };
 
 
 //函数适配器综合案例
 void main()
 {
 	vector<int> v1;
 	for (int i = 0; i < 10; i++)
 	{
 		v1.push_back(i+1);
 	}
 	for (vector<int>::iterator it = v1.begin(); it != v1.end(); it++)
 	{
 		cout << *it << " ";
 	}
 
 	cout << endl;
 
 	int num1 = count(v1.begin(),v1.end(),3);
 	cout << "num1:" << num1 << endl;
 
 	//通过 谓词 求大于2 的个数	
 	int num2 = count_if(v1.begin(),v1.end(),IsGreat(2));
 	cout << "num2:" << num2 << endl;
 
 	//通过 预定义的函数对象 求大于2 的个数
 	//greater<int>() 有两个参数 左参数来自容器的元素 ，右参数固定成2 （通过bind2nd做的）
 	int num3 = count_if(v1.begin(),v1.end(),bind2nd(greater<int>(),2));
 	cout << "num3:" << num3 << endl;
 
 	//求 奇数的个数
 	//bind2nd 辅助构造binder2nd适配器实例 绑定固定值到二元函数的第二个参数位置
 	int num4 = count_if(v1.begin(), v1.end(), bind2nd(modulus<int>(), 2));
 	cout << "奇数的个数num4:" << num4 << endl;
 
 	//求 偶数的个数 取反器(negator)
 	//辅助构造unary_negate适配器实例 生成一元函数的逻辑反函数
 	int num5 = count_if(v1.begin(),v1.end(),not1(bind2nd(modulus<int>(),2)));
 	cout << "偶数的个数 num5:" << num5 << endl;
 
 	system("pause");
 }

#include <iostream>
 using namespace std;
 
 #include "string"
 #include <vector>
 #include <list>
 #include "set"
 #include <algorithm>
 #include "functional"
 #include "iterator" //输出流迭代器的头文件
 //	for_each : 用指定函数依次对指定范围内所有元素进行迭代访问。该函数不得修改序列中的元素
 
 void printV(vector<int> &v)
 {
 	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
 	{
 		cout << *it << " ";
 	}
 }
 
 void showElem(int &n)
 {
 	cout << n << " ";
 }
 
 //一元谓词案例
 class CMyShow
 {
 public:
 	CMyShow()
 	{
 		num = 0;
 	}
 
 	void operator()(int &n)
 	{
 		num++;
 		cout << n << " ";
 	}
 
 	void printNum()
 	{
 		cout << "num:" << num << endl;
 	}
 
 private:
 	int num;
 };
 
 
 
 void main01()
 {
 	vector<int> v1;
 	v1.push_back(1);
 	v1.push_back(3);
 	v1.push_back(5);
 
 	printV(v1);
 	cout << endl;
 
 	//函数对象 回调函数入口地址
 	for_each(v1.begin(),v1.end(),showElem);
 	/*
 	template<class _InIt,
 	class _Fn1> inline
 	_Fn1 for_each(_InIt _First, _InIt _Last, _Fn1 _Func)
 	{	// perform function for each element
 	_DEBUG_RANGE(_First, _Last);
 	_DEBUG_POINTER(_Func);
 	return (_For_each(_Unchecked(_First), _Unchecked(_Last), _Func));
 	} */
 	cout << endl;
 
 	for_each(v1.begin(),v1.end(),CMyShow());
 	cout << endl;
 
 	CMyShow mya;
 	CMyShow my1 = for_each(v1.begin(), v1.end(), mya); //给my1初始化
 	mya.printNum(); //ma1和my1 是两个不同的对象
 	my1.printNum();
 
 
 	my1 = for_each(v1.begin(), v1.end(), mya); //给my1赋值
 	my1.printNum();
 
 	system("pause");
 }
 
 int increase(int i)
 {
 	return i + 100;
 }
 
 void printList(list<int> &v)
 {
 	for (list<int>::iterator it = v.begin(); it != v.end(); it++)
 	{
 		cout << *it << " ";
 	}
 }
 //transform : 与for_each类似，遍历所有元素，但可对容器的元素进行修改
 void main02()
 {
 	vector<int> v1;
 	v1.push_back(1);
 	v1.push_back(3);
 	v1.push_back(5);
 
 	printV(v1);
 	cout << endl;
 
 	//transform 使用回调函数
 	transform(v1.begin(),v1.end(),v1.begin(),increase);
 	printV(v1);
 	cout << endl;
 
 	//transform 使用 预定义的函数对象
 	transform(v1.begin(),v1.end(),v1.begin(),negate<int>());
 	printV(v1);
 	cout << endl;
 
 	//transform 使用 函数适配器 和函数对象
 	list<int> mylist;
 	mylist.resize(v1.size());
 
 
 	transform(v1.begin(),v1.end(),mylist.begin(),bind2nd(multiplies<int>(),10));
 	printList(mylist);
 	cout << endl;
 
 	//transform 也可以把运算结果 直接输出到屏幕
 	transform(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "),negate<int>() );
 	cout << endl;
 
 
 	system("pause");
 }
 
 //一般情况下：for_each所使用的函数对象，参数是引用，没有返回值
 //transform所使用的函数对象，参数一般不使用引用，而是还有返回值、
 
 int showElem2(int n)
 {
 	cout << n << " ";
 	return n;
 }
 void main()
 {
 	vector<int> v1;
 	v1.push_back(1);
 	v1.push_back(3);
 	v1.push_back(5);
 
 	vector<int> v2 = v1;
 
 
 	for_each(v1.begin(),v1.end(),showElem);
 	//transform 对 函数对象的要求
 	/*
 	c:\program files\microsoft visual studio 10.0\vc\include\algorithm(1119):
 	参见对正在编译的函数 模板 实例化
 	“_OutIt std::_Transform1<int*,_OutIt,
 	void(__cdecl *)(int &)>(_InIt,_InIt,_OutIt,_Fn1,
 	std::tr1::true_type)”的引用
 	1> with
 	1> [
 	1> _OutIt=std::_Vector_iterator<std::_Vector_val<int,std::allocator<int>>>,
 	1> _InIt=int *,
 	1> _Fn1=void (__cdecl *)(int &)
 	1> ]
 	*/
 
 	/*
 	template<class _InIt,
 	class _OutIt,
 	class _Fn1> inline
 	_OutIt _Transform(_InIt _First, _InIt _Last,
 	_OutIt _Dest, _Fn1 _Func)
 	{	// transform [_First, _Last) with _Func
 	for (; _First != _Last; ++_First, ++_Dest)
 	*_Dest = _Func(*_First); //解释了 为什么 要有返回值
 	return (_Dest);
 	}
 	*/
 	transform(v2.begin(), v2.end(), v2.begin(), showElem2);
 
 	system("pause");
 }

### 10.3.3常用的查找算法 ###

adjacent\_find()

在iterator对标识元素范围内，查找一对相邻重复元素，找到则返回指向这对元素的第一个元素的迭代器。否则返回past-the-end。

vector<int> vecInt;

vecInt.push\_back(1);

vecInt.push\_back(2);

vecInt.push\_back(4);

vecInt.push\_back(5);

vector<int>::iterator it = adjacent\_find(vecInt.begin(), vecInt.end());            //\*it == 2

binary\_search

在有序序列中查找value,找到则返回true。注意：在无序序列中，不可使用。

set<int> setInt;

setInt.insert(3);

setInt.insert(1);

setInt.insert(7);

setInt.insert(5);

setInt.insert(9);

bool bFind = binary\_search(setInt.begin(),setInt.end(),5);

count()

利用等于操作符，把标志范围内的元素与输入值比较，返回相等的个数。

vector<int> vecInt;

vecInt.push\_back(1);

vecInt.push\_back(2);

vecInt.push\_back(4);

vecInt.push\_back(2);

vecInt.push\_back(5);

int iCount = count(vecInt.begin(),vecInt.end(),2);  //iCount==3

count\_if()

假设vector<int>vecIntA，vecIntA包含1,3,5,7,9元素

//先定义比较函数

bool GreaterThree(int iNum)

if(iNum>=3)

return true;

else

return false;

int iCount = count\_if(vecIntA.begin(), vecIntA.end(), GreaterThree);

//此时iCount == 4

find()

*  find:  利用底层元素的等于操作符，对指定范围内的元素与输入值进行比较。当匹配时，结束搜索，返回该元素的迭代器。
 *  equal\_range:    返回一对iterator，第一个表示lower\_bound,第二个表示upper\_bound。

vector<int> vecInt;

vecInt.push\_back(1);

vecInt.push\_back(3);

vecInt.push\_back(5);

vecInt.push\_back(7);

vecInt.push\_back(9);

vector<int>::iterator it = find(vecInt.begin(), vecInt.end(), 5);                 //\*it == 5

**find\_if()**

**find\_if:   使用输入的函数代替等于操作符执行find。返回被找到的元素的迭代器。**

假设vector<int>vecIntA，vecIntA包含1,3,5,3,9元素

vector<int>::it = find\_if(vecInt.begin(),vecInt.end(),GreaterThree);

此时 \*it==3, \*(it+1)==5, \*(it+2)==3, \*(it+3)==9

#include <iostream>
 using namespace std;
 
 #include "string"
 #include <vector>
 #include <list>
 #include "set"
 #include <algorithm>
 #include "functional"
 #include "iterator" //输出流迭代器的头文件
 
 //adjacent_find()
 //在iterator对标识元素范围内，查找一对相邻重复元素，找到则返回指向这对元素的第一个元素的迭代器。否则返回past - the - end。
 
 void main01()
 {
 	vector<int>	v1;
 	v1.push_back(1);
 	v1.push_back(2);
 	v1.push_back(2);
 	v1.push_back(3);
 	v1.push_back(5);
 
 	vector<int>::iterator it = adjacent_find(v1.begin(),v1.end());
 	if (it == v1.end())
 	{
 		cout << "没有找到重复的元素" << endl;
 	} else{
 		cout << *it << endl;
 	}	
 	//distance()
 	//函数distance()用来处理两个迭代器之间的距离
 	//Dist distance(pos1, pos2);
 	//1.传回两个input迭代器pos1和pos2之间的距离；
 	//2.两个迭代器都必须指向同一个容器；
 	//3.对于random access迭代器，此函数仅仅只是传回pos2 - pos1，因此具备常数复杂度；
 	//4.对于其他迭代器类型，distance()会不断递增pos1，直到抵达pos2为止，然后传回递增次数，也就是说其他类型的迭代器，distance()具备线性复杂度，所以对于non - random access迭代器，尽力避免使用此函数；
 	//5.如果需要更换容器型别和迭代器的型别，就应该使用distance()而不是operator - ，但是存在对“non - random access迭代器”性能变差的问题，并且第一个迭代器绝对不能位于第二个迭代器之后，否则未定义行为；
 	int index = distance(v1.begin(),it);
 	cout << index << endl;
 	system("pause");
 }
 
 //binary_search
 //在有序序列中查找value, 找到则返回true。注意：在无序序列中，不可使用
 void main02()
 {
 	vector<int> v1;
 	v1.push_back(1);
 	v1.push_back(3);
 	v1.push_back(5);
 	v1.push_back(7);
 	v1.push_back(9);
 
 
 	bool b = binary_search(v1.begin(),v1.end(),7);
 	/*
 	// TEMPLATE FUNCTION binary_search
 template<class _FwdIt,
 	class _Ty> inline
 	bool binary_search(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
 	{	// test if _Val equivalent to some element, using operator<
 	return (_STD binary_search(_First, _Last, _Val, less<>()));
 	}
 	*/
 	if (true == b)
 	{
 		cout << "找到了" << endl;
 	}
 	else{
 		cout << "没到了" << endl;
 	}
 	system("pause");
 }
 
 //count()
 //利用等于操作符，把标志范围内的元素与输入值比较，返回相等的个数
 void main03()
 {
 	vector<int> v1;
 	v1.push_back(1);
 	v1.push_back(3);
 	v1.push_back(5);
 	v1.push_back(7);
 	v1.push_back(7);
 	v1.push_back(9);
 	v1.push_back(7);
 
 	int num = count(v1.begin(),v1.end(),7);
 
 	cout << num << endl;
 
 	system("pause");
 }
 
 //count_if()
 //假设vector<int>vecIntA，vecIntA包含1, 3, 5, 7, 9元素
 //谓词 重载()运算符或者回调函数 最终返回值是布尔型
 
 //一元谓词函数参数1个，函数返回值是bool类型，可以作为一个判断式
 //谓词可以是一个仿函数，也可以是一个回调函数
 
 bool GreatThree(int iNum)
 {
 	if (iNum > 3)
 	{
 		return true;
 	}
 	return false;
 }
 
 void main04()
 {
 	vector<int> v1;
 	v1.push_back(1);
 	v1.push_back(3);
 	v1.push_back(5);
 	v1.push_back(7);
 	v1.push_back(7);
 	v1.push_back(9);
 	v1.push_back(7);
 
 	int num = count_if(v1.begin(), v1.end(), GreatThree);
 
 	system("pause");
 }
 
 //find:利用底层元素的等于操作符，对指定范围内的元素与输入值进行比较。当匹配时，结束搜索，返回该元素的迭代器
 void main05()
 {
 	vector<int> v1;
 	v1.push_back(1);
 	v1.push_back(3);
 	v1.push_back(5);
 	v1.push_back(7);
 	v1.push_back(7);
 	v1.push_back(9);
 	v1.push_back(7);
 
 	vector<int>::iterator it = find(v1.begin(),v1.end(),5);
 	cout << "*it:" << *it << endl;
 
 	//第一个大于3的位置
 	vector<int>::iterator it2 = find_if(v1.begin(),v1.end(),GreatThree);
 	cout << "*it2:" << *it2 << endl;
 
 	system("pause");
 }

### 10.3.4常用的排序算法 ###

merge()

*  以下是排序和通用算法：提供元素排序策略
 *  merge:    合并两个有序序列，存放到另一个序列。

例如：vecIntA,vecIntB,vecIntC是用vector<int>声明的容器，vecIntA已包含1,3,5,7,9元素，vecIntB已包含2,4,6,8元素

vecIntC.resize(9);  //扩大容量

merge(vecIntA.begin(),vecIntA.end(),vecIntB.begin(),vecIntB.end(),vecIntC.begin());

此时vecIntC就存放了按顺序的1,2,3,4,5,6,7,8,9九个元素

sort()

*  sort:  以默认升序的方式重新排列指定范围内的元素。若要改排序规则，可以输入比较函数。

//学生类

Class CStudent:

public:

CStudent(int iID, string strName)

m\_iID=iID;

m\_strName=strName;

public:

int m\_iID;

string m\_strName;

//学号比较函数

bool Compare(const CStudent &stuA,const CStudent &stuB)

return (stuA.m\_iID<strB.m\_iID);

void main()

vector<CStudent> vecStu;

vecStu.push\_back(CStudent(2,"老二"));

vecStu.push\_back(CStudent(1,"老大"));

vecStu.push\_back(CStudent(3,"老三"));

vecStu.push\_back(CStudent(4,"老四"));

sort(vecStu.begin(),vecStu.end(),Compare);

//  此时，vecStu容器包含了按顺序的"老大对象","老二对象","老三对象","老四对象"

random\_shuffle()

*  random\_shuffle:     对指定范围内的元素随机调整次序。

srand(time(0));                            //设置随机种子

vector<int> vecInt;

vecInt.push\_back(1);

vecInt.push\_back(3);

vecInt.push\_back(5);

vecInt.push\_back(7);

vecInt.push\_back(9);

string str("itcastitcast ");

random\_shuffle(vecInt.begin(), vecInt.end());   //随机排序，结果比如：9,7,1,5,3

random\_shuffle(str.begin(), str.end());                //随机排序，结果比如："itstcasticat"

reverse()

vector<int> vecInt;

vecInt.push\_back(1);

vecInt.push\_back(3);

vecInt.push\_back(5);

vecInt.push\_back(7);

vecInt.push\_back(9);

reverse(vecInt.begin(), vecInt.end());               //\{9,7,5,3,1\}

### 10.3.5常用的拷贝和替换算法 ###

copy()

vector<int> vecIntA;

vecIntA.push\_back(1);

vecIntA.push\_back(3);

vecIntA.push\_back(5);

vecIntA.push\_back(7);

vecIntA.push\_back(9);

vector<int> vecIntB;

vecIntB.resize(5);                       //扩大空间

copy(vecIntA.begin(), vecIntA.end(), vecIntB.begin());   //vecIntB: \{1,3,5,7,9\}

replace()

*  replace(beg,end,oldValue,newValue):    将指定范围内的所有等于oldValue的元素替换成newValue。

vector<int> vecIntA;

vecIntA.push\_back(1);

vecIntA.push\_back(3);

vecIntA.push\_back(5);

vecIntA.push\_back(3);

vecIntA.push\_back(9);

replace(vecIntA.begin(), vecIntA.end(), 3, 8);                   //\{1,8,5,8,9\}

replace\_if()

*  replace\_if : 将指定范围内所有操作结果为true的元素用新值替换。

用法举例：

replace\_if(vecIntA.begin(),vecIntA.end(),GreaterThree,newVal)

其中vecIntA是用vector<int>声明的容器

GreaterThree 函数的原型是bool GreaterThree(int iNum)

//把大于等于3的元素替换成8

vector<int> vecIntA;

vecIntA.push\_back(1);

vecIntA.push\_back(3);

vecIntA.push\_back(5);

vecIntA.push\_back(3);

vecIntA.push\_back(9);

replace\_if(vecIntA.begin(), vecIntA.end(), GreaterThree, 8);                   //GreaterThree的定义在上面。

swap()

*  swap:   交换两个容器的元素

vector<int> vecIntA;

vecIntA.push\_back(1);

vecIntA.push\_back(3);

vecIntA.push\_back(5);

vector<int> vecIntB;

vecIntB.push\_back(2);

vecIntB.push\_back(4);

swap(vecIntA, vecIntB);  //交换

### 10.3.6常用的算术和生成算法 ###

accumulate()

* accumulate:  对指定范围内的元素求和，然后结果再加上一个由val指定的初始值。
 * \#include<numeric>

vector<int> vecIntA;

vecIntA.push\_back(1);

vecIntA.push\_back(3);

vecIntA.push\_back(5);

vecIntA.push\_back(7);

vecIntA.push\_back(9);

int iSum = accumulate(vecIntA.begin(), vecIntA.end(), 100);          //iSum==125

fill()

*  fill:   将输入值赋给标志范围内的所有元素。

vector<int> vecIntA;

vecIntA.push\_back(1);

vecIntA.push\_back(3);

vecIntA.push\_back(5);

vecIntA.push\_back(7);

vecIntA.push\_back(9);

fill(vecIntA.begin(), vecIntA.end(), 8);               //8, 8, 8, 8, 8

### 10.3.7常用的集合算法 ###

set\_union(),set\_intersection(),set\_difference()

*  set\_union:  构造一个有序序列，包含两个有序序列的并集。
 *  set\_intersection:  构造一个有序序列，包含两个有序序列的交集。
 *  set\_difference:  构造一个有序序列，该序列保留第一个有序序列中存在而第二个有序序列中不存在的元素。

vector<int> vecIntA;

vecIntA.push\_back(1);

vecIntA.push\_back(3);

vecIntA.push\_back(5);

vecIntA.push\_back(7);

vecIntA.push\_back(9);

vector<int> vecIntB;

vecIntB.push\_back(1);

vecIntB.push\_back(3);

vecIntB.push\_back(5);

vecIntB.push\_back(6);

vecIntB.push\_back(8);

vector<int> vecIntC;

vecIntC.resize(10);

//并集

set\_union(vecIntA.begin(), vecIntA.end(), vecIntB.begin(), vecIntB.end(), vecIntC.begin());                  //vecIntC : \{1,3,5,6,7,8,9,0,0,0\}

//交集

fill(vecIntC.begin(),vecIntC.end(),0);

set\_intersection(vecIntA.begin(), vecIntA.end(), vecIntB.begin(), vecIntB.end(), vecIntC.begin());               //vecIntC: \{1,3,5,0,0,0,0,0,0,0\}

//差集

fill(vecIntC.begin(),vecIntC.end(),0);

set\_difference(vecIntA.begin(), vecIntA.end(), vecIntB.begin(), vecIntB.end(), vecIntC.begin());                            //vecIntC: \{7,9,0,0,0,0,0,0,0,0\}

### 10.3.8常用的遍历算法 ###

for\_each()

*  for\_each:  用指定函数依次对指定范围内所有元素进行迭代访问。该函数不得修改序列中的元素。

void show(const int &iItem)

cout << iItem;

main()

int iArray\[\] = \{0,1,2,3,4\};

vector<int> vecInt(iArray,iArray+sizeof(iArray)/sizeof(iArray\[0\]));

for\_each(vecInt.begin(), vecInt.end(), show);

//结果打印出0 1 2 3 4

transform()

*  transform:   与for\_each类似，遍历所有元素，但可对容器的元素进行修改

int increase (int i)

return i+1;

main()

vector<int> vecIntA;

vecIntA.push\_back(1);

vecIntA.push\_back(3);

vecIntA.push\_back(5);

vecIntA.push\_back(7);

vecIntA.push\_back(9);

transform(vecIntA.begin(),vecIntA.end(),vecIntA.begin(),increase);              //vecIntA : \{2,4,6,8,10\}

#include <iostream>
 using namespace std;
 
 #include "string"
 #include <vector>
 #include <list>
 #include "set"
 #include <algorithm>
 #include "functional"
 #include "iterator" //输出流迭代器的头文件
 #include <numeric> //accumulate 该算法在numeric头文件中定义
 
 //merge()
 //以下是排序和通用算法：提供元素排序策略
 //merge : 合并两个有序序列，存放到另一个序列
 
 void printV(vector<int> &v)
 {
 	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
 	{
 		cout << *it << " ";
 	}
 }
 void main01()
 {
 	vector<int> v1;
 	v1.push_back(1);
 	v1.push_back(3);
 	v1.push_back(5);
 
 	vector<int> v2;
 	v2.push_back(2);
 	v2.push_back(4);
 	v2.push_back(6);
 
 	vector<int> v3;
 	v3.resize(v1.size() + v2.size());//扩大容量
 
 	merge(v1.begin(),v1.end(),v2.begin(),v2.end(),v3.begin());
 	// TEMPLATE FUNCTION merge
 	//template<class _InIt1,
 	//class _InIt2,
 	//class _OutIt> inline
 	//	_OutIt merge(_InIt1 _First1, _InIt1 _Last1,
 	//	_InIt2 _First2, _InIt2 _Last2,
 	//	_OutIt _Dest)
 	//{	// copy merging ranges, both using operator<
 	//	return (_STD merge(_First1, _Last1, _First2, _Last2, _Dest,
 	//		less<>()));
 	//}
 	printV(v3);
 	system("pause");
 }
 
 class Student
 {
 public:
 	Student(string name,int id)
 	{
 		m_name = name;
 		m_id = id;
 	}
 
 	void printT()
 	{
 		cout << "name: " << m_name << " id " << m_id << endl;
 	}
 
 public:
 	string	m_name;
 	int		m_id;
 };
 //二元谓词 使用的是回调函数
 bool CompareS(Student &s1, Student &s2)
 {
 	return (s1.m_id < s2.m_id);
 }
 
 void main02()
 {
 	Student s1("老大", 1);
 	Student s2("老二", 2);
 	Student s3("老三", 3);
 	Student s4("老四", 4);
 
 	vector<Student> v1;
 	v1.push_back(s4);
 	v1.push_back(s3);
 	v1.push_back(s2);
 	v1.push_back(s1);
 
 	for (vector<Student>::iterator it = v1.begin(); it != v1.end(); it++)
 	{
 		it->printT();
 	}
 
 	//sort 根据自定义函数对象 进行自定义数据类型的排序 
 	//替换 算法的统一性 (实现的算法和数据类型的分离) ===>技术手段函数对象
 	sort(v1.begin(),v1.end(),CompareS);
 	cout << "\n排序之后....\n";
 	for (vector<Student>::iterator it = v1.begin(); it != v1.end(); it++)
 	{
 		it->printT();
 	}
 
 	system("pause");
 }
 
 //random_shuffle()
 //random_shuffle : 对指定范围内的元素随机调整次序
 void main03()
 {
 	vector<int> v1;
 	v1.push_back(1);
 	v1.push_back(3);
 	v1.push_back(5);
 	v1.push_back(7);
 
 	random_shuffle(v1.begin(),v1.end());
 	printV(v1);
 
 	string str = "abcdefg";
 	random_shuffle(str.begin(),str.end());
 	cout << "str: " << str << endl;
 
 	system("pause");
 }
 
 //reverse() 逆序
 void main04()
 {
 	vector<int> v1;
 	v1.push_back(1);
 	v1.push_back(3);
 	v1.push_back(5);
 	v1.push_back(7);
 
 	reverse(v1.begin(),v1.end());
 	printV(v1);
 
 
 	system("pause");
 }
 
 //copy() 
 void main05()
 {
 	vector<int> v1;
 	v1.push_back(1);
 	v1.push_back(3);
 	v1.push_back(5);
 	v1.push_back(7);
 
 	vector<int> v2;
 	v2.resize(v1.size());
 
 	copy(v1.begin(),v1.end(),v2.begin());
 	printV(v2);
 
 	system("pause");
 }
 //二元谓词
 bool greater_equal_5(int &n)
 {
 	if (n >= 5)
 	{
 		return true;
 	}
 	return false;
 }
 
 //replace(beg, end, oldValue, newValue) : 将指定范围内的所有等于oldValue的元素替换成newValue
 //replace_if : 将指定范围内所有操作结果为true的元素用新值替换
 void main06()
 {
 	vector<int> v1;
 	v1.push_back(1);
 	v1.push_back(3);
 	v1.push_back(5);
 	v1.push_back(7);
 	v1.push_back(3);
 	/*
 	template<class _FwdIt,
 	class _Ty> inline
 	void replace(_FwdIt _First, _FwdIt _Last,
 		const _Ty& _Oldval, const _Ty& _Newval)
 	{	// replace each matching _Oldval with _Newval
 	_DEBUG_RANGE(_First, _Last);
 	_Replace(_Unchecked(_First), _Unchecked(_Last),
 		_Oldval, _Newval);
 	}
 	*/
 	replace(v1.begin(),v1.end(),3,8);
 
 	printV(v1);
 	cout << "\nreplace_if\n";
 	//>=5
 	replace_if(v1.begin(),v1.end(),greater_equal_5,1);
 
 	printV(v1);
 	system("pause");
 }
 
 //	swap: 交换两个容器的元素
 void main07()
 {
 	vector<int> v1;
 	v1.push_back(1);
 	v1.push_back(3);
 	v1.push_back(5);
 
 	vector<int> v2;
 	v2.push_back(2);
 	v2.push_back(4);
 	v2.push_back(6);
 
 	swap(v1,v2);
 	printV(v1);
 	printV(v2);
 	system("pause");
 }
 
 //accumulate: 对指定范围内的元素求和，然后结果再加上一个由val指定的初始值。
 void main08()
 {
 	vector<int> v1;
 	v1.push_back(1);
 	v1.push_back(3);
 	v1.push_back(5);
 	int tmp = accumulate(v1.begin(),v1.end(),10);
 	cout << tmp << endl;
 
 	system("pause");
 }
 
 //fill: 将输入值赋给标志范围内的所有元素。
 void main09()
 {
 	vector<int> v1;
 	v1.push_back(1);
 	v1.push_back(3);
 	v1.push_back(5);
 	/*
 	template<class _FwdIt,
 	class _Ty> inline
 	void fill(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
 	{	// copy _Val through [_First, _Last)
 	_DEBUG_RANGE(_First, _Last);
 	_Fill(_Unchecked(_First), _Unchecked(_Last), _Val);
 	}
 	*/
 	fill(v1.begin(),v1.end(),8);
 	printV(v1);
 
 	system("pause");
 }
 
 //set_union : 构造一个有序序列，包含两个有序序列的并集。
 //set_intersection : 构造一个有序序列，包含两个有序序列的交集。
 //set_difference : 构造一个有序序列，该序列保留第一个有序序列中存在而第二个有序序列中不存在的元素。
 void main10()
 {
 	vector<int> v1;
 	v1.push_back(1);
 	v1.push_back(3);
 	v1.push_back(5);
 
 	vector<int> v2;
 	v2.push_back(2);
 	v2.push_back(4);
 	v2.push_back(6);
 
 	vector<int> v3;
 	v3.resize(v1.size() + v2.size());
 	/*
 	// TEMPLATE FUNCTION set_union
 template<class _InIt1,
 	class _InIt2,
 	class _OutIt> inline
 	_OutIt set_union(_InIt1 _First1, _InIt1 _Last1,
 		_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
 	{	// OR sets [_First1, _Last1) and [_First2, _Last2), using operator<
 	return (_STD set_union(_First1, _Last1, _First2, _Last2, _Dest,
 		less<>()));
 	}
 	*/
 	set_union(v1.begin(),v1.end(),v2.begin(),v2.end(),v3.begin());
 
 	printV(v3);
 	system("pause");
 }

# #

[70]: /images/20220519/207f60a7f01144ecb161bd2d4ab88310.png
[70 1]: /images/20220519/ab0fb4f0832d44d8a7e80f797b3a97b1.png
[70 2]: /images/20220519/22d393df17474efe9ca8cc976321ed42.png
[70 3]: /images/20220519/7a3089d92ea94f26a80ad29cdfac56db.png
[70 4]: /images/20220519/c9b086b9984149f9875bf1c5cb3c3c55.png
[70 5]: /images/20220519/913945de7f89415aa0a9a1be85d6b245.png
[Link 1]: http://baike.baidu.com/view/8423750.htm
[Link 2]: http://baike.baidu.com/view/126530.htm
[70 6]: /images/20220519/93de3b08e18646db9ab6221311a69967.png
[70 7]: /images/20220519/8a3edf4797e94d9184ed69ee8f00e976.png
[70 8]: /images/20220519/b3aaa2382bd64a2aaaedcae5f0d93f75.png
[70 9]: /images/20220519/e5fe37dc5851496ebdc7e4f3705ce937.png
[70 10]: /images/20220519/492af9a57ef648dc9ca1727f429fe48e.png