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

# 模版

模版的概念：模版就是建立通用的模具，大大提高代码的复用性。模版的特点：模版不可以直接使用，它只是一个框架，模版的通用并不是万能的。

# 函数模版

C++ 另一种编程思想称为泛型编程，主要利用的技术就是模版。
C++ 提供两种模版机制：函数模版和类模版。
函数模版的作用：建立一个通用函数，其函数返回值类型和形参类型可以不具体指定，用一个虚拟的类型来代表。
函数模版的语法： template<typename T> 函数声明或定义 。
解释： template = 声明创建模版， typename = 表示其后面的符号是一种数据类型，可以用 class 代替， T = 通用的数据类型，名称可以替换，通过为大写字母。

函数模版语法.cpp

	/**
	* 函数模版语法
	*/
	#include <iostream>

	using namespace std;

	// 函数模版
	template<typename T>
	// 声明一个模版
	void mySwap(T &a, T &b) {
	T temp = a;
	a = b;
	b = temp;
	}

	void test01() {
	int a = 10;
	int b = 20;
	// 利用函数模版进行交换
	// 1. 自动类型推导
	// mySwap(a, b);
	// 2. 显示指定类型
	mySwap<int>(a,b);

	cout << "a = " << a << endl;
	cout << "b = " << b << endl;
	}

	int main() {
	test01();
	}

总结：函数模版利用关键字 template 。使用函数模版有两种方式：自动类型推导、显示指定类型。模版的目的是为了提高复用性，将类型参数化。

# 函数模版注意事项

注意事项：自动类型推导，必须推导出一致的数据类型 T 才可以使用。模版必须要确定出 T 的数据类型才可以使用。

函数模版注意事项.cpp

	/**
	* 函数模版注意事项
	*/
	#include <iostream>

	using namespace std;

	// 函数模版注意事项
	template<class T>
	//typename 可以替换成 class
	// 声明一个模版
	void mySwap(T &a, T &b) {
	T temp = a;
	a = b;
	b = temp;
	}

	// 1. 自动类型推导，必须推导出一致的数据类型 T 才可以使用
	void test01() {
	int a = 10;
	int b = 20;
	char c = 'c';
	// mySwap (a, b);// 正确
	// mySwap (a, c);// 错误：推导不出一致的 T 类型
	cout << "a = " << a << endl;
	cout << "b = " << b << endl;
	}

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

	void test02() {
	// func ();// 错误：因为这种必须要指定数据类型
	func<int>();
	}

	int main() {
	test01();
	test02();
	}

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

# 函数模版案例

案例描述：利用函数模版封装一个排序的函数，可以对不同数据类型的数组进行排序。排序规则从大到小，排序算法为选择排序。并分别利用 char 数组和 int 数组进行测试。

函数模版案例.cpp

	/**
	* 函数模版案例
	*/
	#include <iostream>

	using namespace std;

	// 交换的函数模版
	template<typename T>
	void mySwap(T &a, T &b) {
	T temp = a;
	a = b;
	b = temp;
	}

	// 选择排序
	// 实现通用对数组进行排序的函数，规则：从大到小，算法：选择排序，并且测试 char 数组、int 数组。
	template<class T>
	void mySort(T arr[], int len) {
	for (int i = 0; i < len; i++) {
	// 认定最大值的下标
	int max = i;
	for (int j = i + 1; j < len; j++) {
	// 认定的最大值比遍历初的数值要小，这就说明 j 下标的元素才是真正的最大值
	if (arr[max] < arr[j]) {
	// 更新最大值下标
	max = j;
	}
	}
	if (max != i) {
	// 交换 max 和 i 下标的元素
	mySwap(arr[max], arr[i]);
	}
	}
	}

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

	void test01() {
	// 测试 char 数组
	char charArr[] = "badcfe";
	int num = sizeof(charArr) / sizeof(char);
	mySort(charArr, num);
	printArray(charArr,num);
	}

	void test02(){
	// 测试 int 数组
	int array[] = {11,12,34,15,4,96,10,63,58};
	int num = sizeof(array) / sizeof(int);
	mySort(array, num);
	printArray(array, num);
	}

	int main() {
	test01();
	test02();
	/**
	* 执行结果：
	* f e d c b a
	* 96 63 58 34 15 12 11 10 4
	*/
	}

# 普通函数与函数模版的区别

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

普通函数与函数模版的区别.cpp

	/**
	* 普通函数与函数模版的区别
	*/
	#include <iostream>

	using namespace std;

	// 3. 函数模版用显示指定类型，可以发生隐式类型转换

	// 普通函数
	// 1. 普通函数调用可以发生隐式类型转换
	int myAdd01(int a, int b) {
	return a + b;
	}

	void test01() {
	int a = 10;
	int b = 20;
	char c = 'c';// ASCLL 码：a = 97,c = 99
	cout << myAdd01(a, c) << endl;
	}

	// 函数模版
	// 2. 函数模版用自动类型推导，不可以发生隐式类型转换
	template<class T>
	T myAdd02(T a, T b) {
	return a + b;
	}

	void test02(){
	int a = 10;
	int b = 20;
	char c = 'c';
	// 自动类型推导
	// cout << myAdd02 (a, c) << endl; // 错误：无法推导出 c 的数据类型，因为 c 和 a 的数据类型不一致
	// 显示指定类型
	cout << myAdd02<int>(a, c) << endl;
	}

	int main() {
	test02();
	}

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

# 普通函数与函数模版调用规则

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

普通函数与函数模版调用规则.cpp

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

	using namespace std;

	// 如果只有声明没有具体的实现也会报错，并且普通调用不会自动走模版函数
	void myPrint(int a, int b);

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

	template<class T>
	void myPrint(T a, T b) {
	cout << "模版函数被调用" << endl;
	}

	template<class T>
	void myPrint(T a, T b, T c) {
	cout << "重载的模版函数被调用" << endl;
	}

	void test01() {
	int a = 10;
	int b = 20;
	// 1. 普通函数被调用
	myPrint(a, b);

	// 2. 通过空模版参数列表，强制调用函数模版
	myPrint<>(a, b);
	// 3. 重载的模版函数被调用
	myPrint<>(a, b, 100);

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

	int main() {
	test01();
	}

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

# 模版的局限性

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

示例1.cpp

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

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

示例2.cpp

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

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

因此 C++ 为了解决这种问题，提供了模版重载的技术，可以为这些特点的类型提供具体化的模版.

模版的局限性.cpp

	/**
	* 模版的局限性
	* 模版的通用性并不是万能的
	*/
	#include <iostream>

	using namespace std;

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

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

	void test01() {
	int a = 10;
	int b = 20;
	bool ref = myCompare(a, b);
	if (ref) {
	cout << "a == b" << endl;
	} else {
	cout << "a != b" << endl;
	}
	}

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

	string name;
	int age;
	};

	template<class T>
	bool myCompare(T &a, T &b) {
	if (a == b) {
	return true;
	} else {
	return false;
	}
	}

	// 利用具体化 Person 的版本实现代码，具体化优先调用
	bool myCompare(Person &p1, Person &p2) {
	if (p1.name == p2.name && p1.age == p2.age) {
	return true;
	} else{
	return false;
	}

	}

	void test02() {
	Person p1("Tom", 18);
	Person p2("Tom", 18);
	bool ref = myCompare(p1, p2);
	if (ref) {
	cout << "p1 == p2" << endl;
	} else {
	cout << "p1 != p2" << endl;
	}
	}

	int main() {
	test01();
	test02();
	}

总结：1. 利用具体化的模版，可以解决自定义类型的通用化。2. 学习模版并不是为了写模版，而是在 STL 能够运用系统提供的模版。

# 类模版基本语法

类模版作用：建立一个通用类，类中的成员，数据类型可以不具体制定，用一个虚拟的类型来代表，语法: template<typename T> 类 .

类模版基本语法.cpp

	/**
	* 类模版基本语法
	*/
	#include <iostream>

	using namespace std;

	#include <string>

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

	void showPerson() {
	cout << "name：" << this->name << " age：" << this->age << endl;
	}

	NameType name;
	AgeType age;
	};

	void test01() {
	Person<string, int> p1("张三", 18);
	p1.showPerson();
	}

	int main() {
	test01();
	}

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

# 类模版与函数模版的区别

类模版与函数模版的区别主要由两点：1. 类模版没有自动类型推导的使用方式. 2. 类模版在模版参数列表中可以有默认参数.

类模版与函数模版的区别.cpp

	/**
	* 类模版与函数模版的区别
	* 1. 类模版没有自动类型推导的使用方式
	* 2. 类模版在模版参数列表中可以有默认参数
	*/
	#include <iostream>

	using namespace std;

	// 类模版与函数模版的区别

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

	void showPerson() {
	cout << "name：" << this->name << " age：" << this->age << endl;
	}

	NameType name;
	AgeType age;
	};

	// 1. 类模版没有自动类型推导的使用方式
	void test01(){
	Person<string,int> p1("Tom",16);
	p1.showPerson();
	}

	// 2. 类模版在模版参数列表中可以有默认参数
	void test02(){
	Person<string> p1("Tom2",18);
	p1.showPerson();
	}


	int main() {
	test01();
	test02();
	}

# 类模版中成员函数创建时机

类模版中成员函数和普通类中成员函数创建时机是有区别的：1. 普通类中的成员函数一开始就可以创建. 2. 类模版中的成员函数在调用时才开始创建.

类模版中成员函数创建时机.cpp

	/**
	* 类模版中成员函数创建时机
	* 类模版中成员函数和普通类中成员函数创建时机是有区别的：
	* 1. 普通类中的成员函数一开始就可以创建.
	* 2. 类模版中的成员函数在调用时才开始创建.
	*/
	#include <iostream>

	using namespace std;

	class Person1 {
	public:
	void showPerson1() {
	cout << "Person1 show" << endl;
	}
	};

	class Person2 {
	public:
	void showPerson2() {
	cout << "Person2 show" << endl;
	}
	};

	template<class T>
	class MyClass {
	public:
	T obj;

	// 类模版中的成员函数
	void func1() {
	obj.showPerson1();
	}

	void func2(){
	obj.showPerson2();
	}

	};

	void test01(){
	MyClass<Person1> myClass;
	myClass.func1();
	// myClass.func2();
	}

	int main() {
	test01();
	}

总结：类模版中的成员函数并不是一开始就创建的，而是在调用时才会去创建。

# 类模版对象做函数参数

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

类模版对象做函数参数.cpp

	/**
	* 类模版对象做函数参数
	* 类模版实例化的对象，向函数传参的方式一共有三种传入方式：
	* 1. 指定传入的类型 (直接显示对象的数据类型).
	* 2. 参数模版化 (将对象中的参数变为模版进行传递).
	* 3. 整个类模版化 (将这个对象类型模版化进行传递).
	*/
	#include <iostream>

	using namespace std;

	// 类模版对象做函数参数
	template<class T1, class T2>
	class Person {
	public:
	Person(T1 name, T2 age) {
	this->name = name;
	this->age = age;
	}

	void showPerson() {
	cout << "name：" << this->name << " age：" << this->age << endl;
	}

	T1 name;
	T2 age;
	};

	// 1. 指定传入类型
	void printPerson1(Person<string, int> &p) {
	p.showPerson();
	}

	void test01() {
	Person<string, int> p1("孙悟空", 100);
	printPerson1(p1);
	}

	// 2. 参数模版化
	template<class T1, class T2>
	void printPerson2(Person<T1, T2> &p) {
	p.showPerson();
	cout << "T1的类型为：" << typeid(T1).name() << endl;
	cout << "T2的类型为：" << typeid(T2).name() << endl;
	}

	void test02() {
	Person<string, int> p2("猪八戒", 90);
	printPerson2(p2);
	}

	// 3. 整个类模版化
	template<class T>
	void printPerson3(T &p) {
	p.showPerson();
	cout << "T的数据类型为：" << typeid(T).name() << endl;
	}

	void test03() {
	Person<string, int> p3("沙悟净", 80);
	printPerson3(p3);
	}

	int main() {
	test01();
	test02();
	test03();
	}

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

# 类模版与继承

当类模版碰到继承时，需要注意一下几点：1. 当子类继承的父类是一个类模版时，子类在声明的时候，要指定出父类中 T 的类型. 2. 如果不指定，编译器无法给与子类分配内存. 3. 如果想灵活指出父类中 T 的数据类型，子类也需要变为类模版.

类模版与继承.cpp

	/**
	* 类模版与继承
	* 当类模版碰到继承时，需要注意一下几点
	* 当子类继承的父类是一个类模版时，子类在声明的时候，要指定出父类中 T 的类型
	* 如果不指定，编译器无法给与子类分配内存
	* 如果想灵活指出父类中 T 的数据类型，子类也需要变为类模版
	*/
	#include <iostream>

	using namespace std;

	// 类模版与继承
	template<class T>
	class Base {
	public:
	T m;
	};

	//class Son:public Base {}; // 错误，因为必须要知道父类中的 T 类型才能继承给子类

	class Son : public Base<int> {

	};

	void test01() {
	Son s1;
	}

	// 如果想灵活指定父类中 T 类型，子类也需要变为类模版
	template<class T1, class T2>
	class Son2 : public Base<T2> {
	public:
	Son2(){
	cout << "T1的类型为：" << typeid(T1).name() << endl;
	cout << "T2的类型为：" << typeid(T2).name() << endl;
	}
	T1 obj;
	};

	void test02() {
	Son2<int, char> son2;
	}

	int main() {
	test01();
	test02();
	}

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

# 类模版成员函数类外实现

掌握类模版中的成员函数并且在类外实现.

类模版成员函数类外实现.cpp

	/**
	* 类模版成员函数类外实现
	*/
	#include <iostream>

	using namespace std;

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

	void showPerson();
	// {
	// cout << "name：" << this->name << " age：" << this->age << endl;
	// }

	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>::showPerson() {
	cout << "name：" << this->name << " age：" << this->age << endl;
	}

	void test01() {
	Person<string,int> person("Tom",19);
	person.showPerson();
	}

	int main() {
	test01();
	}

