C++中的STL

目录标题

• 1. STL初识
• • • 1.1 STL的背景
    • 1.2 STL基本概念
    • 1.3 STL中的组件
    • 1.4 STL中容器、算法、迭代器
    • 1.5 容器算法迭代器
    • • • 1.5.1 vector
        • 1.5.2 vector存放自定义数据类型
        • 1.5.3 vector容器嵌套容器
• 2. STL常用的容器
• • • 2.1 string容器
    • • • 2.1.1 string的基本概念
        • 2.1.2 构造函数
        • 2.1.3 赋值操作
        • 2.1.4 string字符串拼接
        • 2.1.5 string查找和替换
        • 2.1.6 string字符串比较
        • 2.1.7 string字符串存取
        • 2.1.8 string插入和删除
        • 2.1.9 string子串
    • 2.2 vector容器
    • • • 2.2.1 vector基本概念
        • 2.2.3 vector的构造函数
        • 2.2.3 vector赋值操作
        • 2.2.4 vector容量和大小
        • 2.2.5 vector插入和删除
        • 2.2.6 vector数据存取
        • 2.2.6 vector互换容器
        • 2.2.7 vector预留空间
    • 2.3 deque容器
    • • • 2.3.1 deque容器基本概念
        • 2.3.2 deque构造函数
        • 2.3.3 deque赋值操作
        • 2.3.4 deque大小操作
        • 2.3.5 deque插入和删除
        • 2.3.6 deque数据存取
        • 2.3.7 deque排序
    • 2.4 stack容器
    • • • 2.4.1 stack基本概念
        • 2.4.2 stack常用接口
    • 2.5 queue容器
    • • • 2.5.1 queue基本概念
        • 2.5.2 queue常用接口
    • 2.6 list容器
    • • • 2.6.1 list基本概念
        • 2.6.2 list构造函数
        • 2.6.3 list赋值和交换
        • 2.6.4 list大小操作
        • 2.6.5 list插入和删除
        • 2.6.6 list数据读取
        • 2.6.7 list反转和排序
    • 2.7 set/multiset容器
    • • • 2.7.1 set基本概念
        • 2.7.2 set构造和赋值
        • 2.7.3 set大小和交换
        • 2.7.4 set插入和删除
        • 2.7.5 set查找和统计
        • 2.7.6 set和multiset的区别
        • 2.7.7 pair对组创建
        • 2.7.8 set容器排序
    • 2.8 map/multimap容器
    • • • 2.8.1 map基本概念
        • 2.8.2 map构造和赋值
        • 2.8.3 map大小和交换
        • 2.8.4 map插入和删除
        • 2.8.5 map查找和统计
        • 2.8.6 map容器排序
• 3. STL-函数对象
• • • 3.1 函数对象
    • • • 3.1.1 函数对象的概念
        • 3.1.2 函数对象的使用
    • 3.2 谓词
    • • • 3.2.1 谓词的概念
        • 3.2.2 一元谓词
        • 3.2.3 二元谓词
    • 3.3 内建函数对象
    • • • 3.3.1 内建函数对象意义
        • 3.3.2 算术仿函数
        • 3.3.3 关系仿函数
        • 3.3.4 逻辑仿函数
• 4. STL-常用算法
• • • 4.1 常用遍历算法
    • • • 4.1.1 for_earch
        • 4.1.2 transform
    • 4.2 常用查找算法
    • • • 4.2.1 find
        • 4.2.2 find_if
        • 4.2.3 adjacent_find
        • 4.2.4 binary_search
        • 4.2.5 count
        • 4.2.5 count_if
    • 4.3 常用排序算法
    • • • 4.3.1 sort
        • 4.3.2 random_shuffle
        • 4.3.3 merge
        • 4.3.4 reverse
    • 4.4 常用拷贝和替换算法
    • • • 4.4.1 copy
        • 4.4.2 replace
        • 4.4.2 replace_if
        • 4.4.2 swap
    • 4.5 常用算术生成算法
    • • • 4.5.1 accumulate
        • 4.5.1 fill
    • 4.6 常用的集合算法
    • • • 4.6.1 set_intersection
        • 4.6.2 set_union
        • 4.6.3 set_difference

1. STL初识 1.1 STL的背景

C++面向对象和泛型编程思想，目的就是复用性的提升。为了建立数据结构和算法的一套流程，诞生了STL

1.2 STL基本概念

STL（Standard Template Library，标准模板库），可以从广义上分为：容器、算法和迭代器。容器和算法通过迭代器无缝连接，STL几乎所有的代码都采用了模板类或者模板函数。

1.3 STL中的组件

分别为：
1）容器：各种数据结构，如：vector、list、deque、set、map等，用来存放数据。
2）算法：各种常用的算法，如sort、find、copy等
3）迭代器：扮演了容器与算法之间的胶合剂。
4）仿函数：行为类似函数，可作为算法的某种策略。
5）适配器（配接器）：一种用来修饰容器或者仿函数或迭代器接口的东西。
6）空间配置器：负责空间的配置与管理。

1.4 STL中容器、算法、迭代器

STL容器就是将运用最广泛的一些数据结构实现出来，常用的数据结构：数组、链表、树、栈、队列、集合、映射表等。这些容器分为序列式容器和关联式容器两种：
序列式容器：强调值的排序，序列式容器中的每个元素均有固定的位置。
关联式容器：二叉树结构，各元素之间没有严格的物理上的顺序关系。
算法：有限的步骤，解决逻辑或数学上的问题。分为：
1）质变算法：是指运算过程中会更改区间内的元素的内容。例如拷贝、计数、替换、删除等等。
2）非质变算法：是指运算过程中不会更改区间内的元素内容，例如查找、计数、遍历、寻找极值，等等。
迭代器：提供一种方法，使之能够依序寻访某个容器所含的各个元素，而又无需暴露该容器的内部表示方式。每个容器都有自己专属的迭代器，迭代器使用非常类似于指针，初学阶段我们可以先理解迭代器为指针。

1.5 容器算法迭代器 1.5.1 vector

容器：vector
算法：for_each
迭代器：vector::iterator

