本阶段主要针对C++泛型编程和STL技术做详细讲解，探讨C++更深层的使用。

STL（Standard Template Library，标准模板库）是 C++ 标准库的一部分，也是 C++ 中非常重要的一个技术。它是由 Alexander Stepanov 和 Meng Lee 于 1994 年开发的，旨在提供一组通用的、高效的数据结构和算法，能够满足大多数程序的需求。

STL 技术的核心是模板（template）和泛型编程（generic programming）。模板是一种 C++ 语言特性，可以让程序员编写通用的代码，而不用为不同的类型分别编写不同的代码。泛型编程则是一种编程理念，强调代码的通用性和复用性，通过使用模板来实现。

STL 中提供了多种容器（container）和算法（algorithm），容器是一种用于存储数据的对象，包括 vector、list、set、map 等；算法则是一些用于对容器中的数据进行操作的函数，包括排序、查找、遍历等。

此外，STL 还提供了迭代器（iterator）、函数对象（function object）和适配器（adapter）等辅助组件，帮助程序员更方便地使用容器和算法。

STL 技术的优点包括：

• 代码通用且重用性高，可以大大提高开发效率；
• STL 中的容器和算法都经过了充分测试和优化，具有高效性和可靠性；
• STL 技术为 C++ 中的面向对象编程和泛型编程提供了支持，使得程序设计更加灵活和可扩展。

因此，STL 技术已经成为了 C++ 程序员必备的技能之一，广泛应用于各种领域的软件开发中。

1. 模板

1.1 模板的概念

在 C++ 中，模板（template）是一种通用的代码结构，可以用于生成特定类型或值的代码。通过模板，程序员可以编写一次代码，然后使用不同的数据类型或值来实例化该模板，生成不同的代码实例。这种方式被称为泛型编程（generic programming），它可以提高代码的可重用性和通用性。

generic: 英[dʒəˈnerɪk] 美[dʒəˈnerɪk]
adj. 通用的; 一般的; 普通的; 无厂家商标的; 无商标的;

模板就是建立通用的模具，大大提高复用性。

例如生活中的模板：一寸照片模板、PPT模板。

模板的特点：

• 模板不可以直接使用，它只是一个框架
• 模板的通用并不是万能的

1.2 函数模板

• C++另一种编程思想称为泛型编程（generic programming），主要利用的技术就是模板。
• C++提供两种模板机制：①函数模板和②类模板

1.2.1 函数模板语法

函数模板作用：建立一个通用函数，其函数返回值类型和形参类型可以不具体制定，用一个虚拟的类型来代表。

语法：

template<typename T>
函数的声明或定义

解释：

• template —— 声明创建模板
• typename —— 表面其后面的符号是一种数据类型，可以用class代替
• T —— 通用的数据类型，名称可以替换，通常为大写字母T(Template)。

可以换别的名称，但一般用T比较清晰明了

总结：

• 函数模板利用关键字template
• 使用函数模板有两种方式：
  1. 自动类型推导：函数名() —— swap_fn(a, b);
  2. 显示指定类型：函数名<指定数据类型>() —— swap_fn<int>(a, b);
• 模板的目的是为了提高复用性，将类型参数化

#include <iostream>
using namespace std;


// 函数模板


// [传统方法]交互两个整型函数
void swap_int(int& a, int& b) {
	int tmp = a;
	a = b;
	b = tmp;
}


// [传统方法]交换两个浮点型函数
void swap_double(double& a, double& b) {
	double tmp = a;
	a = b;
	b = tmp;
}


void test01_01() {
	int a = 10;
	int b = 20;
	swap_int(a, b);
	cout << "a: " << a << "\tb: " << b << endl;  // a: 20   b: 10

	double c = 1.1;
	double d = 2.2;
	swap_double(c, d);
	cout << "c: " << c << "\td: " << d << endl;  // c: 2.2  d: 1.1
}


/*
	我们可以发现，如果我们想把所有的数据类型都写完，要写好久。
	如果还有自定义数据类型，那就需要随时再写交换函数，这样太麻烦了。

	我们看上面写的两个交互代码，其实可以发现，两个函数很像，不同点：
		1. 函数名不同
		2. 参数的数据类型不一样
	剩下的都一样，所以我们使用模板来实现各种数据类型的交换。
*/


// 函数模板
template<typename T>  // 声明一个模板，告诉编译器，后面代码中紧跟着的T不要报错。T是一个通用的数据类型
void swap_fn(T& a, T& b) {
	T tmp = a;
	a = b;
	b = tmp;
}


void test01_02() {
	/*
		利用函数模板实现交换，有两种使用方式：
			1. 自动类型推导：函数名()
			2. 显示指定类型：函数名<指定数据类型>()
	*/
	int a = 10;
	int b = 20;

	// 1. 自动类型推导
	swap_fn(a, b);
	cout << "a: " << a << "\tb: " << b << endl;  // a: 20   b: 10

	// 2. 显示指定类型
	swap_fn<int>(a, b);  // <T>直接指明T的数据类型
	cout << "a: " << a << "\tb: " << b << endl;  // a: 10   b: 20
}


int main() {

	test01_01();

	test01_02();

	system("pause");
	return 0;
}

1.2.2 函数模板注意事项

注意事项：

• 自动类型推导，必须推导出一致的数据类型T，才可以使用
• 模板必须要确定出T的数据类型，才可以使用

示例：

#include <iostream>
using namespace std;


/*
	函数模板注意事项:
		1. 自动类型推导，必须推导出一致的数据类型T才可以使用
		2. 模板必须要确定出T的数据类型，才可以使用
*/


template<typename T>  // typename可以替换成class（效果是一样的）
void swap_02(T& a, T& b) {
	T tmp = a;
	a = b;
	b = tmp;
}


void test02_01() {
	int a = 10;
	int b = 20;
	float c = 1.1f;

	// 1. 自动类型推导，必须推导出一致的数据类型T才可以使用

	swap_02(a, b);  // a和b的数据类型一致，没问题

	// swap_02(a, c);  // Error: 没有与参数列表匹配的函数模板"swap_02"实例
	// 推导不出一致的数据类型
}

// 2. 模板必须要确定出T的数据类型，才可以使用
template<class T>
void func() {
	cout << "func函数的调用" << endl;
}

void test02_02() {
	// 2. 模板必须要确定出T的数据类型，才可以使用

	// func();  // 没有与参数列表匹配的函数模板"func"实例

	// 这种情况下，要想成功调用，只能在调用的时候指定数据类型
	func<int>();  // 随便给它一个数据类型就可以正常调用了
}


int main() {

	test02_01();

	test02_02();

	system("pause");
	return 0;
}

总结：使用模板时必须确定出通用数据类型T，并且能够推导出一致的类型。

1.2. 3函数模板案例

案例描述：

利用函数模板封装一个排序的函数，可以对不同数据类型数组进行排序。排序规则从大到小，排序算法为选择排序。

分别利用char数组和int数组进行测试。

示例：

#include <iostream>
using namespace std;


/*
	实现通用 对数组进行排序的函数
	规则：从大到小
	算法：选择排序
	测试：char数组、int数组
*/


// 交换函数模板
template<class T>
void swap_two_element(T& a, T& b) {
	T tmp = a;
	a = b;
	b = tmp;
}


// 利用模板写排序算法
template<class T>
void select_sort(T arr[], int len) {
	/*
	* arr: 数组
	* len: 数组的长度
	*/
	
	for (int i = 0; i < len; i++)
	{
		int max_idx = i;  // 最大值的idx
		for (int j = i + 1; j < len; j++)
		{
			if (arr[max_idx] < arr[j])
			{
				// 更新最大值下标
				max_idx = j;
			}
		}
		if (max_idx != i)
		{
			// 交换元素
			swap_two_element(arr[max_idx], arr[i]);
		}
	}
}


// 打印数组的模板
template<class T>
void print_array(T arr[], int len) {
	for (int i = 0; i < len; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
}


void test03_01() {
	// 测试：char数组
	char char_arr[] = "badcfe";

	int len = sizeof(char_arr) / sizeof(char);
	select_sort(char_arr, len);
	print_array(char_arr, len);  // f e d c b a
}


void test03_02() {
	// 测试：int数组
	int int_arr[] = { 7, 5, 1, 3, 9, 2, 4, 6, 8 };
	int len = sizeof(int_arr) / sizeof(int);

	select_sort(int_arr, len);
	print_array(int_arr, len);  // 9 8 7 6 5 4 3 2 1
}


int main() {

	test03_01();
	test03_02();

	system("pause");
	return 0;
}

1.2.4 普通函数与函数模板的区别

普通函数与函数模板区别：

• 普通函数调用时可以发生自动类型转换(隐式类型转换)
• 函数模板调用时，如果利用自动类型推导，不会发生隐式类型转换
• 如果利用显示指定类型的方式，可以发生隐式类型转换

---

隐式类型转换是指在表达式中自动地将一种类型转换为另一种类型，而无需显式地使用类型转换运算符。例如，将整数类型转换为浮点数类型，或将字符类型转换为整数类型。隐式类型转换可以简化代码编写，但有时也可能导致意外的错误。因此，在进行隐式类型转换时需要格外小心。

下面是一个隐式类型转换的例子：

int a = 10;
double b = a; // 将整数类型a隐式转换为浮点数类型b

在上面的代码中，a是整数类型，b是浮点数类型。当将a赋值给b时，C++会自动将a转换为浮点数类型，这个过程就是隐式类型转换。

---

示例：

#include <iostream>
using namespace std;

/*
	普通函数与函数模板区别：
		1. 普通函数调用时可以发生自动类型转换(隐式类型转换)
		2. 函数模板调用时，如果利用自动类型推导，不会发生隐式类型转换
		3. 如果利用显示指定类型的方式，可以发生隐式类型转换
*/


// 普通函数
int add_fn_01(int a, int b) {
	return a + b;
}


void test04_01() {
	int a = 10;
	int b = 20;

	cout << add_fn_01(a, b) << endl;  // 30

	// 1. 普通函数调用时可以发生自动类型转换(隐式类型转换)
	char c = 'c';  // a -> 97
	cout << add_fn_01(a, c) << endl;  // 109
}


template<class T>
T add_fn_02(T a, T b) {
	return a + b;
}


void test04_02() {
	int a = 10;
	int b = 20;

	// 自动类型推导
	cout << add_fn_02(a, b) << endl;

	char c = 'c';
	// cout << add_fn_02(a, c) << endl;  // 没有与参数列表匹配的函数模板"add fn 02"实例

	// 显式指定类型
	// （告诉编译器不用推导了，都是int类型，不是int类型就强转到int，转不过去再报错！）
	cout << add_fn_02<int>(a, c) << endl;  // 109
}


int main() {

	test04_01();
	test04_02();

	system("pause");
	return 0;
}

总结：建议使用显示指定类型的方式调用函数模板，因为可以自己确定通用类型T。

1.2.5 普通函数与函数模板的调用规则

调用规则如下：

1. 如果函数模板和普通函数都可以实现（函数模板和普通函数是重载关系），优先调用普通函数（即便普通函数是空函数，也会优先调用普通函数）
2. 可以通过空模板参数列表<>来强制调用函数模板
3. 函数模板也可以发生重载
4. 如果函数模板可以产生更好的匹配，优先调用函数模板

总结：既然提供了函数模板，最好就不要提供普通函数，否则容易出现二义性。

---

C++函数重载的条件如下：

1. 函数名称必须相同
2. 函数参数个数不同
3. 或者参数类型不同
4. 或者参数顺序不同

函数的返回类型可以相同也可以不同（不能作为重载的条件！）。

当函数满足以上条件时，可以使用函数重载，也就是在同一作用域内使用同一个函数名定义多个函数。C++编译器会根据调用时传入的参数类型、个数和顺序来区分不同的函数，并选择合适的函数进行调用。函数重载可以提高程序的可读性和可维护性。

---

示例：

#include <iostream>
using namespace std;

/*
	普通函数与函数模板的调用规则
		1. 如果函数模板和普通函数都可以实现，优先调用普通函数
		2. 可以通过空模板参数列表来强制调用函数模板
		3. 函数模板也可以发生重载
		4. 如果函数模板可以产生更好的匹配，优先调用函数模板
*/


void my_print(int a, int b) {
	cout << "调用普通函数" << endl;
}


template<class T>
void my_print(T a, T b) {  // 函数overloading
	cout << "调用函数模板" << endl;
}


// 3. 函数模板也可以发生重载
template<class T>
void my_print(T a, T b, T c) {
	cout << "调用重载的函数模板" << endl;
}


void test05_01() {
	int a = 10;
	int b = 20;

	// 1. 如果函数模板和普通函数都可以实现，优先调用普通函数
	my_print(a, b);

	// 2. 可以通过空模板参数列表来强制调用函数模板
	my_print<>(a, b);  // 调用函数模板

	// 3. 函数模板也可以发生重载
	my_print(a, b, 100);  // 调用重载的函数模板

	// 4. 如果函数模板可以产生更好的匹配，优先调用函数模板
	char c1 = 'a';
	char c2 = 'b';
	my_print(c1, c2);  // 调用函数模板
}


int main() {

	test05_01();  // 调用普通函数

	system("pause");
	return 0;
}

1.2.6 模板的局限性

局限性：

• 模板的通用性并不是万能的

例如：

template<class T>
void f(T a, T b) {
    a = b;
}

在上述代码中提供的赋值操作，如果传入的a和b是一个数组，就无法实现了。

再例如:

template<class T>
void f(T a, T b) {
    if (a > b) {...}
}

在上述代码中，如果T的数据类型传入的是像Person这样的自定义数据类型，也无法正常运行。

因此C++为了解决这种问题，提供模板的重载，可以为这些特定的类型提供具体化的模板。

语法：template<> 返回值类型 同名模板(具体参数类型 参数名称, ...) {}

// 对比两个数据是否相等的函数模板
template<class T>
bool my_compare(T& a, T& b) {
	if (a == b)
	{
		cout << "两者相等" << endl;
		return true;
	}
	else
	{
		cout << "两者不相等" << endl;
		return false;
	}
}

// 利用具体化的Person的版本实现代码，具体化会优先调用
template<> bool my_compare(Person& p1, Person& p2) {
	if (p1.name == p2.name && p1.age == p2.age)
	{
		cout << "两者相等" << endl;
		return true;
	}
	else
	{
		cout << "两者不相等" << endl;
		return false;
	}
}

总结：

• 利用具体化的模板，可以解决自定义类型的通用化
• 学习模板并不是为了写模板，而是在STL能够运用系统提供的模板

示例：

#include <iostream>
using namespace std;
#include <string>

/*
	模板并不是万能的，有些特定的数据类型，需要使用具体化方式做特殊实现
*/


// 对比两个数据是否相等的函数
template<class T>
bool my_compare(T& a, T& b) {
	if (a == b)
	{
		cout << "两者相等" << endl;
		return true;
	}
	else
	{
		cout << "两者不相等" << endl;
		return false;
	}
}


void test06_01() {
	int a = 10;
	int b = 20;

	bool res = my_compare(a, b);
}


class Person {
public:
	Person(string name, int age) {
		this->name = name;
		this->age = age;
	}
public:
	string name;
	int age;
};


// 利用具体化的Person的版本实现代码，具体化会优先调用
template<> bool my_compare(Person& p1, Person& p2) {
	if (p1.name == p2.name && p1.age == p2.age)
	{
		cout << "两者相等" << endl;
		return true;
	}
	else
	{
		cout << "两者不相等" << endl;
		return false;
	}
}


void test06_02() {
	Person p1("Tom", 10);
	Person p2("Jerry", 10);

	// bool res = my_compare(p1, p2);  // 二进制”==":"T"不定义该运算符或到预定义运算符可接收的类型的转换

	/*
		解决思路：
			1. 运算符重载
			2. 模板重载
	*/
	bool res = my_compare(p1, p2);  // 两者不相等
}


int main() {

	test06_01();
	test06_02();

	system("pause");
	return 0;
}

1.3 类模板

1.3.1 类模板语法

类模板作用：建立一个通用类，类中的成员数据类型可以不具体制定，用一个虚拟的类型来代表。

语法:

template<typename T>
类的声明或定义

解释：

• template —— 声明创建模板
• typename —— 表面其后面的符号是一种数据类型，可以用class代替
• T —— 通用的数据类型，名称可以替换，通常为大写字母

总结：类模板和函数模板语法相似，在声明模板template后面加类class，此类称为类模板。

示例：

#include <iostream>
using namespace std;
#include <string>


// 类模板
template<class NameType, class AgeType>
class Person {
public:
	Person(string name, int age) {
		this->name = name;
		this->age = age;
	}

public:
	void show_info() {
		cout << "name: " << this->name << "\tage: " << this->age << endl;
	}

private:
	/*
		因为name和age的数据类型不一样，所以我们在定义模板的时候可以多定义几个数据类型
	*/
	NameType name;
	AgeType age;
};


void test01_01() {
	Person<string, int> p1("张三", 23);
	p1.show_info();  // name: 张三      age: 23
}


int main() {

	test01_01();

	system("pause");
	return 0;
}

1.3.2 类模板与函数模板的区别

类模板与函数模板区别主要有两点：

1. 类模板没有自动类型推导的使用方式（必须要提前指定数据类型）
2. 类模板在模板参数列表中可以有默认参数（在实例化时，<>也必须要写）

语法示例：

// 1. 类模板没有自动类型推导的使用方式（必须要提前指定数据类型）
template<class NameType, AgeType>
class Person01 {
private:
	NameType name;
	AgeType age;
};

Person01 p1("张三", 23);  // 报错！类模板没有自动类型推导的使用方式
Person01<string, int> p1("张三", 23);  // 不报错！（必须要提前指定数据类型）


// 2. 类模板在模板参数列表中可以有默认参数
template<class NameType=string, class AgeType=int>
class Person02 {
private:
	NameType name;
	AgeType age;
};

Person02 p2("李四", 20);  // 报错！基本有默认参数，<>也必须要写
Person02<> p2("李四", 20);  // 不报错！

总结：

1. 类模板使用只能用显式指定类型方式
2. 类模板中的模板参数列表可以有默认参数
3. 类模板在实例化时必须有<>

示例：

#include <iostream>
using namespace std;
#include <string>


/*
	类模板与函数模板的区别：
		1. 类模板没有自动类型推导的使用方式
		2. 类模板在模板参数列表中可以有默认参数
*/
template<class NameType, class AgeType>
class Person02_1 {
public:
	Person02_1(string name, int age) {
		this->name = name;
		this->age = age;
	}
public:
	void show_info() {
		cout << "name: " << this->name << "\tage: " << this->age << endl;
	}
private:
	NameType name;
	AgeType age;
};


// 2. 类模板在模板参数列表中可以有默认参数
template<class NameType = string, class AgeType = int>  // 可以加默认的数据类型
class Person02_2 {
public:
	Person02_2(string name, int age) {
		this->name = name;
		this->age = age;
	}
public:
	void show_info() {
		cout << "name: " << this->name << "\tage: " << this->age << endl;
	}
private:
	NameType name;
	AgeType age;
};



// 1. 类模板没有自动类型推导的使用方式
void test02_01() {
	// Person02 p("张三", 23);  // 错误：无法用自动类型推导 —— 缺少类模板"Person02"的参数列表

	Person02_1<string, int> p("张三", 23);  // 只能用显式指定类型
	p.show_info();  // name: 张三      age: 23
}


// 2. 类模板在模板参数列表中可以有默认参数
void test02_02() {
	// Person02_2 p = { "李四", 20 };  // 在实例化类模板的时候，必须有<>
	Person02_2<> p = { "李四", 20 };
	p.show_info();  // name: 李四      age: 20
}


int main() {

	test02_01();
	test02_02();

	system("pause");
	return 0;
}

1.3.3 类模板中成员函数创建时机

类模板中成员函数和普通类中成员函数创建时机是有区别的：

• 普通类中的成员函数一开始就可以创建
• 类模板中的成员函数在调用时才创建

这是因为类模板的数据类型T不能确定，所以类模板中的成员函数一开始是不会创建的，只有在调用时，数据类型T才确定，此时类模板的成员函数才可以创建。

因此在使用类模板时，编译器代码生成可能不会报错，但会在运行时出错，此时问题一般发生在类模板的成员函数这里。

示例：

#include <iostream>
using namespace std;
#include <string>


/*
	类模板中成员函数和普通类中成员函数创建时机是有区别的：
		+ 普通类中的成员函数一开始就可以创建
		+ 类模板中的成员函数在调用时才创建
*/


class Person03_01 {
public:
	void show_info_1() {
		cout << "show Person03_01" << endl;
	}
};


class Person03_02 {
public:
	void show_info_2() {
		cout << "show Person03_02" << endl;
	}
};


template <class T>
class  MyClass {
	/*
		生成代码的时候不会报错，因为类模板的数据类型不能确定，
		所以类模板中的成员函数一开始是不会创建的，
		只有在调用时，数据类型T才确定，此时类模板的成员函数才可以创建。
	*/
public:
	T obj;

	// 类模板中的成员函数
	void func_1() {
		obj.show_info_1();
	}

	void func_2() {
		obj.show_info_2();
	}
};


void test_03_01() {
	MyClass<Person03_01> m;
	m.func_1();
	m.func_2();  // Error: "show_info_2":不是"Person03_01"的成员
}


int main() {

	test_03_01();

	system("pause");
	return 0;
}

1.3.4 类模板对象做函数参数

学习目标：

• 类模板实例化出的对象，向函数传参的方式。

一共有三种传入方式：

1. 指定传入的类型：直接显式对象的数据类型 —— 普通函数调用类模板
2. 参数模板化：将对象中的参数变为模板进行传递 —— 函数模板调用类模板
3. 整个类模板化：将这个对象类型模板化进行传递 —— 函数模板调用类模板

语法示例：

// 1. 指定传入的类型：直接显式对象的数据类型
void print_person_1(Person04<string, int>& p) {
	p.show_info();
}

// 2. 参数模板化：将对象中的参数变为模板进行传递
template<class T1, class T2>
void print_person_2(Person04<T1, T2>& p) {
	p.show_info();  // 姓名: 李四      年龄: 20
	cout << "T1的类型为: " << typeid(T1).name() << endl;
	// class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >
	cout << "T2的类型为: " << typeid(T2).name() << endl;  // int
}

// 3. 整个类模板化：将这个对象类型模板化进行传递
template<class T>
void print_person_3(T& p) {
	p.show_info();
}

在日常开发中，三种方式中第一种指定传入类型最为常用。

总结：

• 通过类模板创建的对象，可以有三种方式向函数中进行传参
• 使用比较广泛是第一种：指定传入的类型

示例：

#include <iostream>
using namespace std;
#include <string>


/*
	+类模板实例化出的对象，向函数传参的方式。一共有三种传入方式：
		1. 指定传入的类型：直接显式对象的数据类型
		2. 参数模板化：将对象中的参数变为模板进行传递
		3. 整个类模板化：将这个对象类型模板化进行传递
*/


template<class T1, class T2>
class Person04 {
public:
	Person04(T1 name, T2 age) {
		this->name = name;
		this->age = age;
	}
public:
	void show_info() {
		cout << "姓名: " << this->name << "\t年龄: " << this->age << endl;
	}
private:
	T1 name;
	T2 age;
};


// 1. 指定传入的类型：直接显式对象的数据类型
void print_person_1(Person04<string, int>& p) {
	p.show_info();
}


void test04_01() {
	Person04<string, int> p("张三", 23);
	print_person_1(p);  // 姓名: 张三      年龄: 23
}


// 2. 参数模板化：将对象中的参数变为模板进行传递
template<class T1, class T2>
void print_person_2(Person04<T1, T2>& p) {
	p.show_info();  // 姓名: 李四      年龄: 20
	cout << "T1的类型为: " << typeid(T1).name() << endl;
	// class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >
	cout << "T2的类型为: " << typeid(T2).name() << endl;  // int
}


void test04_02() {
	Person04<string, int> p("李四", 20);
	print_person_2(p);
}


// 3. 整个类模板化：将这个对象类型模板化进行传递
template<class T>
void print_person_3(T& p) {
	p.show_info();
}


void test04_03() {
	Person04<string, int> p("王五", 30);
	print_person_3(p);  // 姓名: 王五      年龄: 30
	cout << "p的数据类型: " << typeid(p).name() << endl;
	// class Person04<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >,int>
}


int main() {

	test04_01();
	test04_02();
	test04_03();

	system("pause");
	return 0;
}

1.3.5 类模板与继承

当类模板碰到继承时，需要注意几点：

1. 当子类继承的父类是一个类模板时，子类在声明的时候，要指定出父类中T的类型。如果不指定，编译器无法给子类分配内存 —— 类继承类模板
2. 如果想灵活指定出父类中T的类型，子类也需变为类模板 —— 类模板继承类模板

总结：如果父类是类模板，子类需要指定出父类中T的教据类型

示例：

#include <iostream>
using namespace std;
#include <string>


/*
	当类模板碰到继承时，需要注意几点：
		1. 当子类继承的父类是一个类模板时，子类在声明的时候，要指定出父类中`T`的类型。
			如果不指定，编译器无法给子类分配内存 —— 类继承类模板
		2. 如果想灵活指定出父类中`T`的类型，子类也需变为类模板
*/
template<class T>
class Base {
private:
	T m;
};


// 1. 当子类继承的父类是一个类模板时，子类在声明的时候，要指定出父类中`T`的类型。如果不指定，编译器无法给子类分配内存 —— 类继承类模板
/*
class Son : public Base {  // 必须要知道父类中T的类型，才能继承给子类
		如果没有指定父类T的数据类型，那么子类就没法创建，
		因为不知道到底该开拓多大的内存空间
};
*/
class Son : public Base<int> {  // 显式说明父类模板数据类型

};


void test05_01() {
	Son s1;
}


// 2. 如果想灵活指定出父类中`T`的类型，子类也需变为类模板 —— 类模板继承类模板
template <class T1, class T2>
class Son2 : public Base<T1> {
public:
	Son2() {
		cout << "T1的数据类型为: " << typeid(T1).name() << endl;  // int
		cout << "T2的数据类型为: " << typeid(T2).name() << endl;  // char
	}
private:
	T2 obj;
};


void test05_02() {
	Son2<int, char> s2;
}


int main() {

	test05_01();
	test05_02();

	system("pause");
	return 0;
}

1.3.6 类模板成员函数的类外实现

学习目标：能够掌握类模板中的成员函数类外实现。

语法示例：

// 类外实现
// 构造函数的类外实现
template<class T1, class T2>
Person06<T1, T2>::Person06(T1 name, T2 age) {
	this->name = name;
	this->age = age;
}


// 成员函数的类外实现
template<class T1, class T2>
void Person06<T1, T2>::show_info() {
	cout << "姓名: " << this->name << "\t年龄: " << this->age << endl;
}

1. 写模板的参数列表template<class T1, class T2>
2. 加上作用域，且填入模板的参数列表成员函数返回值类型 Person06<T1, T2>::要实现的成员函数名

总结：类模板中成员函数类外实现时，需要加上模板参数列表。

本质上就是函数模板的类外实现。

示例：

#include <iostream>
using namespace std;
#include <string>


// 类模板成员函数的类外实现
template<class T1, class T2>
class Person06 {
public:
	Person06(T1 name, T2 age);

public:
	void show_info();

private:
	T1 name;
	T2 age;
};


// 类外实现
// 构造函数的类外实现
template<class T1, class T2>
Person06<T1, T2>::Person06(T1 name, T2 age) {
	this->name = name;
	this->age = age;
}


// 成员函数的类外实现
template<class T1, class T2>
void Person06<T1, T2>::show_info() {
	cout << "姓名: " << this->name << "\t年龄: " << this->age << endl;
}


void test06_01() {
	Person06<string, int> p("Tom", 20);
	p.show_info();  // 姓名: Tom       年龄: 20
}


int main() {

	test06_01();

	system("pause");
	return 0;
}

1.3.7 类模板分文件编写

学习目标：掌握类模板成员函数分文件编写产生的问题以及解决方式。

问题：

• 类模板中成员函数创建时机是在调用阶段，导致分文件编写时链接不到。

解决：

• 解决方式1：直接包含.cpp源文件
• 解决方式2：将声明和实现写到同一个文件中，并更改后缀名为.hpp，hpp是约定的名称，并不是强制。

总结：主流的解决方式是第二种，即类模板和其成员函数的实现写到一起，并将后缀名改为.hpp

示例：

person.hpp中代码：

#pragma once
#include <iostream>
using namespace std;


template<class T1, class T2>
class Person
{
public:
	Person(T1 name, T2 age);

public:
	void show_info();

private:
	T1 name;
	T2 age;
};


template<class T1, class T2>
Person<T1, T2>::Person(T1 name, T2 age) {
	this->name = name;
	this->age = age;
}


template<class T1, class T2>
void Person<T1, T2>::show_info() {
	cout << "name: " << this->name << " age: " << this->age << endl;
}

类模板分文件编写.cpp中代码：

#include <iostream>
using namespace std;
#include <string>

// 第一种解决方式，直接包含原文件：#include "person.cpp"
//#include "person.cpp"

// 第二种解决方法，将.h和.cpp中的内容写到一起，将后缀名改为.hpp文件
#include "person.hpp"

// 类模板分文件编写的问题以及解决
void test07_01() {
	Person<string, int> p("Jerry", 20);
	p.show_info();
}


int main() {

	test07_01();

	system("pause");
	return 0;
}

1.3.8 类模板与友元

学习目标：掌握类模板配合友元函数的类内和类外实现，

• 全局函数类内实现：直接在类内声明友元即可
• 全局函数类外实现：需要提前让编译器知道全局函数的存在

---

虽然友元函数的实现在类的内部，但它仍然是一个全局函数，因为它没有被声明为类的成员函数。它只是被声明为类的友元函数，因此它可以访问类的私有成员变量。

将它声明为全局函数的好处是，它可以在类的外部被访问和调用，而不需要创建类的实例。

Q：友元函数都是全局函数吗？
A：是的，友元函数通常是全局函数，因为它们在类外定义，但在类内声明。它们不是类的成员函数，因此可以在类的外部访问和调用。友元函数可以访问类的私有和保护成员，这使得它们非常有用，可以实现一些特殊的功能，

但应该谨慎使用友元函数，因为它们破坏了类的封装性。

---

对于类模板，全局函数的类内和类外实现的语法与普通类有所不同。以下是语法示例：

1. 类内实现全局函数：

// 1. 先写类模板
template <typename T>
class MyClass {
public:
	// 2. 声明并实现友元函数
  friend T myFunction(MyClass<T> obj) { 
    return obj.myValue + 1;  // 具体实现
  }
private:
  T myValue = 0;
};

在这个示例中，myFunction函数被声明为MyClass的友元函数，并在类内定义为一个全局函数。由于MyClass是一个类模板，因此要在函数名后面加上模板参数T。

2. 类外实现全局函数：

// 1. 先写类模板的声明
template <typename T>
class MyClass;

// 2. 全局函数的类外实现
template <typename T>
T myFunction(MyClass<T> obj) {
  return obj.myValue + 1;  // 具体实现
}

// 3. 最后写类模板
template <typename T>
class MyClass {
public:
  friend T myFunction<>(MyClass<T> obj); // 声明友元函数且加上参数列表<>
private:
  T myValue = 0;
};

在这个示例中，myFunction函数被声明为MyClass的友元函数，并在类外定义为一个全局函数。由于MyClass是一个类模板，因此要在函数名后面加上模板参数T，并在函数定义前面加上template。

需要注意的是，类模板的友元函数的语法有些特殊，但它们的作用与普通类的友元函数相同。

总结：建议全局函数做类内实现，用法简单，而且编译器可以直接识别。类外实现太麻烦了！

---

示例:

#include <iostream>
using namespace std;
#include <string>


// 类模板与友元


/*
	通过全局函数打印Person08的信息：
		1. 类内实现
		2. 类外实现
*/


template<class T1, class T2>
class Person08_01 {
public:
	Person08_01(T1 name, T2 age) {
		this->name = name;
		this->age = age;
	}
public:
	// 1. 全局函数：类内实现
	/*
		虽然print_person_01函数的实现在类的内部，但它仍然是一个全局
		函数，因为它没有被声明为类的成员函数。它只是被声明为类的友元
		函数，因此它可以访问类的私有成员变量。
		将它声明为全局函数的好处是，它可以在类的外部被访问和调用，而
		不需要创建类的实例。

		Q：友元函数都是全局函数吗？
		A：是的，友元函数通常是全局函数，因为它们在类外定义，但在类内
		声明。它们不是类的成员函数，因此可以在类的外部访问和调用。友元
		函数可以访问类的私有和保护成员，这使得它们非常有用，可以实现一
		些特殊的功能，但应该谨慎使用，因为它们破坏了类的封装性。
	*/
	friend void print_person_01(Person08_01<T1, T2>& p) {
		cout << "[1. 全局函数的类内实现]name: " << p.name << "\tage: " << p.age << endl;
	}
private:
	T1 name;
	T2 age;
};


// 1. 全局函数：类内实现
void test08_01() {
	Person08_01<string, int> p("Tom", 20);
	print_person_01(p);  // [1. 全局函数的类内实现]name: Tom        age: 20
}


// 提前让编译器知道Person类的存在
template<class T1, class T2>
class Person08_02;


// 类外实现（因为是全局函数，所以不用加作用域）
template <class T1, class T2>
void print_person_02(Person08_02<T1, T2>& p) {
	cout << "[2. 全局函数的类外实现]name: " << p.name << "\tage: " << p.age << endl;
}


template<class T1, class T2>
class Person08_02 {
public:
	Person08_02(T1 name, T2 age) {
		this->name = name;
		this->age = age;
	}
public:
	// 2. 全局函数：类外实现（类内只做声明，不做实现）
	// 需要加一个空模板的参数列表<>
	// 如果全局函数是类外实现的话，需要让编译器提前知道这个函数的存在，
	// 即先写实现，再写声明（实现的代码在声明代码的上面）
	// 但这样会导致一个问题，实现的时候会用到Person08_02这个类，所以
	// 我们还需要声明一下这个类模板
	// 类外实现全局函数太过于麻烦了！
	friend void print_person_02<>(Person08_02<T1, T2>& p);
private:
	T1 name;
	T2 age;
};


// 2. 全局函数：类外实现
void test08_02() {
	Person08_02<string, int> p("Tom", 20);
	print_person_02(p);  // [2. 全局函数的类外实现]name: Tom        age: 20
}


// 1. 先写类模板的声明
template <typename T>
class MyClass;

// 2. 全局函数的类外实现
template <typename T>
T myFunction(MyClass<T> obj) {
	return obj.myValue + 1;
}

// 3. 最后写类模板
template <typename T>
class MyClass {
public:
	friend T myFunction<>(MyClass<T> obj); // 声明友元函数且加上参数列表<>
private:
	T myValue = 0;
};


void test08_03() {
	MyClass<int> obj;
	int res = myFunction(obj);
	cout << "res: " << res << endl;  // res: 1
}


int main() {

	test08_01();
	test08_02();
	test08_03();

	system("pause");
	return 0;
}

1.3.9 类模板案例

案例描述：实现一个通用的数组类，要求如下:

1. 可以对内置数据类型以及自定义数据类型的教据进行存储
2. 将数组中的数据存储到堆区
3. 构造函数中可以传入数组的容量
4. 提供对应的拷贝构造函数以及operator=防止浅拷贝问题
5. 提供尾插法和尾删法对数组中的数据进行增加和删除
6. 可以通过下标的方式访问数组中的元素
7. 可以获取数组中当前元素个数和数组的容量

示例：

my_array.h中代码：

// 自己的通用的数组类
#pragma once
#include <iostream>
using namespace std;
#include "person09.h"


template<class T>  // T表示数组中的数据类型
class MyArray {
public:
	MyArray(int capacity) {  // 有参构造
		this->capacity = capacity;
		this->size = 0;
		this->ptr_address = new T[this->capacity];
	}

	MyArray(const MyArray& arr) {  // 拷贝构造（深拷贝）
		this->capacity = arr.capacity;
		this->size = arr.size;
		// this->ptr_address = arr.ptr_address;  // 指针不能直接复制，否则会导致内存重复释放，应该使用深拷贝

		this->ptr_address = new T[arr.capacity];  // 深拷贝

		// 将arr中的数据都拷贝过来
		for (int i = 0; i < this->size; i++)
		{
			/*
				使用已有对象的capacity属性来动态分配内存，以避免缓冲区溢出的问题。
				同时，在写入数据之前，可以先判断写入的位置是否超出了缓冲区的范围，以避免缓冲区溢出的问题。
			*/
			if (i < this->capacity)
			{
				this->ptr_address[i] = arr.ptr_address[i];
			}
		}
	}

	~MyArray() {  // 析构函数
		if (this->ptr_address != NULL)
		{
			delete[] this->ptr_address;
			ptr_address = NULL;
		}
	}

public:
	// 重载=操作符，防止浅拷贝问题
	MyArray& operator=(const MyArray& arr) {
		// 先判断原来堆区是否有数据，如果有：先释放
		if (this != &arr)  // 在重载=操作符时，应该先判断是否自我赋值，否则可能会导致内存泄漏问题。
		{
			if (this->ptr_address != NULL)
			{
				delete[] this->ptr_address;
				this->ptr_address = NULL;
				this->capacity = 0;
				this->size = 0;
			}

			// 再深拷贝
			this->capacity = arr.capacity;
			this->size = arr.size;
			this->ptr_address = new T[arr.capacity];

			for (int i = 0; i < this->size; i++)
			{
				this->ptr_address[i] = arr.ptr_address[i];
			}
		}
		return *this;  // 返回自身
	}

	// 尾插法
	void push_back(const T& value) {
		// 判断容量是否等于大小
		if (this->capacity == this->size)
		{
			cout << "数组容量受限，无法继续添加元素!" << endl;
			return;
		}

		this->ptr_address[this->size] = value;  // 在数组末尾插入数据
		this->size += 1;  // 更新数组大小
	}

	// 尾删法
	void pop_back() {
		// 让用户访问不到最后一个元素即为尾删（逻辑上的删除）
		if (this->size != 0)
		{
			this->size -= 1;
		}
		else
		{
			cout << "数组中没有元素，无法删除!" << endl;
			return;
		}
	}

	// 通过下标的方式访问数组中的元素 —— 重载[]运算符
	T& operator[](int idx) {  // 返回T&可以返回数值的本身，更好一些
		return this->ptr_address[idx];
	}

	// 返回数组的容量（数组容纳元素的最大个数）
	int get_capacity() {
		return this->capacity;
	}

	// 返回数组的大小（当前有几个元素）
	int get_size() {
		return this->size;
	}

	// 打印输出
	void print() {
		cout << "[ ";
		int count = 1;
		for (int i = 0; i < this->size; i++)
		{
			if (count != this->size)
			{
				cout << this->ptr_address[i] << ", ";
			}
			else
			{
				cout << this->ptr_address[i];
			}
			count += 1;
		}
		cout << " ]" << endl;
	}

	// 重载print成员函数
	void print(bool) {
		cout << "[ ";
		int count = 1;
		for (int i = 0; i < this->size; i++)
		{
			if (count != this->size)
			{
				cout << "姓名: " << this->ptr_address[i].get_name() << " 年龄: " << this->ptr_address[i].get_age() << ", ";
			}
			else
			{
				cout << "姓名: " << this->ptr_address[i].get_name() << " 年龄: " << this->ptr_address[i].get_age();
			}
			count += 1;
		}
		cout << " ]" << endl;
	}


private:
	T* ptr_address;  // 指针指向堆区开辟的真实数组（数组指针，指向数组的首地址）
	int capacity;  // 数组容量（数组容纳元素的最大个数）
	int size;  // 数组大小（当前有几个元素）
};

person09.h中代码：

#pragma once
#include <iostream>
#include<string>
using namespace std;


// 自定义数据类型
class Person09 {
public:
	Person09();
	Person09(string name, int age);

public:
	string get_name();

	int get_age();

private:
	string name;
	int age;
};

person09.cpp中代码：

#include "person09.h"


// 类实现
Person09::Person09() {}

Person09::Person09(string name, int age) {
	this->name = name;
	this->age = age;
}


string Person09::get_name() {
	return this->name;
}

int Person09::get_age() {
	return this->age;
}

主函数.cpp中代码：

#include <iostream>
using namespace std;
#include <string>
#include "MyArray.hpp"
#include "person09.h"


void test09_01() {
	MyArray<int> arr1(5);  // 有参构造

	MyArray<int> arr2(arr1);  // 拷贝构造

	MyArray <int> arr3(100);
	arr3 = arr1;  // =运算符

	// arr1[0];  // 没有与这些操作数匹配的“"运算符

	for (int i = 0; i < 5; i++)
	{
		// 利用尾插法向数组中插入数据
		arr1.push_back(i);
	}
	arr1.print();  // [ 0, 1, 2, 3, 4 ]
	cout << "arr1的容量: " << arr1.get_capacity() << endl;  // arr1的容量: 5
	cout << "arr1的大小: " << arr1.get_size() << endl;  // arr1的大小: 5

	// 尾删法删除最后一个元素
	arr2 = arr1;  // 利用重载后的=对arr2进行赋值
	arr2.pop_back();
	arr2.pop_back();
	arr2.print();  // [ 0, 1, 2 ]
	cout << "arr2的容量: " << arr2.get_capacity() << endl;  // arr2的容量: 5
	cout << "arr2的大小: " << arr2.get_size() << endl;  // arr2的大小: 3
}


void test09_02() {
	MyArray<Person09> arr(10);

	// 利用尾插法插入元素
	arr.push_back(Person09("张三", 20));
	arr.push_back(Person09("李四", 23));
	arr.push_back(Person09("王五", 26));
	arr.push_back(Person09("周六", 21));
	arr.push_back(Person09("田七", 18));

	// 打印数组
	arr.print(true);  // 这里对打印的成员函数进行重载，打印Person类型需要填入bool类型
	// 姓名: 张三 年龄: 20, 姓名: 李四 年龄: 23, 姓名: 王五 年龄: 26, 姓名: 周六 年龄: 21, 姓名: 田七 年龄: 18 ]
	cout << "arr的容量: " << arr.get_capacity() << endl;  // arr的容量: 10
	cout << "arr的大小: " << arr.get_size() << endl;  // arr的大小: 5
}


int main() {

	test09_01();
	test09_02();

	system("pause");
	return 0;
}

2. STL（Standard Template Library，标准模板库）初识

2.1 STL的诞生

• 长久以来，软件界一直希望建立一种可重复利用的东西
• C++的面向对象和泛型编程思想，目的就是复用性的提升
• 大多情况下，数据结构和算法都未能有一套标准，导致被迫从事大量重复工作
• 为了建立数据结构和算法的一套标准，诞生了STL

面向对象三大特性：封装、继承、多态

面向对象编程（Object-Oriented Programming，简称OOP）的三大特性包括：

• 封装性（Encapsulation）：指将对象的状态信息隐藏在对象内部，只暴露必要的接口给外部使用。通过封装，可以保证对象的内部状态不受外部的干扰和破坏，从而提高了程序的可靠性和安全性。
• 继承性（Inheritance）：指一个类可以派生出子类，子类会继承父类的属性和方法，并且可以在此基础上进行扩展和修改。通过继承，可以减少代码的重复，提高代码的复用性和可维护性。
• 多态性（Polymorphism）：指同一种类型的对象，在不同的情况下可以具有不同的表现形式和行为。多态性分为编译时多态和运行时多态，其中编译时多态是指函数重载，而运行时多态是指通过虚函数实现的动态绑定。通过多态性，可以提高代码的灵活性和可扩展性，使得程序更加易于扩展和维护。

2.2 STL基本概念

STL（Standard Template Library，标准模板库）是C++标准库的一部分，它提供了一组模板类和函数，用于处理常见的数据结构和算法，如序列、关联容器、迭代器、算法等。STL的设计思想是将数据结构和算法分离，以便在不同的场景下重复使用。STL包含三个主要组件：容器、迭代器和算法。

• STL从广义上分为：
  1. 容器(container)：用来存储和管理数据的类模板。STL提供了多种容器，包括vector、list、deque、set、map等。容器可以分为序列式容器和关联式容器两种类型。
  2. 算法(algorithm)：用来对容器中的数据进行操作的函数模板。STL提供了大量的算法，包括排序、查找、遍历、变换等。算法可以独立于容器使用，也可以和容器配合使用。
     1. 序列容器包括vector、deque、list等，它们按照元素的线性次序存储元素，并提供了随机访问的功能。
     2. 关联容器包括set、multiset、map、multimap等，它们根据元素的键值来存储元素，并提供了按照键值进行查找、插入和删除的功能。
  3. 迭代器(iterator)：用来遍历容器中的元素的对象。STL提供了多种迭代器，包括输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机访问迭代器。迭代器是STL的核心概念，它使得算法和容器之间解耦，从而提高了代码的灵活性和复用性。
• 容器和算法之间通过迭代器进行无缝连接。
• STL几乎所有的代码都采用了模板类或者模板函数

总之，STL是C++标准库中的一个重要组成部分，提供了丰富的容器、迭代器和算法等组件，可以大大提高C++程序的开发效率和代码质量。STL的设计思想是将数据结构和算法分离，提高代码的可读性和可维护性。同时，STL中的大多数组件都是用模板实现的，可以支持多种数据类型，使得代码的复用性更高。

在使用STL时，需要了解各种容器、迭代器和算法的特点和使用方法，以便正确地选择和使用它们。同时，由于STL中的很多组件都是用模板实现的，因此需要注意模板参数的类型和范围，避免出现编译错误或运行时错误。另外，STL中的一些算法和容器可能会引入一些性能开销，因此需要根据实际情况选择合适的组件，以满足程序的性能要求。

2.3 STL六大组件

STL大体分为六大组件，分别是：容器、算法、迭代器、仿函数、适配器(配接器)、空间配置器。

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

仿函数（Function object）是一种重载了函数调用运算符 () 的类或结构体，它可以像函数一样被调用，可以接受参数，并且可以返回值。仿函数可以看作是一种特殊的函数对象，它可以像普通函数一样被调用，但具有更高的灵活性和可定制性。

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

1. 容器(Container)：置物之所也

• STL容器就是将运用最广泛的一些数据结构实现出来。
• 常用的数据结构有数组、链表、树、栈、队列、集合、映射表等。
• 这些容器分为①序列式容器和②关联式容器两种：
  1. 序列式容器（Sequence container）强调值的排序，其中每个元素均有固定的位置；
  2. 关联式容器（Associative container）采用二叉树结构，各元素之间没有严格的物理上的顺序关系。

2. 算法：问题之解法也

• 算法是指用有限的步骤解决逻辑或数学上的问题。这一门学科我们叫做算法（Algorithms）。
• 算法分为①质变算法和②非质变算法：
  1. 质变算法（Mutating algorithm）是指运算过程中会更改区间内的元素的内容，例如拷贝、替换、删除等等；
  2. 非质变算法（Non-mutating algorithm）是指运算过程中不会更改区间内的元素内容，例如查找、计数、遍历、寻找极值等等。

3. 迭代器：容器和算法之间的粘合剂

• 迭代器提供了一种方法，使得可以依次访问某个容器所包含的各个元素，而又无需暴露该容器的内部表示方式。
• 每个容器都有自己专属的迭代器，可以通过迭代器访问容器中的元素。
• 迭代器不仅是容器的重要组成部分，也是算法的重要参数之一，它将容器和算法之间紧密地联系在一起，成为它们之间的粘合剂（沟通的桥梁）。
• 迭代器使用非常类似于指针，初学阶段我们可以先理解迭代器为指针

迭代器种类：

种类	功能	支持运算
输入迭代器（Input iterator）	对教据的只读访问	只读，支持++、==、!=
输出迭代器（Output iterator）	对数据的只写访问	只写，支持++
前向迭代器（Forward iterator）	读写操作，并能向前推进迭代器	读写，支持++、==、!=
双向迭代器（Bidirectional iterator）	读写操作，并能向前和向后操作	读写，支持++、--
随机访问迭（Random access iterator）	读写操作，可以以跳跃的方式访问任意数据，功能最强的迭代器	读写，支持++、--、[n]、-n、<、<=、>、>=

常用的容器中迭代器种类为双向迭代器和随机访问迭代器。

2.5 容器、算法、迭代器初识

了解了STL中容器、算法、迭代器的概念之后，我们可以通过编写代码来感受STL的魅力。在STL中，最常用的容器之一是vector，它可以理解为一个动态数组。下面我们将学习如何向vector容器中插入数据，并遍历这个容器。

2.5.1 vector存放内置数据类型

容器：vector
算法：for_each
迭代器：vector<int>::iterator（<int>表示vector容器存放的数据类型为int）

语法：

1. 使用while循环
2. 使用for循环
3. 使用for_each

在使用vector容器时需要引入<vector>头文件

在使用for_each迭代器时需要引入<algorithm>头文件

语法示例：

#include <vector>
#include <algorithm>

vector<int> v;
for (int i = 0; i < 6; i++)
{
	v.push_back(i * 10);
}

vector<int>::iterator iter_begin = v.begin();;
vector<int>::iterator iter_end = v.end();

// 第一种遍历方式：while循环
while (iter_begin != iter_end)
{
	cout << *iter_begin << endl;
	iter_begin += 1;
}


// 第二种遍历方式：for循环
for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
{
	cout << *it << endl;
}


// 第三种遍历方式：利用STL提供的遍历算法 —— for_each
for_each(v.begin(), v.end(), my_print);  // my_print是一个函数

示例代码：

#include <iostream>
using namespace std;
#include <vector>  // STL中每个容器使用前都需要包含其头文件
#include <algorithm>  // 标准算法的头文件


// vector容器存放内置数据类型


// 第一种遍历方式：while循环
void test01_01() {
	vector<int> v;
	// 向容器中插入数据
	for (int i = 0; i < 6; i++)
	{
		v.push_back(i * 10);
	}

	// 通过迭代器访问容器中的数据
	vector<int>::iterator iter_begin = v.begin();;  // v.begin为起始迭代器，指向容器中第一个元素
	vector<int>::iterator iter_end = v.end();  // v.end()为结束迭代器，指向容器中最后一个元素的下一个位置

	// 第一种遍历方式：while循环
	while (iter_begin != iter_end)
	{
		cout << *iter_begin << endl;
		iter_begin += 1;
	}
}


// 第二种遍历方式：for循环
void test01_02() {
	vector<int> v;
	for (int i = 0; i < 6; i++)
	{
		v.push_back(i * 10);
	}

	vector<int>::iterator iter_begin = v.begin();;
	vector<int>::iterator iter_end = v.end();

	// 第二种遍历方式：for循环
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << endl;
	}
}


