[C++知识库]C++中的STL

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<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void print(int val) {
	cout << val << " ";
}
int main() {
	//创建
	vector<int> vec;
	//插入数据
	vec.push_back(1);
	vec.push_back(2);
	vec.push_back(3);
	vec.push_back(4);
	vec.push_back(5);
	//通过迭代器访问
	vector<int>::iterator iter = vec.begin();//起始迭代器 执行容器中第一个元素
	vector<int>::iterator iterend = vec.end();//结束迭代器 指向容器最后一个元素的下一个位置
	//第一种遍历
	while (iter != iterend) {
		cout << *iter << " ";
		iter++;
	}
	cout << endl;
	//第二种遍历
	for (vector<int>::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<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
class person {
public:
	person(string name, int age) {
		this->name = name;
		this->age = age;
	}
	string name;
	int age;
};
int main() {
	vector<person> 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<person>::iterator it = vec.begin(); it != vec.end(); it++) {
		cout << (*it).name << " " << (*it).age << endl;
	}
	for (vector<person>::iterator it = vec.begin(); it != vec.end(); it++) {
		cout << it->name << " " << it->age << endl;
	}
	cout << endl;
	//存放自定义类型的指针
	vector<person*> 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<person*>::iterator it = vec1.begin(); it != vec1.end(); it++) {
		cout << (*it)->name << " " << (*it)->age << endl;
	}
	return 0;
}