#include
#include
#include
using namespace std;
void print(int val) {
	cout << val << " ";
}
int main() {
	//创建
	vector vec;
	//插入数据
	vec.push_back(1);
	vec.push_back(2);
	vec.push_back(3);
	vec.push_back(4);
	vec.push_back(5);
	//通过迭代器访问
	vector::iterator iter = vec.begin();//起始迭代器 执行容器中第一个元素
	vector::iterator iterend = vec.end();//结束迭代器 指向容器最后一个元素的下一个位置
	//第一种遍历
	while (iter != iterend) {
		cout << *iter << " ";
		iter++;
	}
	cout << endl;
	//第二种遍历
	for (vector::iterator it = vec.begin(); it != vec.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
	//第三种遍历 利用STL提供的遍历算法
	for_each(vec.begin(),vec.end(),print);
	return 0;
}

1.5.2 vector存放自定义数据类型

#include
#include
#include
#include
using namespace std;
class person {
public:
	person(string name, int age) {
		this->name = name;
		this->age = age;
	}
	string name;
	int age;
};
int main() {
	vector vec;
	person p1("zhinen", 10);
	person p2("yaodashuai", 20);
	person p3("ccc", 30);
	person p4("ddd", 40);
	person p5("eee", 50);
	vec.push_back(p1);
	vec.push_back(p2);
	vec.push_back(p3);
	vec.push_back(p4);
	vec.push_back(p5);
	for (vector::iterator it = vec.begin(); it != vec.end(); it++) {
		cout << (*it).name << " " << (*it).age << endl;
	}
	for (vector::iterator it = vec.begin(); it != vec.end(); it++) {
		cout << it->name << " " << it->age << endl;
	}
	cout << endl;
	//存放自定义类型的指针
	vector vec1;
	person p6("zhinen", 10);
	person p7("yaodashuai", 20);
	person p8("ccc", 30);
	person p9("ddd", 40);
	person p10("eee", 50);
	vec1.push_back(&p6);
	vec1.push_back(&p7);
	vec1.push_back(&p8);
	vec1.push_back(&p9);
	vec1.push_back(&p10);
	for (vector::iterator it = vec1.begin(); it != vec1.end(); it++) {
		cout << (*it)->name << " " << (*it)->age << endl;
	}
	return 0;
}

1.5.3 vector容器嵌套容器

#include
#include
#include
using namespace std;
int main() {
	vector> vec;
	//创建小容器
	vector vec1;
	vector vec2;
	vector vec3;
	vector vec4;
	for (int i = 1; i <=4; i++) {
		vec1.push_back(i);
		vec2.push_back(i*2);
		vec3.push_back(i*3);
		vec4.push_back(i*4);
	}
	vec.push_back(vec1);
	vec.push_back(vec2);
	vec.push_back(vec3);
	vec.push_back(vec4);
	//遍历
	for (vector>::iterator it = vec.begin(); it != vec.end(); it++) {
		for (vector::iterator iter = (*it).begin(); iter != (*it).end(); iter++) {
			cout << *iter << " ";
		}
		cout << endl;
	}
	return 0;
}

2. STL常用的容器 2.1 string容器 2.1.1 string的基本概念

本质：string是C++风格的字符串，而string本质上是一个类
string和char的区别：char是一个指针；string是一个类，类内封装了char*，管理这个字符串，是一个char的容器。
特点：
1）string内部封装了很多成员方法
2）string管理char所分配的内存，不用担心复制越界和取值越界等，由类内部进行负责

2.1.2 构造函数

函数原型：
string();//空的
string(const char* s);//使用字符串s初始化
string(const string& str);//使用一个string对象初始化另一个strng对象
string(int n,char c);//使用n个字符c初始化

2.1.3 赋值操作

函数原型：
string& operator=(const char* s);//char*类型字符串 赋值给当前的字符串
string& operator=(const string &s);//把字符串s赋给当前的字符串
string& operator=(char c);//字符赋值给当前的字符串
string& assign(const char *s);//把字符串s赋给当前的字符串
string& assign(const char *s, int n);//把字符串s的前n个字符赋给当前的字符串
string& assign(const string &s);//把字符串s赋给当前字符串
string& assign(int n,char c);//用n个字符c赋给当前字符串

2.1.4 string字符串拼接

实现字符串末尾拼接字符串
函数原型：
string& operator+=(const char* s);//重载+=操作符
string& operator+=(const char c);//重载+=操作符
string& operator+=(const string& str);//重载+=操作符
string& append(const char *s);//把字符串s连接到当前字符串末尾
string& append(const char *s, int n);//把字符串s的前n个字符连接到当前的字符串结尾
string& append(const string &s);//同 operator+=(const string& str)
string& append(const string &s,int pos,int n);//从字符串s中从pos开始的n个字符连接到字符串的结尾

2.1.5 string查找和替换

#include
#include
#include
using namespace std;
int main() {
	string str1 = "zhinenin";
	//查找
	//int find(const string& str,int pos=0);//查找str第一次出现位置，从pos开始查找，成功返回第一个字符的位置查找失败为-1
	int pos=str1.find("in");
	if(pos==-1)
		cout << "查找失败" << endl;
	else
		cout << pos << endl;
	//find从左往右查找，rfind从右往左查找
	pos = str1.rfind("in");
	cout << pos << endl;

	//替换：需指定起始位置和终止位置，替换成什么样的字符串
	//从1号位置到3号位置，替换成zjw
	str1.replace(1, 3, "zjw");
	cout << str1 << endl;
	return 0;
}

2.1.6 string字符串比较

字符串比较是按字符的ASCII码进行比较的：=返回0，>返回1，<返回-1.

#include
#include
#include
using namespace std;
int main() {
	string str1 = "zhinen", str2 = "zhinen";
	if (str1.compare(str2) == 0) {
		cout << "=" << endl;
	}
	else if (str1.compare(str2) == 1) {
		cout << ">" << endl;
	}
	else {
		cout << "<" << endl;
	}
	return 0;
}

2.1.7 string字符串存取

#include
#include
#include
using namespace std;
int main() {
	string str = "zhinen";
	//通过[]访问单个字符
	for (int i = 0; i < str.size(); i++) {
		cout << str[i];
	}
	cout << endl;
	//通过at方式访问单个字符
	for (int i = 0; i < str.size(); i++) {
		cout << str.at(i);
	}
	cout << endl;
	//修改单个字符
	str[1] = 'u';
	cout << str << endl;
	str.at(2) = 'j';
	cout << str << endl;
	return 0;
}

2.1.8 string插入和删除

#include
#include
#include
using namespace std;
int main() {
	string str = "zhinen";
	//插入
	str.insert(1,"jw");
	cout << str << endl;
	//删除
	str.erase(3, 5);
	cout << str << endl;
	return 0;
}

2.1.9 string子串

从子串中获取想要的子串

#include
#include
#include
using namespace std;
int main() {
	string str = "zhinen";
	string sub_str = str.substr(0, 3);
	cout << sub_str << endl;
	return 0;
}

2.2 vector容器 2.2.1 vector基本概念

vector数据结构和数组非常类似，也称为单端数组。不同之处在于数组是静态空间，而vector可以动态扩展。
动态扩展并不是在原空间之后续接新空间，而是寻找更大的内存空间，然后将原数据拷贝到新空间，释放原空间。
vector容器的迭代器支持随机访问的迭代器

2.2.3 vector的构造函数

#include
#include
#include
using namespace std;
void print(vector &vec) {
	for (int i = 0; i < vec.size(); i++) {
		cout << vec[i] << " ";
	}
	cout << endl;
}
int main() {
	//默认构造，无参构造
	vector vec1;
	for (int i = 1; i <= 10; i++) {
		vec1.push_back(i);
	}
	print(vec1);
	//区间的方式进行构造
	vector vec2(vec1.begin(), vec1.end());
	print(vec2);

	//n个elem的构造方式
	vector vec3(10, 1);
	print(vec3);
	//拷贝构造
	vector vec4(vec3);
	print(vec4);
	return 0;
}

2.2.3 vector赋值操作

#include
#include
#include
using namespace std;
void print(vector &vec) {
	for (int i = 0; i < vec.size(); i++) {
		cout << vec[i] << " ";
	}
	cout << endl;
}
int main() {
	vector vec;
	for (int i = 1; i < 10; i++) {
		vec.push_back(i * i);
	}
	print(vec);
	//赋值
	vector vec2;
	vec2 = vec;
	print(vec2);
	//assign
	vector vec3;
	vec3.assign(vec.begin(), vec.end());
	print(vec3);

	vector vec4;
	vec4.assign(10, 100);
	print(vec4);
	return 0;
}

2.2.4 vector容量和大小

函数原型：
empty();//判断容器是否为空
capacity();//容器的容量
size();//返回容器中元素的个数
resize(int num);//重新指定容器的长度为num，若容器变长，则以默认值填充新位置，若变短，超过长度的元素被删除
resize(int num, elem);//重新指定容器的长度为num，若容器变长，则以elem填充新位置，若变短，超过长度的元素被删除

2.2.5 vector插入和删除

#include
#include
#include
using namespace std;
void print(vector &vec) {
	for (int i = 0; i < vec.size(); i++) {
		cout << vec[i] << " ";
	}
	cout << endl;
}
int main() {
	vector vec;
	//尾部插入元素
	for (int i = 1; i < 10; i++) {
		vec.push_back(i * i);
	}
	print(vec);
	//尾部删除数据
	vec.pop_back();
	print(vec);
	//插入，第一个参数必须是迭代器
	vec.insert(vec.begin() + 2, 10);
	print(vec);
	vec.insert(vec.begin() + 1, 2, 20);
	print(vec);
	//删除，参数也是迭代器
	vec.erase(vec.begin() + 4);
	print(vec);
	return 0;
}

2.2.6 vector数据存取

#include
#include
#include
using namespace std;
void print(vector &vec) {
	for (int i = 0; i < vec.size(); i++) {
		cout << vec[i] << " ";
	}
	cout << endl;
}
int main() {
	vector vec;
	for (int i = 1; i < 10; i++) {
		vec.push_back(i * i);
	}
	//[]方式访问
	print(vec);
	//利用at方式访问
	for (int i = 0; i < vec.size(); i++) {
		cout << vec.at(i) << " ";
	}
	cout << endl;
	//第一个元素
	cout << vec.front() << endl;
	//最后一个元素
	cout << vec.back() << endl;
	return 0;
}

2.2.6 vector互换容器

#include
#include
#include
using namespace std;
void print(vector &vec) {
	for (int i = 0; i < vec.size(); i++) {
		cout << vec[i] << " ";
	}
	cout << endl;
}
int main() {
	vector vec;
	for (int i = 1; i < 10; i++) {
		vec.push_back(i * i);
	}
	print(vec);
	vector vec1;
	for (int i = 0; i < 10; i++) {
		vec1.push_back((10 - i) * (10 - i));
	}
	print(vec1);
	//交换
	vec.swap(vec1);
	print(vec);
	print(vec1);

	//巧用swap可以收缩内存空间
	vector v;
	for (int i = 0; i < 10000000; i++) {
		v.push_back(i);
	}
	cout << v.capacity() << endl;
	cout << v.size() << endl;
	v.resize(10);
	cout << v.capacity() << endl;
	cout << v.size() << endl;
	//巧用swap收缩内存
	vector(v).swap(v);
	cout << v.capacity() << endl;
	cout << v.size() << endl;
	return 0;
}

2.2.7 vector预留空间

减少vector在动态扩展容量时的扩展次数
函数原型：reserve(int len);//容器预留len个元素长度，预留位置不初始化，元素不可访问

#include
#include
#include
using namespace std;
void print(vector &vec) {
	for (int i = 0; i < vec.size(); i++) {
		cout << vec[i] << " ";
	}
	cout << endl;
}
int main() {
	vector vec;
	int num = 0;//开辟的次数
	int* p = NULL;
	for (int i = 0; i < 100000; i++) {
		vec.push_back(i);
		if (p != &vec[0]) {
			p = &vec[0];
			num++;
		}
	}
	cout << num << endl;
	vector vec1;
	vec1.reserve(1000000);//利用reserve预留空间
	int num1 = 0;//开辟的次数
	int* p1 = NULL;
	for (int i = 0; i < 1000000; i++) {
		vec1.push_back(i);
		if (p1 != &vec1[0]) {
			p1 = &vec1[0];
			num1++;
		}
	}
	cout << num1 << endl;
	return 0;
}

2.3 deque容器 2.3.1 deque容器基本概念

功能：双端数组，可以对头端进行插入删除操作
deque和vector的区别：
1）vector对于头部的插入删除效率低，数据量大，效率越低
2）deque相对而言，对头部的插入删除速度比vector快
3）vector访问元素时的速度会比deque快，这和两者的内部实现有关

内部的工作原理：deque内部有个中控器，维护每段缓冲区中的内容，缓冲区存放真实数据，中控器维护的时每个缓冲区的地址，使得使用deque时像一片连续的内存空间。deque容器的迭代器也是支持随机访问的。

2.3.2 deque构造函数

#include
#include
using namespace std;
void print(const deque &d) {
	//设置容器里面的数据不可以修改
	for (deque::const_iterator it = d.begin(); it != d.end();it++) {
		cout << *it << " ";
	}
	cout << endl;
}
int main() {
	deque d1;
	for (int i = 1; i < 10; i++) {
		d1.push_back(i * i);
	}
	print(d1);
	deque d2(d1.begin(), d1.end());
	print(d2);
	deque d3(d1);
	print(d3);
	deque d4(10, 1);
	print(d4);
	return 0;
}

2.3.3 deque赋值操作

#include
#include
using namespace std;
void print(const deque &d) {
	//设置容器里面的数据不可以修改
	for (deque::const_iterator it = d.begin(); it != d.end();it++) {
		cout << *it << " ";
	}
	cout << endl;
}
int main() {
	deque d1;
	for (int i = 1; i < 10; i++) {
		d1.push_back(i * i);
	}
	print(d1);
	//operator=赋值
	deque d2;
	d2 = d1;
	print(d2);
	//assign
	deque d3;
	d3.assign(d1.begin(), d1.end());
	print(d3);
	//
	deque d4;
	d4.assign(10, 1);
	print(d4);
	return 0;
}

2.3.4 deque大小操作

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

2.3.5 deque插入和删除

两端插入删除操作：

#include
#include
using namespace std;
void print(const deque &d) {
	//设置容器里面的数据不可以修改
	for (deque::const_iterator it = d.begin(); it != d.end();it++) {
		cout << *it << " ";
	}
	cout << endl;
}
int main() {
	deque d;
	//尾插
	for (int i = 1; i < 10; i++) {
		d.push_back(i * i);
	}
	print(d);
	//头插
	for (int i = 1; i < 10; i++) {
		d.push_front(i * i);
	}
	print(d);
	//尾部删除
	d.pop_back();
	print(d);
	//头部删除
	d.pop_front();
	print(d);
	return 0;
}

指定位置进行插入和删除

#include
#include
using namespace std;
void print(const deque &d) {
	//设置容器里面的数据不可以修改
	for (deque::const_iterator it = d.begin(); it != d.end();it++) {
		cout << *it << " ";
	}
	cout << endl;
}
int main() {
	deque d;
	//尾插
	for (int i = 1; i < 10; i++) {
		d.push_back(i * i * i);
	}
	print(d);
	//insert插入
	d.insert(d.begin(), 999);
	print(d);
	d.insert(d.begin() + 3, 3, 999);//重复插入
	print(d);
	//区间插入
	deque d1;
	d1.push_back(1);
	d1.push_back(2);
	d1.push_back(3);
	d1.push_back(4);
	d1.push_back(5);
	d.insert(d.begin() + 4, d1.begin(), d1.end());
	print(d);
	//删除
	d.erase(d.begin()+1);
	print(d);
	//区间删除
	d.erase(d.begin(), d.begin() + 7);
	print(d);
	d.clear();
	print(d);
	return 0;
}

2.3.6 deque数据存取

#include
#include
using namespace std;
void print(const deque &d) {
	//设置容器里面的数据不可以修改
	for (deque::const_iterator it = d.begin(); it != d.end();it++) {
		cout << *it << " ";
	}
	cout << endl;
}
int main() {
	deque d;
	//尾插
	for (int i = 1; i < 10; i++) {
		d.push_back(i * i * i);
	}
	print(d);
	//通过[]的方式访问元素
	for (int i = 0; i < d.size(); i++) {
		cout << d[i] << " ";
	}
	cout << endl;
	//通过at的方式
	for (int i = 0; i < d.size(); i++) {
		cout << d.at(i) << " ";
	}
	cout << endl;
	cout << d.front() << endl;
	cout << d.back() << endl;
	return 0;
}

2.3.7 deque排序

#include
#include
#include
using namespace std;
void print(const deque &d) {
	//设置容器里面的数据不可以修改
	for (deque::const_iterator it = d.begin(); it != d.end();it++) {
		cout << *it << " ";
	}
	cout << endl;
}
int main() {
	deque d;
	//尾插
	for (int i = 1; i < 10; i++) {
		if (i <= 5)
			d.push_back(i * i * i);
		else
			d.push_front(i * i * i);
	}
	print(d);
	sort(d.begin(), d.end());
	print(d);
	return 0;
}

2.4 stack容器 2.4.1 stack基本概念

概念：stack是一种先进后出（First In Last Out, FILO）的数据结构，他只有一个出口。栈不允许有遍历的行为，栈中只有顶端的元素才可以被外界使用。
1）栈中进入数据称为入栈push；
2）栈中弹出数据称为出栈pop；

2.4.2 stack常用接口

构造函数：
stack< T> stk;//stack采用模板类实现，stack对象的默认构造形式
stack(const stack &stk);//拷贝构造函数

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

数据存取：
push(elem);//向栈顶添加一个元素
pop();//从栈顶删除第一个元素
top();//返回栈顶元素

大小操作：
empty();//判断栈顶是否为空
size();//返回栈的大小

#include
#include
using namespace std;
int main() {
	stack d;
	//入栈
	for (int i = 1; i < 10; i++) {
		d.push(i);
	}
	cout << d.size() << endl;
	while (!d.empty()) {
		cout << d.top() << " ";
		d.pop();
	}
	cout << endl;
	cout << d.size() << endl;
	return 0;
}

2.5 queue容器 2.5.1 queue基本概念

queue是一种先进先出的数据结构，他有两个出口

队列容器允许从一端新增元素，从另一端移除元素；队列中只有对头和队尾才可以被外界使用，因此队列不允许有遍历的行为；队列中进数据称为入队（push）；队列中出数据称为出队（pop）。

2.5.2 queue常用接口

构造函数：
queue< T> que;//queue采用模板类实现，queue对象的默认构造形式
queue(const queue &que);//拷贝构造函数
赋值操作：
queue& operator=(const queue &que);//重载等号操作符
数据存取：
push(elem);//往队尾添加元素
pop();//从对头移除第一个元素
back();//返回最后一个元素
front();//返回第一个元素
大小操作：
empty();//判断堆栈是否为空
size();//返回栈的大小

2.6 list容器 2.6.1 list基本概念

STL中的链表是一个双向循环链表
功能：将数据进行链式存储
链表（list）是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链表实现的。
链表的组成：链表是一系列节点组成
节点的组成：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域。

由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于双向迭代器。
优点：可以对任意位置进行快速的插入删除元素，不需要移动大量元素，只需要修改指针即可。采用动态存储分配，不会造成内存浪费和溢出。
缺点：容器遍历速度，没有数组快，占用空间比数组大。
list还有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的。（vector在插入数据时，内存不够用时，会开辟一个新的空间，这时迭代器失效）。

2.6.2 list构造函数

#include
#include
using namespace std;
void print(const list& l) {
	for (list::const_iterator it = l.begin(); it != l.end(); it++) {
		cout << (*it) << " ";
	}
	cout << endl;
}
int main() {
	//创建list容器
	list li;//默认构造
	//添加数据
	li.push_back(1);
	li.push_back(2);
	li.push_back(3);
	li.push_back(4);
	li.push_back(5);
	//遍历容器
	print(li);
	//区间的方式构造
	list li1(li.begin(), li.end());
	print(li1);
	//拷贝构造
	list li2(li);
	print(li2);
	//n个elem
	list li3(10,1000000);
	print(li3);
	return 0;
}

2.6.3 list赋值和交换

#include
#include
using namespace std;
void print(const list& l) {
	for (list::const_iterator it = l.begin(); it != l.end(); it++) {
		cout << (*it) << " ";
	}
	cout << endl;
}
int main() {
	//创建list容器
	list li;//默认构造
	//添加数据
	li.push_back(1);
	li.push_back(2);
	li.push_back(3);
	li.push_back(4);
	li.push_back(5);
	print(li);
	list li1;
	li1 = li;//operator=赋值
	print(li1);

	list li2;
	li2.assign(li.begin(), li.end());
	print(li2);

	list li3;
	li3.assign(10, 1);
	print(li3);
	//交换
	li3.swap(li);
	print(li3);
	print(li);
	return 0;
}

2.6.4 list大小操作

#include
#include
using namespace std;
void print(const list& l) {
	for (list::const_iterator it = l.begin(); it != l.end(); it++) {
		cout << (*it) << " ";
	}
	cout << endl;
}
int main() {
	//创建list容器
	list li;//默认构造
	//添加数据
	li.push_back(1);
	li.push_back(2);
	li.push_back(3);
	li.push_back(4);
	li.push_back(5);
	print(li);
	//判断容器是否为空
	if (li.empty()) {
		cout << "empty!" << endl;
	}else {
		//输出容器大小
		cout << "size:" << li.size() << endl;
	}
	//重新指定大小
	li.resize(10);
	print(li);
	li.resize(20,100);
	print(li);
	li.resize(3);
	print(li);
	return 0;
}

2.6.5 list插入和删除

函数原型：
push_back(elem);//在容器尾部加入一个元素
pop_back();//删除容器中最后一个元素
push_front(elem);//在容器开头插入一个元素
pop_front();//在容器开头移除第一个元素
insert(pos,elem);//在pos位置插elem元素的拷贝，返回新数据的位置
insert(pos,n,elem);//在pos位置插n个elem数据，无返回值
insert(pos,beg,end);//在pos位置插入[beg，elem]区间的数据，无返回值
clear();//移除容器中所有数据
erase(beg,end);//删除[beg，end]区间的数据，返回下一个数据的位置
erase(pos);//删除pos位置的数据，返回下一个数据的位置
remove(elem);//删除容器中所有与elem值匹配的元素

#include
#include
using namespace std;
void print(const list& l) {
	for (list::const_iterator it = l.begin(); it != l.end(); it++) {
		cout << (*it) << " ";
	}
	cout << endl;
}
int main() {
	//创建list容器
	list li;//默认构造
	
	//push_back(elem);//在容器尾部加入一个元素
	li.push_back(1);
	li.push_back(2);
	li.push_back(3);
	li.push_back(4);
	li.push_back(5);
	print(li);
	//pop_back();//删除容器中最后一个元素
	li.pop_back();
	print(li);
	//push_front(elem);//在容器开头插入一个元素
	li.push_front(1000);
	li.push_front(100);
	print(li);
	//pop_front();//在容器开头移除第一个元素
	li.pop_front();
	print(li);
	//insert(pos, elem);//在pos位置插elem元素的拷贝，返回新数据的位置
	li.insert(li.begin(), 999);
	print(li);
	//insert(pos, n, elem);//在pos位置插n个elem数据，无返回值
	list::iterator iter = li.begin();
	iter++;
	iter++;
	iter++;
	li.insert(iter, 6, 111);
	print(li);
	//insert(pos, beg, end);//在pos位置插入[beg，elem]区间的数据，无返回值
	//clear();//移除容器中所有数据
	//erase(beg, end);//删除[beg，end]区间的数据，返回下一个数据的位置
	//erase(pos);//删除pos位置的数据，返回下一个数据的位置
	iter = li.begin();
	li.erase(iter);
	print(li);
	//remove(elem);//删除容器中所有与elem值匹配的元素
	li.remove(111);
	print(li);
	return 0;
}

2.6.6 list数据读取

#include
#include
using namespace std;
void print(const list& l) {
	for (list::const_iterator it = l.begin(); it != l.end(); it++) {
		cout << (*it) << " ";
	}
	cout << endl;
}
int main() {
	//创建list容器
	list li;
	li.push_back(1);
	li.push_back(2);
	li.push_back(3);
	li.push_back(4);
	li.push_back(5);
	print(li);
	//不可以用[]访问list元素，也不可以用at访问，因为list本质是链表，迭代器不支持随机访问。
	cout << li.back() << endl;
	cout << li.front() << endl;
	return 0;
}

2.6.7 list反转和排序

#include
#include
#include
using namespace std;
void print(const list& l) {
	for (list::const_iterator it = l.begin(); it != l.end(); it++) {
		cout << (*it) << " ";
	}
	cout << endl;
}
bool compare(int a,int b) {
	return a > b;
}
int main() {
	//创建list容器
	list li;
	li.push_back(100);
	li.push_back(22);
	li.push_back(32);
	li.push_back(44);
	li.push_back(15);
	print(li);
	//反转
	reverse(li.begin(), li.end());
	print(li);
	li.reverse();
	print(li);
	//排序
	//所有不支持随机迭代器的容器，不可以用标准的算法
	//不支持随机访问的迭代器，内部会提供对应的一些算法
	//sort(li.begin(), li.end());
	li.sort();//默认规则，从小到大；
	print(li);
	li.sort(compare);
	print(li);
	return 0;
}

2.7 set/multiset容器 2.7.1 set基本概念

简介：所有元素都会在插入时自动被排序。
本质：set/multiset属于关联式容器，底层结构是用二叉树实现。
set和multiset区别：
1）set不允许容器中有重复的元素；
2）multiset允许容器中有重复的元素。

2.7.2 set构造和赋值

#include
#include
using namespace std;
void print(const set &s) {
	for (set::const_iterator it = s.begin(); it != s.end();it++) {
		cout << *it << " ";
	}
	cout << endl;
}
int main() {
	set s;
	//插入数据只有insert方式
	s.insert(7);
	s.insert(5);
	s.insert(3);
	s.insert(2);
	s.insert(4);
	s.insert(7);
	s.insert(6);
	s.insert(1);
	print(s);
	set s1(s);
	print(s1);
	set s2;
	s2 = s;
	print(s1);
	return 0;
}

2.7.3 set大小和交换

#include
#include
using namespace std;
void print(const set &s) {
	for (set::const_iterator it = s.begin(); it != s.end();it++) {
		cout << *it << " ";
	}
	cout << endl;
}
int main() {
	set s;
	//插入数据只有insert方式
	s.insert(7);
	s.insert(5);
	s.insert(3);
	s.insert(2);
	s.insert(4);
	s.insert(7);
	s.insert(6);
	s.insert(1);
	print(s);
	if (s.empty()) {
		cout << "empty" << endl;
	}
	else {
		cout << "not empty" << endl;
		cout << "size:" << s.size() << endl;
	}
	set s1;
	s1.insert(70);
	s1.insert(50);
	s1.insert(30);
	s1.insert(20);
	s1.insert(40);
	cout << "交换前：";
	print(s1);
	cout << "交换后：";
	s1.swap(s);
	print(s1);
	return 0;
}

2.7.4 set插入和删除

#include
#include
using namespace std;
void print(const set &s) {
	for (set::const_iterator it = s.begin(); it != s.end();it++) {
		cout << *it << " ";
	}
	cout << endl;
}
int main() {
	set s;
	//插入
	s.insert(7);
	s.insert(5);
	s.insert(3);
	s.insert(2);
	s.insert(4);
	s.insert(7);
	s.insert(6);
	s.insert(1);
	print(s);
	//删除
	s.erase(s.begin());
	print(s);
	//删除重载版本
	s.erase(7);
	print(s);
	//清空
	s.erase(s.begin(), s.end());//或者s.clear();
	print(s);
	return 0;
}

2.7.5 set查找和统计

函数原型：
find(key);//查找key是否存在；若存在，返回该键的元素的迭代器；若不存在，返回set.end();
count(key);//统计key的元素个数；

#include
#include
using namespace std;
void print(const set &s) {
	for (set::const_iterator it = s.begin(); it != s.end();it++) {
		cout << *it << " ";
	}
	cout << endl;
}
int main() {
	set s;
	//插入
	s.insert(7);
	s.insert(5);
	s.insert(3);
	s.insert(2);
	s.insert(4);
	s.insert(7);
	s.insert(6);
	s.insert(1);
	print(s);
	//查找
	set::iterator pos = s.find(5);
	if (pos != s.end()) {
		cout << "find element: " << *pos << endl;
	}
	else {
		cout << "element not find" << endl;
	}
	//统计
	int num = s.count(7);
	//对于set而言，统计结果要么是0，要么是1
	cout << num << endl;
 	return 0;
}

2.7.6 set和multiset的区别

1）set不可以插入重复数据，而multiset可以；
2）set插入数据的同时会返回插入结果，表示插入是否成功；
3）multiset不会检测数据，因此可以插入重复数据。

#include
#include
using namespace std;
void print(const set &s) {
	for (set::const_iterator it = s.begin(); it != s.end();it++) {
		cout << *it << " ";
	}
	cout << endl;
}
int main() {
	set s;
	//插入
	pair::iterator,bool> ret=s.insert(7);
	if (ret.second) {
		cout << "insterted successfully" << endl;
	}
	else {
		cout << "insert failed" << endl;
	}
	ret = s.insert(5);
	if (ret.second) {
		cout << "insterted successfully" << endl;
	}
	else {
		cout << "insert failed" << endl;
	}
	ret = s.insert(2);
	if (ret.second) {
		cout << "insterted successfully" << endl;
	}
	else {
		cout << "insert failed" << endl;
	}
	ret = s.insert(4);
	if (ret.second) {
		cout << "insterted successfully" << endl;
	}
	else {
		cout << "insert failed" << endl;
	}
	ret = s.insert(7);
	if (ret.second) {
		cout << "insterted successfully" << endl;
	}
	else {
		cout << "insert failed" << endl;
	}
	ret = s.insert(6);
	if (ret.second) {
		cout << "insterted successfully" << endl;
	}
	else {
		cout << "insert failed" << endl;
	}
	ret = s.insert(1);
	if (ret.second) {
		cout << "insterted successfully" << endl;
	}
	else {
		cout << "insert failed" << endl;
	}
	print(s);
	multiset ms;
	ms.insert(12);
	ms.insert(12);
	ms.insert(12);
	ms.insert(12);
	ms.insert(1);
	for (multiset::iterator it = ms.begin(); it != ms.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
 	return 0;
}

2.7.7 pair对组创建

成对出现的数据，利用对组可以返回两个数据。

#include
#include
using namespace std;
int main() {
	//第一种方式
	pair pa("zhinen", 22);
	cout << pa.first << " " << pa.second << endl;
	//第二种方式
	pair pa1 = make_pair("zhinen", 22);
	cout << pa1.first << " " << pa1.second << endl;
 	return 0;
}

2.7.8 set容器排序

set容器默认排序规则为从小到大，可以利用仿函数，改变排序规则。
set存放内置数据类型：

#include
#include
using namespace std;
class Compare {
public:
	bool operator()(int a,int b) const{
		return a > b;
	}
};
int main() {
	set s;
	//插入
	s.insert(7);
	s.insert(5);
	s.insert(3);
	s.insert(2);
	s.insert(4);
	s.insert(7);
	s.insert(6);
	s.insert(1);
	for (set::iterator it = s.begin(); it != s.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
	//指定排序规则从大到小
	set s1;
	//插入
	s1.insert(7);
	s1.insert(5);
	s1.insert(2);
	s1.insert(4);
	s1.insert(7);
	s1.insert(6);
	s1.insert(1);
	for (set::iterator iter = s1.begin(); iter != s1.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;
	return 0;
}

set存放自定义数据类型：

#include
#include
#include
using namespace std;
class person {
public:
	person(string name,int age) {
		this->name = name;
		this->age = age;
	}
	string name;
	int age;
};
class Compare {
public:
	bool operator()(const person &a, const person &b) const{
		//姓名从大到小排序
		return a.name > b.name;
	}
};
int main() {
	//自定义的数据类型，都会指定排序规则
	set s;
	//创建person对象
	person p1("zhinen", 22);
	person p2("yaodashuai", 24);
	person p3("aaa", 12);
	person p4("bbb", 23);
	person p5("ccc", 45);
	s.insert(p1);
	s.insert(p2);
	s.insert(p3);
	s.insert(p4);
	s.insert(p5);
	s.insert(p3);
	for (set::iterator it = s.begin(); it != s.end(); it++) {
		cout << it->name << " " << it->age << endl;
	}
	return 0;
}

2.8 map/multimap容器 2.8.1 map基本概念

简介：
1）map中所有元素都是pair；
2）pair中第一个元素为key（键值），起到索引作用，第二个元素为value（实值）。
3）所有元素都会根据元素的键值自动排序。
本质：map/multimap属于关联式容器，底层结构是用二叉树实现。
优点：可以根据key值快速找到value值。
map/multimap：
1）map不允许容器中有重复key值元素；
2）multimap允许容器中有重复key值元素。

2.8.2 map构造和赋值

#include
#include

2.8.3 map大小和交换

#include
#include

2.8.4 map插入和删除

函数原型：
insert(elem);//在容器中插入元素
clear();//清除所有元素
erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器
erase(beg,end);//删除区间[beg,end]的所有元素，返回下一个元素的迭代器
erase(key);//删除容器中值为key的元素

#include
#include

2.8.5 map查找和统计

#include
#include

2.8.6 map容器排序

#include
#include

3. STL-函数对象 3.1 函数对象 3.1.1 函数对象的概念

概念：重载函数调用操作符的类，其对象常称为函数对象，函数对象使用重载的（）时，行为类似于函数调用，也叫仿函数。
本质：函数对象（仿函数）是一个类，不是一个函数。

3.1.2 函数对象的使用

特点：
1）在使用时，可以像普通函数那样调用，可以有参数、可以有返回值。
2）函数对象超出普通函数的概念，函数对象可以有自己的状态
3）函数对象可以作为参数传递。

#include
#include

3.2 谓词 3.2.1 谓词的概念

1）返回bool类型的仿函数称为谓词；
2）如果operator（）接受一个参数，那么叫一元谓词；
3）如果operator（）接受两个参数，那么叫两元谓词；

3.2.2 一元谓词

#include
#include
#include
#include
#include
using namespace std;
class findnumber {
public:
	bool operator()(int val) {
		return val > 90;
	}
};
int main() {
	vector vec;
	srand((unsigned)time(NULL));
	for (int i = 0; i < 10; i++) {
		vec.push_back(rand() % 100);
	}
	//查找容器中有没有大于90的数字；
	//findnumber()匿名函数对象
	vector::iterator it=find_if(vec.begin(), vec.end(), findnumber());
	if (it == vec.end()) {
		cout << "not found" << endl;
	}
	else {
		cout << "find it: " << *it << endl;
	}
	return 0;
}

3.2.3 二元谓词

#include
#include
#include
#include
#include
using namespace std;
class Compare {
public:
	bool operator()(int val1,int val2) {
		return val1>val2;
	}
};
int main() {
	vector vec;
	srand((unsigned)time(NULL));
	for (int i = 0; i < 10; i++) {
		vec.push_back(rand() % 100);
	}
	sort(vec.begin(), vec.end());
	for (int i = 0; i < 10; i++) {
		cout << vec[i] << " ";
	}
	cout << endl;
	sort(vec.begin(), vec.end(), Compare());
	for (int i = 0; i < 10; i++) {
		cout << vec[i] << " ";
	}
	cout << endl;
	return 0;
}

3.3 内建函数对象 3.3.1 内建函数对象意义

STL内建了一些函数对象。
分类：算术仿函数、关系仿函数、逻辑仿函数
用法：这些仿函数所产生的对象，用法和一般函数完全相同；使用内建函数，需要引入头文件#include

3.3.2 算术仿函数

实现四则运算，其中negate是一元运算，其他的都是二元运算。仿函数原型：
template T plus;//加法仿函数
template T minus;//减法仿函数
template T multiplies;//乘法仿函数
template T divides;//除法仿函数
template T modulus;//取模仿函数
template T negate;//取反仿函数

#include
#include
#include
using namespace std;
int main() {
	negate n;
	cout << n(50) << endl;
	plus pl;
	cout << pl(10, 10) << endl;
	return 0;
}

3.3.3 关系仿函数

实现关系对比。仿函数原型：
template bool eual_to;//等于
template bool not_eual_to;//不等于
template bool greater;//大于
template bool greater_equal;//大于等于
template bool less;//小于
template bool less_equal;//小于等于

#include
#include
#include
#include
#include
using namespace std;
class Compare {
public:
	bool operator()(int v1,int v2) {
		return v1 > v2;
	}
};
int main() {
	vector vec;
	srand((unsigned)time(NULL));
	for (int i = 0; i < 10; i++) {
		vec.push_back(rand() % 100);
	}
	for (int i = 0; i < 10; i++) {
		cout << vec[i] << " ";
	}
	cout << endl;
	sort(vec.begin(), vec.end(), greater());//内建的函数类型
	//==sort(vec.begin(), vec.end(), Compare());
	for (int i = 0; i < 10; i++) {
		cout << vec[i] << " ";
	}
	cout << endl;
	return 0;
}

3.3.4 逻辑仿函数

实现逻辑运算。函数原型：
template bool logical_and;//逻辑与
template bool logical_or;//逻辑或
template bool logical_not;//逻辑非

#include
#include
#include
#include
#include
#include
using namespace std;
int main() {
	vector vec;
	srand((unsigned)time(NULL));
	for (int i = 0; i < 10; i++) {
		vec.push_back((rand() % 100) % 2);
	}
	for (int i = 0; i < 10; i++) {
		cout << vec[i] << " ";
	}
	cout << endl;
	//利用逻辑非，将容器vec搬运到容器vec1中，并执行取反操作。
	vector vec1;
	vec1.resize(vec.size());//
	transform(vec.begin(), vec.end(), vec1.begin(), logical_not<>());
	for (int i = 0; i < 10; i++) {
		cout << vec1[i] << " ";
	}
	cout << endl;
	return 0;
}

4. STL-常用算法

算法主要是由头文件 ：
：是所有STL头文件中最大的一个，范围涉及到比较、交换、查找、遍历操作、赋值、修改等；
：体积很小，只包括几个在序列上面进行简单的数学运算的模板函数；
：定义了一些模板类，用以声明函数对象。

4.1 常用遍历算法 4.1.1 for_earch

实现遍历容器，函数原型for_each(iterator beg, iterator end, _func);：遍历算法，遍历容器元素，beg开始迭代器，end结束迭代器，—_func函数或函数对象。

#include
#include
#include
#include
#include
using namespace std;
void _func(int val) {
	cout << val << " ";
}
class _func1 {
public:
	void operator()(int val) {
		cout << val << " ";
	}
};
int main() {
	vector vec;
	srand((unsigned)time(NULL));
	for (int i = 0; i < 10; i++) {
		vec.push_back(rand() % 100);
	}
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;
	for_each(vec.begin(), vec.end(), _func1());
	return 0;
}

4.1.2 transform

搬运容器到另一个容器中。函数原型transform(iterator beg1, iterator end1, iterator beg2, _func);：beg1源容器开始迭代器，end源容器结束迭代器，beg2目标容器开始迭代器，_func函数或函数对象。

#include
#include
#include
#include
#include
using namespace std;
void _func(int val) {
	cout << val << " ";
}
class _func1 {
public:
	int operator()(int v) {
		return v*v;
	}
};
int main() {
	vector vec, vec1;
	srand((unsigned)time(NULL));
	for (int i = 0; i < 10; i++) {
		vec.push_back(rand() % 100);
	}
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;
	vec1.resize(vec.size());//需要提前开辟空间
	transform(vec.begin(), vec.end(), vec1.begin(), _func1());
	for_each(vec1.begin(), vec1.end(), _func);
	cout << endl;
	return 0;
}

4.2 常用查找算法 4.2.1 find

查找指定元素，找到返回指定元素的迭代器，找不到返回结束迭代器end()；
函数原型：find(iterator beg, iterator end, value);：按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置，beg开始迭代器，end结束迭代器，value查找的元素。

#include
#include
#include
#include
#include
#include
using namespace std;
void _func(int val) {
	cout << val << " ";
}
class person {
public:
	person(string name, int age) {
		this->name = name;
		this->age = age;
	}
	//重载==，底层find知道如何对比person数据类型
	bool operator==(const person &p) {
		return this->name == p.name && this->age == p.age;
	}
	string name;
	int age;
};
int main() {
	//内置函数类型查找
	vector vec;
	srand((unsigned)time(NULL));
	for (int i = 0; i < 50; i++) {
		vec.push_back(rand() % 100);
	}
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;
	cout << endl;
	vector::iterator it = find(vec.begin(), vec.end(), 50);
	if (it == vec.end()) {
		cout << "not found" << endl;
	}
	else {
		cout << "find it" << endl;
	}
	//自定义数据类型查找
	vector vec1;
	person p1("zhinen", 22);
	person p2("aaa", 12);
	person p3("ggg", 34);
	person p4("eee", 54);
	person p5("kkk", 23);
	vec1.push_back(p1);
	vec1.push_back(p2);
	vec1.push_back(p3);
	vec1.push_back(p4);
	vec1.push_back(p5);
	person p("kkkk", 23);
	vector::iterator iter = find(vec1.begin(), vec1.end(), p);
	if (iter == vec1.end()) {
		cout << "not found" << endl;
	}
	else {
		cout << "find it" << endl;
	}
	return 0;
}

4.2.2 find_if

函数原型：find(iterator beg, iterator end, _pred);：按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置，beg开始迭代器，end结束迭代器，_pred查找的元素（返回bool类型的仿函数）。

#include
#include
#include
#include
#include
#include
using namespace std;
void _func(int val) {
	cout << val << " ";
}
class Greater {
public:
	bool operator()(int val) {
		return val > 50;
	}
};

class person {
public:
	person(string name, int age) {
		this->name = name;
		this->age = age;
	}
	//重载==，底层find知道如何对比person数据类型
	bool operator==(const person &p) {
		return this->name == p.name && this->age == p.age;
	}
	string name;
	int age;
};
class Greater1 {
public:
	bool operator()(person& p) {
		return p.age > 20;
	}
};
int main() {
	//内置函数类型查找
	vector vec;
	srand((unsigned)time(NULL));
	for (int i = 0; i < 3; i++) {
		vec.push_back(rand() % 100);
	}
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;
	cout << endl;
	vector::iterator it = find_if(vec.begin(), vec.end(), Greater());
	if (it == vec.end()) {
		cout << "less than 50" << endl;
	}
	else {
		cout << "greater than 50" << endl;
	}
	//自定义数据类型查找
	vector vec1;
	person p1("zhinen", 22);
	person p2("aaa", 12);
	person p3("ggg", 34);
	person p4("eee", 54);
	person p5("kkk", 23);
	vec1.push_back(p1);
	vec1.push_back(p2);
	vec1.push_back(p3);
	vec1.push_back(p4);
	vec1.push_back(p5);
	person p("kkkk", 23);
	vector::iterator iter = find_if(vec1.begin(), vec1.end(), Greater1());
	if (iter == vec1.end()) {
		cout << "not found" << endl;
	}
	else {
		cout << "find it" << endl;
		cout << iter->name << " " << iter->age << endl;
	}
	return 0;
}

4.2.3 adjacent_find

函数原型：adjacent_find(iterator beg, iterator end);：查找相邻重复元素，返回相邻元素的第一个元素的迭代器，beg开始迭代器，end结束迭代器。

#include
#include
#include
#include
#include
#include
using namespace std;
void _func(int val) {
	cout << val << " ";
}
int main() {
	//内置函数类型查找
	vector vec;
	srand((unsigned)time(NULL));
	for (int i = 0; i < 50; i++) {
		vec.push_back(rand() % 100);
	}
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;
	cout << endl;
	vector::iterator it = adjacent_find(vec.begin(), vec.end());
	if (it == vec.end()) {
		cout << "not found" << endl;
	}
	else {
		cout << "find it:" << *it << endl;
	}
	return 0;
}

4.2.4 binary_search

查找指定元素是否存在。
函数原型：binary_search(iterator beg, iterator end, value);：查找指定的元素，查到返回true，否则返回false，beg开始迭代器，end结束迭代器，value查找的元素。
注意：在无序序列中不可用，而且必须是从小到大排序

#include
#include
#include
#include
#include
#include
using namespace std;
void _func(int val) {
	cout << val << " ";
}
int main() {
	//内置函数类型查找
	vector vec;
	srand((unsigned)time(NULL));
	for (int i = 0; i < 20; i++) {
		vec.push_back(rand() % 100);
	}
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;
	sort(vec.begin(), vec.end());
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;
	bool ret = binary_search(vec.begin(), vec.end(), 50);
	if (ret) {
		cout << "find it" << endl;
	}
	else {
		cout << "not found" << endl;
	}
	return 0;
}

4.2.5 count

统计元素个数
函数原型：count(iterator beg, iterator end, value);：统计元素出现的次数，beg开始迭代器，end结束迭代器，value统计的元素。

#include
#include
#include
#include
#include
#include
using namespace std;
void _func(int val) {
	cout << val << " ";
}
class person {
public:
	person(string name, int age) {
		this->name = name;
		this->age = age;
	}
	bool operator==(const person& p) {
		return this->age == p.age;
	}
	string name;
	int age;
};
int main() {
	//内置函数类型统计
	vector vec;
	srand((unsigned)time(NULL));
	for (int i = 0; i < 100; i++) {
		vec.push_back(rand() % 100);
	}
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;
	int num = count(vec.begin(), vec.end(), 50);
	cout << num << endl << endl;
	//自定义类型统计
	vector vec1;
	person p1("zhinen", 22);
	person p2("aaa", 12);
	person p3("bbb", 22);
	person p4("eee", 54);
	person p5("kkk", 22);
	vec1.push_back(p1);
	vec1.push_back(p2);
	vec1.push_back(p3);
	vec1.push_back(p4);
	vec1.push_back(p5);
	person p("alice", 22);
	//统计年龄相同的人，重载==
	num = count(vec1.begin(), vec1.end(), p);
	cout << num << endl << endl;
	return 0;
}

4.2.5 count_if

按条件统计元素个数
函数原型：count_if(iterator beg, iterator end, _pred);：按条件统计元素出现的次数，beg开始迭代器，end结束迭代器，_pred谓词。

#include
#include
#include
#include
#include
#include
using namespace std;
void _func(int val) {
	cout << val << " ";
}
class person {
public:
	person(string name, int age) {
		this->name = name;
		this->age = age;
	}
	bool operator==(const person& p) {
		return this->age == p.age;
	}
	string name;
	int age;
};
class Greater {
public:
	bool operator()(int val) {
		return val > 50;
	}
};
class Greater1 {
public:
	bool operator()(const person& val) {
		return val.age>20;
	}
};
int main() {
	//内置函数类型统计
	vector vec;
	srand((unsigned)time(NULL));
	for (int i = 0; i < 20; i++) {
		vec.push_back(rand() % 100);
	}
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;
	int num = count_if(vec.begin(), vec.end(), Greater());
	cout << num << endl << endl;
	//自定义类型统计
	vector vec1;
	person p1("zhinen", 22);
	person p2("aaa", 12);
	person p3("bbb", 15);
	person p4("eee", 14);
	person p5("kkk", 34);
	vec1.push_back(p1);
	vec1.push_back(p2);
	vec1.push_back(p3);
	vec1.push_back(p4);
	vec1.push_back(p5);
	num = count_if(vec1.begin(), vec1.end(), Greater1());
	cout << num << endl << endl;
	return 0;
}

4.3 常用排序算法 4.3.1 sort

对容器内的元素进行排序
函数原型：sort(iterator beg, iterator end, _pred);：beg开始迭代器，end结束迭代器，_pred谓词。

#include
#include
#include
#include
#include
#include
using namespace std;
void _func(int val) {
	cout << val << " ";
}
class Greater {
public:
	bool operator()(int val1,int val2) {
		return val1>val2;
	}
};
int main() {
	vector vec;
	srand((unsigned)time(NULL));
	for (int i = 0; i < 20; i++) {
		vec.push_back(rand() % 100);
	}
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;
	//从小到大
	sort(vec.begin(), vec.end());
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;
	//从大到小
	sort(vec.begin(), vec.end(),Greater());//仿函数
	//==sort(vec.begin(), vec.end(),greater<>());//内建函数
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;
	return 0;
}

4.3.2 random_shuffle

洗牌，指定范围内的元素随机调整次序。
函数原型：random_shuffle(iterator beg, iterator end);：beg开始迭代器，end结束迭代器。

#include
#include
#include
#include
#include
#include
using namespace std;
void _func(int val) {
	cout << val << " ";
}
int main() {
	vector vec;
	srand((unsigned)time(NULL));
	for (int i = 0; i < 20; i++) {
		vec.push_back(rand() % 100);
	}
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;
	random_shuffle(vec.begin(), vec.end());
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;
	return 0;
}

4.3.3 merge

两个容器合并，并存储到另一个容器中，合并后还是有序的
函数原型：merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);：beg1容器1开始迭代器，end1容器1结束迭代器，beg2容器2开始迭代器，end2容器2结束迭代器，dest目标容器开始迭代器。
注意：两个容器必须是有序的

#include
#include
#include
#include
#include
#include
using namespace std;
void _func(int val) {
	cout << val << " ";
}
int main() {
	vector vec,vec1;
	srand((unsigned)time(NULL));
	for (int i = 0; i < 10; i++) {
		vec.push_back(rand() % 100);
	}
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;
	sort(vec.begin(), vec.end());
	for_each(vec.begin(), vec.end(), _func);
	cout << endl << endl;
	for (int i = 0; i < 10; i++) {
		vec1.push_back(rand() % 100);
	}
	for_each(vec1.begin(), vec1.end(), _func);
	cout << endl;
	sort(vec1.begin(), vec1.end());
	for_each(vec1.begin(), vec1.end(), _func);
	cout << endl << endl;
	//目标容器
	vector res;
	res.resize(vec.size() + vec1.size());
	merge(vec.begin(), vec.end(), vec1.begin(), vec1.end(), res.begin());
	for_each(res.begin(), res.end(), _func);
	cout << endl;
	return 0;
}

4.3.4 reverse

将容器内元素进行反转。
函数原型：reverse(iterator beg, iterator end);：反转指定范围的元素。beg开始迭代器，end结束迭代器。

#include
#include
#include
#include
#include
#include
using namespace std;
void _func(int val) {
	cout << val << " ";
}
int main() {
	vector vec;
	srand((unsigned)time(NULL));
	for (int i = 0; i < 10; i++) {
		vec.push_back(rand() % 100);
	}
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;
	reverse(vec.begin(), vec.end());
	for_each(vec.begin(), vec.end(), _func);
	cout << endl << endl;
	return 0;
}

4.4 常用拷贝和替换算法 4.4.1 copy

容器内指定范围的元素拷贝到另一容器中
函数原型：copy(iterator beg, iterator end, iterator dest);：beg开始迭代器，end结束迭代器，dest目标起始迭代器。

#include
#include
#include
#include
#include
#include
using namespace std;
void _func(int val) {
	cout << val << " ";
}
int main() {
	vector vec, vec1;
	srand((unsigned)time(NULL));
	for (int i = 0; i < 10; i++) {
		vec.push_back(rand() % 100);
	}
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;
	//目标容器需提前开辟空间
	vec1.resize(vec.size());
	copy(vec.begin(), vec.end(),vec1.begin());
	for_each(vec1.begin(), vec1.end(), _func);
	cout << endl;
	return 0;
}

4.4.2 replace

将容器内指定范围的旧元素改为新元素。
函数原型：replace(iterator beg, iterator end, oldvalue, newvalue);：beg开始迭代器，end结束迭代器，oldvalue旧元素，newvalue新元素。

#include
#include
#include
#include
#include
#include
using namespace std;
void _func(int val) {
	cout << val << " ";
}
int main() {
	vector vec;
	srand((unsigned)time(NULL));
	for (int i = 0; i < 100; i++) {
		vec.push_back(rand() % 100);
	}
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;

	replace(vec.begin(), vec.end(), 50, 1000);//将值50改为1000
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;
	return 0;
}

4.4.2 replace_if

将区间内满足条件的元素，替换成指定元素。
函数原型：replace_if(iterator beg, iterator end, _pred, newvalue);：beg开始迭代器，end结束迭代器，_pred谓词，newvalue新元素。

#include
#include
#include
#include
#include
#include
using namespace std;
void _func(int val) {
	cout << val << " ";
}
class Greater {
public:
	bool operator()(int val) {
		return val > 50;
	}
};
int main() {
	vector vec;
	srand((unsigned)time(NULL));
	for (int i = 0; i < 20; i++) {
		vec.push_back(rand() % 100);
	}
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;

	replace_if(vec.begin(), vec.end(), Greater(), 1000);//将值大于50改为1000
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;
	return 0;
}

4.4.2 swap

互换两个容器的元素
函数原型：swap(container c1, container c2);：c1容器1，c2容器2。

#include
#include
#include
#include
#include
#include
using namespace std;
void _func(int val) {
	cout << val << " ";
}
int main() {
	vector vec, vec1;
	srand((unsigned)time(NULL));
	for (int i = 0; i < 20; i++) {
		vec.push_back(rand() % 100);
	}
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;
	for (int i = 0; i < 20; i++) {
		vec1.push_back(rand() % 100);
	}
	for_each(vec1.begin(), vec1.end(), _func);
	cout << endl;
	cout << endl;

	swap(vec, vec1);
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;
	for_each(vec1.begin(), vec1.end(), _func);
	cout << endl;
	return 0;
}

4.5 常用算术生成算法

算术生成算法属于小型算法，使用时包含的头文件为#include

4.5.1 accumulate

计算区间内，容器元素累计总和。
函数原型：accumulate(iterator beg, iterator end, value);：beg开始迭代器，end结束迭代器，value起始值。

#include
#include
#include
#include
#include
#include
using namespace std;
void _func(int val) {
	cout << val << " ";
}
int main() {
	vector vec;
	srand((unsigned)time(NULL));
	for (int i = 0; i < 100; i++) {
		vec.push_back(rand() % 100);
	}
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;
	int sum = accumulate(vec.begin(), vec.end(), 0);
	cout << sum << endl;
	return 0;
}

4.5.1 fill

向容器中填充指定的元素。
函数原型：fill(iterator beg, iterator end, value);：beg开始迭代器，end结束迭代器，value起始值。

#include
#include
#include
#include
#include
#include
using namespace std;
void _func(int val) {
	cout << val << " ";
}
int main() {
	vector vec;
	srand((unsigned)time(NULL));
	for (int i = 0; i < 10; i++) {
		vec.push_back(rand() % 100);
	}
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;
	fill(vec.begin(), vec.end(), 1000);
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;
	return 0;
}

4.6 常用的集合算法 4.6.1 set_intersection

求两个容器的交集。
函数原型：set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);：beg1容器1开始迭代器，end1容器1结束迭代器，beg2容器2开始迭代器，end2容器2结束迭代器，dest目标容器开始迭代器。
注意：两个序列必须是有序的序列

#include
#include
#include
#include
#include
#include
#include
using namespace std;
void _func(int val) {
	cout << val << " "; 
}
int main() {
	vector vec, vec1, res;
	srand((unsigned)time(NULL));
	for (int i = 0; i < 20; i++) {
		vec.push_back(rand() % 100);
	}
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;
	sort(vec.begin(), vec.end());
	for_each(vec.begin(), vec.end(), _func);
	cout << endl << endl;

	for (int i = 0; i < 20; i++) {
		vec1.push_back(rand() % 100);
	}
	for_each(vec1.begin(), vec1.end(), _func);
	cout << endl;
	sort(vec1.begin(), vec1.end());
	for_each(vec1.begin(), vec1.end(), _func);
	cout << endl << endl;

	//需要提前开辟空间
	res.resize(min(vec.size(), vec1.size()));
	vector::iterator it=set_intersection(vec.begin(), vec.end(), vec1.begin(), vec1.end(), res.begin());
	for_each(res.begin(), it, _func);
	cout << endl;
	return 0;
}

4.6.2 set_union

求两个容器的并集。
函数原型：set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);：beg1容器1开始迭代器，end1容器1结束迭代器，beg2容器2开始迭代器，end2容器2结束迭代器，dest目标容器开始迭代器。
注意：两个序列必须是有序的序列

#include
#include
#include
#include
#include
#include
using namespace std;
void _func(int val) {
	cout << val << " "; 
}
int main() {
	vector vec, vec1, res;
	srand((unsigned)time(NULL));
	for (int i = 0; i < 20; i++) {
		vec.push_back(rand() % 100);
	}
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;
	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());//去除相同的元素
	for_each(vec.begin(), vec.end(), _func);
	cout << endl << endl;

	for (int i = 0; i < 20; i++) {
		vec1.push_back(rand() % 100);
	}
	for_each(vec1.begin(), vec1.end(), _func);
	cout << endl;
	sort(vec1.begin(), vec1.end());
	vec1.erase(unique(vec1.begin(), vec1.end()), vec1.end());
	for_each(vec1.begin(), vec1.end(), _func);
	cout << endl << endl;

	//需要提前开辟空间
	res.resize(vec.size() + vec1.size());
	vector::iterator it=set_union(vec.begin(), vec.end(), vec1.begin(), vec1.end(), res.begin());
	for_each(res.begin(), it, _func);
	cout << endl;
	return 0;
}