总结：类模版中成员函数在类外实现时，需要加上模版参数列表才可以正常使用.

# 类模版分文件写

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

问题：问题：类模版中成员函数创建时机是在调用阶段，导致分文件编写时链接不到的问题

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

# 方式一

person.h

	#ifndef DEMO_PERSON_H
	#define DEMO_PERSON_H

	#endif //DEMO_PERSON_H

	// 防止头文件重复包含
	#pragma once

	#include <iostream>

	using namespace std;

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

	void showPerson();

	T1 name;
	T2 age;
	};

person.cpp

	#include "person.h"

	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>::showPerson() {
	cout << "姓名：" << this->name << " 年龄：" << this->age << endl;
	}

类模版分文件编写方式一.cpp

	/**
	* 类模版分文件编写
	* 掌握类模版成员函数分文件编写产生的问题以及解决方式
	*
	* 问题：类模版中成员函数创建时机是在调用阶段，导致分文件编写时链接不到的问题
	* 解决：
	* 解决方式一：直接包含.cpp 源文件
	* 解决方式二：将声明和实现写到同一个文件中，并更改后缀名为.hpp,hpp 是约定的名称，并不是强制
	*/
	#include <iostream>

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

	using namespace std;

	void test01(){
	Person<string,int> p1("Jerry",18);
	p1.showPerson();
	}

	int main() {
	test01();
	}

# 方式二

person.hpp

	#ifndef DEMO_PERSON_H
	#define DEMO_PERSON_H

	#endif //DEMO_PERSON_H

	// 防止头文件重复包含
	#pragma once

	#include <iostream>

	using namespace std;

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

	void showPerson();

	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>::showPerson() {
	cout << "姓名：" << this->name << " 年龄：" << this->age << endl;
	}

类模版分文件编写方式二.cpp

	/**
	* 类模版分文件编写
	* 掌握类模版成员函数分文件编写产生的问题以及解决方式
	*
	* 问题：类模版中成员函数创建时机是在调用阶段，导致分文件编写时链接不到的问题
	* 解决：
	* 解决方式一：直接包含.cpp 源文件
	* 解决方式二：将声明和实现写到同一个文件中，并更改后缀名为.hpp,hpp 是约定的名称，并不是强制
	*/
	#include <iostream>

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

	using namespace std;

	void test01(){
	Person<string,int> p1("Jerry",18);
	p1.showPerson();
	}

	int main() {
	test01();
	}

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

# 类模板与友元

学习目标：掌握类模版配合友元函数的类内和类外实现。全局函数类内实现：直接在类内声明友元即可。全局函数类外实现：需要提前让编译器知道全局函数的存在.

类模板与友元.cpp

	/**
	* 类模版与友元
	*/
	#include <iostream>

	using namespace std;

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

	// 2. 类外实现
	template<class T1, class T2>
	void printPerson2(Person<T1, T2> p) {
	cout << "类外实现 - " << "姓名：" << p.name << " 年龄：" << p.age << endl;
	}

	// 通过全局函数打印 Person 信息
	template<class T1, class T2>
	class Person {
	// 全局函数类内实现
	friend void printPerson(Person<T1, T2> p) {
	cout << "类内实现 - " << "姓名：" << p.name << " 年龄：" << p.age << endl;
	}

	// 全局函数类外实现
	// 添加空模版的参数列表
	// 如果全局函数是类外实现，需要让编译器提前知道这个函数的存在
	friend void printPerson2<>(Person<T1, T2> p);


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

	private:
	T1 name;
	T2 age;
	};

	// 1. 全局函数在类内实现
	void test01() {
	Person<string, int> p("Tom", 20);
	printPerson(p);
	}


	void test02() {
	Person<string, int> p("Jerry", 22);
	printPerson2(p);
	}

	int main() {
	test01();
	test02();
	}

总结：建议全局函数做类内实现，用法简单，而且编译器可以直接识别.

# 类模版案例

实现一个通过的数组类，要求如下：
可以对内置数据类型以及自定义数据类型的数据进行存储
将数组中的数据存储到堆区
构造函数中可以传入数组的容量
提供对应的拷贝构造函数以及 operator= 防止浅拷贝问题
提供尾插法和尾删法对数组中的数据进行增加和删除
可以通过下标的方式访问数组中的元素
可以获取数组中当前的元素个数和数组的容量

类模版案例.cpp

	/**
	* 类模版案例
	*/
	#include <iostream>

	using namespace std;

	#include "MyArray.hpp"

	void printIntArray(MyArray<int> &array) {
	for (int i = 0; i < array.getSize(); i++) {
	cout << array[i] << endl;
	}
	}

	void test01() {
	MyArray<int> array1(5);
	// MyArray<int> array2(array1);
	// MyArray<int> array3(100);
	// array3 = array1;

	for (int i = 0; i < 5; i++) {
	// 利用尾插法向数组中插入数据
	array1.Push_Back(i);
	}
	cout << "arr1的打印输出为：" << endl;
	printIntArray(array1);

	cout << "arr1的容量为：" << array1.getCapacity() << endl;
	cout << "arr1的大小为：" << array1.getSize() << endl;

	MyArray<int> array2(array1);
	cout << "arr2的打印输出为：" << endl;
	printIntArray(array2);


	// 尾删
	array2.Pop_Back();
	cout << "arr2尾删后：" << endl;
	cout << "arr2的容量为：" << array2.getCapacity() << endl;
	cout << "arr2的大小为：" << array2.getSize() << endl;

	}

	// 测试自定义数据类型
	class Person {
	public:
	Person() {}

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

	string name;
	int age;
	};

	void printPersonArray(MyArray<Person> &array) {
	for (int i = 0; i < array.getSize(); i++) {
	cout << "姓名：" << array[i].name << " 年龄：" << array[i].age << endl;
	}
	}

	void test02() {
	MyArray<Person> array(10);

	Person p1("孙悟空", 18);
	Person p2("韩信", 19);
	Person p3("张良", 20);
	Person p4("诸葛亮", 21);
	Person p5("诸葛瑾", 22);
	Person p6("周瑜", 23);
	Person p7("猪八戒", 24);
	Person p8("沙悟净", 25);
	Person p9("唐三藏", 26);
	Person p10("李信", 27);
	// 将数据插入到数组中
	array.Push_Back(p1);
	array.Push_Back(p2);
	array.Push_Back(p3);
	array.Push_Back(p4);
	array.Push_Back(p5);
	array.Push_Back(p6);
	array.Push_Back(p7);
	array.Push_Back(p8);
	array.Push_Back(p9);
	array.Push_Back(p10);

	// 打印数组
	printPersonArray(array);

	// 打印容量
	cout << "array的容量为：" << array.getCapacity() << endl;
	// 输出大小
	cout << "array的大小为：" << array.getSize() << endl;
	}


	int main() {
	test01();
	test02();
	}

能够利用所学知识点实现通用数组.

# STL 的基本概念

C++ 的面向对象和泛型编程思想的目的就是复用性的提升.
大多数情况下，数据结构和算法都未能有一套标准导致被迫从事大量的重复工作.
为了建立数据结构和算法的一套标准，后来就诞生了 STL 概念.
STL(StandardTemplateLibrary,标准模板库) .
STL从广义上分为：容器(container)算法(algorithm)迭代器(iterator) .
容器和算法之间通过迭代器进行无缝链接.
STL 几乎所有的代码都采用了模版类或模版函数.

STL 分为六大组件：它们是容器、算法、迭代器、仿函数、适配器、空间配置器.

容器：各种数据结构，如 vector 、 list 、 deque 、 set 、 map 等用来存放数据.
算法：各种常用的算法，如 sort 、 find 、 copy 、 for_each 等.
迭代器：扮演了容器与算法之间的胶合剂.
适配器：一种用来修饰容器或者仿函数或迭代器接口的东西.
空间配置器：负责空间的配置与管理.
迭代器种类：

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

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

# 容器算法迭代器初始

了解 STL 中容器、算法、迭代器概念之后，我们利用代码感受 STL 的魅力. STL 中最常见的容器为 Vector , 可以理解为数组.

# vector 存放内置数据类型

容器： vector
算法： for_each
迭代器： vector<int>::iterator

迭代器第一种遍历方式.cpp

	/**
	* vector 存放内置数据类型
	*/
	#include <iostream>
	#include <vector>
	using namespace std;

	void test01() {
	// 创建迭代器
	vector<int> v;
	// 向容器中插入数据
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	// 通过迭代器访问容器中的数据
	vector<int>::iterator itBegin = v.begin(); // 起始迭代器，指向容器中的第一个元素
	vector<int>::iterator itEnd = v.end(); // 结束迭代器，指向容器中最后一个元素的下一个位置

	// 第一种遍历方式
	while (itBegin!=itEnd){
	cout << *itBegin << endl;
	itBegin++;
	}

	}

	int main() {
	test01();
	}

迭代器第二种遍历方式.cpp

	/**
	* vector 存放内置数据类型
	*/
	#include <iostream>
	#include <vector>
	using namespace std;

	void test01() {
	// 创建迭代器
	vector<int> v;
	// 向容器中插入数据
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);

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

	}

	int main() {
	test01();
	}

迭代器第三种遍历方式.cpp

	/**
	* vector 存放内置数据类型
	*/
	#include <iostream>
	#include <vector>
	// 标准算法头文件
	#include <algorithm>
	using namespace std;

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

	void test01() {
	// 创建迭代器
	vector<int> v;
	// 向容器中插入数据
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);

	// 第三种遍历方式，利用 STL 提供遍历算法
	for_each(v.begin(),v.end(),myPrint);

	}

	int main() {
	test01();
	}

# vector 存放自定义数据类型

向 vector 中存放自定义数据类型，并打印输出.

vector存放自定义数据类型.cpp

	/**
	* vector 存放自定义数据类型
	*/
	#include <iostream>
	#include <vector>
	#include <algorithm>

	using namespace std;

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

	string name;
	int age;
	};

	void myPrint(Person val) {
	cout << val.name << " " << val.age << endl;
	};

	void test01() {
	vector<Person> v;
	Person p1("孙悟空", 18);
	Person p2("Tom", 20);
	Person p3("Jee", 22);
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	// 遍历
	for_each(v.begin(), v.end(), myPrint);

	// for (const auto &item: v){
	// cout << item.name << item.age << endl;
	// }

	}

	// 存放自定义数据类型的指针
	void test02() {
	vector<Person *> v;
	Person p1("孙悟空", 18);
	Person p2("Tom", 20);
	Person p3("Jee", 22);
	v.push_back(&p1);
	v.push_back(&p2);
	v.push_back(&p3);

	// 遍历容器
	for (vector<Person *>::iterator it = v.begin(); it != v.end(); it++) {
	cout << (it)->name << (it)->age << endl;
	// 二级指针
	cout << (it).name << (it).age << endl;
	}
	}

	int main() {
	test01();
	test02();
	}

# vector 容器嵌套容器

容器中嵌套容器，将所有数据进行遍历输出.

vector容器嵌套容器.cpp

	/**
	* vector 容器嵌套容器
	*/
	#include <iostream>
	#include <vector>

	using namespace std;

	// 容器嵌套容器
	void test01() {
	vector<vector<int>> vector1;

	// 创建小容器
	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);
	}
	// 将小容器插入到大容器中
	vector1.push_back(v1);
	vector1.push_back(v2);
	vector1.push_back(v3);
	vector1.push_back(v4);

	// 通过大容器把所有数据遍历一遍
	int i = 1;
	for (vector<vector<int>>::iterator it = vector1.begin(); it != vector1.end(); it++) {
	cout << "v" << i << "开始进行遍历：" << endl;
	for (vector<int>::iterator iit = it->begin(); iit != it->end(); iit++) {
	cout << *iit << " ";
	}
	cout << endl;
	i++;
	}

	}

	int main() {
	test01();
	/**
	* 执行结果：
	* v1 开始进行遍历：
	* 1 2 3 4
	* v2 开始进行遍历：
	* 2 3 4 5
	* v3 开始进行遍历：
	* 3 4 5 6
	* v4 开始进行遍历：
	* 4 5 6 7
	*/
	}

# string 容器

# string 容器基本概念

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

string 和 char * 的区别：
- char * 它是一个指针.
- string 它是一个类，类内部封装了 char * 用来管理这个字符串，是一个 char* 型的容器.
特点：
- string 类内部封装了很多成员方法.
- 例如：查找 find , 拷贝 copy , 删除 delete , 替换 replace , 插入 insert .
- string 管理 char* 所分配的内存，不用担心复制越界和取值越界等，由类内部进行负责.

# string 容器构造函数

构造函数原型：
string() ：创建一个空的字符串例如： string str .
string(const char* s) ：使用字符串 s 初始化.
string(const string& str) ：使用一个 string 对象初始化另一个 string .
string(int n,char c) ：使用 n 个字符 c 初始化.

string容器构造函数.cpp

	/**
	* string 容器构造函数
	*/
	#include <iostream>
	#include <string>

	using namespace std;

	void test01() {
	// 默认构造
	string s1;
	// 初始化字符串
	const char *str = "hello world";
	string s2(str);
	cout << "S2 = " << s2 << endl;
	// 用一个 string 对象初始化另一个 string 对象
	string s3(s2);
	cout << "S3 = " << s3 << endl;
	// 使 n 个字符进行初始化
	string s4(5, 'A');
	cout << "S4 = " << s4 << endl;
	}

	int main() {
	test01();
	}

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

# 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容器赋值操作.cpp

	/**
	* string 容器赋值操作
	*/
	#include <iostream>

	using namespace std;

	void test01() {
	//char 类型字符串赋值给当前的字符串
	string str1;
	str1 = "hello";
	cout << "str1 = " << str1 << endl;

	// 把字符串 s 赋值给当前的字符串
	string str2;
	str2 = str1;
	cout << "str2 = " << str2 << endl;

	// 字符赋值给当前的字符串
	string str3;
	str3 = 'A';
	cout << "str3 = " << str3 << endl;

	// 把字符串 s 赋给当前的字符串
	string str4;
	str4.assign("world");
	cout << "str4 = " << str4 << endl;

	// 把字符串 s 的前 n 个字符赋给当前的字符串
	string str5;
	str5.assign("hello C++", 5);
	cout << "str5 = " << str5 << endl;

	// 把字符串 s 赋给当前字符串
	string str6;
	str6.assign(str5);
	cout << "str6 = " << str6 << endl;

	// 用 n 个字符 c 赋给当前字符串
	string str7;
	str7.assign(10, 'W');
	cout << "str7 = " << str7 << endl;
	}

	int main() {
	test01();
	}

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