1.5.3 vector容器嵌套容器

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
	vector<vector<int>> vec;
	//创建小容器
	vector<int> vec1;
	vector<int> vec2;
	vector<int> vec3;
	vector<int> 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<vector<int>>::iterator it = vec.begin(); it != vec.end(); it++) {
		for (vector<int>::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<iostream>
#include<string>
#include<algorithm>
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<iostream>
#include<string>
#include<algorithm>
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<iostream>
#include<string>
#include<algorithm>
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<iostream>
#include<string>
#include<algorithm>
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<iostream>
#include<string>
#include<algorithm>
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<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void print(vector<int> &vec) {
	for (int i = 0; i < vec.size(); i++) {
		cout << vec[i] << " ";
	}
	cout << endl;
}
int main() {
	//默认构造，无参构造
	vector<int> vec1;
	for (int i = 1; i <= 10; i++) {
		vec1.push_back(i);
	}
	print(vec1);
	//区间的方式进行构造
	vector<int> vec2(vec1.begin(), vec1.end());
	print(vec2);

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

2.2.3 vector赋值操作

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

	vector<int> 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<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void print(vector<int> &vec) {
	for (int i = 0; i < vec.size(); i++) {
		cout << vec[i] << " ";
	}
	cout << endl;
}
int main() {
	vector<int> 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<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void print(vector<int> &vec) {
	for (int i = 0; i < vec.size(); i++) {
		cout << vec[i] << " ";
	}
	cout << endl;
}
int main() {
	vector<int> 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<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void print(vector<int> &vec) {
	for (int i = 0; i < vec.size(); i++) {
		cout << vec[i] << " ";
	}
	cout << endl;
}
int main() {
	vector<int> vec;
	for (int i = 1; i < 10; i++) {
		vec.push_back(i * i);
	}
	print(vec);
	vector<int> 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<int> 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<int>(v).swap(v);
	cout << v.capacity() << endl;
	cout << v.size() << endl;
	return 0;
}

2.2.7 vector预留空间

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

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

2.3.3 deque赋值操作

#include<iostream>
#include<deque>
using namespace std;
void print(const deque<int> &d) {
	//设置容器里面的数据不可以修改
	for (deque<int>::const_iterator it = d.begin(); it != d.end();it++) {
		cout << *it << " ";
	}
	cout << endl;
}
int main() {
	deque<int> d1;
	for (int i = 1; i < 10; i++) {
		d1.push_back(i * i);
	}
	print(d1);
	//operator=赋值
	deque<int> d2;
	d2 = d1;
	print(d2);
	//assign
	deque<int> d3;
	d3.assign(d1.begin(), d1.end());
	print(d3);
	//
	deque<int> 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<iostream>
#include<deque>
using namespace std;
void print(const deque<int> &d) {
	//设置容器里面的数据不可以修改
	for (deque<int>::const_iterator it = d.begin(); it != d.end();it++) {
		cout << *it << " ";
	}
	cout << endl;
}
int main() {
	deque<int> 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<iostream>
#include<deque>
using namespace std;
void print(const deque<int> &d) {
	//设置容器里面的数据不可以修改
	for (deque<int>::const_iterator it = d.begin(); it != d.end();it++) {
		cout << *it << " ";
	}
	cout << endl;
}
int main() {
	deque<int> 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<int> 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<iostream>
#include<deque>
using namespace std;
void print(const deque<int> &d) {
	//设置容器里面的数据不可以修改
	for (deque<int>::const_iterator it = d.begin(); it != d.end();it++) {
		cout << *it << " ";
	}
	cout << endl;
}
int main() {
	deque<int> 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<iostream>
#include<deque>
#include<algorithm>
using namespace std;
void print(const deque<int> &d) {
	//设置容器里面的数据不可以修改
	for (deque<int>::const_iterator it = d.begin(); it != d.end();it++) {
		cout << *it << " ";
	}
	cout << endl;
}
int main() {
	deque<int> 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<iostream>
#include<stack>
using namespace std;
int main() {
	stack<int> 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<iostream>
#include<list>
using namespace std;
void print(const list<int>& l) {
	for (list<int>::const_iterator it = l.begin(); it != l.end(); it++) {
		cout << (*it) << " ";
	}
	cout << endl;
}
int main() {
	//创建list容器
	list<int> li;//默认构造
	//添加数据
	li.push_back(1);
	li.push_back(2);
	li.push_back(3);
	li.push_back(4);
	li.push_back(5);
	//遍历容器
	print(li);
	//区间的方式构造
	list<int> li1(li.begin(), li.end());
	print(li1);
	//拷贝构造
	list<int> li2(li);
	print(li2);
	//n个elem
	list<int> li3(10,1000000);
	print(li3);
	return 0;
}

2.6.3 list赋值和交换

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

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

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

2.6.4 list大小操作

#include<iostream>
#include<list>
using namespace std;
void print(const list<int>& l) {
	for (list<int>::const_iterator it = l.begin(); it != l.end(); it++) {
		cout << (*it) << " ";
	}
	cout << endl;
}
int main() {
	//创建list容器
	list<int> 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<iostream>
#include<list>
using namespace std;
void print(const list<int>& l) {
	for (list<int>::const_iterator it = l.begin(); it != l.end(); it++) {
		cout << (*it) << " ";
	}
	cout << endl;
}
int main() {
	//创建list容器
	list<int> 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<int>::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<iostream>
#include<list>
using namespace std;
void print(const list<int>& l) {
	for (list<int>::const_iterator it = l.begin(); it != l.end(); it++) {
		cout << (*it) << " ";
	}
	cout << endl;
}
int main() {
	//创建list容器
	list<int> 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<iostream>
#include<list>
#include<algorithm>
using namespace std;
void print(const list<int>& l) {
	for (list<int>::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<int> 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<iostream>
#include<set>
using namespace std;
void print(const set<int> &s) {
	for (set<int>::const_iterator it = s.begin(); it != s.end();it++) {
		cout << *it << " ";
	}
	cout << endl;
}
int main() {
	set<int> 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<int> s1(s);
	print(s1);
	set<int> s2;
	s2 = s;
	print(s1);
	return 0;
}

2.7.3 set大小和交换

#include<iostream>
#include<set>
using namespace std;
void print(const set<int> &s) {
	for (set<int>::const_iterator it = s.begin(); it != s.end();it++) {
		cout << *it << " ";
	}
	cout << endl;
}
int main() {
	set<int> 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<int> 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<iostream>
#include<set>
using namespace std;
void print(const set<int> &s) {
	for (set<int>::const_iterator it = s.begin(); it != s.end();it++) {
		cout << *it << " ";
	}
	cout << endl;
}
int main() {
	set<int> 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<iostream>
#include<set>
using namespace std;
void print(const set<int> &s) {
	for (set<int>::const_iterator it = s.begin(); it != s.end();it++) {
		cout << *it << " ";
	}
	cout << endl;
}
int main() {
	set<int> 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<int>::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<iostream>
#include<set>
using namespace std;
void print(const set<int> &s) {
	for (set<int>::const_iterator it = s.begin(); it != s.end();it++) {
		cout << *it << " ";
	}
	cout << endl;
}
int main() {
	set<int> s;
	//插入
	pair<set<int>::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<int> ms;
	ms.insert(12);
	ms.insert(12);
	ms.insert(12);
	ms.insert(12);
	ms.insert(1);
	for (multiset<int>::iterator it = ms.begin(); it != ms.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
 	return 0;
}

2.7.7 pair对组创建

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

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

2.7.8 set容器排序

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

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

set存放自定义数据类型：

#include<iostream>
#include<set>
#include<string>
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<person,Compare> 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<person,Compare>::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<iostream>
#include<map>
#include<string>
using namespace std;
void print(const map<int,int>& m) {
	for (map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) {
		cout << it->first << " " << it->second << endl;
	}
	cout << endl;
}
int main() {
	map<int, int> m;
	m.insert(pair<int, int>(1, 10));
	m.insert(pair<int, int>(5, 50));
	m.insert(pair<int, int>(6, 60));
	m.insert(pair<int, int>(3, 30));
	m.insert(pair<int, int>(5, 90));
	print(m);
	//拷贝构造
	map<int, int> m1(m);
	print(m1);
	//赋值
	map<int, int> m2;
	m2 = m;
	print(m2);
	return 0;
}

2.8.3 map大小和交换

#include<iostream>
#include<map>
using namespace std;
void print(const map<int,int>& m) {
	for (map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) {
		cout << it->first << " " << it->second << endl;
	}
	cout << endl;
}
int main() {
	map<int, int> m;
	m.insert(pair<int, int>(1, 10));
	m.insert(pair<int, int>(5, 50));
	m.insert(pair<int, int>(6, 60));
	m.insert(pair<int, int>(3, 30));
	m.insert(pair<int, int>(5, 90));
	if (m.empty()) {
		cout << "empty" << endl;
	}
	else {
		cout << "not empty" << endl;
		cout << "size=" << m.size() << endl;
		print(m);
	}
	map<int, int> m1;
	m1.insert(pair<int, int>(8, 80));
	m1.insert(pair<int, int>(1, 10));
	m1.insert(pair<int, int>(5, 50));
	print(m1);
	cout << "exchange:" << endl;
	m1.swap(m);
	print(m1);
	return 0;
}

2.8.4 map插入和删除

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

#include<iostream>
#include<map>
using namespace std;
void print(const map<int,int>& m) {
	for (map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) {
		cout << it->first << " " << it->second << endl;
	}
	cout << endl;
}
int main() {
	map<int, int> m;
	//插入
	//第一种
	m.insert(pair<int, int>(1, 10));
	m.insert(pair<int, int>(5, 50));
	m.insert(pair<int, int>(6, 60));
	m.insert(pair<int, int>(3, 30));
	print(m);
	//第二种
	m.insert(make_pair(2, 230));
	print(m);
	//第三种
	m.insert(map<int, int>::value_type(7, 70));
	print(m);
	//第四种
	m[9] = 90;
	print(m);

	//删除
	m.erase(m.begin());
	print(m);
	m.erase(9);//按照key值删除
	print(m);
	m.clear();//==m.erase(m.begin(), m.end());
	print(m);
	return 0;
}

2.8.5 map查找和统计

#include<iostream>
#include<map>
using namespace std;
void print(const map<int,int>& m) {
	for (map<int, int>::const_iterator it = m.begin(); it != m.end(); it++) {
		cout << it->first << " " << it->second << endl;
	}
	cout << endl;
}
int main() {
	map<int, int> m;
	m.insert(pair<int, int>(1, 10));
	m.insert(pair<int, int>(5, 50));
	m.insert(pair<int, int>(5, 60));
	m.insert(pair<int, int>(3, 30));
	print(m);
	map<int, int>::iterator it = m.find(5);
	if (it != m.end()) {
		cout << "find it: " << it->first << " " << it->second << endl;
	}
	else {
		cout << "not found" << endl;
	}
	int num = m.count(5);//要么为1，要么为0。不允许有重复的元素，multimap可能大于1
	cout << num << endl;
	return 0;
}

2.8.6 map容器排序

#include<iostream>
#include<map>
using namespace std;
class Compare {
public:
	bool operator()(int a,int b) const {
		return a > b;
	}
};
int main() {
	map<int, int,Compare> m;
	m.insert(pair<int, int>(1, 10));
	m.insert(pair<int, int>(5, 50));
	m.insert(pair<int, int>(5, 60));
	m.insert(pair<int, int>(3, 30));
	m.insert(pair<int, int>(6, 60));
	m.insert(pair<int, int>(4, 30));
	for (map<int, int, Compare>::iterator it = m.begin(); it != m.end(); it++) {
		cout << it->first << " " << it->second << endl;
	}
	cout << endl;
	return 0;
}

3. STL-函数对象

3.1 函数对象

3.1.1 函数对象的概念

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

3.1.2 函数对象的使用

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

#include<iostream>
#include<map>
#include<string>
using namespace std;
//1）在使用时，可以像普通函数那样调用，可以有参数、可以有返回值。
class Add {
public:
	int operator()(int a,int b) {
		return a + b;
	}
};
//2）函数对象超出普通函数的概念，函数对象可以有自己的状态
class print {
public:
	print():count(0) {
	}
	void operator()(string str) {
		cout << str << endl;
		count++;
	}
	int count;
};
//3）函数对象可以作为参数传递。
void fun(print &pr, string str) {
	pr(str);
}
int main() {
	Add a;
	int num = a(10, 10);
	cout << num << endl;
	print pr;
	pr("zhinen");
	cout << "number of calls: " << pr.count << endl;
	fun(pr, "XDer");
	return 0;
}

3.2 谓词

3.2.1 谓词的概念

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

3.2.2 一元谓词

#include<iostream>
#include<algorithm>
#include<vector>
#include<ctime>
#include<cstdlib>
using namespace std;
class findnumber {
public:
	bool operator()(int val) {
		return val > 90;
	}
};
int main() {
	vector<int> vec;
	srand((unsigned)time(NULL));
	for (int i = 0; i < 10; i++) {
		vec.push_back(rand() % 100);
	}
	//查找容器中有没有大于90的数字；
	//findnumber()匿名函数对象
	vector<int>::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<iostream>
#include<algorithm>
#include<vector>
#include<ctime>
#include<cstdlib>
using namespace std;
class Compare {
public:
	bool operator()(int val1,int val2) {
		return val1>val2;
	}
};
int main() {
	vector<int> 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<functional>

3.3.2 算术仿函数

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

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

3.3.3 关系仿函数

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

#include<iostream>
#include<algorithm>
#include<vector>
#include<ctime>
#include<cstdlib>
using namespace std;
class Compare {
public:
	bool operator()(int v1,int v2) {
		return v1 > v2;
	}
};
int main() {
	vector<int> 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<int>());//内建的函数类型
	//==sort(vec.begin(), vec.end(), Compare());
	for (int i = 0; i < 10; i++) {
		cout << vec[i] << " ";
	}
	cout << endl;
	return 0;
}

3.3.4 逻辑仿函数

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

#include<iostream>
#include<algorithm>
#include<vector>
#include<ctime>
#include<cstdlib>
#include<functional>
using namespace std;
int main() {
	vector<bool> 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<bool> 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;
}