4.6.3 set_difference

求两个容器的差集。
函数原型：set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);：beg1容器1开始迭代器，end1容器1结束迭代器，beg2容器2开始迭代器，end2容器2结束迭代器，dest目标容器开始迭代器。
注意：两个序列必须是有序的序列

#include
#include
#include
#include
#include
#include
using namespace std;
void _func(int val) {
	cout << val << " "; 
}
int main() {
	vector vec, vec1, res;
	srand((unsigned)time(NULL));
	for (int i = 0; i < 20; i++) {
		vec.push_back(rand() % 100);
	}
	for_each(vec.begin(), vec.end(), _func);
	cout << endl;
	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());//去除相同的元素
	for_each(vec.begin(), vec.end(), _func);
	cout << endl << endl;

	for (int i = 0; i < 20; i++) {
		vec1.push_back(rand() % 100);
	}
	for_each(vec1.begin(), vec1.end(), _func);
	cout << endl;
	sort(vec1.begin(), vec1.end());
	vec1.erase(unique(vec1.begin(), vec1.end()), vec1.end());
	for_each(vec1.begin(), vec1.end(), _func);
	cout << endl << endl;

	//需要提前开辟空间
	res.resize(max(vec.size(), vec1.size()));
	vector::iterator it=set_difference(vec.begin(), vec.end(), vec1.begin(), vec1.end(), res.begin());
	cout << "vec和vec1的差集：";
	for_each(res.begin(), it, _func);
	cout << endl;
	res.clear();
	res.resize(max(vec.size(), vec1.size()));
	vector::iterator iter = set_difference(vec1.begin(), vec1.end(), vec.begin(), vec.end(), res.begin());
	cout << "vec1和vec的差集：";
	for_each(res.begin(), iter, _func);
	cout << endl;
	return 0;
}