# 字符串拼接

实现在字符串末尾拼接字符串.

函数原型：
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容器字符串拼接.cpp

	/**
	* 字符串拼接
	*/
	#include <iostream>

	using namespace std;

	void test01() {
	//string& operator+=(const char* str) ：重载 +=` 操作符.
	string str1 = "我喜欢";
	str1 += "羽毛球";
	cout << "str1 = " << str1 << endl;

	//string& operator+=(const char* c)：重载 `+= 操作符.
	str1 += ":";
	cout << "str1 = " << str1 << endl;

	//string& operator+=(const string& str)：重载 += 操作符.
	string str2 = "LOL DNF ";
	str1 += str2;
	cout << "str1 = " << str1 << endl;

	//string& append (const char *s)：把字符串 s 连接到当前字符串结尾.
	string str3 = "I";
	str3.append(" love ");
	cout << "str3 = " << str3 << endl;

	//string& append (const char *s, int n)：把字符串 s 的前 n 个字符连接当前字符串结尾.
	str3.append("game abce", 5);// I love game
	cout << "str3 = " << str3 << endl;

	//string& append (const string &s)：同 operator+=(const string&& str).
	str3.append(str2);
	// I love game LOL DNF
	cout << "str3 = " << str3 << endl;

	//string& append (const string &s,int pos,int n)：字符串 s 中从 pos 开始的 n 个字符连接到字符串结尾.
	str3.append(str2,0,3);
	cout << "str3 = " << str3 << endl;

	}

	int main() {
	test01();
	}

# 字符串查找和替换

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

函数原型：
int find(const string& str, int pos = 0) 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

字符串查找和替换.cpp

	/**
	* 字符串查找和替换
	*/
	#include <iostream>

	using namespace std;

	void test01(){
	string text = "hello world, hello C++";

	// find(const string& str, int pos = 0)
	size_t pos1 = text.find("hello"); // 从 0 开始查找 "hello" 第一次出现的位置
	cout << "find(\"hello\"): " << pos1 << endl;

	// find(const char* s, int pos = 0)
	size_t pos2 = text.find("world"); // 查找 "world" 第一次出现的位置
	cout << "find(\"world\"): " << pos2 << endl;

	// find(const char* s, int pos, int n)
	size_t pos3 = text.find("world++", 0, 5); // 只查找前 5 个字符 "world"
	cout << "find(\"world++\", 0, 5): " << pos3 << endl;

	// find(const char c, int pos = 0)
	size_t pos4 = text.find('C'); // 查找字符 'C' 第一次出现的位置
	cout << "find('C'): " << pos4 << endl;

	// rfind(const string& str, int pos = npos)
	size_t pos5 = text.rfind("hello"); // 查找 "hello" 最后一次出现的位置
	cout << "rfind(\"hello\"): " << pos5 << endl;

	// rfind(const char* s, int pos = npos)
	size_t pos6 = text.rfind("C++"); // 查找 "C++" 最后一次出现的位置
	cout << "rfind(\"C++\"): " << pos6 << endl;

	// rfind(const char* s, int pos, int n)
	size_t pos7 = text.rfind("C++xx", string::npos, 3); // 查找前 3 个字符 "C++"
	cout << "rfind(\"C++xx\", npos, 3): " << pos7 << endl;

	// rfind(const char c, int pos = npos)
	size_t pos8 = text.rfind('l'); // 查找字符 'l' 最后一次出现的位置
	cout << "rfind('l'): " << pos8 << endl;

	// replace(int pos, int n, const string& str)
	string replaced1 = text;
	replaced1.replace(0, 5, "Hi"); // 替换从位置 0 开始的 5 个字符为 "Hi"
	cout << "replace(0, 5, \"Hi\"): " << replaced1 << endl;

	// replace(int pos, int n, const char* s)
	string replaced2 = text;
	replaced2.replace(13, 5, "Python"); // 替换 "hello" 为 "Python"
	cout << "replace(13, 5, \"Python\"): " << replaced2 << endl;
	}

	int main(){
	test01();
	}

总结：1. find 查找是从左往右， rfind 是从右往左. 2. find 找到字符串后返回查找的第一个字符位置，找不到则返回 -1 . 3. replace 在进行替换的时候，要指定从哪个位置起，多少个字符，要替换成什么样的字符串.

# 字符串比较

字符串之间的比较，字符串比较是按字符串的 ASCLL 码进行对比 = 返回 0 . > 返回 1 < 返回 - .

函数原型：
int compare(const string &s) const ：与字符串 s 进行比较.
int compare(const char *s) const ：与字符串 s 进行比较.

字符串比较.cpp

	/**
	* 字符串比较
	*/
	#include <iostream>

	using namespace std;

	void test01() {
	string str1 = "hello";
	string str2 = "xello";
	if (str1.compare(str2) == 0) {
	cout << "str1 == str2" << endl;
	} else if (str1.compare(str2) > 0) {
	cout << "str1 > str2" << endl;
	} else{
	cout << "str1 < str2" << endl;
	}
	}

	int main() {
	test01();
	}

总结：字符串对比主要是用于比较两个字符串是否相等，判断谁大谁小的意义并不是很大.

# 字符存取

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

字符存取.cpp

	/**
	* 字符存取
	*/
	#include <iostream>

	using namespace std;

	void test01() {
	string str = "hello";
	// 1. 通过 [] 访问单个字符
	for (int i = 0; i < str.size(); ++i) {
	cout << str[i] << " ";
	}
	cout << endl;
	// 2. 通过 at 方式访问单个字符
	for (int i = 0; i < str.size(); ++i) {
	cout << str.at(i) << " ";
	}
	cout << endl;

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

	int main() {
	test01();
	}

总结： string 字符串中单个字符存取有两种方式，利用 [] 或 at 来进行.

# 字符串插入和删除

对 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 个字符

字符串插入和删除.cpp

	/**
	* 字符串插入和删除
	*/
	#include <iostream>

	using namespace std;

	void test01(){
	string str = "hello";
	// 插入
	str.insert(1,"111");
	cout << str << endl;

	// 删除
	str.erase(1,3);
	cout << str << endl;
	}

	int main(){
	test01();
	}

插入和删除的起始下标都是从 0 开始.

# 字符串子串获取

从字符串中获取想要的子串.

函数原型：
string substr(int pos = 0, int n = npos) const ：返回有 pos 开始的 n 个字符组成的字符串.

字符串子串获取.cpp

	/**
	* 字符串子串获取
	*/
	#include <iostream>

	using namespace std;

	void test01() {
	string str = "abcdefg";
	string subStr = str.substr(1, 3);
	cout << subStr << endl;
	}

	// 实用操作
	void test02() {
	string email = "zhangsan@sina.com";
	int pos = email.find("@");
	string userName = email.substr(0, pos);
	cout << userName << endl;
	}

	int main() {
	test02();
	}

# vector 容器

# vector 容器基本概念

vector 数据结构和数组非常相似，也被称为单端数组. vector 与普通数组的区别是：不同之处在于数组是静态空间，而 vector 则可以动态扩展.

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

vector 容器的迭代器是支持随机访问的迭代器.

# vector 构造函数

创建 vector 容器

函数原型：
vector<T> v ：采用模版实现类实现，默认构造函数.
vector(v.begin(), v.end()) ：将 v[begin(), end()] 区间中的元素拷贝给本身.
vector(n,elem) ：构造函数将 n 个 elem 拷贝给本身.
vector(const vector &vec) ：拷贝构造函数.

vector构造函数.cpp

	/**
	* vector 构造函数
	*/
	#include <iostream>
	#include <vector>

	using namespace std;
	// 打印函数
	void printVector(vector<int> val) {
	for (vector<int>::iterator it = val.begin(); it != val.end(); it++) {
	cout << *it << " ";
	}
	cout << endl;
	}

	//vector 容器构造
	void test01() {
	vector<int> v1; // 默认构造无参构造
	for (int i = 0; i < 10; ++i) {
	v1.push_back(i);
	}
	printVector(v1);

	// 通过区间方式进行构造
	vector<int> v2(v1.begin(), v1.end());
	printVector(v2);

	//n 个 elem 方式进行构造
	vector<int> v3(10,100);
	printVector(v3);

	// 拷贝构造
	vector<int> v4(v3);
	printVector(v4);
	}

	int main() {
	test01();
	}

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

# vector 赋值操作

给 vector 容器进行赋值.

函数原型：
vector& operator=(const vector &vec) ：重载等号运算符.
assign(beg,end) ：将 [beg,end] 区间中的数据拷贝赋值给本身.
assign(n,elem) ：将 n 个 elem 拷贝赋值给本身.

vector赋值操作.cpp

	/**
	* vector 赋值操作
	*/
	#include <iostream>
	#include <vector>

	using namespace std;

	void printVector(vector<int> &v) {
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
	cout << *it << " ";
	}
	cout << endl;
	}

	void test01() {
	vector<int> vector1;
	for (int i = 0; i < 10; i++) {
	vector1.push_back(i);
	}
	printVector(vector1);

	// 赋值 operator=
	vector<int> vector2;
	vector2 = vector1;
	printVector(vector2);

	// assign
	vector<int> vector3;
	vector3.assign(vector1.begin(),vector1.end());
	printVector(vector3);

	//n 个 elem 方式赋值
	vector<int> vector4;
	vector4.assign(10,100);
	printVector(vector4);
	}

	int main() {
	test01();
	}

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

# vector 容量和大小

对 vector 容器的容量和大小操作.

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

vector容量和大小.cpp

	/**
	* vector 容量和大小
	*/
	#include <iostream>
	#include <vector>

	using namespace std;

	// 打印函数
	void printVector(vector<int> val) {
	for (vector<int>::iterator it = val.begin(); it != val.end(); it++) {
	cout << *it << " ";
	}
	cout << endl;
	}

	void test01() {
	vector<int> v1;
	for (int i = 0; i < 10; i++) {
	v1.push_back(i);
	}
	printVector(v1);

	// 判断是否为空
	if (v1.empty()) {
	cout << "v1为空" << endl;
	} else {
	cout << "v1不为空" << endl;
	cout << "v1的容量为：" << v1.capacity() << endl;
	cout << "v1的大小为：" << v1.size() << endl;
	}

	// 重新指定大小
	v1.resize(15, 100);// 利用重载版本，可以指定默认填充值，参数 2
	printVector(v1); // 如果重新指定的长度比原来长，默认用 0 进行填充

	v1.resize(5);// 如果重新指定的比原来的短，超出的部分会删除掉
	printVector(v1);

	}

	int main() {
	test01();
	}

总结

判断是否为空： empty()
返回元素个数： size()
返回容器容量： capacity()
重新指定大小： resize()

# vector 插入和删除

对 vector 容器进行插入，删除操作.

函数原型：
pubu_back(ele) ：尾部插入元素 ele
pop_back() ：删除最后一个元素
insert(const_iterator pos,ele) ：迭代器指向位置 pos 插入元素 ele
insert(const_iterator pos,int count,ele) ：迭代器指向位置 pos 插入 count 个元素 ele
erase(const_iterator pos) ：删除迭代器指向的元素
erase(const_iterator start,const_iterator end) ：删除迭代器从 start 到 end 之间的元素
clear() ：删除容器中所有的元素

vector插入和删除.cpp

	/**
	* vector 插入和删除
	*/
	#include <iostream>
	#include <vector>

	using namespace std;

	// 打印函数
	void printVector(vector<int> val) {
	for (vector<int>::iterator it = val.begin(); it != val.end(); it++) {
	cout << *it << " ";
	}
	cout << endl;
	}


	void test01() {
	//pubu_back (ele)：尾部插入元素 ele
	vector<int> v1;
	// 尾插
	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);
	v1.push_back(40);
	v1.push_back(50);
	printVector(v1);

	//pop_back ()：删除最后一个元素
	// 尾删
	v1.pop_back();
	printVector(v1);

	//insert (const_iterator pos,ele)：迭代器指向位置 pos 插入元素 ele
	// 插入
	v1.insert(v1.begin(), 60);
	printVector(v1);

	//insert (const_iterator pos,int count,ele)：迭代器指向位置 pos 插入 count 个元素 ele
	// 插入 n 个元素
	v1.insert(v1.begin(), 2, 100);
	printVector(v1);

	//erase (const_iterator pos)：删除迭代器指向的元素
	// 删除参数也是迭代器
	v1.erase(v1.end());
	v1.erase(v1.begin());
	printVector(v1);

	//erase (const_iterator start,const_iterator end)：删除迭代器从 start 到 end 之间的元素
	// 删除头和尾
	v1.erase(v1.begin(), v1.end());
	// 没有则多出一个换行属于正常状态
	printVector(v1);

	//clear ()：删除容器中所有的元素
	v1.clear();
	printVector(v1);
	}

	int main() {
	test01();
	}

总结

尾插： push_back()
尾插： pop_back()
插入： insert() ：参数是迭代器
删除： erase() ：参数是迭代器
清空： clear()

# vector 数据存取

对 vector 中的数据的存取操作.

函数原型：
at(int idx) ：但会索引 idx 所指的数据.
operator[] ：返回索引 idx 所指的数据.
front() ：返回容器中第一个数据元素.
back() ：返回容器中最后一个数据元素.

vector数据存取.cpp

	/**
	* vector 数据存取
	*/
	#include <iostream>

	#include <vector>

	using namespace std;

	void test01() {
	vector<int> v1;
	for (int i = 0; i < 10; ++i) {
	v1.push_back(i);
	}

	// 利用 [] 方式访问数组中的元素
	for (int i = 0; i < v1.size(); i++) {
	cout << v1[i] << " ";
	}
	cout << endl;

	// 利用 at 方式访问元素
	for (int i = 0; i < v1.size(); ++i) {
	cout << v1.at(i) << " ";
	}
	cout << endl;

	// 获取第一个元素
	cout << "第一个元素为：" << v1.front() << endl;
	// 获取最后一个元素
	cout << "最后一个元素为：" << v1.back() << endl;
	}

	int main() {
	test01();
	}