void my_print(int val) {
	cout << val << endl;
}


// 第三种遍历方式：利用STL提供的遍历算法 —— for_each
void test01_03() {
	vector<int> v;
	for (int i = 0; i < 6; i++)
	{
		v.push_back(i * 10);
	}

	vector<int>::iterator iter_begin = v.begin();;
	vector<int>::iterator iter_end = v.end();

	// 第三种遍历方式：利用STL提供的遍历算法 —— for_each
	for_each(v.begin(), v.end(), my_print);
}


int main() {

	test01_01();
	test01_02();
	test01_03();

	system("pause");
	return 0;
}

2.5.2 Vector存放自定义数据类型

学习目标: vector中存放自定义数据类型，并打印输出。

对于vector<数据类型>：<>中是什么数据类型，那么解引用后就是什么数据类型。

举个例子：

vector<Person*>::iterator iter = v.begin();
// 那么*iter的数据类型就是Person*

示例：

#include <iostream>
using namespace std;
#include <vector>  // STL中每个容器使用前都需要包含其头文件
#include <algorithm>  // 标准算法的头文件
#include <string>


// vector容器存放自定义数据类型
class Person {
public:
	Person(string name, int age) {
		this->name = name;
		this->age = age;
	}

public:
	string get_name() {
		return this->name;
	}

	int get_age() {
		return this->age;
	}

private:
	string name;
	int age;
};


// 存放自定义数据类型
void test02_01() {
	cout << "--------------存放自定义数据类型----------------" << endl;
	vector<Person> v;

	v.push_back(Person("aaa", 10));
	v.push_back(Person("bbb", 20));
	v.push_back(Person("ccc", 30));
	v.push_back(Person("ddd", 40));
	v.push_back(Person("eee", 50));

	// 遍历容器中的数据
	// 方法1：while循环
	// 必须先提高.begin()的作用域
	//vector<Person>::iterator iter_begin = v.begin();
	//while (iter_begin != v.end()) {
	//	cout << "Name: " << (*iter_begin).get_name() << "\tAge: " << (*iter_begin).get_age() << endl;

	//	// 解引用再.可以直接写成->
	//	cout << "Name: " << iter_begin->get_name() << "\tAge: " << iter_begin->get_age() << endl;

	//	iter_begin += 1;
	//}

	// 方法2：for循环
	//for (vector<Person>::iterator iter = v.begin(); iter != v.end(); iter++)
	//{
	//	cout << "Name: " << (*iter).get_name() << "\tAge: " << (*iter).get_age() << endl;

	//	// 解引用再.可以直接写成->
	//	cout << "Name: " << iter->get_name() << "\tAge: " << iter->get_age() << endl;
	//}

	// 方法3：for_each循环
	// 用lambda表达式写匿名函数
	auto fn = [](Person p) -> void {
		cout << "Name: " << p.get_name() << "\tAge: " << p.get_age() << endl;
	};
	for_each(v.begin(), v.end(), fn);
}


// 存放自定义数据类型的指针
void test02_02() {
	cout << "--------------存放自定义数据类型的指针----------------" << endl;
	vector<Person*> v;
	v.push_back(new Person("aaa", 10));
	v.push_back(new Person("bbb", 20));
	v.push_back(new Person("ccc", 30));
	v.push_back(new Person("ddd", 40));
	v.push_back(new Person("eee", 50));


	// 遍历容器
	// while循环
	//vector<Person*>::iterator iter_begin = v.begin();
	// <>中是什么数据类型，那么解引用后就是什么数据类型
	//while (iter_begin != v.end())
	//{
	//	cout << "Name: " << (*(*iter_begin)).get_name() << "\tAge: " << (*(*iter_begin)).get_age() << endl;

	//	// 解引用再.可以直接写成->
	//	cout << "Name: " << (*iter_begin)->get_name() << "\tAge: " << (*iter_begin)->get_age() << endl;

	//	iter_begin += 1;
	//}

	// for循环
	//for (vector<Person*>::iterator iter = v.begin(); iter != v.end(); iter++)
	// <>中是什么数据类型，那么就是什么数据类型
	//{
	//	cout << "Name: " << (*(*iter)).get_name() << "\tAge: " << (*(*iter)).get_age() << endl;

	//	// 解引用再.可以直接写成->
	//	cout << "Name: " << (*iter)->get_name() << "\tAge: " << (*iter)->get_age() << endl;
	//}

	// for_each循环
	// 先写匿名函数
	auto fn = [](Person* ptr)->void {
		cout << "Name: " << ptr->get_name() << "\tAge: " << ptr->get_age() << endl;
	};
	for_each(v.begin(), v.end(), fn);
}


int main() {

	test02_01();
	test02_02();

	system("pause");
	return 0;
}

2.5.3 Vector容器嵌套容器

学习目标：容器中嵌套容器，我们将所有数据进行遍历输出。

示例：

#include <iostream>
using namespace std;
#include <vector>  // STL中每个容器使用前都需要包含其头文件
#include <algorithm>  // 标准算法的头文件
#include <string>


// 容器嵌套容器
void test03_01() {
	vector<vector<int>> v;

	// 创建小容器
	vector<int> v1;
	vector<int> v2;
	vector<int> v3;
	vector<int> v4;

	// 向小容器中添加数据
	for (int i = 0; i < 4; i++)
	{
		v1.push_back(i + 1);
		v2.push_back(i + 2);
		v3.push_back(i + 3);
		v4.push_back(i + 4);
	}

	// 将小容器插入到大容器中
	v.push_back(v1);
	v.push_back(v2);
	v.push_back(v3);
	v.push_back(v4);

	// 通过大容器，把所有数据遍历一遍
	for (vector<vector<int>>::iterator iter = v.begin(); iter != v.end(); iter++)
	{
		// *iter的数据类型是vector<int>，所以还要遍历
		for (vector<int>::iterator iter2 = (*iter).begin(); iter2 != (*iter).end(); iter2++)
		{
			cout << *iter2 << " ";  // 解引用后的数据类型为int
		}
		cout << endl;
	}

	// 解引用再.可以直接写成->
	for (vector<vector<int>>::iterator iter = v.begin(); iter != v.end(); iter++)
	{
		// *iter的数据类型是vector<int>，所以还要遍历
		for (vector<int>::iterator iter2 = iter->begin(); iter2 != iter->end(); iter2++)
		{
			cout << *iter2 << " ";  // 解引用后的数据类型为int
		}
		cout << endl;
	}
}


int main() {

	test03_01();

	system("pause");
	return 0;
}

3. STL —— 常用容器

3.1 string容器

3.1.1 string基本概念

本质：string是C++风格的字符串，而string本质上是一个类。

string和char*区别：

• char*是一个指针
• string是一个类，类内部封装了char*，管理这个字符串，是一个char*型的容器。

特点：string类内部封装了很多成员方法。

例如：查找find，拷贝copy，删除delete，替换replace，插入insert。

string管理char*所分配的内存，不用担心复制越界和取值越界等，由类内部进行负责。

3.1.2 string构造函数

构造函数原型：

• string(); //创建一个空的字符串例如: string str;
string(const char* s); //使用字符串s初始化
• string(const string& str); //使用一个string对象初始化另一个string对象
• string(int n, char c); //使用n个字符c初始化

总结：string的多种构造方式没有可比性，灵活使用即可。

示例：

#include <iostream>
using namespace std;
#include <string>


// string的构造函数
/*
	构造函数原型：
		+ `string();`  //创建一个空的字符串例如: `string str;`
		  `string(const char* s);`  //使用字符串`s`初始化
		+ `string(const string& str);`  //使用一个`string`对象初始化另一个`string`对象
		+ `string(int n, char c);`  // 使用`n`个字符`c`初始化
*/
void test01_01() {
	string s1;  // 默认构造
	// string s1();  // 两种写法都可以，因为都是默认构造

	const char* str = "Hello World";  // C语言风格的字符串
	string s2(str);  // 有参构造
	cout << "s2: " << s2 << endl;  // s2: Hello World

	string s3(s2);  // 拷贝构造
	cout << "s3: " << s3 << endl;  // s3: Hello World

	string s4(10, 'a');  // 使用n个字符c初始化
	cout << "s4: " << s4 << endl;  // s4: aaaaaaaaaa
}