总结

除了用迭代器获取 vector 容器中的元素，还可以使用 [] 或 at() 函数也可以.
front() 返回容器第一个元素.
back() 返回容器最后一个元素.

# vector 互换容器

实现两个容器内的元素互换.

函数原型：
swap(vec) ：将 vec 与本身的元素进行互换.

vector互换容器.cpp

	/**
	* 容器的互换
	*/
	#include <iostream>

	#include <vector>

	using namespace std;

	// 打印函数
	void printVector(vector<int> val) {
	for (vector<int>::iterator it = val.begin(); it != val.end(); it++) {
	cout << *it << " ";
	}
	cout << endl;
	}

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

	cout << "交换前：" << endl;

	printVector(v1);

	vector<int> v2;
	for (int i = 10; i > 0; i--) {
	v2.push_back(i);
	}

	printVector(v2);

	cout << "交换后：" << endl;
	v1.swap(v2);
	printVector(v1);
	printVector(v2);
	}

	// 实用案例 - swap 可以用于收缩空间
	void test02() {
	cout << endl;
	vector<int> v;
	for (int i = 0; i < 100000; ++i) {
	v.push_back(i);
	}

	cout << "v的容量为：" << v.capacity() << endl;
	cout << "v的大小为：" << v.size() << endl;

	cout << endl;

	// 重新指定大小
	v.resize(3);
	cout << "v的容量为：" << v.capacity() << endl;
	cout << "v的大小为：" << v.size() << endl;

	cout << endl;

	// 使用 swap 收缩内存
	vector<int>(v).swap(v);
	cout << "v的容量为：" << v.capacity() << endl;
	cout << "v的大小为：" << v.size() << endl;
	}

	int main() {
	test01();
	test02();
	}

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

# vector 预留空间

减少 vector 在动态扩展容量时的扩展次数.

函数原型：
reserve(int len) ：容器预留 len 个元素长度，预留位置不初始化，元素不可访问.

vector预留空间.cpp

	/**
	* vector 预留空间
	*/
	#include <iostream>

	#include <vector>

	using namespace std;

	//vector 容器 - 预留空间
	void test01() {
	vector<int> v;

	// 利用 reserve 预留空间
	v.reserve(100000);

	// 统计开辟的次数
	int num = 0;
	int *p = NULL;
	for (int i = 0; i < 100000; ++i) {
	v.push_back(i);
	// 如果 p 不等于 vector 容器的首地址，则强制将 p 改为 vector 容器的首地址
	if (p != &v[0]) {
	p = &v[0];
	num++;
	}
	}
	cout << "num = " << num << endl;

	}

	int main() {
	test01();
	}

总结：如果数据量较大，可以一开始利用 reserve 预留空间.

# deque 容器

# deque 基本概念

双端数组，可以对头端进行插入删除操作.

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

# deque 构造函数

deque 容器构造.

deque<T> deqT ：默认构造形式.
deque(beg, end) ：构造函数将 [beg,end] 区间中的元素拷贝给本身.
deque(n, elem) ：构造函数将 n 个 elem 拷贝给本身.
deque(const deque &deq) ：拷贝构造函数.

deque构造函数.cpp

	/**
	* deque 构造函数
	*/
	#include <iostream>

	#include <deque>

	using namespace std;

	void printDeque(const deque<int> &d) {
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
	cout << *it << " ";
	}
	cout << endl;
	}

	void test01() {
	deque<int> d1;
	for (int i = 0; i < 10; ++i) {
	d1.push_back(i);
	}
	printDeque(d1);

	deque<int> d2(d1.begin(), d1.end());
	printDeque(d2);

	deque<int> d3(10, 100);
	printDeque(d3);

	deque<int> d4(d3);
	printDeque(d4);
	}

	int main() {
	test01();
	}

总结： deque 容器和 vector 容器的构造方式几乎一致，灵活使用即可.

# deque 赋值操作

给 deque 容器进行赋值.

函数原型：
deque& operator=(const deque &deq) ：重载等号操作符.
assign(beg, end) ：将 [beg,end] 区间中的数据拷贝赋值给本身.
assign(n, elem) ：将 n 个 elem 拷贝赋值给本身.

deque赋值操作.cpp

	/**
	* deque 赋值操作
	*/
	#include <iostream>
	#include <deque>

	using namespace std;

	void printDeque(const deque<int> &d) {
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
	cout << *it << " ";
	}
	cout << endl;
	}

	void test01(){
	deque<int> d1;
	for (int i = 0; i < 10; ++i) {
	d1.push_back(i);
	}
	printDeque(d1);

	//operator = 赋值
	deque<int> d2;
	d2 = d1;
	printDeque(d2);

	//assign 赋值
	deque<int> d3;
	d3.assign(d1.begin(),d1.end());
	printDeque(d3);

	deque<int> d4;
	d4.assign(10,100);
	printDeque(d4);
	}

	int main(){
	test01();
	}

总结： deque 赋值操作也与 vector 相同.

# deque 大小操作

对 deque 容器的大小进行操作.

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

deque大小操作.cpp

	/**
	* deque 大小操作
	*/
	#include <iostream>
	#include <deque>

	using namespace std;

	void printDeque(const deque<int> &d) {
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
	cout << *it << " ";
	}
	cout << endl;
	}

	void test01() {
	deque<int> d1;
	for (int i = 0; i < 10; ++i) {
	d1.push_back(i);
	}
	printDeque(d1);

	// 判断是否为空
	if (d1.empty()) {
	cout << "d1为空" << endl;
	} else {
	cout << "d1不为空" << endl;
	cout << "d1的大小为：" << d1.size() << endl;
	//deque 容器没有容量概念

	// 重新指定大小
	// d1.resize(15);
	d1.resize(15,1);
	printDeque(d1);

	d1.resize(5);
	printDeque(d1);
	}
	}

	int main() {
	test01();
	}

总结

deque 没有容量的概念
判断是否为空： empty()
返回元素个数： size()
重新指定个数： resize()

# deque 插入和删除

向 deque 容器中插入和删除数据.

函数原型：
- 两端插入操作：
  - push_back(elem) ：在容器尾部添加一个数据
  - push_front(elem) ：在容器头部插入一个数据
  - pop_back() ：删除容器最后一个数据
  - 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 位置的数据，返回下一个数据的位置

deque插入和删除.cpp

	/**
	* deque 插入和删除
	*/
	#include <iostream>
	#include <deque>

	using namespace std;

	void printDeque(const deque<int> &d) {
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
	cout << *it << " ";
	}
	cout << endl;
	}

	// 两端插入操作
	void test01() {
	deque<int> d1;
	// 尾插
	d1.push_back(10);
	d1.push_back(20);
	// 头插
	d1.push_front(30);
	d1.push_front(40);
	printDeque(d1);

	// 尾删
	d1.pop_back();

	// 头删
	d1.pop_front();

	printDeque(d1);
	}

	// 指定位置操作 - 插入
	void test02() {
	deque<int> d1;
	d1.push_back(10);
	d1.push_back(20);
	d1.push_front(30);
	d1.push_front(40);
	printDeque(d1);

	//insert 插入
	d1.insert(d1.begin(), 1000);
	printDeque(d1);

	d1.insert(d1.begin(), 2, 2000);
	printDeque(d1);

	// 按照区间进行插入
	deque<int> d2;
	d2.push_back(1);
	d2.push_back(2);
	d2.push_back(3);

	d1.insert(d1.begin(), d2.begin(), d2.end());
	printDeque(d1);
	}

	// 删除
	void test03() {
	deque<int> d1;
	d1.push_back(10);
	d1.push_back(20);
	d1.push_front(30);
	d1.push_front(40);
	// 删除
	d1.erase(d1.begin());
	// 30 10 20
	printDeque(d1);
	// 指定删除
	deque<int>::iterator it = d1.begin();
	it++;
	d1.erase(it);
	// 30 20
	printDeque(d1);

	// 按照区间方式删除
	d1.erase(d1.begin(), d1.end());
	// 清空
	d1.clear();
	printDeque(d1);
	}

	int main() {
	test03();
	}

总结

插入和删除提供的位置是迭代器.
尾插： push_back() .
尾删： pop_back() .
头插： pushi_front() .
头删： pop_front() .

# deque 数据存取

对 deque 中的数据的存取.

函数原型：
at(int idx) ：返回索引 idx 所指的数据
operator[] ：返回索引 idx 所指的数据
front() ：返回容器中第一个数据元素
back() ：返回容器中最后一个数据元素

deque数据存取.cpp

	/**
	* deque 数据存取
	*/
	#include <iostream>
	#include <deque>

	using namespace std;

	void test01() {
	deque<int> d;
	d.push_back(10);
	d.push_back(20);
	d.push_back(30);
	d.push_back(40);
	d.push_front(100);
	d.push_front(200);
	d.push_front(300);
	// 通过 [] 方式访问元素
	for (int i = 0; i < d.size(); i++) {
	cout << d[i] << " ";
	}
	cout << endl;
	// 300 200 100 10 20 30 40

	// 通过 at 方式访问元素
	for (int i = 0; i < d.size(); ++i) {
	cout << d.at(i) << " ";
	}
	cout << endl;

	cout << "第一个元素为：" << d.front() << endl;
	cout << "最后一个元素为：" << d.back() << endl;

	}

	int main() {
	test01();
	}

总结

除了用迭代器获取 deque 容器中的元素，还可以使用 [] 或 at 来进行获取
front() ：返回容器的第一个元素
back() ：返回容器的最后一个元素

# deque 排序操作

利用算法实现对 deque 容器进行排序.

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

deque排序操作.cpp

	/**
	* deque 排序操作
	*/
	#include <iostream>
	#include <deque>
	#include <algorithm>

	using namespace std;

	void printDeque(const deque<int> &d) {
	for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
	cout << *it << " ";
	}
	cout << endl;
	}

	void test01() {
	deque<int> d;
	d.push_back(10);
	d.push_back(21);
	d.push_back(50);
	d.push_back(5);
	d.push_back(59);
	d.push_back(33);
	d.push_back(18);
	printDeque(d);

	// 排序默认排序规则从小到大升序
	// 对于支持随机访问的迭代器的容器，都可以利用 sort 算法直接对其进行排序
	//vector 容器也可以利用，sort 进行排序
	sort(d.begin(),d.end());
	printDeque(d);
	}

	int main() {
	test01();
	}

总结： sort 算法非常实用，使用时包含头文件 algorithm 即可，例如： #include <algorithm> .

# stack 容器

# stack 基本概念

概念： stack 是一种先进先出 (FirstInLastOut,FILO) 的数据结构，它只有一个出口.

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

# stack 常用接口

栈容器常用的对外接口.

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

stack常用接口.cpp

	/**
	* stack 常用接口
	*/
	#include <iostream>
	#include <stack>

	using namespace std;

	void test01() {
	// 特点：符合先进后出数据结构
	stack<int> stack1;

	stack1.push(10);
	stack1.push(20);
	stack1.push(30);
	stack1.push(40);
	// 只有栈不为空，查看栈顶，并且执行出栈的操作
	while (!stack1.empty()) {
	// 查看栈顶元素
	cout << "栈顶元素为：" << stack1.top() << endl;

	// 出栈
	stack1.pop();
	}

	cout << "栈的大小：" << stack1.size() << endl;

	}

	int main() {
	test01();
	}

总结

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

# queue 容器

# queue 基本概念

概念： Queue 是一种先进先出 (FirstInFirstOut,FIFO) 的数据结构，它有两个出口.

# queue 常用接口

栈容器常用的对外接口.

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

queue容器常用接口.cpp

	/**
	* queue 常用接口
	*/
	#include <iostream>
	#include <queue>

	using namespace std;

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

	string name;
	int age;
	};

	void test01() {
	queue<Person> q;
	// 入队
	q.push(Person("张三", 18));
	q.push(Person("李四", 19));
	q.push(Person("Tom", 20));
	// 判断只要队列不为空，查看队头，查看队尾，出队
	while (!q.empty()) {
	// 查看队头
	cout << "队头元素 --- 姓名：" << q.front().name << " 年龄：" << q.front().age << endl;

	// 查看队尾
	cout << "队尾元素 --- 姓名：" << q.back().name << " 年龄：" << q.back().age << endl;

	// 出队
	q.pop();

	cout << endl;
	}
	}

	int main() {
	test01();
	}

总结

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

# list 容器

# list 基本概念

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

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

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

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