int main() {

	test01_01();

	system("pause");
	return 0;
}

3.1.3 string赋值操作

功能描述：给string字符串进行赋值。

赋值的函数原型：

函数重载	含义
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赋给当前字符串

总结：string的赋值方式很多，operator=这种方式是比较实用的。

示例：

#include <iostream>
using namespace std;
#include <string>


// string的赋值操作
/*
	1. string& operator=(const char* s);  //char*类型字符串赋值给当前的字符串
	2. string& operator=(const string &s);  //把字符串s赋给当前的字符串
	3. string& operator=(char c);  //字符赋值给当前的字符串
	4. string& assign(const char *s);  //把字符串s赋给当前的字符串
	5. string& assign(const char *s, int n);  //把字符串s的前n个字符赋给当前的字符串
	6. string& assign(const string &s);  //把字符串s赋给当前字符串
	7. string& assign(int n, char c);  //用n个字符c赋给当前字符串
*/
// 打印字符串的全局函数
void print_str(string str) {
	cout << str << endl;
}



void test_02_01() {

	// 1. string& operator=(const char* s);  //char*类型字符串赋值给当前的字符串
	string str1;
	str1 = "Hello World";
	print_str(str1);  // Hello World

	// 2. string& operator=(const string &s);  //把字符串s赋给当前的字符串
	string str2;
	str2 = str1;
	print_str(str2);  // Hello World

	// 3. string& operator=(char c);  //字符赋值给当前的字符串
	string str3;
	str3 = 'a';
	print_str(str3);  // a

	// 	4. string& assign(const char *s);  //把字符串s赋给当前的字符串
	string str4;
	str4.assign("Hello C++");
	print_str(str4);  // Hello C++

	// 5. string & assign(const char* s, int n);  //把字符串s的前n个字符赋给当前的字符串
	string str5;
	str5.assign("Hello C++", 3);
	print_str(str5);  // Hel

	// 6. string & assign(const string & s);  //把字符串s赋给当前字符串
	string str6;
	str6.assign(str5);
	print_str(str6);  // Hel

	// 7. string & assign(int n, char c);  //用n个字符c赋给当前字符串
	string str7;
	str7.assign(10, 'a');
	print_str(str7);  // aaaaaaaaaa
}


int main() {

	test_02_01();

	system("pause");
	return 0;
}

3.1.4 string字符串拼接

功能描述：实现在字符串末尾拼接字符串。

函数原型：

函数重载	含义
string& operator+=(const char* str);	重载+=操作符
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个字符连接到字符串结尾

对于string& append(const string& str, size_t pos, size_t n);而言，其中，str 是要追加的字符串，pos 是指定要追加的 str 中的起始位置，n 是指定要追加的字符数：

• 如果 pos 大于等于 str 的长度，则 append() 函数不会追加任何字符。
• 如果如果 n 大于 str 中从 pos 位置开始的字符数，则只会追加 str 中从 pos 位置开始的所有字符。

当 n 的值为 -1 时，append() 函数会将 str 中从 pos 位置开始的所有字符都追加到当前字符串的末尾，直到 str 的末尾为止。这相当于将 str 中从 pos 位置开始的所有字符全部追加到当前字符串的末尾。
需要注意的是，虽然在 C++11 标准中，string::append() 函数的 n 参数允许取负数，但是在 C++03 标准中，n 参数只能取非负数。因此，如果你使用的是 C++03 标准，你需要将 n 参数的值限制为非负数。

总结：空符串拼接的重载版本很多，初学阶段记住几种即可。

示例：

#include <iostream>
using namespace std;
#include <string>


// string字符串的拼接
/*
	函数原型：
		1. string& operator+=(const char* str);  //重载+=操作符
		2. string& operator+=(const char c);  //重载+=操作符
		3. string& operator+-(const string& str);  //重载+=操作符
		4. string& append(const char *s);  //把字符串s连接到当前字符串结尾
		5. string& append(const char *s, int n);  //把字符串s的前n个字符连接到当前字符串结尾
		6. string& append(const string &s);  //同operator+=(const string& str)
		7. string& append(const string &s, int pos, int n);  //字符串s中从pos开始的n个字符连接到字符串结尾
*/
void print_string(string str) {
	cout << str << endl;
}


void test03_01() {

	// 1. string& operator+=(const char* str);  //重载+=操作符
	string str1 = "Hello";
	str1 += " World";
	print_string(str1);  // Hello World

	// 2. string & operator+=(const char c);  //重载+=操作符
	string str2 = "Hell";
	str2 += 'o';
	print_string(str2);  // Hello

	// 3. string & operator+=(const string & str);  //重载+=操作符
	string str3 = "World";
	str3 += str2;
	print_string(str3);  // WorldHello

	// 4. string & append(const char* s);  //把字符串s连接到当前字符串结尾
	string str4 = "Hi";
	str4.append(", Tom");
	print_string(str4);  // Hi, Tom

	// 5. string & append(const char* s, int n);  //把字符串s的前n个字符连接到当前字符串结尾
	string str5 = "Hi";
	str5.append("Jerry", 1);
	print_string(str5);  // HiJ

	// 6. string & append(const string & s);  //同operator+=(const string& str)
	string str6;
	str6.append(str5);
	print_string(str6);  // HiJ

	// 7. string & append(const string & s, int pos, int n);  //字符串s中从pos开始的n个字符连接到字符串结尾
	string str7 = "Hi";
	str7.append("Jerry. How are you?", 5, -1);  // -1表示截取pos之后的所有字符
	print_string(str7);  // Hi. How are you?
}


int main() {

	test03_01();

	system("pause");
	return 0;
}

3.1.5 string查找和替换

功能描述：

• 查找：查找指定字符串是否存在
• 替换：在指定的位置替换字符串、

函数原型：

函数重载	含义
int find(const string& str, int pos = e) const;	查找str第一次出现位置，从pos开始查找
int find(const char* s, int pos = 0) const;	查找s第一次出现位置，从pos开始查找
int find(const char* s, int pos, int n) const;	从pos位置查找s的前n个字符第一次位置
int find(const char c, int pos = 0) const;	查找字符c第一次出现位置
int rfind(const string& str, int pos = npos) const;	查找str最后一次位置（从右往左查，只不过返回的位置还是从左往右计算的），从pos开始查找
int rfind(const char* s, int pos = npos) const;	查找s最后一次出现位置（从右往左查，只不过返回的位置还是从左往右计算的），从pos开始查找
int rfind( const char* s, int pos, int n) const;	从pos查找s的前n个字符最后一次位置（从右往左查，只不过返回的位置还是从左往右计算的）
int rfind( const char c, int pos = 0) const;	查找字符c最后一次出现位置（从右往左查，只不过返回的位置还是从左往右计算的）
string& replace(int pos，int n,const string& str);	替换从pos开始n个字符为字符串str
string& replace(int pos, int n,const char* s );	替换从pos开始的n个字符为字符串s

• find：从左往右找
• rfind：从右往左找（但是返回的位置信息还是从左往右计算的）

总结：

• find查找是从左往后，rfind从右往左
• find找到字符串后返回查找的第一个字符位置，找不到返回-1
• replace在替换时，要指定从哪个位置起，多少个字符，替换成什么样的字符串

示例:

#include <iostream>
using namespace std;
#include <string>


// string字符串的查找与替换
/*
	函数原型：
		1. int find(const string& str, int pos = 0) const;  //查找str第一次出现位置，从pos开始查找
		2. int find(const char* s, int pos = 0) const;  //查找s第一次出现位置，从pos开始查找
		3. int find(const char* s, int pos, int n) const;  //从pos位置查找s的前n个字符第一次位置
		4. int find(const char c, int pos = 0) const;  //查找字符c第一次出现位置
		5. int rfind(const string& str, int pos = npos) const;  //查找str最后一次位置，从pos开始查找
		6. int rfind(const char* s, int pos = npos) const;  //查找s最后一次出现位置，从pos开始查找
		7. int rfind( const char* s, int pos, int n) const;  //从pos查找s的前n个字符最后一次位置
		8. int rfind( const char c, int pos = 0) const;  //查找字符c最后一次出现位置
		9. string& replace(int pos，int n,const string& str);  //替换从pos开始n个字符为字符串str
		10. string& replace(int pos, int n,const char* s );  //替换从pos开始的n个字符为字符串s
*/
template <typename T>
void my_print(T elem) {
	cout << elem << endl;
}


void test04_01() {
	// 1. int find(const string& str, int pos = 0) const;  //查找str第一次出现位置，从pos开始查找
	string str1 = "de";
	string str2 = "abcdefg";
	int pos1 = str2.find(str1);
	my_print(pos1);  // 3
	

	// 2. int find(const char* s, int pos = 0) const;  //查找s第一次出现位置，从pos开始查找
	int pos2 = str2.find("ccc");
	my_print(pos2);  // -1

	// 3. int find(const char* s, int pos, int n) const;  //从pos位置查找s的前n个字符第一次位置
	int pos3 = str2.find("cdef", 0, 2);  // 2
	my_print(pos3);

	// 4. int find(const char c, int pos = 0) const;  //查找字符c第一次出现位置
	int pos4 = str2.find('e');
	my_print(pos4);  // 4

	// 5. int rfind(const string & str, int pos = npos) const;  //查找str最后一次位置（从右往左查，只不过返回的位置还是从左往右计算的），从pos开始查找
	string str3 = "abcdefgde";
	int pos5 = str3.rfind("de");
	my_print(pos5);  // 7（查到的就是最后一个de，然后再从左往右计算它的位置）

	// 6. int rfind(const char* s, int pos = npos) const;  //查找s最后一次出现位置，从pos开始查找

	// 7. int rfind(const char* s, int pos, int n) const;  //从pos查找s的前n个字符最后一次位置

	// 8. int rfind(const char c, int pos = 0) const;  //查找字符c最后一次出现位置

	// 9. string & replace(int pos，int n, const string & str);  //替换从pos开始n个字符为字符串str
	str1 = "abcdefg";
	str2 = "1111111";
	str1.replace(1, 3, str2);
	my_print(str1);  // a1111111efg

	// 10. string & replace(int pos, int n, const char* s);  //替换从pos开始的n个字符为字符串s
	str1 = "abcedfg";
	str1.replace(1, 3, "1111111");
	my_print(str1);  // a1111111efg
}


int main() {

	test04_01();

	system("pause");
	return 0;
}

3.1.6 string字符串比较

功能描述：字符串之间的比较。

比较方式：字符串比较是按字符的ASCII码进行对比。

情况	返回值
=	0
>	1
<	-1

需要注意的是，就是单纯的一个字符比较，如果字符串A和第一个字符大于字符串B的第一个字符，那么就直接A>B，返回1。只有两个字符串的字符相等时，才会对比第二个字符。

函数原型：

函数重载	含义
int compare(const string &s) const;	与字符串s比较
int compare(const char *s) const;	与字符串s比较

注意：字符串比较其实应用的场景比较受限，因为对于英文字符串而言，还可以通过ASCII码进行比较，对于中文而言，得到哪个字符串大或哪个字符串小是没有什么意义的。所以在应用中，我们对比两个字符长的目的，主要是想知道这两个字符串是否相等，仅此而已！

中文字符串的比较不是ASCII码，因为就没有，而是将其转换为Unicode编码，再做比较。

示例：

#include <iostream>
using namespace std;
#include <string>


// string字符串的比较
void test05_01() {
	string str1 = "haaaa";
	string str2 = "Haaaa";

	if (str1.compare(str2) == 0)
	{
		cout << "str1 等于 str2" << endl;
	}
	else if (str1.compare(str2) == 1)
	{
		cout << "str1 大于 str2" << endl;
	}
	else if (str1.compare(str2) == -1)
	{
		cout << "str1 小于 str2" << endl;
	}


	// 下面这个是比较常用的
	if (str1.compare(str2) == 0)
	{
		cout << "str1 等于 str2" << endl;
	}
	else 
	{
		cout << "str1 不等于 str2" << endl;
	}
}



int main() {

	test05_01();

	system("pause");
	return 0;
}

3.1.7 string字符存取

string中单个字符存取方式有两种：

1. char& operator[](int n); // 通过[]方式取字符
2. char& at(int n); // 通过at方法获取字符

示例：

#include <iostream>
using namespace std;
#include <string>


/*
	string中单个字符存取方式有两种：
		1. char& operator[](int n);  // 通过[]方式取字符
		2. char& at(int n);  // 通过at方法获取字符
*/
void test06_01() {

	string str = "Hello";

	// 1. 通过[]访问单个字符
	for (int i = 0; i < str.size(); i++)
	{
		cout << str[i] << " ";  // H e l l o
	}
	cout << endl;

	// 2. 通过at方式访问单个字符
	for (int i = 0; i < str.size(); i++)
	{
		cout << str.at(i) << " ";  // H e l l o
	}
	cout << endl;

	// 修改单个字符
	str[0] = 'x';
	str.at(1) = 'Y';
	cout << str << endl;  // xYllo
}


int main() {

	test06_01();

	system("pause");
	return 0;
}

3.1.8 string插入和删除

功能描述：对string字符串进行插入和删除字符操作。

函数原型：

函数重载	含义
string& insert(int pos, const char* s);	插入字符串
string& insert(int pos, const string& str);	插入字符串
string& insert(int pos, int n, char c);	在指定位置插入n个字符c
string& erase(int pos, int n = npos);	删除从Pos开始的n个字符

总结：插入和删除的起始下标都是从0开始。

示例：

#include <iostream>
using namespace std;
#include <string>


/*
	字符串的插入和删除
		1. string& insert(int pos, const char* s);  //插入字符串
		2. string& insert(int pos, const string& str);  //插入字符串
		3. string& insert(int pos, int n, char c);  //在指定位置插入n个字符c
		4. string& erase(int pos, int n = npos);  //删除从Pos开始的n个字符
*/


void test07_01() {
	// 1. string& insert(int pos, const char* s);  //插入字符串
	string str = "Hello";
	str.insert(1, "11111");
	cout << str << endl;  // H11111ello

	// 2. string & insert(int pos, const string & str);  //插入字符串

	// 3. string & insert(int pos, int n, char c);  //在指定位置插入n个字符c

	// 4. string & erase(int pos, int n = npos);  //删除从Pos开始的n个字符
	str.erase(1, 5);
	cout << str << endl;  // Hello
}


int main() {

	test07_01();

	system("pause");
	return 0;
}

3.1.9 string子串

功能描述：从字符串中获取想要的子串。

函数原型：

函数重载	含义
string substr(int pos = 0, int n = npos) const;	返回由pos开始的n个字符组成的字符串

返回一个string

总结：灵活的运用求子串功能，可以在实际开发中获取有效的信息。

示例：

#include <iostream>
using namespace std;
#include <string>


// string截取子串
void test08_01() {
	string str = "abcdefg";
	string sub_str = str.substr(0, 3);
	cout << "str: " << str << endl;  // str: abcdefg
	cout << "sub_str: " << sub_str << endl;  // sub_str: abc
}


// 使用操作
void test08_02() {
	string email = "Leovin@163.com";

	// 从邮件地址中获取用户名信息
	// 先求@在哪里
	int idx = email.find('@');
	if (idx != -1)
	{
		string user_name = email.substr(0, idx);
		cout << "user name: " << user_name << endl;  // user name: Leovin
	}
	else
	{
		cout << "没有有效关键字@" << endl;
	}

	// 求出邮件所属机构名
	// 先求.com所在位置
	int pos = email.rfind(".com");
	if (pos != -1)
	{
		string cooperation_name = email.substr(idx + 1, pos);
		cout << "Cooperation name: " << cooperation_name << endl;  // Cooperation name: 163.com
	}
	else
	{
		cout << "没有有效关键字.com" << endl;
	}
}


int main() {

	test08_01();
	test08_02();

	system("pause");
	return 0;
}

3.2 vector容器

向量容器。

3.2.1 vector基本概念

功能：vector数据结构和数组非常相似，也称为单端数组。

vector与普通数组区别：不同之处在于数组是静态空间，而vector可以动态扩展。

动态扩展：并不是在原空间之后续接新空间，而是找更大的内存空间，然后将原数据拷贝新空间，释放原空间。

因为很有可能后面的内存空间已经被别人用到了，申请不到了。

• front()为vector容器的第一个元素
• back()为vector容器的最后一个元素
• v.begin()为第一个元素的位置
• v.end()为最后一个元素的下一个位置
• v.rend()为第一个元素的前一个位置
• v.rbegin()为最后一个元素的位置
• 我们比较常用的是v.begin()和v.end()

注意：vector容器的迭代器是支持随机访问的迭代器（最强悍的迭代器）。

3.2.2 vector构造函数

功能描述：创建vector容器。

函数原型：

函数重载	含义
vector<T> v;	采用模板实现类实现，默认构造函数
vector(v.begin(), v.end());	将v[ begin(), end() )区间（左闭右开）中的元素拷贝给本身
vector(n, elem);	构造函数将n个elem拷贝给本身
vector(const vector &vec);	拷贝构造函数

总结: vector的多种构造方式没有可比性，灵活使用即可。

示例：

#include <iostream>
using namespace std;
#include <string>
#include <vector>


// vector容器构造
/*
	1. vector<T> v;  //采用模板实现类实现，默认构造函数
	2. vector(v.begin(), v.end());  //将v[ begin(), end() )区间（左闭右开）中的元素拷贝给本身
	3. vector(n, elem);  //构造函数将n个elem拷贝给本身
	4. vector(const vector &vec);  //拷贝构造函数
*/
template <class T>
void print_vector(vector<T>& v) {
	for (typename vector<T>::iterator iter = v.begin(); iter != v.end(); iter++)
	{
		cout << *iter << " ";
	}
	cout << endl;
}


void test01_01() {
	// 1. vector<T> v;  //采用模板实现类实现，默认构造函数
	vector<int> v1;  // 默认构造（无参构造）

	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	print_vector(v1);  // 0 1 2 3 4 5 6 7 8 9


	// 2. vector(v.begin(), v.end());  //将v[ begin(), end() )区间（左闭右开）中的元素拷贝给本身
	vector<int> v2(v1.begin(), v1.end());
	print_vector(v2);  // 0 1 2 3 4 5 6 7 8 9


	// 3. vector(n, elem);  //构造函数将n个elem拷贝给本身
	vector<int> v3(5, 100);
	print_vector(v3);  // 100 100 100 100 100


	// 4. vector(const vector &vec);  //拷贝构造函数
	vector<int> v4(v3);
	print_vector(v4);  // 100 100 100 100 100
}


int main() {

	test01_01();

	system("pause");
	return 0;
}

3.2.3 vector赋值操作

功能描述：给vector容器进行赋值。

函数原型：

函数重载	含义
vector& operator=(const vector &vec);	重载等号操作符
assign(beg, end);	将[beg, end)区间中的数据拷贝赋值给本身
assign(n, elem);	将n个elem拷贝赋值给本身

总结: vector赋值方式比较简单，使用operator=，或者assign都可以

示例：

#include <iostream>
using namespace std;
#include <string>
#include <vector>


// vector容器的赋值操作
/*
	1. vector& operator=(const vector &vec);  //重载等号操作符
	2. assign(beg, end);  //将[beg, end)区间中的数据拷贝赋值给本身
	3. assign(n, elem);  //将n个elem拷贝赋值给本身
*/

template <class T>
void print_vector(vector<T>& vec) {
	for (class vector<T>::iterator iter = vec.begin(); iter != vec.end(); iter++)
	{
		cout << *iter << " ";
	}
	cout << endl;
}


void test_02() {
	vector<int> v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	print_vector(v1);  // 0 1 2 3 4 5 6 7 8 9

	// 1. vector& operator=(const vector &vec);  //重载等号操作符
	vector<int> v2;
	v2 = v1;
	print_vector(v2);  // 0 1 2 3 4 5 6 7 8 9


	// 2. assign(beg, end);  //将[beg, end)区间中的数据拷贝赋值给本身
	vector<int> v3;
	v3.assign(v1.begin(), v1.end());
	print_vector(v3);


	// 3. assign(n, elem);  //将n个elem拷贝赋值给本身
	vector<char> v4;
	v4.assign(10, 'A');
	print_vector(v4);  // A A A A A A A A A A
}


int main() {

	test_02();

	system("pause");
	return 0;
}

3.2.4 vector容量和大小

功能描述：对vector容器的容量和大小操作。

函数原型：

函数重载	含义
empty();	判断容器是否为空
capacity();	容器的容量
size();	返回容器中元素的个数
resize(int num);	重新指定容器的长度为num，用默认构造填充
resize(int num, elem);	重新指定容器的长度为num，用elem填充

在调用 C++ 中的 vector 容器的 resize() 方法时，如果不提供任何值，则会使用默认构造函数来初始化新元素。也就是说，默认值取决于元素类型的默认构造函数。例如，如果元素类型是 int，则新元素将被初始化为 0。如果元素类型是自定义类，则必须提供该类的默认构造函数。如果提供了值，则使用提供的值来初始化新元素。

对于resize(int num);而言：

• 如果容器变长，则以默认值填充新位置
• 如果容器变短，则末尾超出容器长度的元素被删除

对于resize(int num, elem);而言：

• 如果器变长，则以elem值填充新位置
• 如果容器变短，则末尾超出容器长度的元素被删除

示例：

#include <iostream>
using namespace std;
#include <string>
#include <vector>