list 的优点:
- 采用动态存储分配，不会造成内存浪费和溢出
- 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
list 的缺点:
- 链表灵活，但是空间 (指针域）和时间（遍历）额外耗费较大
list 有一个重要的性质，插入操作和删除操作都不会造成原有 list 迭代器的失效，这在 vector 是不成立的.
总结： STL 中 list 和 vector 是两个最常被使用的容器，各有优缺点.

# list 构造函数

函数原型：
list<T> lst ： list 采用模版类实现，对象的默认构造形式
list(beg,end) ：构造函数将 [beg,end] 区间中的元素拷贝给本身
list(n,elem) ：构造函数将 n 个 elem 拷贝给本身
list(const list &lst) ：拷贝构造函数

list容器构造函数.cpp

	/**
	* list 构造函数
	*/
	#include <iostream>
	#include <list>

	using namespace std;

	void printList(const list<int> &l) {
	for (list<int>::const_iterator it = l.begin(); it != l.end(); it++) {
	cout << *it << " ";
	}
	cout << endl;
	}

	void test01() {
	// 创建容器
	list<int> l1;
	// 添加数据
	l1.push_back(10);
	l1.push_back(20);
	l1.push_back(30);
	l1.push_back(40);

	// 遍历容器
	printList(l1);

	// 区间方式构造
	list<int> l2(l1.begin(), l1.end());
	printList(l2);

	// 拷贝构造
	list<int> l3(l2);
	printList(l3);

	//n 个 elem
	list<int> l4(10,100);
	printList(l4);
	}

	int main() {
	test01();
	}

总结： list 构造方式同其他几个 STL 常用容器一样.

# list 赋值和交换

给 list 容器进行赋值，以及交换 list 容器.

函数原型：
assign(beg,end ：将 [beg,end] 区间中的数据拷贝赋值给本身
assign(n,elem) ：将 n 个 elem 拷贝赋值给本身
list& operator=(const list &lst) ：重载等号操作符
swap(lst) ：将 lst 与本身的元素互换

list赋值和交换.cpp

	/**
	* list 赋值和交换
	*/
	#include <iostream>
	#include <list>

	using namespace std;

	void printList(const list<int> &l) {
	for (list<int>::const_iterator it = l.begin(); it != l.end(); it++) {
	cout << *it << " ";
	}
	cout << endl;
	}

	// 赋值
	void test01() {
	list<int> l1;
	l1.push_back(10);
	l1.push_back(20);
	l1.push_back(30);
	l1.push_back(40);
	printList(l1);

	//operator= 赋值
	list<int> l2;
	l2 = l1;
	printList(l2);

	list<int> l3;
	l3.assign(l2.begin(), l2.end());
	printList(l3);

	list<int> l4;
	l4.assign(10, 100);
	printList(l4);
	}

	void test02() {
	list<int> l1;
	l1.push_back(10);
	l1.push_back(20);
	l1.push_back(30);
	l1.push_back(40);

	list<int> l2;
	l2.assign(10, 100);

	cout << "交换前：" << endl;
	printList(l1);
	printList(l2);

	l1.swap(l2);

	cout << "交换后：" << endl;
	printList(l1);
	printList(l2);
	}

	int main() {
	test01();
	test02();
	}

# list 大小操作

对 list 容器的大小进行操作

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

list大小操作.cpp

	/**
	* list 大小操作
	*/
	#include <iostream>
	#include <list>

	using namespace std;

	void printList(const list<int> &l) {
	for (list<int>::const_iterator it = l.begin(); it != l.end(); it++) {
	cout << *it << " ";
	}
	cout << endl;
	}

	void test01() {
	list<int> l1;
	l1.push_back(10);
	l1.push_back(20);
	l1.push_back(30);
	l1.push_back(40);

	printList(l1);

	// 判断容器是否为空
	if (l1.empty()) {
	cout << "L1为空" << endl;
	} else {
	cout << "L1不为空" << endl;
	cout << "L1的元素个数为：" << l1.size() << endl;
	}

	// 重新指定大小
	l1.resize(10, 100);
	printList(l1);

	l1.resize(2);
	printList(l1);

	}

	int main() {
	test01();
	}

总结

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

# 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 值匹配的元素

list插入和删除.cpp

	/**
	* list 插入和删除
	*/
	#include <iostream>
	#include <list>
	#include <algorithm> // for std::find
	using namespace std;

	void printList(const list<int>& lst, const string& msg) {
	cout << msg;
	for (int val : lst)
	cout << val << " ";
	cout << endl;
	}

	void test01(){
	list<int> lst;

	//push_back (elem)：尾部添加元素
	lst.push_back(10);
	lst.push_back(20);
	lst.push_back(30);
	printList(lst, "After push_back: ");

	//push_front (elem)：头部添加元素
	lst.push_front(5);
	printList(lst, "After push_front: ");

	//pop_back ()：删除最后一个元素
	lst.pop_back();
	printList(lst, "After pop_back: ");

	//pop_front ()：删除第一个元素
	lst.pop_front();
	printList(lst, "After pop_front: ");

	//insert (pos, elem)：在指定位置插入一个元素
	auto it = lst.begin();
	advance(it, 1); // 移动到第二个位置
	it = lst.insert(it, 99); // 插入 99
	printList(lst, "After insert(pos, 99): ");

	//insert (pos, n, elem)：在指定位置插入 n 个相同元素
	lst.insert(it, 2, 88); // 在 99 之前插入两个 88
	printList(lst, "After insert(pos, 2, 88): ");

	//insert (pos, beg, end)：插入一个区间
	list<int> other = {100, 200};
	lst.insert(lst.end(), other.begin(), other.end());
	printList(lst, "After insert range [100, 200] at end: ");

	//erase (pos)：删除某个位置元素
	it = lst.begin();
	advance(it, 2); // 移动到第三个元素
	it = lst.erase(it); // 删除它
	printList(lst, "After erase(pos): ");

	//erase (beg, end)：删除一个范围
	auto beg = lst.begin();
	auto end = lst.begin();
	advance(end, 2);
	lst.erase(beg, end); // 删除前两个元素
	printList(lst, "After erase(beg, end): ");

	//remove (elem)：删除所有匹配的元素
	lst.push_back(88);
	lst.push_back(88);
	lst.remove(88); // 删除所有 88
	printList(lst, "After remove(88): ");

	//clear ()：清空容器
	lst.clear();
	printList(lst, "After clear(): ");

	}

	int main(){
	test01();
	}

总结

尾插： push_back()
尾删： pop_back()
头删： push_front()
插入： insert()
删除： erase()
移除： remove()
清空： clear()

# list 数据存取

对 list 容器中数据进行存取.

函数原型：
front() ：返回第一个元素
back() ：返回最后一个元素

list数据存取.cpp

	/**
	* list 数据存取
	*/
	#include <iostream>
	#include <list>

	using namespace std;

	void printList(const list<int> &l) {
	for (list<int>::const_iterator it = l.begin(); it != l.end(); it++) {
	cout << *it << " ";
	}
	cout << endl;
	}

	// 数据存取
	void test01() {
	list<int> list1;
	list1.push_back(10);
	list1.push_back(20);
	list1.push_back(30);
	list1.push_back(40);

	//list1 [0] 不可以使用 [] 访问 list 容器中的元素
	//list1.at (0) 不可以使用 at () 函数访问 list 容器中的元素
	// 原因是 list 本质是链表，不是用连续线性空间存储数据的，迭代器也是不支持随机访问的

	cout << "第一个元素为：" << list1.front() << endl;
	cout << "最后一个元素为：" << list1.back() << endl;

	// 验证迭代器是否支持随机访问，迭代器是不支持随机访问的
	list<int>::iterator it = list1.begin();
	// 支持双向操作
	it++;
	it--;
	// it = it + 1; // 不支持随机访问

	}

	int main() {
	test01();
	}

总结

list 容器中不可以通过 [] 或者 at 方式访问数据.
返回第一个元素： front() .
返回最后一个元素： back() .

# list 反转和排序

将容器中的元素反转，以及将容器中的数据进行排序.

函数原型：
reverse() ：反转链表
sort() ：链表排序

list反转和排序.cpp

	/**
	* list 反转和排序
	*/
	#include <iostream>
	#include <algorithm>
	#include <list>

	using namespace std;

	void printList(const list<int> &l) {
	for (list<int>::const_iterator it = l.begin(); it != l.end(); it++) {
	cout << *it << " ";
	}
	cout << endl;
	}

	void test01() {
	list<int> list1;
	list1.push_back(20);
	list1.push_back(10);
	list1.push_back(50);
	list1.push_back(40);
	list1.push_back(30);

	cout << "反转前：";
	printList(list1);

	// 反转
	list1.reverse();
	cout << "反转后：";
	printList(list1);

	}

	bool myCompare(int v1, int v2) {
	// 降序就让第一个数 > 第二个数
	return v1 > v2;
	}

	void test02() {
	list<int> list1;
	list1.push_back(20);
	list1.push_back(10);
	list1.push_back(50);
	list1.push_back(40);
	list1.push_back(30);

	cout << "排序前：";
	printList(list1);

	// 排序，所有不支持随机访问迭代器的容器，不可以用标准算法
	// sort(list1.begin(), list1.end());

	// 不支持随机访问迭代器的容器
	list1.sort();// 默认排序规则从小到大升序

	cout << "排序后：";
	printList(list1);

	list1.sort(myCompare);

	cout << "降序后：";
	printList(list1);
	}

	int main() {
	test01();
	test02();
	}

总结

反转： reverse()
排序： sort(成员函数：myCompare)

# list 排序案例

案例描述：将 Person 自定义数据类型进行排序， Person 中属性有姓名、年龄、身高。排序规则：按照年龄进行升序，如果年龄相同按照身高进行降序.

list排序案例.cpp

	/**
	* list 排序案例
	*/
	#include <iostream>
	#include <list>
	#include <algorithm>

	using namespace std;

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

	const string &getName() const {
	return name;
	}

	int getAge() const {
	return age;
	}

	int getHeight() const {
	return height;
	}

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

	// 打印
	void printList(const list<Person> &l) {
	for (list<Person>::const_iterator it = l.begin(); it != l.end(); it++) {
	cout << "姓名：" << (it).getName() << " 年龄：" << (it).getAge() << " 身高：" << (*it).getHeight() << endl;
	}
	}

	// 指定排序规则
	bool comparePerson(Person &p1, Person &p2) {
	// 相同年龄则按照身高进行排序
	if (p1.getAge() == p2.getAge()) {
	// 按照身高降序
	return p1.getHeight() > p2.getHeight();
	}
	// 按照年龄升序
	return p1.getAge() < p2.getAge();
	}

	void test01() {
	// 创建容器
	list<Person> list1;
	list1.push_back(Person("刘备", 35, 175));
	list1.push_back(Person("曹操", 45, 180));
	list1.push_back(Person("孙权", 40, 170));
	list1.push_back(Person("赵云", 25, 190));
	list1.push_back(Person("张飞", 35, 160));
	list1.push_back(Person("关羽", 35, 200));

	cout << "排序前：" << endl;

	printList(list1);

	cout << "排序后：" << endl;

	// 自定义类型必须指定排序方式
	list1.sort(comparePerson);

	printList(list1);

	}

	int main() {
	test01();
	}

总结：1. 对于自定义数据类型，必须要指定排序规则，否则编译器不知道如何进行排序. 2. 高级排序只是在排序规则上再进行因此逻辑规则制定.

# set 容器

# set 基本概念

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

# set 构造和赋值

创建 set 容器以及赋值

构造：
- set<T> st ：默认构造函数.
- set(const set &st) ：拷贝构造函数.
赋值：
- set& operator=(const set &st) ：重载等号操作符.

set构造和赋值.cpp

	/**
	* set 构造和赋值
	*/
	#include <iostream>
	#include <set>

	using namespace std;

	void prinSet(const set<int> &set1) {
	for (set<int>::const_iterator iterator = set1.begin(); iterator != set1.end(); iterator++) {
	cout << *iterator << " ";
	}
	cout << endl;
	}

	void test01() {
	// 创建容器
	set<int> set1;
	// 插入数据只有 insert 方式
	set1.insert(10);
	set1.insert(40);
	set1.insert(30);
	set1.insert(20);
	set1.insert(30);
	// 遍历容器
	//set 容器特点：所有元素插入时都会被自动排序
	//set 容器不允许插入重复元素
	prinSet(set1);

	// 拷贝构造
	set<int> set2(set1);
	prinSet(set2);

	// 赋值
	set<int> set3;
	set3 = set2;
	prinSet(set3);
	}

	int main() {
	test01();
	}

总结：1. set 容器插入数据时用 insert() . 2. set 容器插入数据时会自动进行排序.

# set 大小和交换

统计 set 容器大小以及交换 set 容器.

函数原型：
size() ：返回容器中元素的数目
empty() ：判断容器是否为空
swap(st) ：交换两个集合容器

	/**
	* set 大小和交换
	*/
	#include <iostream>
	#include <set>

	using namespace std;

	void prinSet(const set<int> &set1) {
	for (set<int>::const_iterator iterator = set1.begin(); iterator != set1.end(); iterator++) {
	cout << *iterator << " ";
	}
	cout << endl;
	}

	void test01() {
	// 创建容器
	set<int> set1;
	set1.insert(10);
	set1.insert(40);
	set1.insert(30);
	set1.insert(20);
	set1.insert(30);
	prinSet(set1);

	if (set1.empty()) {
	cout << "set1元素为空" << endl;
	} else {
	cout << "set1元素不为空" << endl;
	cout << "set1中的元素数量：" << set1.size() << endl;
	}

	// 交换
	// 创建容器
	set<int> set2;
	set2.insert(9);
	set2.insert(8);
	set2.insert(11);
	set2.insert(18);
	set2.insert(6);
	prinSet(set2);

	cout << "交换前：" << endl;
	prinSet(set1);
	prinSet(set2);
	set1.swap(set2);
	cout << "交换后：" << endl;
	prinSet(set1);
	prinSet(set2);
	}

	int main() {
	test01();
	}

总结

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

# set 插入和删除

set 容器进行插入数据和删除数据

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

set插入和删除.cpp

	/**
	* set 插入和删除
	*/
	#include <iostream>
	#include <set>

	using namespace std;

	void prinSet(const set<int> &set1) {
	for (set<int>::const_iterator iterator = set1.begin(); iterator != set1.end(); iterator++) {
	cout << *iterator << " ";
	}
	cout << endl;
	}

	void test01() {
	set<int> set1;
	set1.insert(10);
	set1.insert(30);
	set1.insert(20);
	set1.insert(40);

	prinSet(set1);

	// 删除
	set1.erase(set1.begin());// 删除第一个元素
	prinSet(set1);

	// 删除指定数据
	set1.erase(30);
	prinSet(set1);

	// 清空
	set1.erase(set1.begin(), set1.end());
	set1.clear();
	prinSet(set1);
	}

	int main() {
	test01();
	}

总结

插入： insert()
删除： erase()
清空： clear()

# set 查找和统计

对 set 容器进行查找数据以及统计数据.

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

set查找和统计.cpp

	/**
	* set 查找和统计
	*/
	#include <iostream>
	#include <set>

	using namespace std;

	void prinSet(const set<int> &set1) {
	for (set<int>::const_iterator iterator = set1.begin(); iterator != set1.end(); iterator++) {
	cout << *iterator << " ";
	}
	cout << endl;
	}

	// 查找元素
	void test01() {
	set<int> set1;
	set1.insert(10);
	set1.insert(30);
	set1.insert(20);
	set1.insert(40);
	set<int>::iterator pos = set1.find(30);
	if (pos != set1.end()) {
	cout << "找到元素" << *pos << endl;
	} else {
	cout << "没有找到元素" << endl;
	}
	}

	// 统计元素
	void test02(){
	set<int> set1;
	set1.insert(10);
	set1.insert(30);
	set1.insert(30);
	set1.insert(30);
	set1.insert(20);
	set1.insert(40);

	// 统计 30 的个数对于 set 而言，要么是 0，要么是 1
	int num = set1.count(30);
	cout << "num = " << num << endl;
	}

	int main() {
	test01();
	test02();
	}

总结

查找： find(key) 返回的是迭代器.
统计： count(key) 对于 set 而言，结果为 0 或者 1 .

# set 和 multiset 区别

掌握 set 和 multiset 的区别

区别：
- set 不可以插入重复数据，而 multiset 则可以
- set 插入数据的同时会返回插入结果，表示插入是否成功
- multiset 不会检测数据，因此可以插入重复数据

set和multiset区别.cpp

	/**
	* set 和 multiset 区别
	*/
	#include <iostream>
	#include <set>

	using namespace std;

	void printMultiset(const multiset<int> &ms) {
	for (multiset<int>::const_iterator it = ms.begin(); it != ms.end(); it++) {
	cout << *it << " ";
	}
	cout << endl;
	}

	void test01() {
	set<int> s;
	pair<set<int>::iterator, bool> ret = s.insert(10);

	if (ret.second) {
	cout << "第一次插入成功" << endl;
	} else {
	cout << "第一次插入失败" << endl;
	}

	ret = s.insert(10);

	if (ret.second) {
	cout << "第二次插入成功" << endl;
	} else {
	cout << "第二次插入失败" << endl;
	}

	multiset<int> ms;
	ms.insert(10);
	ms.insert(10);
	ms.insert(10);
	ms.insert(10);

	printMultiset(ms);

	}

	int main() {
	test01();
	}

总结：1. 如果不允许插入重复数据可以利用 set . 2. 如果需要插入重复数据则利用 multiset .

# pair 对组的创建

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

两种创建方式：
- pair<type,type> p(value1,value2)
- pair<type,type> p = make_pair(value1,value2)

pair对组的创建.cpp

	/**
	* pair 对组的创建
	*/
	#include <iostream>

	using namespace std;

	//pair 对组的创建
	void test01() {

	// 第一种方式
	pair<string, int> pair1("Tom", 18);
	cout << "姓名：" << pair1.first << " 年龄：" << pair1.second << endl;

	// 第二种方式
	pair<string,int> pair2 = make_pair("Jerry",28);
	cout << "姓名：" << pair2.first << " 年龄：" << pair2.second << endl;
	}

	int main() {
	test01();
	}

# set 内置类型指定排序规则

set 容器默认排序规则为从小到大，掌握如何改变排序规则。主要技术点：利用仿函数，可以改变排序规则.

set内置类型指定排序规则.cpp

	/**
	* set 内置类型指定排序规则
	*/
	#include <iostream>
	#include <set>

	using namespace std;

	class MyCompare{
	public:
	bool operator()(int v1,int v2)const{
	return v1 > v2;
	}
	};

	void prinSet(const set<int> &set1) {
	for (set<int>::const_iterator iterator = set1.begin(); iterator != set1.end(); iterator++) {
	cout << *iterator << " ";
	}
	cout << endl;
	}
	void prinSet(const set<int,MyCompare> &set1) {
	for (set<int>::const_iterator iterator = set1.begin(); iterator != set1.end(); iterator++) {
	cout << *iterator << " ";
	}
	cout << endl;
	}

	void test01(){
	set<int> set1;
	set1.insert(10);
	set1.insert(40);
	set1.insert(20);
	set1.insert(50);
	set1.insert(30);
	prinSet(set1);

	// 指定排序规则从大到小
	set<int,MyCompare> set2;
	set2.insert(10);
	set2.insert(40);
	set2.insert(20);
	set2.insert(50);
	set2.insert(30);
	prinSet(set2);
	}

	int main(){
	test01();
	}

总结：利用仿函数可以指定 set 容器的排序规则.

# set 自定义数据类型指定排序规则

set 容器默认排序规则为从小到大。利用仿函数来改变排序规则.

set自定义数据类型指定排序规则.cpp

	/**
	* set 自定义数据类型指定排序规则
	*/
	#include <iostream>
	#include <set>

	using namespace std;

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

	// 解决排序方式一
	// bool operator<(const Person& other) const {
	// return age < other.age; // 或者其他你想比较的规则
	// }
	//
	// bool operator==(const Person& other) const {
	// return name == other.name && age == other.age;
	// }

	const string &getName() const {
	return name;
	}

	int getAge() const {
	return age;
	}

	private:
	string name;
	int age;
	};

	// 解决排序方式二
	class MyCompare {
	public:
	bool operator()(const Person &p1, const Person &p2) const {
	// 按照年龄进行降序
	return p1.getAge() > p2.getAge();
	}
	};

	void prinSet(const set<Person, MyCompare> &s1) {
	for (set<Person, MyCompare>::const_iterator it = s1.begin(); it != s1.end(); it++) {
	cout << "姓名：" << (it).getName() << " 年龄：" << (it).getAge() << endl;
	}
	}

	void test01() {
	// 解决排序方式一
	// set<Person> s1;
	// 解决排序方式二
	set<Person, MyCompare> s1;
	Person p1("刘备", 24);
	Person p2("关羽", 28);
	Person p3("张飞", 25);
	Person p4("赵云", 21);

	s1.insert(p1);
	s1.insert(p2);
	s1.insert(p3);
	s1.insert(p4);

	prinSet(s1);
	}

	int main() {
	test01();
	}

总结：对于自定义数据类型， set 必须指定排序规则才可以插入数据.

# map/multimap 容器

# map 基本概念

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

# map 构造和赋值

对 map 容器进行构造和赋值操作

函数原型：
- map<T1,T2> mp ： map 默认构造函数
- map(const map &mp) ：拷贝构造函数
赋值：
- map& operator=(const map &mp) ：重载等号操作符

map构造和赋值.cpp

	/**
	* map 构造和赋值
	*/
	#include <iostream>
	#include <map>

	using namespace std;

	void printMap(const map<int,int> &mp) {
	for(map<int,int>::const_iterator it = mp.begin();it!=mp.end();it++){
	cout << "Key：" << (*it).first << " value = " << it->second << endl;
	}
	}

	void test01() {
	map<int, int> mp;
	mp.insert(pair<int,int>(5,50));
	mp.insert(pair<int,int>(1,10));
	mp.insert(pair<int,int>(2,20));
	mp.insert(pair<int,int>(3,30));
	mp.insert(pair<int,int>(4,40));
	printMap(mp);

	cout << endl;

	// 拷贝构造
	map<int,int> m2(mp);
	printMap(m2);

	cout << endl;

	// 赋值
	map<int,int> m3;
	m3 = m2;
	printMap(m3);
	}

	int main() {
	test01();
	}

总结： map 中所有元素都是成对出现，插入数据时候要使用对组.

# map 大小和交换

统计 map 容器大小以及交换 map 容器.

函数原型：
- size() ：返回容器中元素的数目
- empty() ：判断容器是否为空
- swap() ：交换两个集合容器

map大小和交换.cpp

	/**
	* map 大小和交换
	*/
	#include <iostream>
	#include <map>

	using namespace std;

	void printMap(const map<int,int> &mp) {
	for(map<int,int>::const_iterator it = mp.begin();it!=mp.end();it++){
	cout << "Key：" << (*it).first << " value = " << it->second << endl;
	}
	}

	void test01(){
	map<int,int> mp;
	mp.insert(pair<int,int>(1,10));
	mp.insert(pair<int,int>(2,20));
	mp.insert(pair<int,int>(3,30));
	map<int,int> mp2;
	mp2.insert(pair<int,int>(4,40));
	mp2.insert(pair<int,int>(5,50));
	mp2.insert(pair<int,int>(6,60));

	// 判断是否为空
	if (mp.empty()){
	cout<< "map元素为空" << endl;
	} else{
	cout << "map元素不为空" << endl;
	cout << "map元素数量为：" << mp.size() << endl;
	}

	cout << "交换前：" << endl;
	printMap(mp);
	cout << endl;
	printMap(mp2);

	// 交换
	mp.swap(mp2);


	cout << "交换后：" << endl;
	printMap(mp);
	cout << endl;
	printMap(mp2);
	}

	int main(){
	test01();
	}

总结

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

# map 插入和删除

使用 map 容器进行插入和删除数据的操作.

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

map插入和删除.cpp

	/**
	* map 插入和删除
	*/
	#include <iostream>
	#include <map>

	using namespace std;

	void printMap(const map<int,int> &mp) {
	for(map<int,int>::const_iterator it = mp.begin();it!=mp.end();it++){
	cout << "Key：" << (*it).first << " value = " << it->second << endl;
	}
	}

	void test01(){
	map<int,int> mp;

	// 第一种插入
	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;

	printMap(mp);

	// [] 不建议插入，用途：可以利用 key 访问到 value
	// cout << mp[4] << endl;

	// 删除第一个元素
	mp.erase(mp.begin());
	cout << endl;
	printMap(mp);

	cout << endl;
	mp.erase(3);
	printMap(mp);

	cout << endl;
	mp.erase(mp.begin(), mp.end());
	printMap(mp);

	cout << endl;
	mp.clear();
	printMap(mp);

	}

	int main(){
	test01();
	}

总结

map 插入方式很多.
插入： insert() .
删除： erase() .
清空： clear() .

# map 查找和统计

对 map 容器进行查找数据以及统计数据.

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

map查找和统计.cpp

	/**
	* map 查找和统计
	*/
	#include <iostream>
	#include <map>

	using namespace std;

	void test01(){
	map<int,int> mp;
	mp.insert(pair<int,int>(1,10));
	mp.insert(pair<int,int>(2,20));
	mp.insert(pair<int,int>(3,30));
	mp.insert(pair<int,int>(3,40));

	// 查找
	map<int,int>::iterator pos = mp.find(3);
	if (pos!=mp.end()){
	cout << "查到了元素key = " << pos->first << " value = " << pos->second << endl;
	} else{
	cout << "未找到元素" << endl;
	}

	// 统计 map 不允许插入重复 key 元素，对于 count 统计而言，要么是 0，要么是 1
	//multimap 的 count 统计可能大于 1
	int num = mp.count(3);
	cout << "num = " << num << endl;
	}

	int main(){
	test01();
	}

总结

查找： find(key) ：返回的是迭代器
统计： count() ：对于 map 结果为 0 或 1 .

# map 排序

map 容器默认排序规则按照 key 值进行从大到小排序。利用仿函数可以改变排序规则.

map排序.cpp

	/**
	* map 排序
	*/
	#include <iostream>
	#include <map>

	using namespace std;

	class MyCompare {
	public:
	bool operator()(int v1, int v2) const {
	return v1 > v2;
	}
	};

	void printMap(const map<int, int, MyCompare> &mp) {
	for (map<int, int, MyCompare>::const_iterator it = mp.begin(); it != mp.end(); it++) {
	cout << "Key：" << (*it).first << " value = " << it->second << endl;
	}
	}

	void test01() {
	map<int, int, MyCompare> mp;
	mp.insert(pair<int, int>(1, 10));
	mp.insert(pair<int, int>(2, 20));
	mp.insert(pair<int, int>(3, 30));
	mp.insert(pair<int, int>(3, 40));
	printMap(mp);
	}

	int main() {
	test01();
	}

总结：1. 利用仿函数可以指定 map 容器的排序规则. 2. 对于自定义数据类型 map 必须要指定排序规则，同 set 容器一样.

# 函数对象

# 函数对象基本概念

概念：
- 重载函数调用操作符的类，其对象常称为函数对象.
- 函数对象使用重载的 () ，行为类似函数调用，也叫仿函数.
本质：
- 函数对象 (仿函数) 是一个类，不是一个函数.
函数对象的使用：
- 特点：
- 函数对象在使用时，可以像普通函数那样调用，可以有参数，可以有返回值.
- 函数对象超出普通函数的概念，函数对象可以有自己的状态.
- 函数对象可以作为参数传递.

函数对象基本概念.cpp

	/**
	* 函数对象 (仿函数)
	*/
	#include <iostream>

	using namespace std;

	class MyAdd {
	public:
	int operator()(int v1, int v2) {
	return v1 + v2;
	}
	};

	// 1. 函数对象在使用时，可以像普通函数那样调用，可以有参数，可以有返回值.
	void test01() {
	MyAdd myAdd;
	cout << myAdd(10,10) << endl;
	}

	// 2. 函数对象超出普通函数的概念，函数对象可以有自己的状态
	class MyPrint{
	public:
	MyPrint(){
	this->count = 0;
	}
	void operator()(string test){
	cout << test << endl;
	this->count++;
	}
	int count; // 内部自己的状态
	};

	void test02(){
	MyPrint myPrint;
	myPrint("hello world");
	myPrint("hello world");
	myPrint("hello world");
	myPrint("hello world");
	cout << "myPrint调用的次数为：" << myPrint.count << endl;
	}

	// 3. 函数对象可以作为参数传递
	void doPrint(MyPrint &mp, string test){
	mp(test);
	}

	void test03(){
	MyPrint myPrint;
	doPrint(myPrint,"Hello World");
	}

	int main() {
	test01();
	test02();
	test03();
	}

总结：仿函数写法非常灵活，可以作为参数进行传递.

# 谓词

# 谓词概念

概念：
返回 bool 类型的仿函数称为谓词.
如果 operator() 接受一个参数，那么叫做一元谓词.
如果 operator() 接受两个谓词，那么叫做二元谓词.

一元谓词.cpp

	/**
	* 一元谓词
	*/
	#include <iostream>
	#include <vector>
	#include <algorithm>

	using namespace std;

	class GreaterFive {
	public:
	bool operator()(int val) {
	return val > 5;
	}
	};

	// 仿函数返回值类型是 bool 数据类型，称为谓词
	void test01() {
	vector<int> v;
	for (int i = 0; i < 10; i++) {
	v.push_back(i);
	}

	// 查找容器中有没有大于 5 的数字 GreaterFive () 是名函数对象
	vector<int>::iterator it = find_if(v.begin(), v.end(), GreaterFive());
	if (it == v.end()) {
	cout << "未找到" << endl;
	} else {
	cout << "找到了大于5的数字为：" << *it << endl;
	}
	}

	int main() {
	test01();
	}

总结：参数只有一个的谓词，称为一元谓词.

二元谓词.cpp

	/**
	* 二元谓词
	*/
	#include <iostream>
	#include <algorithm>
	#include <vector>

	using namespace std;

	class MyCompare {
	public:
	bool operator()(int val1, int val2) const {
	return val1 > val2;
	}
	};

	void test01() {
	vector<int> v;
	v.push_back(10);
	v.push_back(40);
	v.push_back(20);
	v.push_back(30);
	v.push_back(50);

	sort(v.begin(), v.end());
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
	cout << *it << " ";
	}
	cout << endl;

	// 使用函数对象，改变算法策略，变为排序规则为从大到小

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

	cout << "---------------------------------------------" << endl;

	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
	cout << *it << " ";
	}
	cout << endl;
	}

	int main() {
	test01();
	}

总结：参数只有两个的谓词，称为二元谓词.

# 内建函数对象

# 内建函数对象意义

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

# 算术仿函数

实现四则运算，其中 negate 是一元运算，其他多少二元运算.

仿函数原型：
template<class T> T plus<T> ：加法仿函数
template<class T> T minus<T> ：减法仿函数
template<class T> T multiplies<T> ：乘法仿函数
template<class T> T divides<T> ：除法仿函数
template<class T> T modulus<T> ：取模仿函数
template<class T> T negate<T> ：取反仿函数

算术仿函数.cpp

	/**
	* 算术仿函数
	*/
	#include <iostream>
	// 内建函数对象的头文件
	#include <functional>

	using namespace std;

	//negate 一元仿函数取反仿函数

	void test01() {
	negate<int> n;
	cout << n(50) << endl;
	}

	//plus 二元仿函数加法仿函数
	void test02() {
	plus<int> p;
	cout << p(10, 20) << endl;
	}

	int main() {
	test01();
	test02();
	}

总结：使用内建函数对象时，需要引入头文件 #include<functional> .

# 关系仿函数

实现关系对比.

仿函数原型：
template<class T> boolequal_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> ：小于等于

关系仿函数.cpp

	/**
	* 关系仿函数
	*/
	#include <iostream>
	#include <functional>
	#include <vector>
	#include <algorithm>

	using namespace std;

	class MyCompare {
	public:
	bool operator()(int v1, int v2) {
	return v1 > v2;
	}
	};

	void test01() {
	vector<int> v;
	v.push_back(10);
	v.push_back(30);
	v.push_back(40);
	v.push_back(20);
	v.push_back(50);

	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
	cout << *it << " ";
	}
	cout << endl;

	// 降序
	// sort(v.begin(), v.end(), MyCompare());

	//greater<int>() 内建函数对象
	sort(v.begin(), v.end(), greater<int>());

	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
	cout << *it << " ";
	}
	cout << endl;
	}

	int main() {
	test01();
	}