// vector容器的容量和大小
/*
	1. empty();  //判断容器是否为空
	2. capacity();  //容器的容量
	3. size();  //返回容器中元素的个数
	4. resize(int num);  //重新指定容器的长度为num
	5. resize(int num, elem);  //重新指定容器的长度为num，用elem填充
*/
template <typename T>
void print_vec(vector<T>& vec) {
	for (typename vector<T>::iterator iter = vec.begin(); iter != vec.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;
}


void test03() {
	vector<int> v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	print_vec(v1);  // 0 1 2 3 4 5 6 7 8 9


	// 1. empty();  //判断容器是否为空
	if (v1.empty())
	{
		cout << "v1为空" << endl;  // v1不为空
	}
	else
	{
		cout << "v1不为空" << endl;
	}


	// 	2. capacity();  //容器的容量
	cout << "v1的容量为: " << v1.capacity() << endl;  // v1的容量为: 13


	// 3. size();  //返回容器中元素的个数
	cout << "v1的元素个数为: " << v1.size() << endl;  // v1的元素个数为: 10


	// 4. resize(int num);  //重新指定容器的长度为num
	v1.resize(15);  // 如果重新指定的过长，默认用0填充新的位置
	print_vec(v1);  // 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0

	// 5. resize(int num, elem);  //重新指定容器的长度为num，用elem填充
	v1.resize(20, 100);
	print_vec(v1);  // 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 100 100 100 100 100

	v1.resize(5);  // 如果重新指定的比原来短了，超出的部分会删掉
	print_vec(v1);  // 0 1 2 3 4

	vector<string> v2;
	v2.push_back("第一句话");
	v2.push_back("第二句话");
	v2.push_back("第三句话");
	v2.push_back("第四句话");
	v2.push_back("第五句话");
	print_vec(v2);

	v2.resize(10);  // 对于string数据类型而言，默认构造什么都没有，所以什么都没有往里面添加，但capacity和size会变
	cout << "v2.capacity(): " << v2.capacity() << endl;  // 10
	cout << "v2.size(): " << v2.size() << endl;  // 10
	print_vec(v2);
	// 第一句话 第二句话 第三句话 第四句话 第五句话

	v2.resize(15, "AAA");
	print_vec(v2);
	// 第一句话 第二句话 第三句话 第四句话 第五句话      AAA AAA AAA AAA AAA
}


int main() {

	test03();

	system("pause");
	return 0;
}

3.2.5 vector插入和删除

功能描述：对vector容器进行插入、删除操作。

函数原型：

函数重载	含义
push_back(elem);	尾部插入元素elem
pop_back();	删除最后一个元素
insert(const_iterator pos, elem);	迭代器指向位置pos插入元素elem
insert(const_iterator pos, int count, elem);	迭代器指向位置pos插入count个elem元素
erase(const_iterator pos);	删除迭代器指向的元素
erase(const_iterator start, const_iterator end);	删除迭代器从start到end之间的元素
clear();	删除容器中所有元素

注意：const_iterator pos这是一个迭代器对象，即vector<数据类型>::iterator，一般我们可以传入.begin(), .end()，+ int也是可以的。

总结：

1. 尾插 — push_back
2. 尾删 — pop_back
3. 插入 — insert(位置迭代器)
4. 删除 — erase(位置迭代器)
5. 清空 — clear

示例:

#include <iostream>
using namespace std;
#include <string>
#include <vector>


// vector容器的插入和删除
/*
	1. push_back(elem);  // 尾部插入元素elem
	2. pop_back();  // 删除最后一个元素
	3. insert(const_iterator pos, elem);  // 迭代器指向位置pos插入元素elem
	4. insert(const_iterator pos, int count, elem);  // 迭代器指向位置pos插入count个elem元素
	5. erase(const_iterator pos);  // 删除迭代器指向的元素
	6. erase(const_iterator start, const_iterator end);  // 删除迭代器从start到end之间的元素
	7. clear();  // 删除容器中所有元素
*/
template <typename T>
void print_vec(vector<T>& vec) {
	for (typename vector<T>::iterator iter = vec.begin(); iter != vec.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;
}


void test04() {
	vector<int> v1;
	for (int i = 1; i <= 5; i++)
	{
		// 1. push_back(elem);  // 尾部插入元素elem
		v1.push_back(i * 10);
	}
	print_vec(v1);  // 10 20 30 40 50


	// 2. pop_back();  // 删除最后一个元素
	v1.pop_back();
	print_vec(v1);  // 10 20 30 40


	// 3. insert(const_iterator pos, elem);  // 迭代器指向位置pos插入元素elem
	v1.insert(v1.begin(), 100);
	print_vec(v1);  // 100 10 20 30 40
	v1.insert(v1.begin() + 3, 200);
	print_vec(v1);  // 100 10 20 200 30 40


	// 4. insert(const_iterator pos, int count, elem);  // 迭代器指向位置pos插入count个elem元素
	v1.insert(v1.begin(), 2, 1000);
	print_vec(v1);  // 1000 1000 100 10 20 200 30 40


	// 5. erase(const_iterator pos);  // 删除迭代器指向的元素
	v1.erase(v1.begin());
	print_vec(v1);  // 1000 100 10 20 200 30 40


	// 6. erase(const_iterator start, const_iterator end);  // 删除迭代器从start到end之间的元素
	v1.erase(v1.begin(), v1.end() - 3);
	print_vec(v1);  // 200 30 40


	// 7. clear();  // 删除容器中所有元素
	v1.clear();
	print_vec(v1);  // 
}


int main() {

	test04();

	system("pause");
	return 0;
}

3.2.6 vector数据存取

功能描述：对vector中的数据的存取操作。

函数原型：

函数重载	含义
at(int idx);	返回索引idx所指的数据
operator[];	返回索引idx所指的数据
front();	返回容器中第一个数据元素
back();	返回容器中最后一个数据元素

总结：

• 除了用迭代器获取vector容器中元素，[]和at也可以
• front返回容器第一个元素
• back返回容器最后一个元素

示例：

#include <iostream>
using namespace std;
#include <string>
#include <vector>


// vector容器的数据存取
/*
	1. at(int idx);  // 返回索引idx所指的数据
	2. operator[];  // 返回索引idx所指的数据
	3. front();  // 返回容器中第一个数据元素
	4. back();  // 返回容器中最后一个数据元素
*/
void test05() {
	vector<int> vec;
	for (int i = 0; i < 10; i++)
	{
		vec.push_back(i);
	}

	// 利用之前学的for循环进行遍历
	for (vector<int>::iterator iter = vec.begin(); iter != vec.end(); iter++)
	{
		cout << *iter << " ";
	}
	cout << endl;  // 0 1 2 3 4 5 6 7 8 9
	

	// 1. at(int idx);  // 返回索引idx所指的数据
	for (int i = 0; i < vec.size(); i++)
	{
		cout << vec.at(i) << " ";
	}
	cout << endl;  // 0 1 2 3 4 5 6 7 8 9


	// 2. operator[];  // 返回索引idx所指的数据
	for (int i = 0; i < vec.size(); i++)
	{
		cout << vec[i] << " ";
	}
	cout << endl;  // 0 1 2 3 4 5 6 7 8 9


	// 3. front();  // 返回容器中第一个数据元素
	cout << vec.front() << endl;  // 0


	// 4. back();  // 返回容器中最后一个数据元素
	cout << vec.back() << endl;  // 9
}


int main() {

	test05();

	system("pause");
	return 0;
}

3.2.7 vector互换容器

功能描述：实现两个容器内元素进行互换。

函数原型：

函数重载	含义
swap(vec);	将vec与本身的元素互换

.swap的实际用途：巧用swap可以收缩内存空间。

总结：swap可以使两个容器互换，可以达到实用的收缩内存效果。

示例：

#include <iostream>
using namespace std;
#include <string>
#include <vector>


// vector容器的互换
/*
	swap(vec);  // 将vec与本身的元素互换
		1. 基本使用
		2. 实际用途：巧用swap可以收缩内存空间
*/
template <class T>
void print_vec(vector<T>& vec) {
	for (int i = 0; i < vec.size(); i++)
	{
		cout << vec[i] << " ";
	}
	cout << endl;
}


// 1. 基本使用
void test06_01() {
	vector<int> vec1;
	for (int i = 0; i < 10; i++)
	{
		vec1.push_back(i);
	}

	vector<int> vec2;
	for (int i = 9; i >= 0; i--)
	{
		vec2.push_back(i);
	}
	cout << "交换前: " << endl;
	print_vec(vec1);  // 0 1 2 3 4 5 6 7 8 9
	print_vec(vec2);  // 9 8 7 6 5 4 3 2 1 0

	cout << "交换后: " << endl;
	vec1.swap(vec2);
	print_vec(vec1);  // 9 8 7 6 5 4 3 2 1 0
	print_vec(vec2);  // 0 1 2 3 4 5 6 7 8 9
}


// 2. 实际用途：巧用swap可以收缩内存空间
void test06_02() {
	vector<int> vec;
	for (int i = 0; i < 100000; i++)
	{
		vec.push_back(i);
	}

	cout << "vec.capacity: " << vec.capacity() << endl;  // 138255
	cout << "vec.size: " << vec.size() << endl;  // 100000

	vec.resize(3);  // 重新指定大小
	cout << "vec.capacity: " << vec.capacity() << endl;  // 138255
	cout << "vec.size: " << vec.size() << endl;  // 3

	// resize之后，capacity并没有减少，会造成内存空间的浪费

	// 巧用swap收缩内存
	vector<int>(vec).swap(vec);
	cout << "vec.capacity: " << vec.capacity() << endl;  // 3
	cout << "vec.size: " << vec.size() << endl;  // 3

	/*
		vector<int>(vec)这是一个匿名对象，并通过vec进行拷贝对象
			vector<int> tmp(vec); 这是拷贝构造
			如果不写变量名，就是匿名对象
		.swap(vec);  // 让匿名对象和vec进行交换

		当这行执行完毕后，匿名对象就被系统回收了。
	*/
}


int main() {

	test06_01();
	test06_02();

	system("pause");
	return 0;
}

3.2.8 vector预留空间

功能描述：减少vector在动态扩展容量时的扩展次数。

函数原型：

函数重载	含义
reserve(int len);	容器预留len个元素长度，预留位置不初始化，元素不可访问

调用reserve方法后，系统会给调用这个方法的vector容器分配内存，但内存上的数据没有初始化，因此不可访问。

总结：如果数据量较大，可以一开始利用reserve方法预留空间，减少资源和算力的浪费。

示例：

#include <iostream>
using namespace std;
#include <string>
#include <vector>


// vector容器的互换
/*
	reserve(int len);  // 容器预留len个元素长度，预留位置不初始化，元素不可访问
*/
void test07_01() {
	vector<int> vec;

	/*
		因为vector容器是动态扩展的，因此在插入这10万个数的过程中，
		会不断的扩展自己的内存占用，那么究竟分配了多少次内存？
	*/
	int count = 0;  // 统计开辟次数
	int* ptr = NULL;
	for (int i = 0; i < 100000; i++) {
		vec.push_back(i);

		if (ptr != &vec[0])
		{
			ptr = &vec[0];
			count += 1;
		}
	}

	cout << "开辟内存次数: " << count << "次" << endl;  // 开辟内存次数: 30次
}


void test07_02() {
	/*
		在上一个测试中可以看到，存放10万量级的数据，需要系统不断的开辟30次内存空间，这还是非常麻烦的。

		如何解决这个问题呢？
		我们可以利用.reserve()方法预留空间，告诉系统，这个vector容器需要多大的内存空间
	*/
	vector<int> vec;
	vec.reserve(100000);
	
	int count = 0;
	int* ptr = NULL;
	for (int i = 0; i < 100000; i++)
	{
		vec.push_back(i);
		if (ptr != &vec[0])
		{
			ptr = &vec[0];
			count += 1;
		}
	}
	cout << "开辟内存次数: " << count << "次" << endl;  // 开辟内存次数: 1次
}


int main() {

	test07_01();
	test07_02();

	system("pause");
	return 0;
}

3.3 deque容器

Deque是 Double Ended Queue 的简称，习惯上称之为双端队列。

Deque的发音为：/dɛk/

3.3.1 deque容器基本概念

功能：双端数组，可以对头端进行插入删除操作。

deque与vector区别：

1. vector对于头部的插入删除效率低，数据量越大，效率越低
2. deque相对而言，对头部的插入删除速度会比vector快
3. vector访问元素时的速度会比deque快，这和两者内部实现有关

vector只能进行尾插和尾删（也可以在任意位置上进行插入）

deque内部工作原理：deque内部有个中控器，维护每段缓冲区中的内容，缓冲区中存放真实数据。

中控器维护的是每个缓冲区的地址，使得使用deque时像一片连续的内存空间。

有中间商赚差价，所以deque访问元素的速度不如vector快😂

• deque容器的迭代器也是支持随机访问的。

3.3.2 deque构造函数

功能描述：deque容器构造。

函数原型：

函数重载	含义
deque<T> deqT;	默认构造形式
deque(beg, end);	构造函数将[beg, end)（左闭右开）区间中的元素拷贝给本身
deque(n, elem);	构造函数将n个elem拷贝给本身
deque(const deque &deq);	拷贝构造函数

重点：

template <class T>
void print_deque(const deque<T>& deq) {  // 添加const防止修改
	// 因为形参是const，所以迭代器应该是只读的迭代器，即const_iterator，而不是iterator
	for (typename deque<T>::const_iterator iter = deq.begin(); iter !=deq.end(); iter++)
	{
		cout << *iter << " ";
	}
	cout << endl;
}

示例：

#include <iostream>
using namespace std;
#include <string>
#include <deque>


// deque容器的构造函数
/*
	1. deque<T> deqT;  // 默认构造形式
	2. deque(beg, end);  // 构造函数将[beg, end)（左闭右开）区间中的元素拷贝给本身
	3. deque(n, elem);  // 构造函数将n个elem拷贝给本身
	4. deque(const deque &deq);  // 拷贝构造函数
*/
template <class T>
void print_deque(const deque<T>& deq) {  // 添加const防止修改
	// 因为形参是const，所以迭代器应该是只读的迭代器，即const_iterator，而不是iterator
	for (typename deque<T>::const_iterator iter = deq.begin(); iter !=deq.end(); iter++)
	{
		cout << *iter << " ";
	}
	cout << endl;
}


void test01() {
	// 1. deque<T> deqT;  // 默认构造形式
	deque<int> d1;
	for (int i = 0; i < 10; i++)
	{
		d1.push_back(i);
	}
	print_deque(d1);  // 0 1 2 3 4 5 6 7 8 9


	// 2. deque(beg, end);  // 构造函数将[beg, end)（左闭右开）区间中的元素拷贝给本身
	deque<int> d2(d1.begin(), d1.end() - 3);
	print_deque(d2);  // 0 1 2 3 4 5 6


	// 3. deque(n, elem);  // 构造函数将n个elem拷贝给本身
	deque<string> d3(5, "Hello");
	print_deque(d3);  // Hello Hello Hello Hello Hello


	// 4. deque(const deque & deq);  // 拷贝构造函数
	deque<string> d4(d3);
	print_deque(d4);  // Hello Hello Hello Hello Hello
}


int main() {

	test01();

	system("pause");
	return 0;
}

3.3.3 deque赋值操作

功能描述：给deque容器进行赋值。

函数原型：

函数重载	含义
deque& operator=(const deque &deq);	重载等号操作符
assign(beg, end);	将[beg, end)（左闭右开）区间中的数据拷贝赋值给本身
assign(n, elem);	将n个elem拷贝赋值给本身

总结：deque赋值操作也与vector相同，需熟练掌握。

示例：

#include <iostream>
using namespace std;
#include <string>
#include <deque>


// deque容器的赋值操作
/*
	1. deque& operator=(const deque &deq);  // 重载等号操作符
	2. assign(beg, end);  // 将[beg, end)（左闭右开）区间中的数据拷贝赋值给本身
	3. assign(n, elem);  // 将n个elem拷贝赋值给本身
*/
template <typename T>
void print_deque(const deque<T>& deq) {
	for (typename deque<T>::const_iterator iter = deq.begin(); iter != deq.end(); iter++)
	{
		cout << *iter << " ";
	}
	cout << endl;
}


void test() {
	deque<int> d1;
	for (int i = 0; i < 10; i++)
	{
		d1.push_back(i);
	}
	print_deque(d1);  // 0 1 2 3 4 5 6 7 8 9
	

	// 1. deque& operator=(const deque &deq);  // 重载等号操作符
	deque<int> d2;
	d2 = d1;
	print_deque(d2);  // 0 1 2 3 4 5 6 7 8 9


	// 2. assign(beg, end);  // 将[beg, end)（左闭右开）区间中的数据拷贝赋值给本身
	deque<int> d3;
	d3.assign(d1.begin() + 2, d1.end() - 1);
	print_deque(d3);  // 2 3 4 5 6 7 8


	// 3. assign(n, elem);  // 将n个elem拷贝赋值给本身
	deque<char> d4;
	d4.assign(5, 'A');
	print_deque(d4);  // A A A A A
}


int main() {

	test();  // 0 1 2 3 4 5 6 7 8 9

	system("pause");
	return 0;
}

3.3.4 deque大小操作

功能描述：对deque容器的大小进行操作。

函数原型：

函数重载	含义
deque.empty();	判断容器是否为空
deque.size();	返回容器中元素的个数
deque.resize(num);	重新指定容器的长度为num
deque.resize(num, elem);	重新指定容器的长度为num

总结：deque大小操作也与vector相同，需熟练掌握。

deque容器和vector容器的区别：

• vector容器有capacity()方法，而deque容器是没有这个方法的，因为二者的本质结构不同

示例：

#include <iostream>
using namespace std;
#include <string>
#include <deque>


// deque容器的赋值操作
/*
	1. deque.empty();  // 判断容器是否为空
	2. deque.size();  // 返回容器中元素的个数
	3. deque.resize(num);  // 重新指定容器的长度为num
	4. deque.resize(num, elem);  // 重新指定容器的长度为num
*/
template <typename T>
void print_deque(const deque<T>& deq) {
	for (typename deque<T>::const_iterator iter = deq.begin(); iter != deq.end(); iter++)
	{
		cout << *iter << " ";
	}
	cout << endl;
}


void test() {
	deque<int> deq;
	for (int i = 0; i < 10; i++)
	{
		deq.push_back(i);
	}
	print_deque(deq);  // 0 1 2 3 4 5 6 7 8 9

	// 1. deque.empty();  // 判断容器是否为空
	if (deq.empty())
	{
		cout << "容器为空" << endl;
	}
	else
	{
		cout << "容器不为空" << endl;
	}


	// 2. deque.size();  // 返回容器中元素的个数
	cout << "deque.size(): " << deq.size() << endl;  // 10


	// 3. deque.resize(num);  // 重新指定容器的长度为num
	deq.resize(5);
	cout << "deque.size(): " << deq.size() << endl;  // 5
	print_deque(deq);  // 0 1 2 3 4
	deq.resize(10);
	print_deque(deq);  // 0 1 2 3 4 0 0 0 0 0


	// 4. deque.resize(num, elem);  // 重新指定容器的长度为num
	deq.resize(15, 999);
	cout << "deque.size(): " << deq.size() << endl;  // 10
	print_deque(deq);  // 0 1 2 3 4 0 0 0 0 0 999 999 999 999 999
}


int main() {

	test();

	system("pause");
	return 0;
}

3.3.5 deque插入和删除

功能描述：向deque容器中插入和删除数据。

1. 两端插入操作

函数原型：

函数重载	含义
push_back(elem);	在容器尾部添加一个数据
push_front(elem);	在容器头部插入一个数据
pop_back();	删除容器最后一个数据
pop_front();	删除容器第一个数据

2. 指定位置操作

函数原型：

函数重载	含义
insert(pos, elem);	在pos位置插入一个elem元素的拷贝，返回新数据的位置（返回值类型是迭代器）
insert(pos, n, elem);	在pos位置插入n个elem教据，无返回值
insert(pos, beg, end);	在pos位置插入[beg, end)区间（左闭右开）的数据，无返回值
clear();	清空容器的所有数据
erase(beg, end);	删除[beg, end)区间（左闭右开）的数据，返回下一个数据的位置
erase(pos);	删除pos位置的数据，返回下一个数据的位置（返回值类型是迭代器）

总结：

• 插入和删除提供的位置是迭代器!（传入固定数字是不行的，因为指针的位置不是从0开始的😂）
• 尾插 — push_back
• 尾删 — pop_back
• 头插 — push_front
• 头删 — pop_front

示例：

#include <iostream>
using namespace std;
#include <string>
#include <deque>


// deque容器的删除与插入操作
/*
两端插入操作：
	1. push_back(elem);  // 在容器尾部添加一个数据
	2. push_front(elem);  // 在容器头部插入一个数据
	3. pop_back();  // 删除容器最后一个数据
	4. pop_front();  // 删除容器第一个数据

指定位置操作：
	1. insert(pos, elem);  // 在pos位置插入一个elem元素的拷贝，返回新数据的位置（返回值类型是迭代器）
	2. insert(pos, n, elem);  // 在pos位置插入n个elem教据，无返回值
	3. insert(pos, beg, end);  // 在pos位置插入[beg, end)区间（左闭右开）的数据，无返回值
	4. clear();  // 清空容器的所有数据
	5. erase(beg, end);  // 删除[beg, end)区间（左闭右开）的数据，返回下一个数据的位置（返回值类型是迭代器）
	6. erase(pos);  // 删除pos位置的数据，返回下一个数据的位置
*/
template <typename T>
void print_deque(const deque<T>& deq) {
	for (typename deque<T>::const_iterator iter = deq.begin(); iter != deq.end(); iter++)
	{
		cout << *iter << " ";
	}
	cout << endl;
}


void test01() {
	deque<int> deq;


	// 1. push_back(elem);  // 在容器尾部添加一个数据
	deq.push_back(10);
	deq.push_back(20);
	print_deque(deq);  // 10 20


	// 2. push_front(elem);  // 在容器头部插入一个数据
	deq.push_front(100);
	deq.push_front(200);
	print_deque(deq);  // 200 100 10 20


	// 3. pop_back();  // 删除容器最后一个数据
	deq.pop_back();
	print_deque(deq);  // 200 100 10


	// 4. pop_front();  // 删除容器第一个数据
	deq.pop_front();
	print_deque(deq);  // 100 10
}


void test02() {
	deque<int> deq;
	for (int i = 1; i < 11; i++)
	{
		deq.push_back(i);
	}
	print_deque(deq);  // 1 2 3 4 5 6 7 8 9 10


	// 1. insert(pos, elem);  // 在pos位置插入一个elem元素的拷贝，返回新数据的位置（返回值类型是迭代器）
	deque<int>::iterator insert_pos = deq.insert(deq.begin(), 100);
	print_deque(deq);  // 100 1 2 3 4 5 6 7 8 9 10
	cout << "insert_pos下的数据: " << *insert_pos << endl;  // 100


	// 2. insert(pos, n, elem);  // 在pos位置插入n个elem教据，无返回值
	deq.insert(deq.begin() + 1, 2, 300);
	print_deque(deq);  // 100 300 300 1 2 3 4 5 6 7 8 9 10


	// 3. insert(pos, beg, end);  // 在pos位置插入[beg, end)区间（左闭右开）的数据，无返回值
	deque<int> tmp_deq(deq.begin(), deq.begin()+3);
	print_deque(tmp_deq);  // 100 300 300

	deq.insert(deq.begin() + 3, tmp_deq.begin(), tmp_deq.end());
	print_deque(deq);  // 100 300 300 100 300 300 1 2 3 4 5 6 7 8 9 10


	// 4. clear();  // 清空容器的所有数据
	tmp_deq.clear();
	cout << tmp_deq.size() << endl;  // 0


	// 5. erase(beg, end);  // 删除[beg, end)区间（左闭右开）的数据，返回下一个数据的位置
	deq.erase(deq.begin(), deq.begin() + 6);
	print_deque(deq);  // 1 2 3 4 5 6 7 8 9 10


	// 6. erase(pos);  // 删除pos位置的数据，返回下一个数据的位置（返回值类型是迭代器）
	deque<int>::iterator return_pos = deq.erase(deq.begin());
	print_deque(deq);  // 2 3 4 5 6 7 8 9 10
	cout << "return_pos下的数据: " << *return_pos << endl;  // 2
}


int main() {

	test01();
	test02();

	system("pause");
	return 0;
}

3.3.6 deque数据存取

功能描述：对deque中的数据的存取操作。

函数原型：

函数重载	含义
at(int idx);	返回索引idx所指的数据
operator[];	返回索引idx所指的数据
front();	返回容器中第一个数据元素
back();	返回容器中最后一个数据元素

总结：deque取存操作也与vector相同，需熟练掌握。

示例：

#include <iostream>
using namespace std;
#include <string>
#include <deque>


// deque容器的数据存取
/*
	1. at(int idx);  // 返回索引idx所指的数据
	2. operator[];  // 返回索引idx所指的数据
	3. front();  // 返回容器中第一个数据元素
	4. back();  // 返回容器中最后一个数据元素
*/
void test() {
	deque<int> deq;
	deq.push_back(10);
	deq.push_back(20);
	deq.push_back(30);
	deq.push_front(100);
	deq.push_front(200);
	deq.push_front(300);

	// 1. at(int idx);  // 返回索引idx所指的数据
	for (int i = 0; i < deq.size(); i++)
	{
		cout << deq.at(i) << " ";
	}
	cout << endl;  // 300 200 100 10 20 30


	// 2. operator[];  // 返回索引idx所指的数据
	for (int i = 0; i < deq.size(); i++)
	{
		cout << deq[i] << " ";
	}
	cout << endl;  // 300 200 100 10 20 30


	// 3. front();  // 返回容器中第一个数据元素
	cout << "deq.front(): " << deq.front() << endl;  // 300


	// 4. back();  // 返回容器中最后一个数据元素
	cout << "deq.back(): " << deq.back() << endl;  // 30
}


int main() {

	test();

	system("pause");
	return 0;
}

3.3.7 deque排序

功能描述：利用算法实现对deque容器进行排序。

算法：sort(iterator beg, iterator end) // 对beg和end区间内元素进行排序

注意：

1. 在使用sort()函数前需要引入<algorithm>头文件
2. sort()函数默认为升序排序
3. 对于支持随机访问迭代器的容器，都可以利用sort()函数直接对其进行排序（目前位置，vector容器和deque容器都可以使用sort()函数排序）

示例：

#include <iostream>
using namespace std;
#include <string>
#include <deque>
#include <algorithm>


// deque容器的排序
/*
	sort(iterator beg, iterator end);  // 对beg和end区间内元素进行排序
*/
template <typename T>
void print_deque(const deque<T>& deq) {
	for (typename deque<T>::const_iterator iter = deq.begin(); iter != deq.end(); iter++)
	{
		cout << *iter << " ";
	}
	cout << endl;
}


void test() {
	deque<int> deq;
	deq.push_back(10);
	deq.push_back(20);
	deq.push_back(30);
	deq.push_front(100);
	deq.push_front(200);
	deq.push_front(300);

	print_deque(deq);  // 300 200 100 10 20 30


	// 排序：sort(iterator beg, iterator end); 
	sort(deq.begin(), deq.end());
	print_deque(deq);  // 10 20 30 100 200 300
}


int main() {

	test();

	system("pause");
	return 0;
}

3.4案例：评委打分

3.4.1 案例描述

有5名选手ABCDE，10个评委分别对每一名选手打分，去除最高分，去除评委中最低分，取平均分。

3.4.2 实现步骤

1. 创建五名选手，放到vector容器中
2. 遍历vector容器，取出每一个选手，执行for循环，可以把10个评分打分存到deque容器中
3. sort()算法对deque容器中分数排序，去除最高和最低分
4. deque容器遍历一遍，累加总分
5. 获取平均分

使用deque容器是因为它对头和尾的操作支持比较好

示例代码：

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <deque>
#include <algorithm>


/*
	有5名选手ABCDE，10个评委分别对每一名选手打分，去除最高分，去除评委中最低分，取平均分。
*/
class Person {
public:
	Person() {}
	Person(string name, int score) {
		this->name = name;
		this->score = score;
	}
	~Person() {}

public:
	string get_name() {
		return this->name;
	}
	int get_score() {
		return this->score;
	}

	void set_name(string name) {
		this->name = name;
	}
	
	void set_score(int score) {
		this->score = score;
	}

private:
	string name;
	int score;
};


void create_player(vector<Person>& vec) {
	string name_seed = "ABCDE";
	for (int i = 0; i < 5; i++)
	{
		string name = "Player_";
		name += name_seed[i];
		int score = 0;

		Person p(name, score);

		// 将创建的Person对象放到vector容器中
		vec.push_back(p);
	}
}


void set_score(vector<Person>& vec) {
	for (vector<Person>::iterator iter = vec.begin(); iter != vec.end(); iter++)
	{
		// 将评委的分数放入deque容器中
		deque<int> deq;
		for (int i = 0; i < 10; i++)
		{
			int score = rand() % 41 + 60;  // 60 ~ 100
			deq.push_back(score);
		}

		// 先对deque容器进行排序，再取出最高分和最低分
		sort(deq.begin(), deq.end());
		deq.pop_back();  // 尾删
		deq.pop_front();  // 头删

		//取平均分
		int sum = 0;
		for (deque<int>::iterator de_iter = deq.begin(); de_iter != deq.end(); de_iter++)
		{
			sum += *de_iter;
		}
		int avg = sum / deq.size();

		// 将平均分赋值给Player
		iter->set_score(avg);
	}
}


int main() {
	// 设置随机种子
	srand(time(NULL));

	// 1. 创建5名选手
	vector<Person> vec;  // 存放选手的容器
	create_player(vec);


	// 2. 给5名选手打分
	set_score(vec);


	// 3. 显示最后得分
	for (vector<Person>::iterator iter = vec.begin(); iter != vec.end(); iter++) {
		cout << "Name: " << iter->get_name() << "\t Average score: " << iter->get_score() << endl;
	}

	/*
		Name: Player_A   Average score: 83
		Name: Player_B   Average score: 86
		Name: Player_C   Average score: 76
		Name: Player_D   Average score: 79
		Name: Player_E   Average score: 81
	*/

	system("pause");
	return 0;
}

3.5 stack容器

3.5.1 stack基本概念

概念：stack是一种先进后出(First In Last Out, FILO)的数据结构，它只有一个出口。

栈中只有顶端的元素才可以被外界使用，因此栈不允许有遍历行为。

• 栈可以判断容器是否为空吗？ —— 可以

• 栈可以返回元素个数吗？ —— 可以（stack这个类在内部记录了，所以可以知道）

• 入栈 — push

• 出栈 — pop

3.5.2 stack常用接口

功能描述：栈容器常用的对外接口。

函数原型：

性质	函数重载	含义
构造函数	stack<T> stk;	stack采用模板类实现，stack对象的默认构造形式
构造函数	stack(const stack& stk);	拷贝构造函数
赋值操作	stack& operator=(const stack& stk);	重载等号操作符
数据存取	push(elem);	向栈顶添加元素
数据存取	pop();	从栈顶移除第一个元素
数据存取	top();	返回栈顶元素
大小操作	empty();	判断堆栈是否为空
大小操作	size();	返回栈的大小

总结：常用的接口如下

• 入栈 — push()
• 出栈 — pop()
• 返回栈顶 — top()
• 判断栈是否为空 — empty()
• 返回栈大小 — size()

示例：

#include <iostream>
using namespace std;
#include <string>
#include <stack>

// 栈stack容器
/*
	1. 构造函数：stack<T> stk;  // stack采用模板类实现，stack对象的默认构造形式
	2. 构造函数：stack(const stack& stk);  // 拷贝构造函数
	3. 赋值操作：stack& operator=(const stack& stk);  // 重载等号操作符
	4. 数据存取：push(elem);  // 向栈顶添加元素
	5. 数据存取：pop();  // 从栈顶移除第一个元素
	6. 数据存取：top();  // 返回栈顶元素
	7. 大小操作：empty();  // 判断堆栈是否为空
	8. 大小操作：size();  // 返回栈的大小
*/
void test() {
	// 1. 构造函数：stack<T> stk;  // stack采用模板类实现，stack对象的默认构造形式
	stack<int> stk;

	// 入栈
	for (int i = 1; i < 6; i++)
	{
		stk.push(i * 10);
	}
	cout << "栈的大小: " << stk.size() << endl;

	// 只要栈不为空，查看栈顶，并且执行出栈操作
	while (!stk.empty())
	{
		// 查看栈顶元素
		cout << "栈顶元素为: " << stk.top() << endl;

		// 出栈
		stk.pop();
	}
	cout << "栈的大小: " << stk.size() << endl;

	/*
		栈的大小: 5
		栈顶元素为: 50
		栈顶元素为: 40
		栈顶元素为: 30
		栈顶元素为: 20
		栈顶元素为: 10
		栈的大小: 0
	*/
}


int main() {

	test();

	system("pause");
	return 0;
}

3.6 queue容器

3.6.1 queue基本概念

概念：Queue是一种先进先出(First In First Out，FIFO)的数据结构，它有两个出口。

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

3.6.2 queue常用接口

功能描述：栈容器常用的对外接口。

函数原型：

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

总结：常用接口如下

• 入队 — push()
• 出队 — pop()
• 返回队头元素 — front()
• 返回队尾元素 — back()
• 判断队是否为空 — empty()
• 返回队列大小 — size()

示例：

#include <iostream>
using namespace std;
#include <string>
#include <queue>

// 队列queue容器
/*
	1. 构造函数：queue<T> que;  // queue采用模板类实现，queue对象的默认构造形式
	2. 构造函数：queue(const queue& que);  // 拷贝构造函数
	3. 赋值操作：queue& operator=(const queue& que);  // 重载等号操作符
	4. 数据存取：push(elem);  // 往队尾添加元素
	5. 数据存取：pop();  // 从队头移除第一个元素
	6. 数据存取：back();  // 返回最后一个元素
	7. 数据存取：front();  // 返回第一个元素
	8. 大小操作：empty();  // 判断堆栈是否为空
	9. 大小操作：size();  // 返回栈的大小
*/
class Person {
public:
	Person(string name, int age) {
		this->name = name;
		this->age = age;
	}

public:
	string get_name() {
		return this->name;
	}
	int get_age() {
		return this->age;
	}
	void set_name(string name) {
		this->name = name;
	}
	void set_age(int age) {
		this->age = age;
	}

private:
	string name;
	int age;
};


void test() {
	queue<Person> que;
	Person p1("张三", 20);
	Person p2("李四", 30);
	Person p3("王五", 35);
	Person p4("赵六", 40);

	que.push(p1);
	que.push(p2);
	que.push(p3);
	que.push(p4);

	cout << "que.size: " << que.size() << endl;

	while (!que.empty())
	{
		cout << "[队头] Name: " << que.front().get_name() << "Age: " << que.back().get_age() << endl;

		// 为了能看到下一个元素，出队
		que.pop();
	}
	cout << "que.size: " << que.size() << endl;

	/*
		que.size: 4
		[队头]  Name: 张三      Age: 40
		[队头]  Name: 李四      Age: 40
		[队头]  Name: 王五      Age: 40
		[队头]  Name: 赵六      Age: 40
		que.size: 0
	*/
}


int main() {

	test();

	system("pause");
	return 0;
}

3.7 list容器

问：C++中的list和Python中的list是一回事吗？
答：虽然它们都叫做list，但是C++中的list和Python中的list是不同的数据结构。

• 在Python中，list是一种动态数组（dynamic array），它可以存储任意类型的数据，而且大小可以动态地调整。Python的list支持随机访问，也就是说可以通过下标访问任意位置的元素，并且支持切片操作、迭代等常见操作。
• 而在C++中，list是一种双向链表（doubly linked list），它也可以存储任意类型的数据，但是不支持随机访问，只能通过迭代器（iterator）访问元素。C++的list支持高效的插入和删除操作，但是在访问元素时效率较低，因为需要从头或尾开始遍历链表。

因此，虽然它们都叫做list，但是它们的实现方式和使用方法有很大的不同。

Python中list是列表；而C++中list是双向链表！

3.7.1 list基本概念

功能：将数据进行链式存储。
链表（list）是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的。

链表的组成：链表由一系列结点组成。

结点的组成：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

链表的优点：

1. 可以对任意位置进行快速插入或删除元素。

链表的缺点：

1. list的遍历速度没有数组array快（array是连续的内存空间）
2. list占用空间比array大（除了数据外要一个指针）

---

STL中的链表是一个双向循环链表，如下图所示：

• 双向：即记录了下一个节点的地址，也记录了上一个节点的地址
• 循环：最后一个节点的next之前头结点的地址；头结点的prev指向最后一个节点的地址

由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于双向迭代器。

• list的优点：
  • 采用动态存储分配，不会造成内存浪费和溢出
  • 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
• list的缺点：
  • 链表灵活，但是空间(指针域)和时间(遍历)额外耗费较大

list有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的。

在C++中，list容器的插入和删除操作不会造成原有list迭代器的失效，这是因为list容器的元素在内存中是通过双向链表连接起来的，每个元素都有指向前一个元素和后一个元素的指针。当进行插入或删除操作时，只需要修改相应元素的指针，不会涉及到其他元素的内存位置，因此不会造成迭代器的失效。而在vector容器中，由于元素在内存中是连续存储的，当进行插入或删除操作时，可能会导致其他元素的内存位置发生改变，从而使得迭代器失效。因此，在vector容器中进行插入或删除操作时需要格外小心，以避免迭代器失效的问题。

总结：STL中list和vector是两个最常被使用的容器，各有优缺点。

---

在C++中，动态分配内存的容器包括：

• vector：动态分配连续的内存空间，支持快速的随机访问和尾部插入/删除操作。
• list：动态分配非连续的内存空间，支持快速的插入/删除操作。
• deque：动态分配多个连续的内存块，支持快速的随机访问和头尾插入/删除操作。
• map：动态分配内存空间，按照键值对的方式存储数据，支持快速的查找操作。
• set：动态分配内存空间，按照键值存储数据，支持快速的查找操作。

而静态分配内存的容器包括：

• array：静态分配连续的内存空间，其大小在编译时就已经确定，无法动态改变。
• forward_list：静态分配非连续的内存空间，其大小在编译时就已经确定，无法动态改变。

需要注意的是，虽然array和forward_list都是静态分配内存的容器，但它们的实现方式不同。array是连续的内存空间，而forward_list是非连续的内存空间。

---

3.7.2 list构造函数

功能描述：创建list容器。

函数重载	含义
list<T> lst;	list采用采用模板类实现对象的默认构造形式
list(beg, end);	构造函数将[beg, end)区间（左闭右开）中的元素拷贝给本身
list(n, elem);	构造函数将n个elem拷贝给本身
list(const list &lst);	拷贝构造函数

总结：list构造方式同其他几个STL常用容器，熟练掌握即可。

主要注意的是，区间构造的方式不能加减内存地址了，因为list的存储方式和array、vector、deque不同！

示例：

#include <iostream>
using namespace std;
#include <string>
#include <list>

// 链表list容器
/*
	1. list<T> lst;  // list采用采用模板类实现对象的默认构造形式
	2. list(beg, end);  // 构造函数将[beg, end)区间（左闭右开）中的元素拷贝给本身
	3. list(n, elem);  // 构造函数将n个elem拷贝给本身
	4. list(const list &lst);  // 拷贝构造函数
*/
template <class T>
void print_list(const list<T>& lst) {
	for (typename list<T>::const_iterator iter = lst.begin(); iter != lst.end(); iter++)
	{
		cout << *iter << " ";
	}
	cout << endl;
}


void test() {
	// 1. list<T> lst;  // list采用采用模板类实现对象的默认构造形式
	list<int> lst;

	for (int i = 0; i < 5; i++)
	{
		lst.push_back((i + 1) * 10);
	}
	print_list(lst);  // 10 20 30 40 50

	// 2. list(beg, end);  // 构造函数将[beg, end)区间（左闭右开）中的元素拷贝给本身
	list<int> lst2(lst.begin(), lst.end());
	// list<int> lst2(lst.begin() + 1, lst.end() - 2);  // 因为list链表的内存地址不是连续的，所以不能加减了
	print_list(lst2);  // 10 20 30 40 50


	// 3. list(n, elem);  // 构造函数将n个elem拷贝给本身
	list<int> lst3(lst2);
	print_list(lst3);  // 10 20 30 40 50


	// 4. list(const list & lst);  // 拷贝构造函数
	list<char> lst4(10, 'A');
	print_list(lst4);  // A A A A A A A A A A
}


int main() {

	test();

	system("pause");
	return 0;
}

3.7.3 list赋值和交换

功能描述：给list容器进行赋值，以及交换list容器。

函数重载	含义
assign(beg, end);	将[beg, end)区间（左开右闭）中的数据拷贝赋值给本身
assign(n, elem);	将n个elem拷贝赋值给本身
list& operator=(const list& lst);	重载等号操作符
swap(lst);	将lst与本身的元素互换

总结：list赋值和交换操作能够灵活运用即可。

示例：

#include <iostream>
using namespace std;
#include <string>
#include <list>

// 链表list容器的赋值和交换
/*
	1. assign(beg, end);  // 将[beg, end)区间（左开右闭）中的数据拷贝赋值给本身
	2. assign(n, elem);  // 将n个elem拷贝赋值给本身
	3. list& operator=(const list& lst);  // 重载等号操作符
	4. swap(lst);  // 将lst与本身的元素互换
*/
template <class T>
void print_list(const list<T>& lst) {
	for (typename list<T>::const_iterator iter = lst.begin(); iter != lst.end(); iter++)
	{
		cout << *iter << " ";
	}
	cout << endl;
}


void test() {
	list<int> lst1;
	for (int i = 0; i < 5; i++)
	{
		lst1.push_back(i);
	}
	print_list(lst1);  // 0 1 2 3 4


	// 1. assign(beg, end);  // 将[beg, end)区间（左开右闭）中的数据拷贝赋值给本身
	list<int> lst2;
	lst2.assign(lst1.begin(), lst1.end());
	print_list(lst2);  // 0 1 2 3 4



	// 2. assign(n, elem);  // 将n个elem拷贝赋值给本身
	list<char> lst3;
	lst3.assign(10, 'A');
	print_list(lst3);  // A A A A A A A A A A


	// 3. list & operator=(const list & lst);  // 重载等号操作符
	list<char> lst4;
	lst4 = lst3;
	print_list(lst4);  // A A A A A A A A A A


	// 4. swap(lst);  // 将lst与本身的元素互换
	list<char> lst5;
	lst5.assign(5, 'B');

	print_list(lst4);  // A A A A A A A A A A
	print_list(lst5);  // B B B B B

	lst5.swap(lst4);  // 交互两个链表

	print_list(lst4);  // B B B B B
	print_list(lst5);  // A A A A A A A A A A
}


int main() {

	test();

	system("pause");
	return 0;
}

3.7.4 list大小操作

功能描述：对list容器的大小进行操作。

函数重载	含义
size();	返回容器中元素的个数
empty();	判断容器是否为空
resize(num);	重新指定容器的长度为num，默认值为数据类型的默认构造
resize(num, elem);	重新指定容器的长度为num，以elem值填充新位置

总结：

• 判断是否为空 — empty()
• 返回元素个数 — size()
• 重新指定个数 — resize()

示例：

#include <iostream>
using namespace std;
#include <string>
#include <list>

// 链表list容器的大小操作
/*
	1. size();  // 返回容器中元素的个数
	2. empty();  // 判断容器是否为空
	3. resize(num);  // 重新指定容器的长度为num，默认值为数据类型的默认构造
	4. resize(num, elem);  // 重新指定容器的长度为num，以elem值填充新位置
*/
template <class T>
void print_list(const list<T>& lst) {
	for (typename list<T>::const_iterator iter = lst.begin(); iter != lst.end(); iter++)
	{
		cout << *iter << " ";
	}
	cout << endl;
}


void test() {
	list<int> lst;
	for (int i = 0; i < 5; i++)
	{
		lst.push_back(i);
	}
	print_list(lst);  // 0 1 2 3 4

	// 1. size();  // 返回容器中元素的个数
	cout << "lst.size(): " << lst.size() << endl;  // 5

	
	// 2. empty();  // 判断容器是否为空
	cout << "lst.empty(): " << lst.empty() << endl;  // 0


	// 3. resize(num);  // 重新指定容器的长度为num，默认值为数据类型的默认构造
	lst.resize(10);
	print_list(lst);  // 0 1 2 3 4 0 0 0 0 0
	cout << "lst.size(): " << lst.size() << endl;  // 10


	// 4. resize(num, elem);  // 重新指定容器的长度为num，以elem值填充新位置
	lst.resize(15, 10);
	print_list(lst);  // 0 1 2 3 4 0 0 0 0 0 10 10 10 10 10
	cout << "lst.size(): " << lst.size() << endl;  // 15
}


int main() {

	test();

	system("pause");
	return 0;
}

3.7.5 list插入和删除

功能描述：对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,end)区间的数据，无返回值
clear();	移除容器的所有数据
erase(beg, end);	删除[beg,end)区间的数据，返回下一个数据的位置
erase(pos);	删除pos位置的数据，返回下一个数据的位置
remove(elem);	删除容器中所有与elem值匹配的元素

注意：

1. 位置参数不要用int，要用迭代器list<T>::iterator、list<T>::const_iterator
2. beg和end不要再加int操作了，因为链表list不像array, vector, deque那样。但是可以自加(++)和自自减(–)。
3. remove()是独一无二的，只有list链表有，其他容器都没有（只是有类似的操作 —— erase()）。
4. remove(elem)会一次性把所有的elem都删除，而不是只删除一个！

总结：

• 尾插 — push_back()
• 尾删 — pop_back()
• 头插 — push_front()
• 头删 — `pop_front()
• 插入 — `insert()
• 删除 — erase()
• 移除 — remove()
• 清空 — clear()

示例：

#include <iostream>
using namespace std;
#include <string>
#include <list>

// 链表list容器的大小操作
/*
	1. push_back(elem);  // 在容器尾部加入一个元素
	2. pop_back();  // 删除容器中最后一个元素
	3. push_front(elem);  // 在容器开头插入一个元素
	4. pop_front();  // 从容器开头移除第一个元素
	5. insert(pos, elem);  // 在pos位置插elem元素的拷贝，返回新数据的位置
	6. insert(pos, n, elem);  // 在pos位置插入n个elem数据，无返回值
	7. insert(pos, beg, end);  // 在pos位置插入[beg,end)区间的数据，无返回值
	8. clear();  // 移除容器的所有数据
	9. erase(beg, end);  // 删除[beg,end)区间的数据，返回下一个数据的位置
	10. erase(pos);  // 删除pos位置的数据，返回下一个数据的位置
	11. remove(elem);  // 删除容器中所有与elem值匹配的元素
*/
template <class T>
void print_list(const list<T>& lst) {
	for (typename list<T>::const_iterator iter = lst.begin(); iter != lst.end(); iter++)
	{
		cout << *iter << " ";
	}
	cout << endl;
}


void test() {
	list<int> lst;
	// 1. push_back(elem);  // 在容器尾部加入一个元素
	lst.push_back(10);
	lst.push_back(20);
	print_list(lst);  // 10 20


	// 2. pop_back();  // 删除容器中最后一个元素
	lst.pop_back();
	print_list(lst);  // 10


	// 3. push_front(elem);  // 在容器开头插入一个元素
	lst.push_front(100);
	lst.push_front(200);
	lst.push_front(300);
	print_list(lst);  // 300 200 100 10


	// 4. pop_front();  // 从容器开头移除第一个元素
	lst.pop_front();
	print_list(lst);  // 200 100 10

	// 5. insert(pos, elem);  // 在pos位置插elem元素的拷贝，返回新数据的位置
	lst.insert(lst.begin(), 999);
	print_list(lst);  // 999 200 100 10


	// 6. insert(pos, n, elem);  // 在pos位置插入n个elem数据，无返回值
	lst.insert(lst.end(), 3, 300);
	print_list(lst);  // 999 200 100 10 300 300 300


	// 7. insert(pos, beg, end);  // 在pos位置插入[beg,end)区间的数据，无返回值
	lst.insert(lst.begin(), lst.begin(), lst.end());
	print_list(lst);  // 999 200 100 10 300 300 300 999 200 100 10 300 300 300


	// 8. clear();  // 移除容器的所有数据
	lst.clear();
	print_list(lst);  // 


	// 9. erase(beg, end);  // 删除[beg,end)区间的数据，返回下一个数据的位置
	lst.push_back(10);
	lst.push_back(20);
	lst.push_back(30);
	lst.erase(lst.begin(), lst.end());
	print_list(lst);  // 


	// 10. erase(pos);  // 删除pos位置的数据，返回下一个数据的位置
	lst.push_front(10);
	lst.push_front(20);
	lst.push_front(30);
	lst.erase(lst.begin());
	print_list(lst);  // 20 10


	/// 11. remove(elem);  // 删除容器中所有与elem值匹配的元素
	lst.push_back(10);
	lst.push_back(10);
	lst.push_back(10);
	lst.push_back(10);
	print_list(lst);  // 20 10 10 10 10 10

	lst.remove(10);
	print_list(lst);  // 20
}


int main() {

	test();

	system("pause");
	return 0;
}

3.7.6 list数据存取

功能描述：对list容器中数据进行存取。

函数重载	含义
front();	返回第一个元素
back();	返回最后一个元素

注意：list链表容器不可以用[]和.at()的方式来访问list容器中的元素，因为list不是用连续线性空间存储数据，迭代器也是不支持随机访问的。

list因为地址空间不是连续的，所以只能看到头和尾，因此不能按索引进行存取数据（不能跳跃式访问）。故，list容器对于数据存取只有front和back两个接口。

示例：

#include <iostream>
using namespace std;
#include <string>
#include <list>

// 链表list容器的数据存取
/*
	1. front();  // 返回第一个元素
	2. back();  // 返回最后一个元素
*/
template <class T>
void print_list(const list<T>& lst) {
	for (typename list<T>::const_iterator iter = lst.begin(); iter != lst.end(); iter++)
	{
		cout << *iter << " ";
	}
	cout << endl;
}


void test() {
	list<int> lst;
	for (int i = 0; i < 5; i++) {
		lst.push_back(i * 10);
	}
	print_list(lst);  // 0 10 20 30 40

	/*
		list链表容器不可以用[]和at的方式来访问list容器中的元素，
		因为list不是用连续线性空间存储数据，迭代器也是不支持随机访问的。
	*/
	// lst[0];  // 没有与这些操作数匹配的“["运算符
	// lst.at(0);  // 类"std:list<int, std:allocator <int> >"没有成员"at"

	// 1. front();  // 返回第一个元素
	cout << "第一个元素为: " << lst.front() << endl;  // 第一个元素为: 0

	// 2. back();  // 返回最后一个元素
	cout << "最后一个元素为: " << lst.back() << endl;  // 最后一个元素为: 40

	// 验证迭代器是不支持随机访问的
	list<int>::iterator it = lst.begin();
	// it = it + 1;  // 没有与这些操作数匹配的"+"运算符 -> 说明迭代器不支持随机访问
	// 虽然不支持 +int，但可以自加！
	cout << "it++的数据: " << *(it++) << endl;  // 0
	cout << "it--的数据: " << *(it--) << endl;  // 10
	cout << "++it的数据: " << *(++it) << endl;  // 10 -> 支持前向
	cout << "--it的数据: " << *(--it) << endl;  // 0  -> 支持后向
	// 同时支持前向和后向，说明是双向的！
}


int main() {

	test();

	system("pause");
	return 0;
}

3.7.7 list反转和排序

功能描述：将容器中的元素反转，以及将容器中的数据进行排序。

函数重载	含义
reverse();	反转链表
sort();	链表排序

注意：lst.sort();而不是sort(lst.begin(), lst.end());

原因：使用algorithm的sort()没有办法对链表list进行排序！

1. 所有不支持随机访问迭代器的容器，不可以用标准算法
2. 不支持随机访问迭代器的容器，内部会提供对应的一些算法

示例：

#include <iostream>
using namespace std;
#include <string>
#include <list>
#include <algorithm>


// 链表list容器的反转与排序
/*
	1. reverse();  // 反转链表
	2. sort();  // 链表排序
*/
template <class T>
void print_list(const list<T>& lst) {
	for (typename list<T>::const_iterator iter = lst.begin(); iter != lst.end(); iter++)
	{
		cout << *iter << " ";
	}
	cout << endl;
}


void test() {
	list<int> lst;
	for (int i = 0; i < 5; i++)
	{
		lst.push_back(rand() % 41 + 60);
	}
	print_list(lst);  // 100 74 90 93 84


	// 1. reverse();  // 反转链表
	lst.reverse();
	print_list(lst);  // 84 93 90 74 100


	// 2. sort();  // 链表排序
	lst.sort();  // 默认是升序
	print_list(lst);  // 74 84 90 93 100

	// 降序
	auto fn = [](int v1, int v2) {return v1 > v2; };
	lst.sort(fn);  // 传入一个函数即可实现降序排序
	print_list(lst);  // 100 93 90 84 74


	/*
		使用algorithm的sort()没有办法对链表list进行排序！

			1. 所有不支持随机访问迭代器的容器，不可以用标准算法
			2. 不支持随机访问迭代器的容器，内部会提供对应的一些算法
	*/
	// sort(lst.begin(), lst.end());  // algorithm报错
}


int main() {

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

	test();

	system("pause");
	return 0;
}

3.7.8 排序案例

案例描述：将Person自定义数据类型进行排序，Person中属性有姓名、年龄、身高。

排序规则：按照年龄进行升序，如果年龄相同按照身高进行降序。

总结：

• 对于自定义数据类型，必须要指定排序规则，否则编译器不知道如何进行排序
• 高级排序只是在排序规则上再进行一次逻辑规则制定，并不复杂
• list.sort()方法的规则最终要的数据类型是bool

示例：

#include <iostream>
using namespace std;
#include <string>
#include <list>


// 链表list容器的排序案例
/*
	案例描述：将Person自定义数据类型进行排序，Person中属性有姓名、年龄、身高。

	排序规则：按照年龄进行升序，如果年龄相同按照身高进行降序。
*/
template <typename T>
void print_lst(list<T>& lst) {
    for (typename list<T>::iterator it = lst.begin(); it != lst.end(); it++)
    {
        cout << "姓名: " << it->get_name()
            << "\t年龄: " << it->get_age()
            << "\t身高: " << it->get_height()
            << endl;
    }
	cout << endl;
}


class Person {
public:
	Person(string name, int age, int height) {
		this->name = name;
		this->age = age;
		this->height = height;
	}

public:
	string get_name() {
		return this->name;
	}
	int get_age() {
		return this->age;
	}
	int get_height() {
		return this->height;
	}

	void set_name(string name) {
		this->name = name;
	}
	void set_age(int age) {
		this->age = age;
	}
	void set_height(int height) {
		this->height = height;
	}

private:
	string name;
	int age;
	int height;
};


void test() {
	list<Person> lst;

	lst.push_back(Person("张三", 35, 175));
	lst.push_back(Person("李四", 45, 180));
	lst.push_back(Person("王五", 40, 170));
	lst.push_back(Person("赵六", 25, 190));
	lst.push_back(Person("孙七", 35, 160));
	lst.push_back(Person("周八", 35, 200));

	// 打印数据
	print_lst(lst);
	/*
		姓名: 张三      年龄: 35        身高: 175
		姓名: 李四      年龄: 45        身高: 180
		姓名: 王五      年龄: 40        身高: 170
		姓名: 赵六      年龄: 25        身高: 190
		姓名: 孙七      年龄: 35        身高: 160
		姓名: 周八      年龄: 35        身高: 200
	*/


	// 直接排序
	/*
		直接排序的话，因为list存放的是自定义数据类型，所以sort方法不知道该怎么排序，
		所以我们要自己写一个函数，来指定排序的规则！
	*/
	// lst.sort();  // 对类类型"std:less void>"的对象的调用:未找到匹配的调用运算符
	// print_lst(lst);


	// 使用匿名函数指定排序规则
	auto compare_fn = [](Person& p1, Person& p2) {
		return p1.get_age() < p2.get_age();
	};  // 本质上是一个匿名函数，只不过我们给他起了个名字而已
	lst.sort(compare_fn);
	print_lst(lst);
	/*
		姓名: 赵六      年龄: 25        身高: 190
		姓名: 张三      年龄: 35        身高: 175
		姓名: 孙七      年龄: 35        身高: 160
		姓名: 周八      年龄: 35        身高: 200
		姓名: 王五      年龄: 40        身高: 170
		姓名: 李四      年龄: 45        身高: 180

		这样排序并没有满足年龄相同时看身高！
	*/


	// 高级排序规则
	auto compare_fn_advanced = [](Person& p1, Person& p2) {
		if (p1.get_age() == p2.get_age())
		{	
			// 按照身高降序排序
			return p1.get_height() > p2.get_height();
		}
		// 按照年龄升序排序
		return p1.get_age() < p2.get_age();
	};
	lst.sort(compare_fn_advanced);
	print_lst(lst);
	/*
		姓名: 赵六      年龄: 25        身高: 190
		姓名: 周八      年龄: 35        身高: 200
		姓名: 张三      年龄: 35        身高: 175
		姓名: 孙七      年龄: 35        身高: 160
		姓名: 王五      年龄: 40        身高: 170
		姓名: 李四      年龄: 45        身高: 180
	*/
}


int main() {

	test();

	system("pause");
	return 0;
}

---

拓展：如果年龄和身高都相同，则按体重降序。

#include <iostream>
using namespace std;
#include <string>
#include <list>


// 链表list容器的排序案例
/*
	案例描述：将Person自定义数据类型进行排序，Person中属性有姓名、年龄、身高。

	排序规则：按照年龄进行升序，如果年龄相同按照身高进行降序；如果年龄和身高都相同，则按体重降序。
*/
template <typename T>
void print_lst(list<T>& lst) {
    for (typename list<T>::iterator it = lst.begin(); it != lst.end(); it++)
    {
        cout << "姓名: " << it->get_name()
            << "\t年龄: " << it->get_age()
            << "\t身高: " << it->get_height()
            << "\t体重: " << it->get_weight()
            << endl;
    }
	cout << endl;
}


class Person {
public:
	Person(string name, int age, int height, int weight) {
		this->name = name;
		this->age = age;
		this->height = height;
		this->weight = weight;
	}

public:
	string get_name() {
		return this->name;
	}
	int get_age() {
		return this->age;
	}
	int get_height() {
		return this->height;
	}
	int get_weight() {
		return this->weight;
	}

	void set_name(string name) {
		this->name = name;
	}
	void set_age(int age) {
		this->age = age;
	}
	void set_height(int height) {
		this->height = height;
	}
	void set_weight(int weight) {
		this->weight = weight;
	}

private:
	string name;
	int age;
	int height;
	int weight;
};


void test() {
	list<Person> lst;

	lst.push_back(Person("张三", 35, 160, 100));
	lst.push_back(Person("李四", 45, 170, 160));
	lst.push_back(Person("王五", 40, 170, 172));
	lst.push_back(Person("赵六", 25, 190, 150));
	lst.push_back(Person("孙七", 35, 160, 120));
	lst.push_back(Person("周八", 35, 200, 157));

	// 打印数据
	print_lst(lst);
	/*
		姓名: 张三      年龄: 35        身高: 160       体重: 100
		姓名: 李四      年龄: 45        身高: 170       体重: 160
		姓名: 王五      年龄: 40        身高: 170       体重: 172
		姓名: 赵六      年龄: 25        身高: 190       体重: 150
		姓名: 孙七      年龄: 35        身高: 160       体重: 120
		姓名: 周八      年龄: 35        身高: 200       体重: 157
	*/


	// 直接排序
	/*
		直接排序的话，因为list存放的是自定义数据类型，所以sort方法不知道该怎么排序，
		所以我们要自己写一个函数，来指定排序的规则！
	*/
	// lst.sort();  // 对类类型"std:less void>"的对象的调用:未找到匹配的调用运算符
	// print_lst(lst);


	// 使用匿名函数指定排序规则
	auto compare_fn = [](Person& p1, Person& p2) {
		return p1.get_age() < p2.get_age();
	};  // 本质上是一个匿名函数，只不过我们给他起了个名字而已
	lst.sort(compare_fn);
	print_lst(lst);
	/*
		姓名: 赵六      年龄: 25        身高: 190       体重: 150
		姓名: 张三      年龄: 35        身高: 160       体重: 100
		姓名: 孙七      年龄: 35        身高: 160       体重: 120
		姓名: 周八      年龄: 35        身高: 200       体重: 157
		姓名: 王五      年龄: 40        身高: 170       体重: 172
		姓名: 李四      年龄: 45        身高: 170       体重: 160

		这样排序并没有满足年龄相同时看身高！
	*/


	// 高级排序规则
	auto compare_fn_advanced = [](Person& p1, Person& p2) {
		if (p1.get_age() == p2.get_age())
		{	
			// 按照身高降序排序
			return p1.get_height() > p2.get_height();
		}
		// 按照年龄升序排序
		return p1.get_age() < p2.get_age();
	};
	lst.sort(compare_fn_advanced);
	print_lst(lst);
	/*
		姓名: 赵六      年龄: 25        身高: 190       体重: 150
		姓名: 周八      年龄: 35        身高: 200       体重: 157
		姓名: 张三      年龄: 35        身高: 160       体重: 100
		姓名: 孙七      年龄: 35        身高: 160       体重: 120
		姓名: 王五      年龄: 40        身高: 170       体重: 172
		姓名: 李四      年龄: 45        身高: 170       体重: 160

		这样排序并没有满足年龄身高同时相同时看体重！
	*/

	
	// 最终排序规则
	auto final_compare_fn = [](Person& p1, Person& p2) {
		if (p1.get_age() < p2.get_age())
		{
			return true;
		}
		else if (p1.get_age() == p2.get_age())
		{
			if (p1.get_height() > p2.get_height())
			{
				return true;
			}
			else if (p1.get_height() == p2.get_height())
			{
				return p1.get_weight() > p2.get_weight();
			}
		}
		return false;
	};
	lst.sort(final_compare_fn);
	print_lst(lst);

	/*
		姓名: 赵六      年龄: 25        身高: 190       体重: 150
		姓名: 周八      年龄: 35        身高: 200       体重: 157
		姓名: 孙七      年龄: 35        身高: 160       体重: 120
		姓名: 张三      年龄: 35        身高: 160       体重: 100
		姓名: 王五      年龄: 40        身高: 170       体重: 172
		姓名: 李四      年龄: 45        身高: 170       体重: 160
	*/
}


int main() {

	test();

	system("pause");
	return 0;
}

3.8 set / multiset容器

在名称上，C++ 中的 set 和 Python 中的 set 都被称为集合（set），但它们在实现和用法上有一些不同。

C++ 中的 set 是一个关联容器，它使用红黑树来存储元素，并且保持元素的顺序。set 中的元素是唯一的，即不允许重复元素，而且元素是有序的。set 提供了插入、删除、查找等操作，并且这些操作的平均时间复杂度都是 $O({\log }^n)$。set 还提供了迭代器和反向迭代器，可以用来遍历集合中的元素。

Python 中的 set 是一个内置类型，它是一个无序的、唯一的元素集合。与 C++ 中的 set 不同，Python 中的 set 不使用红黑树来存储元素，而是使用哈希表来实现。因此，Python 中的 set 中的元素是无序的，但是它们是唯一的。set 提供了添加、删除、查找等操作，并且这些操作的平均时间复杂度都是 $O(1)$。set 还提供了迭代器和集合运算（如并集、交集、差集等），可以用来操作集合中的元素。

因此，虽然 C++ 中的 set 和 Python 中的 set 都被称为集合，但它们在实现和用法上有一些不同。

multiset 的全拼是 multiple set，即“多重集合”的意思。

3.8.1 set基本概念

简介：所有元素都会在插入时自动被排序。

本质：set/multiset属于关联式容器，底层结构是用二叉树实现。

set和multiset区别：

• set不允许容器中有重复的元素

• multiset允许容器中有重复的元素

• set：集合

• multiset：多重集合

3.8.2 set构造和赋值

功能描述：创建set容器以及赋值。

性质	函数重载	含义
构造	set<T> st;	默认构造函数
构造	set(const set& st);	拷贝构造函数
赋值	set& operator=(const set& st);	重载等号操作符

set集合的特点：

1. 没有push和pop方法
2. 所有元素在插入后会自动排序
3. 不允许插入重复的值（不会报错，但不会插入成功）

总结：

• set容器插入数据时用insert
• set容器插入数据的数据会自动排序

示例：

#include <iostream>
using namespace std;
#include <string>
#include <set>


// 集合set容器的构造函数
/*
	1. 构造set<T> st;  // 默认构造函数
	2. 构造set(const set& st);  // 拷贝构造函数
	3. 赋值set& operator=(const set& st);  // 重载等号操作符
*/
template <typename T>
void print_set(set<T>& st) {
	for (typename set<T>::iterator it = st.begin(); it != st.end() ; it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}


void test() {
	// 1. 构造set<T> st_1;  // 默认构造函数
	set<int> st_1;
	
	// 插入数据，只有insert方法
	for (int i = 0; i < 5; i++)
	{
		st_1.insert(rand() % 100);
	}
	print_set(st_1);  // 37 46 72 79 87
	/*
		set容器的特点：
			1. 没有push和pop方法
			2. 所有元素在插入后会自动排序
			3. 不允许插入重复的值（不会报错，但不会插入成功）
	*/

	
	// 2. 构造set(const set & st);  // 拷贝构造函数
	set<int> st_2(st_1);
	print_set(st_2);  // 37 46 72 79 87


	// 3. 赋值set & operator=(const set & st);  // 重载等号操作符
	set<int> st_3;
	st_3 = st_1;
	print_set(st_3);  // 37 46 72 79 87
}


int main() {

	srand(time(NULL));

	test();

	system("pause");
	return 0;
}

3.8.3 set大小和交换

功能描述：统计set容器大小以及交换set容器。

函数重载	含义
size();	返回容器中元素的数目
empty();	判断容器是否为空
swap(st);	交换两个集合容器

set容器没有.resize()方法，因为之前讲的几种容器在resize时有默认值填充，而set容器是不允许有重复值的，所以就没有.resize()方法。

总结：

• 统计大小 — .size()
• 判断是否为空 — .empty()
• 交换容器 — .swap()

示例：

#include <iostream>
using namespace std;
#include <string>
#include <set>


// 集合set容器的大小和交换
/*
	1. size();  // 返回容器中元素的数目
	2. empty();  // 判断容器是否为空
	3. swap(st);  // 交换两个集合容器
*/
template <typename T>
void print_set(set<T>& st) {
	for (typename set<T>::iterator it = st.begin(); it != st.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}


void test() {
	set<int> st;
	for (int i = 0; i < 5; i++)
	{
		st.insert(rand() % 100);
	}
	print_set(st); // 5 18 57 60 70

	// 1. size();  // 返回容器中元素的数目
	cout << "set.size(): " << st.size() << endl;  // 5

	// 2. empty();  // 判断容器是否为空
	cout << "set.empty(): " << st.empty() << endl;  // 0

	// 3. swap(st);  // 交换两个集合容器
	set<int> st2;
	st2.insert(100);

	st2.swap(st);
	print_set(st);  // 100
	print_set(st2);  // 5 18 57 60 70
}


int main() {
	srand(time(NULL));

	test();

	system("pause");
	return 0;
}

3.8.4 set插入和删除

功能描述：set容器进行插入数据和删除数据。

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

注意：.end()方法指向最后一个元素的下一个位置，因此如果要用erase(st.end());就会报错！因为这个位置是空的。而erase(st.begin(), st.end());不会报错，因为是左闭右开的！因此如果我们想用erase(st.end());这样的方法，正确的写法应该是erase(--st.end());，让st.end()返回的迭代器指向最后一个元素，而不是最后一个元素之后的位置。

总结：

• 插入 — .insert()
• 删除 — .erase()
• 清空 — .clear()

示例：

#include <iostream>
using namespace std;
#include <string>
#include <set>


// 集合set容器的插入和删除
/*
	1. insert(elem);  // 在容器中插入元素
	2. clear();  // 清除所有元素
	3. erase(pos);  // 删除pos迭代器所指的元素，返回下一个元素的迭代器
	4. erase(beg, end);  // 删除区间[beg, end)的所有元素，返回下一个元素的迭代器
	5. erase(elem);  // 删除容器中值为elem的元素
*/
template <typename T>
void print_set(set<T>& st) {
	for (typename set<T>::iterator it = st.begin(); it != st.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}


void test() {
	set<int> st;

	// 1. insert(elem);  // 在容器中插入元素
	for (int i = 0; i < 5; i++)
	{
		st.insert(rand() % 100);
	}
	print_set(st); // 0 34 41 67 69

	
	// 2. clear();  // 清除所有元素
	set<int> st2(st);
	st2.clear();
	print_set(st2);   //

	
	// 3. erase(pos);  // 删除pos迭代器所指的元素，返回下一个元素的迭代器
	set<int> st3(st);
	st3.erase(st3.begin());
	print_set(st3);  // 34 41 67 69

	st3.erase(++st3.begin());
	print_set(st3);  // 34 67 69

	st3.erase(--st3.end());  // .end()返回的迭代器指向容器中最后一个元素之后的位置（因此需要前置--）
	print_set(st3);  // 34 67


	// 4. erase(beg, end);  // 删除区间[beg, end)的所有元素，返回下一个元素的迭代器
	set<int> st4;
	st4 = st;
	st4.erase(++st4.begin(), --st4.end());
	print_set(st3);  // 23 71

	// 5. erase(elem);  // 删除容器中值为elem的元素
	set <int> st5;
	st5.insert(10);
	st5.insert(10);
	st5.insert(10);
	st5.insert(20);
	st5.insert(30);
	print_set(st5);  // 10 20 30

	st5.erase(10);
	print_set(st5);  // 20 30

	st5.erase(0);
	print_set(st5);  // 20 30
}


int main() {

	test();

	system("pause");
	return 0;
}

3.8.5 set查找和统计

功能描述：对set容器进行查找数据以及统计数据。

函数重载	含义
find(key);	查找key是否存在。若存在，返回该键的元素的迭代器；若不存在，返回set.end();
count( key );	统计key的元素个数

注意：

• set.end()返回的迭代器指向的是最后一个元素的下一个位置，不能直接调用哦。
• set.count()返回的只可能是0或1，因为set容器它是不允许有重复元素的！

总结：

• 查找 — .find() —— (返回的是迭代器)
• 统计 — .count() —— (对于set，结果只能是0或1)

示例：

#include <iostream>
using namespace std;
#include <string>
#include <set>


// 集合set容器的查找和统计
/*
	1. find(key);  // 查找key是否存在。若存在，返回该键的元素的迭代器；若不存在，返回set.end();
	2. count( key );  // 统计key的元素个数
*/
template <typename T>
void print_set(set<T>& st) {
	for (typename set<T>::iterator it = st.begin(); it != st.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}


void test() {
	set<int> st;
	for (int i = 0; i < 10; i++)
	{
		st.insert(i * 10);
	}
	print_set(st);  // 0 10 20 30 40 50 60 70 80 90


	// 1. find(key);  // 查找key是否存在。若存在，返回该键的元素的迭代器；若不存在，返回set.end();
	set<int>::iterator pos = st.find(10);
	if (pos != st.end())
	{
		cout << "找到[" << *pos << "]元素!" << endl;  // 找到[10]元素!
	}
	else
	{
		cout << "未找到该元素!" << endl;
	}


	// 2. count(key);  // 统计key的元素个数（返回值只可能是0或1）
	st.insert(30);
	st.insert(30);
	st.insert(30);
	st.insert(30);  // 对于set容器而言，不允许插入重复元素
	st.insert(30);
	st.insert(30);
	cout << "st.count(30): " << st.count(30) << endl;  // 1
	cout << "st.count(100): " << st.count(100) << endl;  // 0
}


int main() {

	test();

	system("pause");
	return 0;
}

3.8.6 set和multiset区别

学习目标：掌握set和multiset的区别。

区别：

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

总结：

• 如果不允许插入重复数据可以利用set
• 如果需要插入重复数据利用multiset

注意：multiset是std下的，即std::multiset，不需要引入额外的头文件

示例：

#include <iostream>
using namespace std;
#include <string>
#include <set>


// set容器和multiset容器的区别
/*
区别：
	+ set不可以插入重复数据，而multiset可以
	+ set插入数据的同时会返回插入结果，表示插入是否成功
	+ multiset不会检测数据，因此可以插入重复数据
*/
template <typename T>
void print_set(set<T>& st) {
	for (typename set<T>::iterator it = st.begin(); it != st.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}


void test() {
	set<int> st;
	// pair是一个对组，insert方法返回一个pair，里面包含一个迭代器和一个bool
	pair<set<int>::iterator, bool> res1 = st.insert(10);

	if (res1.second)  // 可以使用.first和.second调用pair的前一个和后一个元素
	{
		cout << "第一次插入成功!" << endl;  // 第一次插入成功!
	}
	else
	{
		cout << "第一次插入失败!" << endl;
	}

	pair<set<int>::iterator, bool> res2 = st.insert(10);
	if (res2.second)
	{
		cout << "第二次插入成功!" << endl;
	}
	else
	{
		cout << "第二次插入失败!" << endl;  // 第二次插入失败!
	}
	

	// 看一下两次返回的迭代器的地址是否相同
	if (&(*res1.first) == &(*res2.first))
	{
		cout << "两个迭代器的地址相同，分别为：" << endl;
		cout << &(*res1.first) << endl;
		cout << &(*res2.first) << endl;
		/*
			两个迭代器的地址相同，分别为：
			000001D36481401C
			000001D36481401C
		*/
	}
	else
	{
		cout << "两个迭代器的地址不相同，分别为：" << endl;
		cout << &(*res1.first) << endl;
		cout << &(*res2.first) << endl;
	}




	multiset<int> mst;  // multiset是std下的，即std::multiset，不需要引入额外的头文件
	multiset<int>::iterator res = mst.insert(10);  // 返回值是一个iterator
	// 看看这个迭代器里面的值
	cout << *res << endl;  // 10

	// 再添加一些数据进去
	mst.clear();
	for (int i = 0; i < 5; i++)
	{
		mst.insert(i);
		mst.insert(i);
	}
	
	// 遍历看一下这个多重集合
	for (multiset<int>::iterator it = mst.begin(); it != mst.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;  // 0 0 1 1 2 2 3 3 4 4
}


int main() {

	test();

	system("pause");
	return 0;
}

3.8.7 pair对组创建

功能描述：成对出现的数据，利用对组可以返回两个数据。

两种创建方式：

1. pair<type, type> p (value1, value2);
2. pair<type, type> p = make_pair(value1, value2);

注意：

1. pair是std下的，即std::pair，不需要引入额外的头文件
2. make_pair()也是std下的，即std::make_pair()
3. make_pair()是一个全局函数，它的返回值是一个pair对组
4. 在 C++ 中，pair.first 和 pair.second 是 std::pair 类型的成员变量，用于表示对组中的第一个值和第二个值。它们的类型分别为 T1 和 T2，可以通过点操作符 . 来访问它们的值。需要注意的是，pair.first 和 pair.second 是成员变量而不是成员函数，因此在访问它们的值时不需要加上圆括号()。如果加上圆括号，编译器会将它们解释为函数调用，从而导致语法错误。

总结：两种方式都可以创建对组，记住一种即可（推荐使用第二种方法，即使用make_pair()函数）。

示例：

#include <iostream>
using namespace std;
#include <string>


// pair对组的创建
/*
	1. pair<type, type> p (value1, value2);
	2. pair<type, type> p = make_pair(value1, value2);
*/


void test() {
	// 1. pair<type, type> p (value1, value2);
	pair<string, int> pr("Tom", 20);
	cout << "姓名: " << pr.first << "\t年龄: " << pr.second << endl;  // 姓名: Tom       年龄: 20


	// 2. pair<type, type> p = make_pair(value1, value2);
	std::pair<string, int> pr2 = std::make_pair("Jerry", 30);
	cout << "姓名: " << pr2.first << "\t年龄: " << pr2.second << endl;  // 姓名: Jerry     年龄: 30
}


int main() {

	test();

	system("pause");
	return 0;
}

3.8.8 set容器排序

学习目标：set容器默认排序规则为从小到大（升序），掌握如何改变排序规则。

主要技术点：利用仿函数，可以改变排序规则。

在 C++ 中，仿函数（Functor）是一个类或结构体，它重载了函数调用运算符 operator()，使得该类或结构体的对象可以像函数一样被调用。

仿函数可以看作是一种特殊的函数对象，它可以封装函数调用所需要的状态和行为，并将其作为一个对象来使用。

仿函数可以用于实现各种算法和函数对象，例如排序、查找、计算等。它可以接受任意数量和类型的参数，并返回一个值或执行一些操作。

由于仿函数是一个对象，因此可以保存状态和行为，并在多个函数调用之间保持状态，从而提高程序的效率和灵活性。

仿函数的简单示例：

#include <iostream>

struct Add {  // struct默认权限为public
    int operator()(int a, int b) const {
        return a + b;
    }
};

int main() {
    Add add;
    int sum = add(1, 2); // 调用仿函数计算两个数的和
    // int sum = Add()()(1, 2); // 这样也是可以的
    std::cout << "Sum: " << sum << std::endl;
    return 0;
}

---

语法：

set<int, MyCompare> st;

注意：

1. 更改排序规则一定要在创建set容器之前进行！
2. 因为<>中要求传入的是数据类型，因此我们不能像之前那样传入一个函数，因为函数不是一个数据类型。所以我们需要用仿函数，因为仿函数是重载()运算符的的类或结构体。类和结构体都是我们自定义数据类型用的，它本身就是一个数据类型，所以符合我们的条件！
3. 对于自定义数据类型：由于set容器是一个有序容器，在insert()元素的时候就会排序，所以对于自定义数据类型，我们应该在调用insert()方法之前就要创建一个仿函数，用来指定排序的规则。

示例一：set存放内置数据类型

#include <iostream>
using namespace std;
#include <string>
#include <set>


// set容器的排序：set存放内置数据类型
/*
	学习目标：set容器默认排序规则为从小到大（升序），掌握如何改变排序规则。

	主要技术点：利用仿函数，可以改变排序规则。
*/
class MyCompare {
public:
	bool operator()(int v1, int v2) const{  // 重载()运算符
		return v1 > v2;  // 降序
	}
};


void test() {
	// 将set容器的排序规则修改为降序（更改排序规则一定要在创建set容器之前进行！）

	/*
		因为<>中要求传入的是数据类型，因此我们不能像之前那样传入一个
		函数，因为函数不是一个数据类型。所以我们需要用仿函数，
		因为仿函数是重载()运算符的的类或结构体。类和结构体都是我们
		自定义数据类型用的，它本身就是一个数据类型，所以符合我们的条件！
	*/
	set<int, MyCompare> st;
	for (int i = 1; i < 6; i++)
	{
		st.insert(i * 10);
	}

	for (set<int, MyCompare>::iterator it = st.begin(); it != st.end(); it++)  // 需要写上MyCompare
	{
		cout << *it << " ";
	}
	cout << endl;  // 50 40 30 20 10
}


int main() {

	test();

	system("pause");
	return 0;
}

示例二：set存放自定义数据类型

注意：由于set容器是一个有序容器，在insert()元素的时候就会排序，所以对于自定义数据类型，我们应该在调用insert()方法之前就要创建一个仿函数，用来指定排序的规则。

#include <iostream>
using namespace std;
#include <string>
#include <set>


// set容器的排序：set存放内置数据类型
/*
	学习目标：set容器默认排序规则为从小到大（升序），掌握如何改变排序规则。

	主要技术点：利用仿函数，可以改变排序规则。
*/
class Person {
public:
	Person(string name, int age) {
		this->name = name;
		this->age = age;
	}

public:
	string get_name() const {
		return this->name;
	}
	int get_age() const {
		return this->age;
	}

private:
	string name;
	int age;
};


class PersonCompare {
public:
	bool operator()(const Person& p1, const Person& p2) const {
		// 按照年龄进行降序排序
		return p1.get_age() > p2.get_age();
	}
};


void test() {
	set<Person, PersonCompare> st;

	/*
		因为set容器是有序的，所以直接插入后，因为不知道怎么排序，插入后会直接报错的！
	*/
	st.insert(Person("张三", 20));
	st.insert(Person("李四", 25));
	st.insert(Person("王五", 22));
	st.insert(Person("赵六", 30));

	for (set<Person>::iterator it = st.begin(); it != st.end(); it++)
	{
		cout << "Name: " << it->get_name() << "\tAge: " << it->get_age() << endl;
	}
	/*
		Name: 赵六      Age: 30
		Name: 李四      Age: 25
		Name: 王五      Age: 22
		Name: 张三      Age: 20
	*/
}


int main() {

	test();

	system("pause");
	return 0;
}

3.9 map / multimap容器

3.9.1 map基本概念

简介：

• map中所有元素都是pair
• pair中第一个元素为key(键值)，起到索引作用，第二个元素为value(实值)
• 所有元素都会根据元素的键值自动排序

本质：

• map / multimap属于关联式容器，底层结构是用二叉树实现。

优点:

• 可以根据key值快速找到value值

map和multimap区别：

1. map不允许容器中有重复key值元素（value值可以重复）
2. multimap允许容器中有重复key值元素

---

C++中的map容器和Python中的dict是类似的数据结构，都是用于存储键值对的容器。

map是C++标准库中的一个关联容器，它将一个键映射到一个值，可以用于快速查找和访问数据。map中的元素是按照键的大小排序的，并且每个键只能出现一次。在C++中，可以使用[]运算符或at()函数来访问map中的元素。

dict是Python中的一个内置类型，它也是一个键值对的容器。dict中的元素是无序的，并且每个键只能出现一次。在Python中，可以使用中括号[]或get()方法来访问dict中的元素。

虽然在语法上有所不同，但是map和dict都提供了类似的功能：用于存储键值对，并可以快速查找和访问数据。如果你熟悉Python中的dict，那么理解C++中的map也会更容易。

3.9.2 map构造和赋值

功能描述：对map容器进行构造和赋值操作。

性质	函数重载	含义
构造	map<T1, T2> mp;	map默认构造函数
构造	map(const map& mp);	拷贝构造函数
赋值	map& operator=(const map& mp);	重载等号操作符

总结：map中所有元素都是成对出现，插入数据时候要使用对组pair。

示例：

#include <iostream>
using namespace std;
#include <string>
#include <map>


// map容器：构造和赋值
/*
	1. 构造：map<T1, T2> mp;  // map默认构造函数
	2. 构造map(const map& mp);  // 拷贝构造函数
	3. 赋值map& operator=(const map& mp);  // 重载等号操作符
*/
template <class T1, class T2>
void print_mp(map<T1, T2>& mp) {
	for (typename map<T1, T2>::iterator it = mp.begin(); it != mp.end(); it++)
	{
		cout << "key: " << it->first << "  value: " << it->second << endl;
	}
	cout << endl;
}


void test() {
	// 1. 构造：map<T1, T2> mp;  // map默认构造函数
	map<int, int> mp;
	
	mp.insert(pair<int, int>(1, 10));
	mp.insert(make_pair(5, 50));
	mp.insert(make_pair(2, 20));
	mp.insert(make_pair(3, 30));
	mp.insert(make_pair(4, 40));
	
	print_mp(mp);
	/*
		key: 1  value: 10
		key: 2  value: 20
		key: 3  value: 30
		key: 4  value: 40
		key: 5  value: 50
	*/


	// 2. 构造map(const map& mp);  // 拷贝构造函数
	map<int, int> mp2(mp);
	print_mp(mp2);
	/*
		key: 1  value: 10
		key: 2  value: 20
		key: 3  value: 30
		key: 4  value: 40
		key: 5  value: 50
	*/


	// 3. 赋值map& operator=(const map& mp);  // 重载等号操作符
	map<int, int> mp3;
	mp3 = mp2;
	print_mp(mp3);
	/*
		key: 1  value: 10
		key: 2  value: 20
		key: 3  value: 30
		key: 4  value: 40
		key: 5  value: 50
	*/
}


int main() {

	test();

	system("pause");
	return 0;
}

3.9.3 map大小和交换

功能描述：统计map容器大小以及交换map容器。

函数重载	含义
size();	返回容器中元素的数目
empty();	判断容器是否为空
swap(mp);	交换两个集合容器

总结：

• 统计大小 — .size()
• 判断是否为空 — .empty()
• 交换容器 — .swap()

示例：

#include <iostream>
using namespace std;
#include <string>
#include <map>


// map容器：大小和交换
/*
	1. size();  // 返回容器中元素的数目
	2. empty();  // 判断容器是否为空
	3. swap(st);  // 交换两个集合容器
*/
template <class T1, class T2>
void print_mp(map<T1, T2>& mp) {
	for (typename map<T1, T2>::iterator it = mp.begin(); it != mp.end(); it++)
	{
		cout << "key: " << it->first << "  value: " << it->second << endl;
	}
	cout << endl;
}


void test() {
	map<int, int> mp;
	for (int i = 0; i < 6; i++)
	{
		mp.insert(make_pair(i, i * 10));
	}
	print_mp(mp);
	/*
		key: 0  value: 0
		key: 1  value: 10
		key: 2  value: 20
		key: 3  value: 30
		key: 4  value: 40
		key: 5  value: 50
	*/


	// 1. size();  // 返回容器中元素的数目
	cout << "mp.size(): " << mp.size() << endl;


	// 2. empty();  // 判断容器是否为空
	cout << "mp.empty(): " << mp.empty() << endl;


	// 3. swap(st);  // 交换两个集合容器
	map<int, int> mp2;
	mp2.insert(make_pair(100, 1));
	mp2.insert(make_pair(200, 2));

	cout << "----------交换前----------" << endl;
	print_mp(mp);
	print_mp(mp2);
	/*
		key: 0  value: 0
		key: 1  value: 10
		key: 2  value: 20
		key: 3  value: 30
		key: 4  value: 40
		key: 5  value: 50

		key: 100  value: 1
		key: 200  value: 2
	*/
	
	mp2.swap(mp);  // 交换两个map容器

	cout << "----------交换后----------" << endl;
	print_mp(mp);
	print_mp(mp2);
	/*
		key: 100  value: 1
		key: 200  value: 2

		key: 0  value: 0
		key: 1  value: 10
		key: 2  value: 20
		key: 3  value: 30
		key: 4  value: 40
		key: 5  value: 50
	*/
}


int main() {

	test();

	system("pause");
	return 0;
}

3.9.4 map插入和删除

功能描述：map容器进行插入数据和删除数据。

函数重载	含义
insert(elem);	在容器中插入元素
clear();	清除所有元素
erase(pos);	删除pos迭代器所指的元素，返回下一个元素的迭代器
erase(beg, end);	删除区间[beg, end)的所有元素，返回下一个元素的迭代器
erase(key);	删除容器中值为key的元素（map中key是唯一的）

总结:

• map插入方式很多，记住其一即可(推荐使用make_pair()函数创建)
• 插入 — .insert()
• 删除 — .erase()
• 清空 — .clear()

示例：

#include <iostream>
using namespace std;
#include <string>
#include <map>


// map容器：插入和删除
/*
	1. insert(elem);  // 在容器中插入元素
	2. clear();  // 清除所有元素
	3. erase(pos);  // 删除pos迭代器所指的元素，返回下一个元素的迭代器
	4. erase(beg, end);  // 删除区间[beg, end)的所有元素，返回下一个元素的迭代器
	5. erase(key);  // 删除容器中值为key的元素（map中key是唯一的）
*/
template <class T1, class T2>
void print_mp(map<T1, T2>& mp) {
	for (typename map<T1, T2>::iterator it = mp.begin(); it != mp.end(); it++)
	{
		cout << "key: " << it->first << "  value: " << it->second << endl;
	}
	cout << endl;
}


void test() {
	map<int, int> mp;

	// 1. insert(elem);  // 在容器中插入元素
	// 第一种
	mp.insert(pair<int, int>(1, 10));

	// 第二种(推荐这种)
	mp.insert(make_pair(2, 20));

	// 第三种
	mp.insert(map<int, int>::value_type(3, 30));

	// 第四种(不太推荐，使用的时候一定要注意)
	mp[4] = 40;

	cout << mp[5] << endl;  // 0
	// 没有找到就会帮我们创建一个(和Python中字典的.setdefault(key, default value)方法有点像)

	print_mp(mp);
	/*
		key: 1  value: 10
		key: 2  value: 20
		key: 3  value: 30
		key: 4  value: 40
		key: 5  value: 0
	*/


	// 2. clear();  // 清除所有元素
	map<int, int> mp2(mp);
	mp2.clear();
	print_mp(mp2);  // 


	// 3. erase(pos);  // 删除pos迭代器所指的元素，返回下一个元素的迭代器
	map<int, int> mp3;
	mp3 = mp;

	mp3.erase(mp3.begin());
	mp3.erase(--mp3.end());
	print_mp(mp3); 
	/*
		key: 2  value: 20
		key: 3  value: 30
		key: 4  value: 40
	*/


	// 4. erase(beg, end);  // 删除区间[beg, end)的所有元素，返回下一个元素的迭代器
	map<int, int> mp4;
	mp4 = mp;

	// 使用迭代器控制区间大小
	auto start_pos = mp4.lower_bound(2);  // 获取第一个键值大于等于2的迭代器
	auto end_pos = mp4.lower_bound(4);    // 获取第一个键值大于等于4的迭代器
	mp4.erase(start_pos, end_pos);            // 删除[start_pos, end_pos)范围内的元素

	print_mp(mp4);
	/*
		key: 1  value: 10
		key: 4  value: 40
		key: 5  value: 0
	*/

	// 更间接的代码
	map<int, int> mp5(mp);
	mp5.erase(mp5.lower_bound(2), mp5.lower_bound(4));

	print_mp(mp5);
	/*
		key: 1  value: 10
		key: 4  value: 40
		key: 5  value: 0
	*/


	// 5. erase(key);  // 删除容器中值为key的元素（map中key是唯一的）
	map<int, int> mp6(mp);
	mp6.erase(5);
	mp6.erase(7);  // 删除一个不存在的key也不会报错
	print_mp(mp6);
	/*
		key: 1  value: 10
		key: 2  value: 20
		key: 3  value: 30
		key: 4  value: 40
	*/
}


int main() {

	test();

	system("pause");
	return 0;
}

3.9.5 map查找和统计

功能描述：对map容器进行查找数据以及统计数据。

函数重载	含义
find(key);	查找key是否存在。若存在，返回该键的元素的迭代器；若不存在，返回mp.end();
count(key);	统计key的元素个数（对于map容器而言，结果要么是0要么是1）

一定要注意，mp.end()返回的是一个迭代器，指向最后一个元素的下一个位置。

总结：

• 查找 — .find() —— (返回的是迭代器)
• 统计 — .count() —— (对于map，结果为0或者1)

示例：

#include <iostream>
using namespace std;
#include <string>
#include <map>


// map容器：查找和统计
/*
	1. find(key);  // 查找key是否存在。若存在，返回该键的元素的迭代器；若不存在，返回mp.end();
	2. count(key);  // 统计key的元素个数
*/
template <class T1, class T2>
void print_mp(map<T1, T2>& mp) {
	for (typename map<T1, T2>::iterator it = mp.begin(); it != mp.end(); it++)
	{
		cout << "key: " << it->first << "  value: " << it->second << endl;
	}
	cout << endl;
}


void test() {
	map<int, int> mp;
	for (int i = 0; i < 6; i++)
	{
		mp.insert(make_pair(i, i * 10));
	}
	print_mp(mp);
	/*
		key: 0  value: 0
		key: 1  value: 10
		key: 2  value: 20
		key: 3  value: 30
		key: 4  value: 40
		key: 5  value: 50
	*/


	// 1. find(key);  // 查找key是否存在。若存在，返回该键的元素的迭代器；若不存在，返回mp.end();
	auto pos_it = mp.find(3);
	if (pos_it != mp.end())
	{
		cout << "查到了元素: key=" << pos_it->first << "  value=" << pos_it->second << endl;  // 查到了元素: key=3  value=30
	}
	else
	{
		cout << "未找到元素!" << endl;
	}


	// 2. count(key);  // 统计key的元素个数（对于map容器而言，结果要么是0要么是1）
	cout << mp.count(3) << endl;  // 1
}


int main() {

	test();

	system("pause");
	return 0;
}

可以使用auto来接收，但一定要让编译器推导出对应的数据类型，只是编译阶段会影响一些速度，运行过程中不会有影响！

3.9.6 map容器排序

学习目标：map容器默认排序规则为按照key值进行从小到大排序，掌握如何改变排序规则。

主要技术点：利用仿函数，可以改变排序规则。

总结：

• 利用仿函数可以指定map容器的排序规则
• 对于自定义数据类型，map必须要指定排序规则，同set容器

注意：

1. 自定义的仿函数中的 operator() 运算符必须声明为 const，否则编译器会报错
2. 自定义数据类型在get数据时需要加上const

示例：

#include <iostream>
using namespace std;
#include <string>
#include <map>


// map容器：查找和统计
/*
	学习目标：map容器默认排序规则为按照key值进行从小到大排序，掌握如何改变排序规则。

	主要技术点：利用仿函数，可以改变排序规则。
*/
template <class T1, class T2>
void print_mp(map<T1, T2>& mp) {
	for (typename map<T1, T2>::iterator it = mp.begin(); it != mp.end(); it++)
	{
		cout << "key: " << it->first << "  value: " << it->second << endl;
	}
	cout << endl;
}


class MapCompare {
public:
	bool operator()(int v1, int v2) const {  // 自定义的仿函数中的 () 运算符必须声明为 const，否则编译器会报错
		// 降序
		return v1 > v2;
	}
};


void test() {
	map<int, int> mp1;
	for (int i = 0; i < 5; i++)
	{
		mp1.insert(make_pair(rand() % 10, rand() % 100));
	}
	print_mp(mp1);
	/*
		key: 0  value: 49
		key: 1  value: 93
		key: 3  value: 24
		key: 4  value: 37
		key: 9  value: 96
	*/


	// 改变排序规则
	map<int, int, MapCompare> mp2;

	// 赋值
	for (int i = 0; i < 5; i++)
	{
		mp2.insert(make_pair(rand() % 10, rand() % 100));
	}

	// 查看
	for (map<int, int, MapCompare>::iterator it = mp2.begin();  it != mp2.end(); it++)
	{
		cout << "key: " << it->first << "  value: " << it->second << endl;
	}
	cout << endl;
	/*
		key: 7  value: 46
		key: 4  value: 63
		key: 3  value: 34
		key: 2  value: 32
	*/
}


int main() {

	srand(1008611);

	test();

	system("pause");
	return 0;
}

拓展：自定义数据类型

#include <iostream>
using namespace std;
#include <string>
#include <map>


// map容器：查找和统计
/*
	学习目标：map容器默认排序规则为按照key值进行从小到大排序，掌握如何改变排序规则。

	主要技术点：利用仿函数，可以改变排序规则。
*/
class Person {
public:
	Person(string name, int age) {
		this->name = name;
		this->age = age;
	}

public:
	string get_name() const {
		return this->name;
	}
	int get_age() const {
		return this->age;
	}

private:
	string name;
	int age;
};


class PersonCompare {
public:
	// 自定义的仿函数中的 () 运算符必须声明为 const，否则编译器会报错
	bool operator()(const Person& p1, const Person& p2) const {  
		return p1.get_age() > p2.get_age();
	}
};


void test() {
	map<Person, int, PersonCompare> mp;
	mp.insert(make_pair(Person("张三", 20), 160));
	mp.insert(make_pair(Person("李四", 25), 140));
	mp.insert(make_pair(Person("王五", 23), 150));
	mp.insert(make_pair(Person("赵六", 24), 170));

	for (map<Person, int>::iterator it = mp.begin(); it != mp.end(); it++)
	{
		cout << "姓名: " << (it->first).get_name()
			<< "\t年龄: " << (it->first).get_age()
			<< "\t体重: " << it->second << endl;
	}
	cout << endl;
	/*
		姓名: 李四      年龄: 25        体重: 140
		姓名: 赵六      年龄: 24        体重: 170
		姓名: 王五      年龄: 23        体重: 150
		姓名: 张三      年龄: 20        体重: 160
	*/
}


int main() {

	test();

	system("pause");
	return 0;
}

3.10案例：员工分组

3.10.1 案例描述

公司今天招聘了10个员工(ABCDEFGHI)，10名员工进入公司之后，需要指派员工在哪个部门工作。

员工信息有：姓名、工资、部门。其中部门分为：1.策划、2.美术、3.研发。

• 随机给10名员工分配部门和工资
• 通过multimap进行信息的插入，其中key为部门编号；value为员工。
• 分部门显示员工信息

3.10.2 实现步骤

1. 创建10名员工，放到vector中
2. 遍历vector容器，取出每个员工，进行随机分组
3. 分组后，将员工部门编号作为key，具体员工作为value，放入到multimap容器中
4. 分部门显示员工信息

案例代码：

#include <iostream>
using namespace std;
#include <string>
#include <map>
#include <vector>

#define Dept_1 1
#define Dept_2 2
#define Dept_3 3

/*
公司今天招聘了10个员工(ABCDEFGHIJ)，10名员工进入公司之后，需要指派员工在哪个部门工作。

员工信息有：姓名、工资、部门。其中部门分为：1.策划、2.美术、3.研发。

+ 随机给10名员工分配部门和工资
+ 通过multimap进行信息的插入，其中key为部门编号；value为员工。
+ 分部门显示员工信息
*/
class Worker {

public:
	void set_name(string name) {
		this->name = name;
	}
	void set_salary(int salary) {
		this->salary = salary;
	}

	string get_name() {
		return this->name;
	}
	int get_salary() {
		return this->salary;
	}

private:
	string name;
	int salary;
};


void create_worker(vector<Worker>& vec) {
	string name_lst = "ABCDEFGHIJ";
	for (int i = 0; i < 10; i++)
	{
		Worker worker;
		string tmp_name = "员工";
		tmp_name += name_lst[i];
		worker.set_name(tmp_name);
		worker.set_salary(rand() % 10000 + 10000);  // 10000 ~ 19999

		// 将员工放入容器中
		vec.push_back(worker);
	}
}


// 员工分组
void set_group(vector<Worker>& vec, multimap<int, Worker>& mmp) {
	for (vector<Worker>::iterator it = vec.begin(); it != vec.end(); it++) {
		// 产生随机部门编号
		int dept_id = rand() % 3 + 1;  // 1~3

		// 将员工插到分组中
		mmp.insert(make_pair(dept_id, *it));  // key为部门编号，value为具体员工
	}
}


void show_worker_by_group(multimap<int, Worker>& mmp) {
	cout << "部门1----------------------" << endl;
	multimap<int, Worker>::iterator pos=mmp.find(Dept_1);  // 找到key为1的位置，返回一个迭代器
	int count = mmp.count(Dept_1);  // 统计部门1的人数
	int idx = 0;  // 统计移动的次数
	for (; pos != mmp.end() && idx < count; pos++, idx++) {  // 两个数都需要++
		cout << "姓名: " << pos->second.get_name() 
			<< "\t工资: " << pos->second.get_salary() 
			<< endl;
	}
	cout << endl;


	cout << "部门2----------------------" << endl;
	pos = mmp.find(Dept_2);
	count = mmp.count(Dept_2);
	idx = 0;
	for (; pos != mmp.end() && idx < count; idx++, pos++) {
		cout << "姓名: " << pos->second.get_name()
			<< "\t工资: " << pos->second.get_salary()
			<< endl;
	}
	cout << endl;


	cout << "部门3----------------------" << endl;
	pos = mmp.find(Dept_3);
	count = mmp.count(Dept_3);
	idx = 0;
	for (; pos != mmp.end() && idx < count; idx++, pos++) {
		cout << "姓名: " << pos->second.get_name()
			<< "\t工资: " << pos->second.get_salary()
			<< endl;
	}
	cout << endl;
}


int main() {

	// 1. 创建员工
	vector<Worker> vec_worker;
	create_worker(vec_worker);

	// 2. 员工分组
	multimap<int, Worker> mmp_worker;  // int: 部门编号; Worker: 员工
	set_group(vec_worker, mmp_worker);

	// 3. 分组显示员工
	show_worker_by_group(mmp_worker);

	/*
		部门1----------------------
		姓名: 员工D     工资: 16500
		姓名: 员工I     工资: 16962
		姓名: 员工J     工资: 14464

		部门2----------------------
		姓名: 员工C     工资: 16334
		姓名: 员工E     工资: 19169
		姓名: 员工G     工资: 11478

		部门3----------------------
		姓名: 员工A     工资: 10041
		姓名: 员工B     工资: 18467
		姓名: 员工F     工资: 15724
		姓名: 员工H     工资: 19358
	*/

	system("pause");
	return 0;
}

4. STL：函数对象

4.1 函数对象

4.1.1 函数对象概念

概念：

• 重载函数调用操作符的类，其对象常称为函数对象。
• 函数对象使用重载的()时，行为类似函数调用，也叫仿函数

本质：函数对象(仿函数)是一个类，不是一个函数。

仿函数除了可以用类class实现外，还可以用结构体struct实现。二者只要重载了operator()都可以称为仿函数。

4.1.2 函数对象使用

特点：

• 函数对象在使用时，可以像普通函数那样调用，可以有参数，可以有返回值
• 函数对象超出普通函数的概念，函数对象可以有自己的状态（因为本质上是一个类/结构体，可以有自定义内容）
• 函数对象可以作为参数传递

示例：

#include <iostream>
using namespace std;
#include <string>


// 仿函数
/*
特点：
	1. 函数对象在使用时，可以像普通函数那样调用，可以有参数，可以有返回值
	2. 函数对象超出普通函数的概念，函数对象可以有自己的状态（因为本质上是一个类/结构体，可以有自定义内容）
	3. 函数对象可以作为参数传递
*/


// 1. 函数对象在使用时，可以像普通函数那样调用，可以有参数，可以有返回值
class MyAdd {
public:
	int operator()(int v1, int v2) {
		return v1 + v2;
	}
};


void test01() {
	MyAdd my_add;
	int res = my_add(10, 10);
	cout << "res: " << res << endl;  // 20
}


// 2. 函数对象超出普通函数的概念，函数对象可以有自己的状态（因为本质上是一个类 / 结构体，可以有自定义内容）
class MyPrint {
public:
	MyPrint() {
		this->obj_count = 0;
		this->class_count += 1;
	}

public:
	void operator()(string str) {
		cout << str << endl;
		this->obj_count += 1;
	}

	int get_call_obj_count() {
		return this->obj_count;
	}

	int get_call_class_count() {
		return this->class_count;
	}

private:
	int obj_count;  // 内部自己的状态：统计类对象调用了多少次
	static int class_count;  // 内部自己的状态：统计类被创建了多少次
};
int MyPrint::class_count = 0;  // static属性需要在类外初始化


void test02() {
	MyPrint mp;
	mp("Hello World!");  // Hello World!
	mp("Hello World!");  // Hello World!
	mp("Hello World!");  // Hello World!
	mp("Hello World!");  // Hello World!
	mp("Hello World!");  // Hello World!

	cout << "mp这个仿函数被调用的次数为: " << mp.get_call_obj_count() << endl;  // 5

	MyPrint mp2;
	MyPrint mp3;
	cout << "MyPrint这个类被创建的次数为: " << mp.get_call_class_count() << endl;  // 3
}


// 3. 函数对象可以作为参数传递
void do_print(MyPrint& mp, string str) {
	mp(str);
}

void test03() {
	MyPrint mp;
	do_print(mp, "Hello C++");  // Hello C++
}


int main() {
	
	test01();
	test02();
	test03();

	system("pause");
	return 0;
}

4.2谓词

在 C++ 中，谓词（Predicate）是一个可调用对象，它接受一个或多个参数并返回一个布尔值，用于对序列中的元素进行测试或筛选。谓词通常用于标准库算法中，例如 std::find_if()、std::remove_if() 等。

predicate：美 [ˈpredɪkeɪt] 英 ['predɪkət]
v.断言；使基于；使以…为依据；表明
adj.述语的；谓项的
n.谓语
网络谓词；述词；断定

4.2.1 谓词概念

概念：返回bool类型的仿函数称为谓词。谓词分为两种：

• 如果operator(参数1)接受一个参数，那么叫做一元谓词
• 如果operator(参数1, 参数2)接受两个参数，那么叫做二元谓词

示例：

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>
#include <set>


// 谓词：仿函数的返回值类型是bool，则称这个仿函数为谓词
/*
	1. 如果operator()接受一个参数，那么叫做一元谓词
	2. 如果operator()接受两个参数，那么叫做二元谓词
*/
class GreaterFive {
public:
	// 1. 如果operator()接受一个参数，那么叫做一元谓词
	bool operator()(int val) {
		if (val > 5)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
};


void test01() {
	vector<int> vec;
	for (int i = 0; i < 10; i++)
	{
		vec.push_back(i);
	}

	// 查找容器中有没有大于5的数字
	// find_if(开始区间, 结束区间, 谓词)
	vector<int>::iterator it = find_if(vec.begin(), vec.end(), GreaterFive());  // GreaterFive()为匿名仿函数对象
	if (it == vec.end()) {
		cout << "未找到" << endl;
	}
	else {
		cout << "找到了大于5的数字，为: " << *it << endl;  // 找到了大于5的数字，为: 6
	}
}


class MyCompare {
public:
	// 2. 如果operator()接受两个参数，那么叫做二元谓词
	bool operator()(int v1, int v2) const {
		return v1 > v2;
	}
};


void test02() {
	vector<int> vec;
	for (int i = 0; i < 5; i++)
	{
		vec.push_back(rand() % 100);
	}

	vector<int> vec2(vec);

	sort(vec.begin(), vec.end());
	for (vector<int>::iterator it = vec.begin(); it != vec.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;  // 0 34 41 67 69

	
	// 使用函数对象，改变其算法策略，将默认的升序改为降序
	// sort(区间1, 区间2, 谓词)
	sort(vec2.begin(), vec2.end(), MyCompare());
	for (vector<int>::iterator it = vec2.begin(); it != vec2.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;  // 69 67 41 34 0

	
	// 在我们之前学set这种自动排序的容器时，改变其排序方式用的就是谓词
	set<int, MyCompare> st;
	for (int i = 0; i < 5; i++) {
		st.insert(rand() % 100);
	}

	for (set<int, MyCompare>::iterator it = st.begin(); it != st.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;  // 78 64 62 58 24
}


int main() {

	test01();
	test02();

	system("pause");
	return 0;
}

4.3 内建国数对象

概念：STL内建了一些函数对象，我们可以直接拿来用。

分类：

1. 算术仿函数
2. 关系仿函数
3. 逻辑仿函数

用法：

• 这些仿函数所产生的对象，用法和一般函数完全相同
• 使用内建函数对象，需要引入头文件#include<functional>

4.3.1 算术仿函数

功能描述：实现四则运算。

仿函数原型	含义
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>	取反仿函数

其中negate是一元运算，其他都是二元运算。

注意：使用内建函数对象时，需要引入头文件#include <functional>

示例：

#include <iostream>
using namespace std;
#include <string>
#include <functional>  // 内建函数对象的头文件


// 内建函数对象（内建仿函数）：算术仿函数
/*
	1. template<class T> T plus<T>;  // 加法仿函数
	2. template<class T> T minus<T>;  // 减法仿函数
	3. template<class T> T multiplies<T>;  // 乘法仿函数
	4. template<class T> T divides<T>;  // 除法仿函数
	5. template<class T> T modulus<T>;  // 取模仿函数
	6. template<class T> T negate<T>;  // 取反仿函数
*/
void test01() {
	// 1. template<class T> T plus<T>;  // 加法仿函数
	plus<int> pls;
	auto res = pls(10, 20);
	cout << "[plus]res: " << res << endl;  // 30
}


void test02() {
	// 2. template<class T> T minus<T>;  // 减法仿函数
	float res1 = minus<float>()(3.14f, 1.11f);
	float res2 = minus<float>()(3.14, 1.11);
	double res3 = minus<float>()(3.14, 1.11);
	cout << "[minus]res1: " << res1 << endl;  // 2.03
	cout << "[minus]res2: " << res2 << endl;  // 2.03
	cout << "[minus]res3: " << res3 << endl;  // 2.03
}


void test03() {
	// 3. template<class T> T multiplies<T>;  // 乘法仿函数
	auto res = multiplies<long>()(100, 10);
	cout << "[multiplies]res: " << res << endl;  // 1000
}


void test04() {
	// 4. template<class T> T divides<T>;  // 除法仿函数
	auto res = divides<long long>()(100, 10);
	cout << "[divides]res: " << res << endl;  // 10
}


void test05() {
	// 5. template<class T> T modulus<T>;  // 取模仿函数
	auto res = modulus<int>()(10, 3);
	cout << "[modulus]res: " << res << endl;  // 1
}


void test06() {
	// 6. template<class T> T negate<T>;  // 取反仿函数
	negate<int> n;
	auto res = n(50);
	cout << "[negate]res: " << res << endl;  // res: -50
}


int main() {

	test01();
	test02();
	test03();
	test04();
	test05();
	test06();

	system("pause");
	return 0;
}

4.3.2 关系仿函数

功能描述：实现关系对比。

仿函数原型	含义
template<class T> bool equal_to<T>	等于
template<class T> bool not_equal_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>	小于等于

注意：

1. 这些关系仿函数可以直接当作sort的谓词使用，不用我们自己写了
2. greater<>、less<>、greater_equal<>、less_equal<>是我们常用的
3. 会自动排序的容器（set、multiset、map、multiset）默认使用的是less<>谓词

在C++中会自动排序的容器只有四个：set、multiset、map、multiset

示例：

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>
#include <functional>  // 内建函数对象的头文件


// 内建函数对象（内建仿函数）：关系仿函数
/*
	1. template<class T> bool equal_to<T>;  // 等于
	2. template<class T> bool not_equal_to<T>;  // 不等于
	3. template<class T> bool greater<T>;  // 大于
	4. template<class T> bool greater_equal<T>;  // 大于等于
	5. template<class T> bool less<T>;  // 小于
	6. template<class T> bool less_equal<T>;  // 小于等于
*/
// 以greater<>举例
class VectorCompare {
public:
	bool operator () (int v1, int v2) const {
		return v1 > v2;
	}
};


void test01() {
	vector<int> vec;
	for (int i = 0; i < 5; i++)
	{
		vec.push_back(rand() % 100);
	}

	for (vector<int>::iterator it = vec.begin(); it != vec.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;  // 41 67 34 0 69

	// 降序排序（使用自定义的谓词）
	sort(vec.begin(), vec.end(), VectorCompare());

	for (vector<int>::iterator it = vec.begin(); it != vec.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;  // 69 67 41 34 0
}


void test02() {
	vector<int> vec;
	for (int i = 0; i < 5; i++)
	{
		vec.push_back(rand() % 100);
	}

	for (vector<int>::iterator it = vec.begin(); it != vec.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;  // 24 78 58 62 64

	// 降序排序（使用内建函数greater）
	sort(vec.begin(), vec.end(), greater<int>());

	for (vector<int>::iterator it = vec.begin(); it != vec.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;  // 78 64 62 58 24
}


int main() {

	test01();
	test02();

	system("pause");
	return 0;
}

4.3.3 逻辑仿函数

功能描述：实现逻辑运算。

仿函数原型	含义
template<class T> bool logical_and<T>	逻辑与
template<class T> bool logical_or<T>	逻辑或
template<class T> bool logical_not<T>	逻辑非

示例：

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>  // transform的头文件
#include <functional>  // 内建函数对象的头文件


// 内建函数对象（内建仿函数）：逻辑仿函数
/*
	1. template<class T> bool logical_and<T>;  // 逻辑与
	2. template<class T> bool logical_or<T>;  // 逻辑或
	3. template<class T> bool logical_not<T>;  // 逻辑非
*/
// 以逻辑非logical_not<>举例
void test() {
	vector<bool> vec;
	vec.push_back(true);
	vec.push_back(true);
	vec.push_back(false);
	vec.push_back(true);
	vec.push_back(false);
	vec.push_back(false);

	for (vector<bool>::iterator it = vec.begin(); it != vec.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;  // 1 1 0 1 0 0


	// 利用逻辑非仿函数，将容器vec搬运到容器vec2中，并执行取反的操作
	vector<bool> vec2;
	vec2.resize(vec.size());  // 指定容器的大小，否则没有空间进行搬运

	// transform(原容器的开始, 原容器的结束, 目标容器的开始, 仿函数)
	transform(vec.begin(), vec.end(), vec2.begin(), logical_not<bool>());
	for (vector<bool>::iterator it = vec2.begin(); it != vec2.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;  // 0 0 1 0 1 1
}


int main() {

	test();

	system("pause");
	return 0;
}

5. STL的常用算法

概述：算法主要是由头文件<algorithm>、<functional>、<numeric>组成。

• <algorithm>是所有STL头文件中最大的一个，范围涉及到比较、交换、查找、遍历操作、复制、修改等等
• <numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数
• <functional>定义了一些模板类，用以声明函数对象（仿函数）。

C++中的函数对象就是仿函数（Functor）。仿函数是一种重载了函数调用运算符()的对象，可以像函数一样被调用。仿函数可以像函数指针一样传递，也可以像普通对象一样拥有状态，因此在某些情况下可以比函数指针更加灵活和高效。

5.1 常用遍历算法

学习目标：掌握常用的遍历算法。

算法简介：

• for_each：遍历容器
• transform：搬运容器到另一个容器中

5.1.1 for_each

功能描述：实现遍历容器。

函数原型	含义
for_each(iterator beg, iterator end, _func);	遍历算法遍历容器元素

其中：

• beg：开始迭代器
• end：结束迭代器
• _func：函数或者函数对象

总结: for_each在实际开发中是最常用遍历算法，需要熟练掌握。

示例：

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>
#include <functional>  // 内建函数对象的头文件


// 常用的遍历算法：for_each
/*
for_each(iterator beg, iterator end, _func);  // 遍历算法遍历容器元素

	其中：
	+ beg：开始迭代器
	+ end：结束迭代器
	+ _func：函数或者函数对象
*/
class Print02 {
public:
	void operator()(int val) const {
		cout << val << " ";
	}
};
void test() {
	vector<int> vec;
	for (int i = 0; i < 10; i++)
	{
		vec.push_back(i);
	}

	// 传统的for循环遍历
	for (vector<int>::iterator it = vec.begin(); it != vec.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;  // 0 1 2 3 4 5 6 7 8 9


	// for_each(开始迭代器, 结束迭代器, 函数)
	// 方法1：利用普通函数（匿名函数）
	auto print01 = [](int val) {
		cout << val << " ";
	};
	for_each(vec.begin(), vec.end(), print01);
	cout << endl;  // 0 1 2 3 4 5 6 7 8 9

	// 方法2：利用仿函数（函数对象）
	for_each(vec.begin(), vec.end(), Print02());
	cout << endl;  // 0 1 2 3 4 5 6 7 8 9
}


int main() {

	test();

	system("pause");
	return 0;
}

5.1.2 transform

功能描述：搬运容器到另一个容器中。

函数原型	含义
transform(iterator beg1, iterator end1, iterator beg2, _func);	搬运容器到另一个容器中

其中：

• beg1：源容器开始迭代器 —— vec1.begin()
• end1：源容器结束迭代器 —— vec1.end()
• beg2：目标容器开始迭代器 —— vec2.begin()
• _func：函数或者函数对象 —— fn()

注意：

1. 目标容器需要提前开辟空间，否则搬不进去（会报错）。
2. 在写搬运规则的时候我们可以对原数据进行操作

示例：

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>
#include <functional>  // 内建函数对象的头文件


// 常用的遍历算法：transform
/*
transform(iterator beg1, iterator end1, iterator beg2, _func);  // 搬运容器到另一个容器中

其中：
	+ beg1：源容器开始迭代器 —— vec1.begin()
	+ end1：源容器结束迭代器 —— vec1.end()
	+ beg2：目标容器开始迭代器 —— vec2.begin()
	+ _func：函数或者函数对象 —— fn()
*/
class TransformFn {
public:
	int operator()(int v) const {
		// 在这里可以一些额外的操作
		return v * 100;
	}
};


class MyPrint {
public:
	void operator()(int val) const {
		cout << val << " ";
	}
};


void test() {
	vector<int> vec;
	for (int i = 0; i < 10; i++)
	{
		vec.push_back(i);
	}

	vector<int> vec_target;  // 这样定义的容器是没有空间的
	vec_target.resize(vec.size());  // 需要我们提前开辟空间

	transform(vec.begin(), vec.end(), vec_target.begin(), TransformFn());

	for_each(vec_target.begin(), vec_target.end(), MyPrint());
	cout << endl;  // 0 100 200 300 400 500 600 700 800 900
}


int main() {

	test();

	system("pause");
	return 0;
}

5.2 常用查找算法

学习目标：掌握常用的查找算法。

算法简介：

1. find()：查找元素
2. find_if()：按条件查找元素
3. adjacent_find()：查找相邻重复元素
4. binary_search()：二分查找法
5. count()：统计元素个数
6. count_if()：按条件统计元素个数

5.2.1 find

功能描述：查找指定元素，找到返回指定元素的迭代器，找不到返回结束迭代器end()。

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

其中：

• beg：开始迭代器
• end：结束迭代器
• value：查找的元素

总结：利用find()可以在容器中找指定的元素，返回值是迭代器。不管有没有找到，返回值都是一个迭代器。

示例：

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>


// 常用的查找算法：find
/*
find(iterator beg, iterator end, value);  // 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器end()的位置

其中：
	+ beg：开始迭代器
	+ end：结束迭代器
	+ value：查找的元素
*/
template <class T>
void print_vec(vector<T>& vec) {
	for (class vector<T>::iterator it = vec.begin(); it != vec.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}


// 查找内置数据类型
void test01() {
	vector<int> vec;
	for (int i = 0; i < 10; i++)
	{
		vec.push_back(i);
	}
	print_vec(vec);  // 0 1 2 3 4 5 6 7 8 9


	// 查找容器中是否有5这个元素
	vector<int>::iterator pos = find(vec.begin(), vec.end(), 5);
	if (pos == vec.end()) {
		cout << "没有找到" << endl;
	}
	else {
		cout << "找到了: " << *pos << endl;  // 找到了: 5
	}
}


// 查找自定义数据类型
class Person {
public:
	Person(string name, int age) {
		this->name = name;
		this->age = age;
	}

public:
	bool operator==(const Person& p) const {
		if (this->name == p.name && this->age == p.age)
		{
			return true;
		}
		else
		{
			return false;
		}
	}

public:
	string name;
	int age;
};


void test02() {
	vector<Person> vec;

	Person p1 = Person("张三", 20);
	Person p2 = Person("李四", 30);
	Person p3 = Person("王五", 40);

	vec.push_back(p1);
	vec.push_back(p2);
	vec.push_back(p3);

	Person pp = Person("李四", 30);

	// find()函数判断是否找到用的是==运算符，而自定义数据类型需要重载==运算符
	vector<Person>::iterator it = find(vec.begin(), vec.end(), pp);
	if (it == vec.end())
	{
		cout << "没有找到" << endl;
	}
	else
	{
		cout << "找到了:\t姓名:" << it->name << "\t年龄: " << it->age << endl;
		// 找到了: 姓名:李四       年龄: 30
	}
}


int main() {

	test01();
	test02();

	system("pause");
	return 0;
}

5.2.2 find_if

功能描述：按条件查找元素。

函数原型	含义
find_if(iterator beg, iterator end, _pred);	按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置

其中：

• beg：开始迭代器
• end：结束迭代器
• _Pred：函数或者谓词(返回bool类型的仿函数)

示例：

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>


// 常用的查找算法：find_if
/*
find_if(iterator beg, iterator end, _pred);  // 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置

	其中：
	+ beg：开始迭代器
	+ end：结束迭代器
	+ _Pred：函数或者谓词(返回bool类型的仿函数)
*/
template <class T>
void print_vec(vector<T>& vec) {
	for (class vector<T>::iterator it = vec.begin(); it != vec.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}


class GreaterFive {
public:
	bool operator()(int value) const {
		return value > 5;  // 这样比写if...else要简洁很多
	}
};


// 查找内置数据类型
void test01() {
	vector<int> vec;
	for (int i = 0; i < 10; i++)
	{
		vec.push_back(i);
	}
	print_vec(vec);  // 0 1 2 3 4 5 6 7 8 9


	// 按条件查找元素
	vector<int>::iterator it = find_if(vec.begin(), vec.end(), GreaterFive());

	if (it == vec.end()) {
		cout << "没有找到" << endl;
	}
	else {
		cout << "找到了: " << *it << endl;  // 找到了: 6
	}
}


// 查找自定义数据类型
class Person {
public:
	Person(string name, int age) {
		this->name = name;
		this->age = age;
	}

public:
	string name;
	int age;
};


void print_Person_vec(const vector<Person>& vec) {
	int idx = 0;
	for (vector<Person>::const_iterator it = vec.begin(); it != vec.end(); it++)
	{
		cout << "第[" << idx << "]个元素->\t" << "姓名: " << it->name << "\t年龄: " << it->age << endl;
		idx += 1;
	}
}


class PersonFindCondition {
public:
	bool operator()(const Person& p) const {
		return p.age > 20;
	}
};


void test02() {
	vector<Person> vec;

	Person p1 = Person("aaa", 10);
	Person p2 = Person("bbb", 20);
	Person p3 = Person("ccc", 30);
	Person p4 = Person("ddd", 40);

	vec.push_back(p1);
	vec.push_back(p2);
	vec.push_back(p3);
	vec.push_back(p4);

	print_Person_vec(vec);
	/*
		第[0]个元素->   姓名: aaa       年龄: 10
		第[1]个元素->   姓名: bbb       年龄: 20
		第[2]个元素->   姓名: ccc       年龄: 30
		第[3]个元素->   姓名: ddd       年龄: 40
	*/


	// 找年龄大于20的人
	vector<Person>::iterator it = find_if(vec.begin(), vec.end(), PersonFindCondition());
	if (it == vec.end()) {
		cout << "未找到" << endl;
	}
	else {
		cout << "找到了: \t姓名: " << it->name << "\t年龄: " << it->age << endl;  
		// 找到了:         姓名: ccc       年龄: 30
	}
}


int main() {

	test01();
	test02();

	system("pause");
	return 0;
}

5.2.3 adjacent_find

功能描述：查找相邻重复元素。

总结：面试题中如果出现查找相邻重复元素，记得用STL中的adjacent_find()算法。

函数原型	含义
adjacent_find(iterator beg, iterator end);	查找相邻重复元素，返回相邻元素的第一个位置的迭代器

其中：

• beg：开始迭代器
• end：结束迭代器

示例：

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>


// 常用的查找算法：adjacent_find
/*
adjacent_find(iterator beg, iterator end);  // 查找相邻重复元素，返回相邻元素的第一个位置的迭代器

	其中：
	+ beg：开始迭代器
	+ end：结束迭代器
*/
void test() {
	vector<int> vec;
	vec.push_back(0);
	vec.push_back(2);
	vec.push_back(0);
	vec.push_back(3);
	vec.push_back(1);
	vec.push_back(4);
	vec.push_back(3);  // 应该返回指向这个元素的迭代器
	vec.push_back(3);
	vec.push_back(2);
	vec.push_back(1);
	vec.push_back(2);


	vector<int>::iterator pos = adjacent_find(vec.begin(), vec.end());
	if (pos == vec.end()) {
		cout << "未查到相邻重复元素!" << endl;
	}
	else {
		cout << "找到相邻重复元素，第一个重复的元素为: " << *pos << endl;
		// 找到相邻重复元素，第一个重复的元素为: 3
	}
}


int main() {

	test();

	system("pause");
	return 0;
}

5.2.4 binary_search

功能描述：查找指定元素是否存在。

函数原型	含义
bool binary_search(iterator beg, iterator end, value);	查找指定的元素，查到返回true否则false

注意：

• 在无序序列中不可用（二分查找本身就只适用于有序序列）
• 二分查找返回的是bool，不是一个iterator
• beg：开始迭代器
• end：结束迭代器
• value：查找的元素
• 如果容器本身是无序的，二分查找不会报错，但结果将不可靠！
• 有序的容器只有：set, multiset, map, multimap

总结：二分查找法查找效率很高，值得注意的是查找的容器中元素必须的有序序列，否则结果不可靠！

---

二分查找是一种在有序数组中查找目标值的算法，其时间复杂度为 $O({\log }^n)$。
这是因为在每一次比较中，我们都将搜索范围缩小一半，因此在最坏情况下，我们需要进行 log n 次比较才能找到目标值。因此，二分查找的时间复杂度为 $O({\log }^n)$。

需要注意的是：

1. 二分查找只适用于有序数组。如果数组是无序的，我们需要先对其进行排序，这将增加算法的时间复杂度。
2. 在算法分析中，通常使用对数的底数不重要，因为不同底数的对数之间只相差一个常数因子。因此，我们通常使用 $\log$ 来表示对数，而不指定底数。在计算机科学中，通常默认对数的底数为 2。但是，在某些特定的情况下，我们可能需要使用其他底数的对数，这时我们需要明确指定底数。

---

示例：

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>


// 常用的查找算法：binary_search
/*
bool binary_search(iterator beg, iterator end, value);  // 查找指定的元素，查到返回true否则false

	其中：
	+ beg：开始迭代器
	+ end：结束迭代器
	+ value：查找的元素

	注意：
	+ 在无序序列中不可用（二分查找本身就只适用于有序序列）
	+ 二分查找返回的是bool，不是一个iterator
*/
void test() {
	vector<int> vec;
	for (int i = 0; i < 10000000; i++)
	{
		vec.push_back(i);
	}


	// 查找容器中是否有元素50000
	int find_elem = 50000;
	bool res = binary_search(vec.begin(), vec.end(), find_elem);
	if (res) {
		cout << "找到了!" << endl;  // 找到了!
	}
	else {
		cout << "找不到!" << endl;
	}
}


int main() {

	test();

	system("pause");
	return 0;
}

5.2.5 count

功能描述：统计元素个数。

函数原型	含义
int count(iterator beg, iterator end, value);	统计元素出现次数

其中：

• beg：开始迭代器
• end：结束迭代器
• value：查找的元素

示例：

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>


// 常用的查找算法：count
/*
int count(iterator beg, iterator end, value);  // 统计元素出现次数

	其中：
	+ beg：开始迭代器
	+ end：结束迭代器
	+ value：查找的元素
*/


// 统计内置数据类型
void test01() {
	vector<int> vec;
	vec.push_back(10);
	vec.push_back(20);
	vec.push_back(40);
	vec.push_back(30);
	vec.push_back(30);
	vec.push_back(40);
	vec.push_back(30);
	vec.push_back(50);
	vec.push_back(50);


	// 统计元素
	int count_elem = 30;
	int res = count(vec.begin(), vec.end(), count_elem);
	cout << "元素[" << count_elem << "]出现的次数为: " << res << endl;
	// 元素[30]出现的次数为: 3
}


// 统计自定义数据类型
class Person {
public:
	Person(string nm, int ag) {
		this->name = nm;
		this->age = ag;
	}

public:
	bool operator==(const Person& p)const {
		if (this->age == p.age) {
			return true;
		}
		else {
			return false;
		}
	}

public:
	string get_name() {
		return this->name;
	}

	int get_age() {
		return this->age;
	}

private:
	string name;
	int age;
};
void test02() {
	vector<Person> vec;

	vec.push_back(Person("aaa", 10));
	vec.push_back(Person("bbb", 20));
	vec.push_back(Person("ccc", 30));
	vec.push_back(Person("ddd", 40));
	vec.push_back(Person("eee", 30));
	vec.push_back(Person("fff", 30));
	vec.push_back(Person("ggg", 30));


	// 统计元素：count()函数进行对比使用的是==，我们自定义数据类型时需要重载==
	Person count_p = { "张三", 30 };
	int res = count(vec.begin(), vec.end(), count_p);
	cout << "和[" << count_p.get_name() << "]同岁的人有: " << res << "个。" << endl;
	// 和[张三]同岁的人有: 4个。
}


int main() {

	test01();
	test02();

	system("pause");
	return 0;
}

---

Q：上面这段代码中，为什么可以直接使用p.age，age不应该是私有属性吗？而且Person类对象p是传入的类，不应该调用不了它的私有方法吗？

A：确实，传入的参数 p 是 Person 类的一个对象，它的成员变量 age 是私有属性，外部无法直接访问。但是，operator== 方法是在 Person 类的内部定义的，因此它可以访问 p 的私有成员变量。这是因为，类的成员函数无论是公有的、私有的或者受保护的都可以访问该类的私有成员变量，因为类的成员函数是该类的一部分，相当于类的内部函数。所以在 operator== 方法中，可以直接访问 p.age 私有成员变量。

5.2.6 count_if

功能描述：按条件统计元素个数。

函数原型	含义
count_if(iterator beg, iterator end, _Pred);	按条件统计元素出现次数

其中：

• beg：开始迭代器
• end：结束迭代器
• _Pred：函数或者谓词(返回bool类型的仿函数)

示例：

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>


// 常用的查找算法：count_if
/*
int count_if(iterator beg, iterator end, _Pred);  // 按条件统计元素出现次数

	其中：
	+ beg：开始迭代器
	+ end：结束迭代器
	+ value：查找的元素
*/


// 统计内置数据类型
class Greater20 {
public:
	bool operator()(int val) const {
		return val > 20;
	}
};


void test01() {
	vector<int> vec;
	vec.push_back(10);
	vec.push_back(20);
	vec.push_back(40);
	vec.push_back(30);
	vec.push_back(30);
	vec.push_back(40);
	vec.push_back(30);
	vec.push_back(50);
	vec.push_back(50);


	// 统计大于20的元素个数
	// count_if(beg, end, _pred)
	int res = count_if(vec.begin(), vec.end(), Greater20());
	cout << "容器中大于20的元素的个数为: " << res << endl;
	// 容器中大于20的元素的个数为: 7
}


// 统计自定义数据类型
class Person {
public:
	Person(string nm, int ag) {
		this->name = nm;
		this->age = ag;
	}

public:
	string get_name() const {
		return this->name;
	}

	int get_age() const {
		return this->age;
	}

private:
	string name;
	int age;
};


class AgeGreater20 {
public:
	bool operator()(const Person& p) const {
		return p.get_age() > 20;
	}
};


void test02() {
	vector<Person> vec;
	vec.push_back(Person("aaa", 35));
	vec.push_back(Person("bbb", 35));
	vec.push_back(Person("ccc", 35));
	vec.push_back(Person("ddd", 40));
	vec.push_back(Person("eee", 20));
	vec.push_back(Person("fff", 18));


	// 统计大于20岁的人员个数
	int res = count_if(vec.begin(), vec.end(), AgeGreater20());
	cout << "容器中大于20岁人员的个数为: " << res << endl;
	// 容器中大于20岁人员的个数为: 4
}


int main() {

	test01();
	test02();

	system("pause");
	return 0;
}

5.3常用排序算法

学习目标：掌握常用的排序算法。

算法简介：

1. sort()：对容器内元素进行排序
2. random_shuffle()：洗牌指定范围内的元素随机调整次序
3. merge()：容器元素合并，并存储到另一容器中
4. reverse()：反转指定范围的元素

5.3.1 sort

功能描述：对容器内元素进行排序。

函数原型	含义
void iterator sort(iterator beg, iterator end, _Pred);	按值的大小对元素进行排序，默认排序为升序排序

其中：

• beg：开始迭代器
• end：开始迭代器
• _Pred：谓词（规则）

注意：

1. 对于sort()函数，_Pred是可选的，默认是升序排序。
2. sort()函数没有返回值
3. 对内置数据类型进行排序时，可以使用<functional>库中提供的greater<数据类型>()这样的仿函数（函数对象）。

示例：

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>
#include <functional>


// 常用的排序算法：sort
/*
void iterator sort(iterator beg, iterator end, _Pred);  // 按值的大小对元素进行排序，默认排序为升序排序

	其中：
	+ beg：开始迭代器
	+ end：结束迭代器
	+ _Pred：谓词（规则）
*/
void print_vec(vector<int> vec) {
	for (vector<int>::iterator it = vec.begin(); it != vec.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}


class VectorIntCompare {
public:
	bool operator()(int v1, int v2) {
		return v1 > v2;
	}
};


void test() {
	vector<int> vec;
	for (int i = 0; i < 10; i++) {
		vec.push_back(rand() % 100);
	}

	print_vec(vec);  // 41 67 34 0 69 24 78 58 62 64


	// 排序
	// 1. 升序（默认）
	sort(vec.begin(), vec.end());
	print_vec(vec);  // 0 24 34 41 58 62 64 67 69 78

	// 2. 降序（用自己的，用functional提供的greater<int>()都可以）
	sort(vec.begin(), vec.end(), VectorIntCompare());
	print_vec(vec);  // 78 69 67 64 62 58 41 34 24 0

	sort(vec.begin(), vec.end(), greater<int>());
	print_vec(vec);  // 78 69 67 64 62 58 41 34 24 0
}


int main() {

	test();

	system("pause");
	return 0;
}

5.3.2 random_shuffle

功能描述：洗牌指定范围内的元素随机调整次序。

函数原型	含义
void random_shuffle(iterator beg, iterator end);	指定范围内的元素随机调整次序

其中：

• beg：开始迭代器
• end：开始迭代器

注意：

1. random_shuffle()没有返回值
2. 随机也是由随机种子控制，可以更改种子以达到真实随机的效果

总结：random_shuffle()洗牌算法比较实用，使用时记得加随机数种子。

示例：

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>


// 常用的排序算法：random_shuffle
/*
void random_shuffle(iterator beg, iterator end);  // 指定范围内的元素随机调整次序

	其中：
	+ beg：开始迭代器
	+ end：结束迭代器
*/
void print_vec(vector<int> vec) {
	for (vector<int>::iterator it = vec.begin(); it != vec.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}


void test() {
	vector<int> vec;
	for (int i = 0; i < 10; i++) {
		vec.push_back(i);
	}

	print_vec(vec);  // 0 1 2 3 4 5 6 7 8 9

	
	// 利用洗牌算法，打乱容器中元素的顺序（也是由随机种子控制的）
	random_shuffle(vec.begin(), vec.end());
	print_vec(vec);  // 8 1 9 2 0 5 7 3 4 6
}


int main() {

	test();

	system("pause");
	return 0;
}

5.3.3 merge

功能描述：两个容器元素合并，并存储到另一容器中。

函数原型	含义
merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);	容器元素合并，并存储到另一容器中

其中：

• beg1：容器1开始迭代器
• end1：容器1结束迭代器
• beg2：容器2开始迭代器
• end2：容器2结束迭代器
• dest：目标容器开始迭代器

注意：

1. 两个容器必须是有序的（两个容器的顺序必须是一致的，要么都是升序，要么都是降序）
2. merge()函数返回的是目标容器的开始迭代器（可以接收也可以不接收！）
3. 目标容器记得提前开辟足够的空间，否则会报错！

示例：

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>


// 常用的排序算法：merge
/*
iterator merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);  // 容器元素合并，并存储到另一容器中

其中：
	+ beg1：容器1开始迭代器
	+ end1：容器1结束迭代器
	+ beg2：容器2开始迭代器
	+ end2：容器2结束迭代器
	+ dest：目标容器开始迭代器
*/
void print_vec(vector<int> vec) {
	for (vector<int>::iterator it = vec.begin(); it != vec.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}


void test() {
	vector<int> vec1;
	vector<int> vec2;
	for (int i = 0; i < 10; i++) {
		if (i % 2 == 0) {
			vec1.push_back(i);  // Odd
		}
		else {
			vec2.push_back(i);  // Even
		}
	}

	print_vec(vec1);  // 0 2 4 6 8
	print_vec(vec2);  // 1 3 5 7 9


	// 目标容器
	vector<int> target_vec;
	// 提前给目标容器分配空间
	target_vec.resize(vec1.size() + vec2.size());

	vector<int>::iterator it = merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), target_vec.begin());
	print_vec(target_vec);  // 0 1 2 3 4 5 6 7 8 9

}


int main() {

	test();

	system("pause");
	return 0;
}

5.3.4 reverse

功能描述：将容器内元素进行反转。

函数原型	含义
reverse(iterator beg, iterator end);	反转指定范围的元素

其中：

• beg：开始迭代器
• end：开始迭代器

注意：

1. reverse()函数没有返回值

示例：

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>


// 常用的排序算法：reverse
/*
void reverse(iterator beg, iterator end);  // 反转指定范围的元素

其中：
	+ beg：开始迭代器
	+ end：开始迭代器
*/
void print_vec(vector<int> vec) {
	for (vector<int>::iterator it = vec.begin(); it != vec.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}


void test() {
	vector<int> vec;
	for (int i = 0; i < 10; i++) {
		vec.push_back(i);
	}

	print_vec(vec);  // 0 1 2 3 4 5 6 7 8 9


	// 翻转容器
	reverse(vec.begin(), vec.end());
	print_vec(vec);  // 9 8 7 6 5 4 3 2 1 0
}


int main() {

	test();

	system("pause");
	return 0;
}

5.4 常用拷贝和替换算法

学习目标：掌握常用的拷贝和替换算法。

算法简介:

• copy()：容器内指定范围的元素拷贝到另一容器中
• replace()：将容器内指定范围的旧元素修改为新元素
• replace_if()：容器内指定范围满足条件的元素替换为新元素
• swap()：互换两个容器的元素

5.4.1 copy

功能描述：容器内指定范围的元素拷贝到另一容器中。

函数原型	含义
iterator copy(iterator beg, iterator end, iterator dest;	按值查找元素，找到返回指定位置迭代器；找不到返回结束迭代器位置

其中：

• beg：开始迭代器
• end：结束迭代器
• dest：目标起始迭代器

注意：

1. copy()算法对于我们来说没有太大的必要，因为很多容器提供了拷贝构造，而且还可以用=运算符
2. 目标容器记得提前开辟空间

示例：

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>


// 常用的拷贝和替换算法：copy
/*
iterator copy(iterator beg, iterator end, iterator dest;  // 按值查找元素，找到返回指定位置迭代器；找不到返回结束迭代器位置

其中：
	+ beg：开始迭代器
	+ end：开始迭代器
	+ dest：目标起始迭代器
*/
void print_vec(vector<int> vec) {
	for (vector<int>::iterator it = vec.begin(); it != vec.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}


void test() {
	vector<int> vec;
	for (int i = 0; i < 10; i++)
	{
		vec.push_back(i);
	}

	print_vec(vec);  // 0 1 2 3 4 5 6 7 8 9


	// 创建目标容器并分配空间
	vector<int> target_vec;
	target_vec.resize(vec.size());

	// 拷贝
	copy(vec.begin(), vec.end(), target_vec.begin());

	print_vec(target_vec);  // 0 1 2 3 4 5 6 7 8 9

}


int main() {

	test();

	system("pause");
	return 0;
}

5.4.2 replace

功能描述：将容器内指定范围的旧元素修改为新元素。

函数原型	含义
void replace(iterator beg, iterator end, oldvalue, newvalue);	将区间内旧元素替换成新元素

其中：

• beg：开始迭代器
• end：结束迭代器
• oldvalue：旧元素
• newvalue：新元素

总结：replace()会替换区间内满足条件的所有元素（不是一个，而是所有）。

示例：

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>


// 常用的拷贝和替换算法：replace
/*
void replace(iterator beg, iterator end, oldvalue, newvalue);  // 将区间内旧元素替换成新元素

其中：
	+ beg：开始迭代器
	+ end：结束迭代器
	+ oldvalue：旧元素
	+ newvalue：新元素
*/
class PrintVector {
public:
	void operator()(int val) {
		cout << val << " ";
	}
};


void test() {
	vector<int> vec;
	vec.push_back(20);
	vec.push_back(30);
	vec.push_back(50);
	vec.push_back(40);
	vec.push_back(20);
	vec.push_back(10);
	vec.push_back(20);
	vec.push_back(20);

	cout << "替换前: " << endl;
	for_each(vec.begin(), vec.end(), PrintVector());
	cout << endl;  // 20 30 50 40 20 10 20 20


	// 将20替换为100
	replace(vec.begin(), vec.end(), 20, 100);

	cout << "替换后: " << endl;
	for_each(vec.begin(), vec.end(), PrintVector());
	cout << endl;  // 100 30 50 40 100 10 100 100
}


int main() {

	test();

	system("pause");
	return 0;
}

5.4.3 replace_if

功能描述：将区间内满足条件的元素，替换成指定元素。

函数原型	含义
void replace_if(iterator beg, iterator end, _pred, newvalue);	按条件替换元素，满足条件的替换成指定元素

其中：

• beg：开始迭代器
• end：结束迭代器
• _pred：谓词
• newvalue：替换的新元素

总结：replace_if()按条件查找，可以利用仿函数灵活筛选满足的条件。

示例：

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>


// 常用的拷贝和替换算法：replace_if
/*
void replace_if(iterator beg, iterator end, _pred, newvalue);  // 按条件替换元素，满足条件的替换成指定元素

其中：
	+ beg：开始迭代器
	+ end：结束迭代器
	+ _pred：谓词
	+ newvalue：替换的新元素
*/
class PrintVector {
public:
	void operator()(int val) {
		cout << val << " ";
	}
};


class GreaterThan30 {
public:
	bool operator()(int val) {
		return val >= 30;
	}
};


void test() {
	vector<int> vec;
	vec.push_back(20);
	vec.push_back(30);
	vec.push_back(50);
	vec.push_back(40);
	vec.push_back(20);
	vec.push_back(10);
	vec.push_back(20);
	vec.push_back(20);


	// 将>=30的元素替换为3000
	cout << "替换前:" << endl;
	for_each(vec.begin(), vec.end(), PrintVector());
	cout << endl;  // 20 30 50 40 20 10 20 20

	cout << "替换后:" << endl;
	
	replace_if(vec.begin(), vec.end(), GreaterThan30(), 3000);

	for_each(vec.begin(), vec.end(), PrintVector());
	cout << endl;  // 20 3000 3000 3000 20 10 20 20
}


int main() {

	test();

	system("pause");
	return 0;
}

5.4.4 swap

功能描述：互换两个容器的元素。

函数原型	含义
void swap(container c1, container c2);	互换两个容器的元素

其中：

• c1：容器1
• c2：容器2

注意：

1. 两个容器必须是同种类型的容器（包括<>里面的数据类型都要相同！）

示例:

#include <iostream>
using namespace std;
#include <string>
#include <vector>
#include <algorithm>


// 常用的拷贝和替换算法：swap
/*
swap(container c1, container c2);  // 互换两个容器的元素

其中：
	+ c1：容器1
	+ c2：容器2
*/
void print_vec(const vector<int>& vec) {
	for (vector<int>::const_iterator it = vec.begin(); it != vec.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}


void test() {
	vector<int> vec1;
	vector<int> vec2;

	for (int i = 0; i < 10; i++)
	{
		vec1.push_back(i);
		vec2.push_back(i + 100);
	}

	cout << "交换前: " << endl;
	print_vec(vec1);  // 0 1 2 3 4 5 6 7 8 9
	print_vec(vec2);  // 100 101 102 103 104 105 106 107 108 109


	cout << "交换后: " << endl;
	swap(vec1, vec2);
	print_vec(vec1);  // 100 101 102 103 104 105 106 107 108 109
	print_vec(vec2);  // 0 1 2 3 4 5 6 7 8 9
}


int main() {

	test();

	system("pause");
	return 0;
}

5.5 常用算术生成算法

学习目标：掌握常用的算术生成算法。

注意：算术生成算法属于小型算法，使用时包含的头文件为#include <numeric>

算法简介：

• accumulate：计算容器元素累计总和
• fill：向容器中添加元素

5.5.1 accumulate

功能描述：计算区间内容器元素累计总和。

函数原型	含义
T accumulate(iterator beg, iterator end, value);	计算容器元素累计总和

其中：

• beg：开始迭代器
• end：结束迭代器
• value：起始值

总结：accumulate()使用时头文件注意是<numeric>，这个算法很实用。可以理解为$\sum$

示例：

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;


// 常用的算术生成算法：accumulate
/*
T accumulate(iterator beg, iterator end, value);  // 计算容器元素累计总和

    其中：
    + beg：开始迭代器
    + end：结束迭代器
    + value：起始值
    
 */
void test() {
    vector<int> vec;

    for (int i = 0; i <= 100; i++) {
        vec.push_back(i);
    }

    // 参数3是起始的累加值（一般我们不用它）
    int total = accumulate(vec.begin(), vec.end(), 0);
    cout << "total: " << total << endl;  // total: 5050

    total = accumulate(vec.begin(), vec.end(), 1000);
    cout << "total: " << total << endl;  // total: 6050
}


int main() {

    test();

    system("pause");
    return 0;
}

5.5.2 fill

功能描述:向容器中填充指定的元素。

函数原型	含义
void fill(iterator beg, iterator end, value);	向容器中填充元素

其中：

• beg：开始迭代器
• end：结束迭代器
• value：起始值

总结：利用fill()可以将容器区间内元素慎充为指定的值。

示例：

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;


// 常用的算术生成算法：fill
/*
fill(iterator beg, iterator end, value);  // 向容器中填充元素

    其中：
    + beg：开始迭代器
    + end：结束迭代器
    + value：起始值

 */
template<class T>
void print_vec(vector<T>& vec) {
    for (vector<int>::iterator it=vec.begin();  it!=vec.end() ; it++) {
        cout << *it << " ";
    }
    cout << endl;
}


void test() {
    vector<int> vec;
    vec.resize(10);
    print_vec<int>(vec);  // 0 0 0 0 0 0 0 0 0 0

    // 后期使用fill()函数对容器重新填充
    fill(vec.begin(), vec.end(), 100);
    print_vec<int>(vec);  // 100 100 100 100 100 100 100 100 100 100
}


int main() {

    test();

    return 0;
}

5.6 常用集合算法

学习目标：掌握常用的集合算法。

算法简介：

1. set_intersection()：求两个容器的交集
2. set_union()：求两个容器的并集
3. set_difference()：求两个容器的差集

5.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：目标容器开始迭代器

注意：

1. 两个集合必须是有序序列，不然结果不能保证！
2. 目标容器开辟空间需要从两个容器中取小值：min(vec1.size(), vec2.size())，使用min时需要引入<algorithm>头文件
3. 遍历的时候要用set_intersection()函数提供的迭代器
4. 遍历容器的特殊写法：for (element_type & element : container) {循环体}

void print_vec(vector<int>& vec) {
	/*
	 这是C++11中引入的一种 "for-each" 循环语法，也叫 "范围 for 循环"。它可以遍历一个容器的所有元素，语法形式为：
		for (element_type & element : container) {循环体}

		其中 "element_type" 是容器中元素的类型，"element" 是对当前元素的引用，"container" 是被遍历的容器。
	 */
	for (int& it : vec) {
		cout << it << " ";
	}
	cout << endl;
}

示例：

#include <iostream>
#include <vector>
#include <algorithm>  // min的头文件

using namespace std;


// 常用的集合算法：set_intersection()
/*
set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);  // 求两个集合的交集

	其中：
	+ beg1：容器1开始迭代器
	+ end1：容器1结束迭代器
	+ beg2：容器2开始迭代器
	+ end2：容器2结束迭代器
	+ dest：目标容器开始迭代器

 */
void print_vec(vector<int>& vec) {
	/*
	 这是C++11中引入的一种 "for-each" 循环语法，也叫 "范围 for 循环"。它可以遍历一个容器的所有元素，语法形式为：
		for (element_type & element : container) {循环体}

		其中 "element_type" 是容器中元素的类型，"element" 是对当前元素的引用，"container" 是被遍历的容器。
	 */
	for (int& it : vec) {
		cout << it << " ";
	}
	cout << endl;
}


void test() {
	vector<int> vec1;
	vector<int> vec2;
	for (int i = 0; i < 10; i++) {
		vec1.push_back(i);  // 0~9
		vec2.push_back(i + 5);  // 5~14
	}
	print_vec(vec1);  // 0 1 2 3 4 5 6 7 8 9
	print_vec(vec2);  // 5 6 7 8 9 10 11 12 13 14


	// 创建目标容器
	vector<int> vec_target;
	// 目标容器需要提前开辟空间：最特殊的情况就是完全包含一个小容器，取min即可
	vec_target.resize(min(vec1.size(), vec2.size()));

	// set_intersection会返回交集的迭代器，指向交集的第最后一个元素的后一个位置
	auto it_end = set_intersection(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), vec_target.begin());

	// 遍历的时候要用set_intersection()函数提供的迭代器
	for_each(vec_target.begin(), vec_target.end(), [](int val) {cout << val << " "; });
	cout << endl;  // 5 6 7 8 9 0 0 0 0 0

	for_each(vec_target.begin(), it_end, [](int val) {cout << val << " "; });
	cout << endl;  // 5 6 7 8 9
}

int main() {

	test();

	return 0;
}

5.6.2 set_union

功能描述：求两个集合的并集。

函数原型	含义
iterator set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);	求两个集合的并集

其中：

• beg1：容器1开始迭代器
• end1：容器1结束迭代器
• beg2：容器2开始迭代器
• end2：容器2结束迭代器
• dest：目标容器开始迭代器

注意：

1. 两个集合必须是有序序列
2. 目标容器开辟空间需要两个容器大小的相加：target_vec.resize(vec1.size() + vec2.size());
3. set_union()返回值是并集中最后一个元素的下一个位置

示例：

#include <iostream>
#include <vector>
#include <algorithm>  // min的头文件

using namespace std;


// 常用的集合算法：set_union()
/*
iterator set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);  // 求两个集合的并集

	其中：
	+ beg1：容器1开始迭代器
	+ end1：容器1结束迭代器
	+ beg2：容器2开始迭代器
	+ end2：容器2结束迭代器
	+ dest：目标容器开始迭代器

 */
void print_vec(vector<int>& vec) {
	for (int val : vec) {
		cout << val << " ";
	}
	cout << endl;
}


void test() {
	vector<int> vec1;
	vector<int> vec2;
	for (int i = 0; i < 10; i++) {
		vec1.push_back(i);  // 0~9
		vec2.push_back(i + 5);  // 5~14
	}
	print_vec(vec1);  // 0 1 2 3 4 5 6 7 8 9
	print_vec(vec2);  // 5 6 7 8 9 10 11 12 13 14

	vector<int> target_vec;
	// 目标容器需要提前开辟空间，最特殊的情况就是两个容器没有交集
	target_vec.resize(vec1.size() + vec2.size());

	// 求并集
	auto it_end = set_union(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), target_vec.begin());

	// 遍历（错误写法）
	for_each(target_vec.begin(), target_vec.end(), [](int val) {cout << val << " "; });
	cout << endl;  // 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 0 0 0 0

	// 遍历（正确写法）
	for_each(target_vec.begin(), it_end, [](int val) {cout << val << " "; });
	cout << endl;  // 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
}

int main() {

	test();

	system("pause");
	return 0;
}

5.6.3 set_difference

功能描述：求两个集合的差集。

在数学中，给定两个集合A和B，它们的差集指的是只属于集合A而不属于集合B的元素组成的集合。差集可以用符号 “-” 表示，即 A - B。

例如，如果集合A包含 {1, 2, 3, 4}，集合B包含 {3, 4, 5, 6}，则 A - B 等于 {1, 2}，因为只有元素 1 和 2 属于集合A，而不属于集合B。

差集的结果是根据谁-谁，A-B和B-A的结果是不一样的。

函数原型	含义
iterator set_difference(iterator beg1，iterator end1，iterator beg2，iterator end2，iterator dest);	求两个集合的差集

其中：

• beg1：容器1开始迭代器
• end1：容器1结束迭代器
• beg2：容器2开始迭代器
• end2：容器2结束迭代器
• dest：目标容器开始迭代器

注意：

1. 两个集合必须是有序序列
2. 目标容器开辟空间需要从两个容器中取最大值：target_vec.resize(max(vec1.size(), vec2.size()));
3. set_difference()返回值是差集中最后一个元素的下一个位置

示例：

#include <iostream>
#include <vector>
#include <algorithm>  // min的头文件

using namespace std;


// 常用的集合算法：set_difference()
/*
iterator set_difference(iterator beg1，iterator end1，iterator beg2，iterator end2，iterator dest);  // 求两个集合的差集

	其中：
	+ beg1：容器1开始迭代器
	+ end1：容器1结束迭代器
	+ beg2：容器2开始迭代器
	+ end2：容器2结束迭代器
	+ dest：目标容器开始迭代器

 */
template<class T>
void print_vec(vector<T>& vec) {
	for (T val : vec) {
		cout << val << " ";
	}
	cout << endl;
}


void test() {
	vector<int> vec1;
	vector<int> vec2;
	for (int i = 0; i < 10; i++) {
		vec1.push_back(i);  // 0~9
		vec2.push_back(i + 5);  // 5~14
	}
	print_vec(vec1);  // 0 1 2 3 4 5 6 7 8 9
	print_vec(vec2);  // 5 6 7 8 9 10 11 12 13 14

	// 创建目标容器
	vector<int> target_vec;

	// 目标容器需要提前开辟空间，最特殊的情况就是两个容器没有交集 -> 取两个容器中大的size作为目标容器的开辟空间
	target_vec.resize(max(vec1.size(), vec2.size()));

	// 求并集
	auto it_end = set_difference(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), target_vec.begin());

	auto fn = [](int val) {cout << val << " ";};

	// 遍历（错误写法）
	for_each(target_vec.begin(), target_vec.end(), fn);
	cout << endl;  // 0 1 2 3 4 0 0 0 0 0

	// 遍历（正确写法）
	for_each(target_vec.begin(), it_end, fn);
	cout << endl;  // 0 1 2 3 4
}

int main() {

	test();

	system("pause");
	return 0;
}
se");
	return 0;
}