总结：关系仿函数中最常见的就是 greater<T>() 大于.

# 逻辑仿函数

实现逻辑运算.

函数原型：
template<class T> bool logical_and<T> ：逻辑与
template<class T> bool logical_or<T> ：逻辑或
template<class T> bool logical_not<T> ：逻辑非

逻辑仿函数.cpp

	/**
	* 逻辑仿函数
	*/
	#include <iostream>
	#include <functional>
	#include <algorithm>

	using namespace std;

	void test01(){
	vector<bool> v;
	v.push_back(true);
	v.push_back(false);
	v.push_back(true);
	v.push_back(false);

	for (vector<bool>::iterator it = v.begin();it!=v.end();it++) {
	cout << *it << " ";
	}
	cout << endl;

	// 利用逻辑非将容器 v 搬运到容器 v2 中，并执行取反操作
	vector<bool> v2;
	v2.resize(v.size());
	transform(v.begin(), v.end(),v2.begin(),logical_not<bool>());

	for (vector<bool>::iterator it = v2.begin();it!=v2.end();it++) {
	cout << *it << " ";
	}
	cout << endl;
	}

	int main(){
	test01();
	}

总结：逻辑仿函数实际应用比较少，了解即可.

# 常用遍历算法

概述：
算法主要是由头文件 algorithm functional numeric 组成.
algorithm 是所有 STL 头文件中最大的一个，范围涉及到比较、交换、查找、遍历、复制、修改等等.
numeric 体积很小，只包括几个在序列上面进行简单数学运算的模版函数.
functional 定义了一些模版类，用以声明函数对象.

常用遍历算法：1. for_each ：遍历容器. 2. transform ：搬运容器到另一个容器中.

# for_each

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

for_each.cpp

	/**
	* for_each 遍历
	*/
	#include <iostream>
	#include <algorithm>
	#include <vector>

	using namespace std;

	// 普通函数
	void print01(int val){
	cout << val << " ";
	}

	// 仿函数
	class print02{
	public:
	void operator()(int val){
	cout << val << " ";
	}
	};

	void test01(){
	vector<int> v;
	for (int i = 0; i < 10; ++i) {
	v.push_back(i);
	}
	for_each(v.begin(), v.end(),print01);
	cout << endl;
	for_each(v.begin(), v.end(),print02());
	}

	int main(){
	test01();
	}

总结： for_each() 在实际开发中是最常用的遍历算法.

# transform

功能：搬运容器到另一个容器中.

函数原型：
transform(iterator beg1,iterator end1,iterator beg2,_func) ： beg1 源容器开始迭代器， end1 源容器结束迭代器， beg2 目标容器开始迭代器， _func 函数或函数对象.

transform.cpp

	/**
	* transform：搬运容器到另一个容器中
	*/
	#include <iostream>
	#include <vector>
	#include <algorithm>

	using namespace std;

	class Transform{
	public:
	int operator()(int v){
	return v + 100;
	}
	};

	class MyPrint{
	public:
	void operator()(int val){
	cout << val << " ";
	}
	};

	void test01(){
	vector<int> v;
	for (int i = 0; i < 10; ++i) {
	v.push_back(i);
	}
	// 目标容器
	vector<int> vTarget;
	// 目标容器需要提前开辟空间
	vTarget.resize(v.size());
	transform(v.begin(), v.end(),vTarget.begin(),Transform());
	for_each(vTarget.begin(),vTarget.end(),MyPrint());
	}

	int main(){
	test01();
	}

总结：搬运的目标容器必须要提前开辟空间，否则无法正常搬运.

# 常用查找算法

算法简介：
find ：查找元素
find_if ：按条件查找元素
adjacent_find ：查找相邻重复元素
binary_search ：二分查找法
count ：统计元素个数
count_if ：按条件统计元素个数

# find

查找指定元素，找到返回指定元素的迭代器，找不到返回结束迭代器 end() .

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

find.cpp

	/**
	* 常用查找算法：find
	*/
	#include <iostream>
	#include <algorithm>
	#include <vector>

	using namespace std;

	// 1. 查找内置数据类型
	void test01() {
	vector<int> v;
	for (int i = 0; i < 10; ++i) {
	v.push_back(i);
	}

	// 查找容器中是否有 5 这个元素
	vector<int>::iterator it = find(v.begin(), v.end(), 5);
	if (it == v.end()) {
	cout << "没有找到！" << endl;
	} else {
	cout << "元素找到了：" << *it << endl;
	}

	}

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

	const string &getName() const {
	return name;
	}

	int getAge() const {
	return age;
	}

	// 重载 == 号让底层的 find 知道如何对比 person 数据类型
	bool operator==(const Person &p) {
	if (this->name == p.name && this->age == p.age) {
	return true;
	}
	return false;
	}

	private:
	string name;
	int age;
	};

	// 2. 查找自定义数据类型
	void test02() {
	vector<Person> v;
	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);
	Person p4("ddd", 40);
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);

	Person pp("bbb",20);

	vector<Person>::iterator it = find(v.begin(), v.end(), pp);

	if (it == v.end()) {
	cout << "没有找到" << endl;
	} else {
	cout << "找到了元素姓名：" << (it).getName() << " 年龄：" << (it).getAge() << endl;
	}
	}

	int main() {
	test01();
	test02();
	}

总结：利用 find() 可以在容器中找指定的元素，返回值是迭代器.

# find_if

按照条件查找元素.

函数原型：
find_if(iterator beg,iterator end,_Pred) ：按值查找元素，找到返回指定位置迭代器，找不到返回结束位置迭代器， beg 开始迭代器，， end 结束迭代器， _Pred 函数或者谓词 (返回 bool 类型的仿函数).

find_if.cpp

	/**
	* 常用查找算法：find_if
	*/
	#include <iostream>
	#include <algorithm>
	#include <vector>

	using namespace std;

	class GreaterFive {
	public:
	bool operator()(int val) {
	return val > 5;
	}
	};

	// 1. 查找内置数据类型
	void test01() {
	vector<int> v;
	for (int i = 0; i < 10; ++i) {
	v.push_back(i);
	}

	vector<int>::iterator it = find_if(v.begin(), v.end(), GreaterFive());

	if (it == v.end()) {
	cout << "没有找到" << endl;
	} else {
	cout << "找到大于5的元素为" << (*it) << endl;
	}
	}

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

	const string &getName() const {
	return name;
	}

	int getAge() const {
	return age;
	}

	private:
	string name;
	int age;
	};

	class Greater20 {
	public:
	bool operator()(const Person &p) {
	if (p.getAge() > 20) {
	return true;
	}
	return false;
	}
	};

	// 2. 查找自定义数据类型
	void test02() {
	vector<Person> v;
	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);
	Person p4("ddd", 40);

	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);

	// 找年龄大于 20 的人
	vector<Person>::iterator it = find_if(v.begin(), v.end(), Greater20());

	if (it == v.end()) {
	cout << "没有找到" << endl;
	} else {
	cout << "姓名：" << (it).getName() << " 年龄：" << (it).getAge() << endl;
	}
	}

	int main() {
	test01();
	test02();
	}

# adjacent_find

查找相邻重复元素.

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

adjacent_find.cpp

	/**
	* 常用查找算法：adjacent_find
	*/
	#include <iostream>
	#include <algorithm>
	#include <vector>

	using namespace std;

	void test01() {
	vector<int> v;
	v.push_back(0);
	v.push_back(2);
	v.push_back(0);
	v.push_back(3);
	v.push_back(1);
	v.push_back(4);
	v.push_back(3);
	v.push_back(3);

	vector<int>::iterator pos = adjacent_find(v.begin(), v.end());

	if (pos == v.end()) {
	cout << "未找到相邻重复元素！" << endl;
	} else {
	cout << "找到相邻重复元素" << *pos << endl;
	}
	}

	int main() {
	test01();
	}

总结：面试题中如果出现查找相邻重复元素，记得用 STL 中的 adjacent_find 算法.

# binary_search

查找指定元素是否存在.

函数原型：
bool binary_search(iterator beg,iterator end, value ：查找指定的元素，查找返回 true ，否则 false , 注意：在无序序列中不可用， beg 开始迭代器， end 结束迭代器， value 查找的元素.

binary_search.cpp

	/**
	* 常用查找算法：binary_search
	*/
	#include <iostream>
	#include <algorithm>
	#include <vector>

	using namespace std;

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

	// v.push_back (2); 如果是无序序列，结果未知！

	// 查找容器中是否存在 9 元素
	// 注意：容器必须是有序的序列
	bool ret = binary_search(v.begin(), v.end(), 9);

	if (ret) {
	cout << "找到了元素" << endl;
	} else {
	cout << "未找到" << endl;
	}
	}

	int main() {
	test01();
	}

总结：二分查找法查找效率很高，值得注意的是查找的容器中元素必须是有序序列才可以.

# count

统计元素个数.

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

count.cpp

	/**
	* 常用查找算法：count
	*/
	#include <iostream>
	#include <algorithm>
	#include <vector>

	using namespace std;

	// 1. 统计内置数据类型
	void test01() {
	vector<int> v;
	v.push_back(10);
	v.push_back(40);
	v.push_back(30);
	v.push_back(40);
	v.push_back(20);
	v.push_back(40);

	int num = count(v.begin(), v.end(), 40);

	cout << "40的元素个数为：" << num << endl;
	}

	// 2. 统计自定义数据类型
	class Person {
	public:
	Person(string name, int age) {
	this->name = name;
	this->age = age;
	}

	// 自定义数据类型统计需要重载 ==
	bool operator==(const Person &p) {
	if (this->age == p.age) {
	return true;
	}
	return false;
	}

	const string &getName() const {
	return name;
	}

	int getAge() const {
	return age;
	}

	private:
	string name;
	int age;
	};

	void test02() {
	vector<Person> v;
	Person p1("刘备", 35);
	Person p2("关羽", 35);
	Person p3("张飞", 35);
	Person p4("赵云", 40);
	Person p5("曹操", 30);

	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	v.push_back(p5);

	Person p("诸葛亮", 35);

	int num = count(v.begin(), v.end(), p);

	cout << "和诸葛亮同岁的人员个数为：" << num << endl;
	}

	int main() {
	test01();
	test02();
	}

总结：对于统计自定义数据类型的时候，需要重载 operator== 才可以.

# count_if

按照条件统计元素个数.

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

count_if.cpp

	/**
	* 常用查找算法：count_if
	*/
	#include <iostream>
	#include <algorithm>
	#include <vector>

	using namespace std;

	// 1. 统计内置数据类型
	class Greater20 {
	public:
	bool operator()(int val) {
	return val > 20;
	}
	};

	void test01() {
	vector<int> v;
	v.push_back(10);
	v.push_back(40);
	v.push_back(30);
	v.push_back(20);
	v.push_back(40);
	v.push_back(20);

	int num = count_if(v.begin(), v.end(), Greater20());

	cout << "大于20的元素为：" << num << endl;

	}

	// 2. 统计自定义数据类型
	class Person {
	public:
	Person(string name, int age) {
	this->name = name;
	this->age = age;
	}

	const string &getName() const {
	return name;
	}

	int getAge() const {
	return age;
	}

	private:
	string name;
	int age;
	};

	class AgeGreater20 {
	public:
	bool operator()(const Person &p) {
	return p.getAge() > 20;
	}
	};

	void test02() {
	vector<Person> v;
	Person p1("刘备", 35);
	Person p2("关羽", 35);
	Person p3("张飞", 35);
	Person p4("赵云", 40);
	Person p5("曹操", 20);

	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	v.push_back(p5);

	// 统计年龄大于 20 岁的人员
	int num = count_if(v.begin(), v.end(), AgeGreater20());

	cout << "年龄大于20岁的人员有：" << num << endl;
	}

	int main() {
	test01();
	test02();
	}

# 常用排序算法

算法简介：
sort ：对容器内元素进行排序.
random_shuffle ：洗牌指定范围内的元素随机调整次序.
merge ：容器元素合并，并存储到另一个容器中.
reverse ：反转指定范围的元素.

# sort

对容器内元素进行排序.

函数原型：
sort(iterator beg,iterator end,_Pred) ：按值查找元素，找到返回指定位置迭代器，找不到返回结束位置迭代器， beg 开始迭代器， end 结束迭代器， _Pred 谓词.

sort.cpp

	/**
	* 常用排序算法：sort
	*/
	#include <iostream>
	#include <algorithm>
	#include <vector>
	#include <functional>

	using namespace std;

	void myPrint(int val) {
	cout << val << " ";
	}

	void test01() {
	vector<int> v;
	v.push_back(10);
	v.push_back(30);
	v.push_back(50);
	v.push_back(20);
	v.push_back(40);

	// 利用 sort 进行升序
	sort(v.begin(), v.end());

	for_each(v.begin(), v.end(), myPrint);
	cout << endl;

	// 改为降序
	sort(v.begin(), v.end(),greater<int>());
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;
	}

	int main() {
	test01();
	}

总结： sort 属于开发中最常用的算法之一.

# random_shuffle

洗牌指定范围内的元素随机调整次序.

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

random_shuffle.cpp

	/**
	* 常用排序算法：random_shuffle
	*/
	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <random>

	using namespace std;

	void myPrint(int val){
	cout << val << " ";
	}

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

	// 创建随机数生成器（高质量种子）
	random_device rd; // 随机设备作为种子
	mt19937 g(rd()); // 使用梅森旋转引擎

	// 利用洗牌算法打乱顺序
	shuffle(v.begin(), v.end(),g);

	for_each(v.begin(), v.end(), myPrint);

	}

	int main(){
	test01();
	}

总结： random_shuffle 洗牌算法比较实用，使用时需要添加随机种子

# merge

两个容器元素合并，并存储到另一个容器中.

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

merge.cpp

	/**
	* 常用排序算法：merge
	*/
	#include <iostream>
	#include <algorithm>
	#include <vector>

	using namespace std;

	void myPrint(int val){
	cout << val << " ";
	}

	void test01(){
	vector<int> v1;
	vector<int> v2;

	for (int i = 0; i < 10; ++i) {
	v1.push_back(i);
	v2.push_back(i+1);
	}

	// 目标容器
	vector<int> vTarget;

	// 提前开辟空间

	vTarget.resize(v1.size()+v2.size());

	merge(v1.begin(), v1.end(),v2.begin(), v2.end(),vTarget.begin());

	for_each(vTarget.begin(), vTarget.end(),myPrint);

	cout << endl;

	}

	int main(){
	test01();
	}

总结： merge 合并的两个容器必须是有序序列，并且还需要给目标容器使用 resize() 开辟所需的空间大小.

# reverse

将容器内元素进行反转.

函数原型：
reverse(iterator beg,iterator end) ：反转指定范围的元素， beg 开始迭代器， end 结束迭代器.

v.cpp

	/**
	* 常用排序算法：reverse
	*/
	#include <iostream>
	#include <algorithm>
	#include <vector>

	using namespace std;

	void myPrint(int val) {
	cout << val << " ";
	}

	void test01() {
	vector<int> v;
	v.push_back(10);
	v.push_back(30);
	v.push_back(50);
	v.push_back(20);
	v.push_back(40);

	cout << "反转前：" << endl;
	for_each(v.begin(), v.end(), myPrint);

	cout << endl;

	cout << "反转后：" << endl;
	reverse(v.begin(), v.end());
	for_each(v.begin(), v.end(), myPrint);
	}

	int main() {
	test01();
	}

总结： reverse 反转区间内的元素.

# 常用拷贝 and 替换算法

算法简介：
copy ：容器内指定范围的元素拷贝到另一个容器中.
replace ：将容器内指定范围的旧元素修改为新元素.
replace_if ：容器内指定范围满足条件的元素替换为新元素.
swap ：互换两个容器的元素.

# copy

容器内指定范围的元素拷贝到另一个容器中.

函数原型：
copy(iterator beg,iterator end,iterator dest) ：按值查找元素，找到返回指定位置迭代器，找不到返回结束位置迭代器， beg 开始迭代器， end 结束迭代器， dest 目标起始迭代器.

copy.cpp

	/**
	* 常用拷贝和替换算法：copy
	*/
	#include <iostream>
	#include <algorithm>
	#include <vector>

	using namespace std;

	void myPrint(int val){
	cout << val << " ";
	}

	void test01(){
	vector<int> v1;
	for (int i = 0; i < 10; ++i) {
	v1.push_back(i);
	}
	vector<int> v2;
	// 提前开辟空间
	v2.resize(v1.size());
	copy(v1.begin(), v1.end(),v2.begin());

	for_each(v2.begin(), v2.end(),myPrint);
	cout << endl;
	}

	int main(){
	test01();
	}

总结：利用 copy 算法在拷贝时，目标容器记得要提前开辟空间.

# replace

将容器内指定范围的旧元素修改为新元素.

函数原型：
replace(iterator beg,iterator end,oldvalue,newvalue ：将区间内旧元素替换成新元素， beg 开始迭代器， end 结束迭代器， oldvalue 旧元素， newvalue 新元素.

replace.cpp

	/**
	* 常用拷贝和替换算法：replace
	*/
	#include <iostream>
	#include <algorithm>
	#include <vector>

	using namespace std;

	void myPrint(int val) {
	cout << val << " ";
	}

	void test01() {
	vector<int> v;
	v.push_back(20);
	v.push_back(30);
	v.push_back(50);
	v.push_back(30);
	v.push_back(40);
	v.push_back(20);
	v.push_back(10);
	v.push_back(20);

	cout << "替换前：" << endl;
	for_each(v.begin(), v.end(), myPrint);

	cout << endl;

	cout << "替换后：" << endl;
	replace(v.begin(), v.end(), 20, 2000);
	for_each(v.begin(), v.end(), myPrint);

	}

	int main() {
	test01();
	}

总结： replace 会替换区间内满足条件的元素.

# replace_if

将区间内满足条件的元素，替换成指定元素.

函数原型：
replace_if(iterator beg,iterator end,_Pred,newvalue) ：按条件替换元素，满足条件的替换成指定元素， beg 开始迭代器， end 结束迭代器， _Pred 谓词， newvalue 替换的新元素.

replace_if.cpp

	/**
	* 常用拷贝和替换算法：replace_if
	*/
	#include <iostream>
	#include <algorithm>
	#include <vector>

	using namespace std;

	void myPrint(int val) {
	cout << val << " ";
	}

	class Greater30 {
	public:
	bool operator()(int val) {
	return val >= 30;
	}
	};

	void test01() {
	vector<int> v;
	v.push_back(10);
	v.push_back(40);
	v.push_back(20);
	v.push_back(40);
	v.push_back(30);
	v.push_back(50);
	v.push_back(20);
	v.push_back(30);


	cout << "替换前：" << endl;
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;

	// 将大于等于 30 的替换为 3000
	replace_if(v.begin(), v.end(), Greater30(), 3000);

	cout << "替换后：" << endl;
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;
	}

	int main() {
	test01();
	}

总结： replace_if 按照条件查找，可以利用仿函数灵活筛选满足的条件.

# swap

互换两个容器中的元素.

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

swap.cpp

	/**
	* 常用拷贝和替换算法：swap
	*/
	#include <iostream>
	#include <algorithm>
	#include <vector>

	using namespace std;

	void myPrint(int val) {
	cout << val << " ";
	}

	void test01() {
	vector<int> v1;
	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);

	vector<int> v2;
	v2.push_back(100);
	v2.push_back(200);
	v2.push_back(300);

	cout << "互换前：" << endl;
	for_each(v1.begin(), v1.end(), myPrint);
	for_each(v2.begin(), v2.end(), myPrint);
	cout << endl;
	swap(v1, v2);
	cout << "互换后：" << endl;
	for_each(v1.begin(), v1.end(), myPrint);
	for_each(v2.begin(), v2.end(), myPrint);
	}

	int main() {
	test01();
	}

总结： swap 交换容器时，注意交换的容器要同一种类型.

# 常用算术生成算法

算术生成算法属于小型算法，使用时包含头文件为 #include <numeric>
算法简介：
- accumulate ：计算容器元素累计总和.
- fill ：向容器中添加元素.

# accumulate

计算区间内容器元素累计总和.

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

accumulate.cpp

	/**
	* 常用算术生成算法：accumulate
	*/
	#include <iostream>
	#include <numeric>
	#include <vector>

	using namespace std;

	void test01() {
	vector<int> v;
	for (int i = 0; i <= 100; ++i) {
	v.push_back(i);
	}

	// 参数 3 是起始的累加
	int total = accumulate(v.begin(), v.end(), 0);
	cout << "total：" << total << endl;
	}

	int main() {
	test01();
	}

总结：在使用 accumulate 时需要包含头文件 numeric ，这个算法很实用.

# fill

向容器中填充指定的元素.

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

fill.cpp

	/**
	* 常用算术生成算法：fill
	*/
	#include <iostream>
	#include <numeric>
	#include <algorithm>
	#include <vector>

	using namespace std;

	void myPrint(int val) {
	cout << val << " ";
	}

	void test01() {
	vector<int> v;
	v.resize(10);

	// 后期重新填充
	fill(v.begin(), v.end(), 100);

	for_each(v.begin(), v.end(), myPrint);
	}

	int main() {
	test01();
	}

总结：利用 fill 可以将容器区间内的元素填充为指定的值.

# 常用集合算法

算法简介：
set_intersection ：求两个容器的交集.
set_union ：求两个容器的并集.
set_difference ：求两个容器的差集.

# set_intersection

求两个容器的交集.

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

set_intersection.cpp

	/**
	* 常用集合算法：set_intersection
	*/
	#include <iostream>
	#include <algorithm>
	#include <vector>

	using namespace std;

	void myPrint(int val) {
	cout << val << " ";
	}

	void test01() {
	vector<int> v1;
	vector<int> v2;
	for (int i = 0; i < 10; ++i) {
	v1.push_back(i);
	v2.push_back(i + 5);
	}

	vector<int> vTarget;

	cout << "v1和v2的交集为：" << endl;

	// 目标容器需要提前开辟空间‘
	// 最特殊的情况是，大容器包含小容器，开辟空间的时候则需要取小容器的 size
	vTarget.resize(min(v1.size(), v2.size()));

	// 获取交集
	vector<int>::iterator itEnd = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());

	for_each(vTarget.begin(), itEnd, myPrint);

	}

	int main() {
	test01();
	}

总结

求交集的两个集合必须是有序序列.
目标容器开辟空间需要从两个容器中取小值.
set_intersection 返回值既是交集中最后一个元素的位置.

# set_union

求两个集合的并集.

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

set_union.cpp

	/**
	* 常用集合算法：set_union
	*/
	#include <iostream>
	#include <algorithm>
	#include <vector>

	using namespace std;

	void myPrint(int val) {
	cout << val << " ";
	}

	void test01() {
	vector<int> v1;
	vector<int> v2;
	for (int i = 0; i < 10; ++i) {
	v1.push_back(i);
	v2.push_back(i + 5);
	}

	vector<int> vTarget;

	cout << "v1和v2的并集为：" << endl;

	// 目标容器需要提前开辟空间‘
	// 最特殊的情况是，两个容器没有交集，交集就是两个容器 size 相加
	vTarget.resize(v1.size()+v2.size());

	// 获取交集
	vector<int>::iterator itEnd = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());

	for_each(vTarget.begin(), itEnd, myPrint);

	}

	int main() {
	test01();
	}

总结

求并集的两个集合必须是有序序列.
目标容器开辟空间需要两个容器相加.
set_union 返回值既是并集中最后一个元素的位置.

# set_difference

求两个集合的差集.

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

set_difference.cpp

	/**
	* 常用集合算法：set_difference
	*/
	#include <iostream>
	#include <algorithm>
	#include <vector>

	using namespace std;

	void myPrint(int val) {
	cout << val << " ";
	}

	void test01() {
	vector<int> v1;
	vector<int> v2;
	for (int i = 0; i < 10; ++i) {
	v1.push_back(i);
	v2.push_back(i + 5);
	}

	vector<int> vTarget;


	cout << "v1和v2的差集为：" << endl;
	// 目标容器需要提前开辟空间‘
	// 最特殊的情况是，两个容器没有交集，取两个容器中取较大的 size 作为目标容器的开辟空间
	vTarget.resize(max(v1.size(), v2.size()));

	// 获取交集
	vector<int>::iterator itEnd = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());

	for_each(vTarget.begin(), itEnd, myPrint);

	cout << endl;

	cout << "v2和v1的差集为：" << endl;

	itEnd = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), vTarget.begin());
	for_each(vTarget.begin(), itEnd, myPrint);
	}

	int main() {
	test01();
	}

总结

求差集的两个集合必须是有序序列.
目标容器开辟空间需要从两个容器取较大值.
set_set_difference 返回值既是差集中最后一个元素的位置.