模板

通常 对 具有相同要求的结果或者类 提供一个模板，根据实际使用时传过来的数据类型，决定函数和类的具体实现。
模板可以让类或者函数支持一种类型，这种通用类型在实际运行的过程中可以使用任何数据类型。
这种编程方式也成为"泛型编程"。

模板函数

如果函数除了参数类型和返回值类型以外，其他部分全部相同，就可以使用模板来定义函数。

template <typename T> // T：数据类型
template <typename T1, typename T2, …>

#include <iostream>
using namespace std;template <typename T>		// 模板只对下面的第一个函数有效
T func()					// 参数没有使用模板中的类型，或者无参，不能通过函数调用直接推导出 T 的类型
{							// 需要显性调用模板return 38;
}template <typename T>		// 模板只对下面的第一个函数有效
T func(T a, T b)			// 两个参数都是模板的数据类型，可以通过函数调用推导出模板类型
{							// 隐性调用模板return a > b ? a : b;
}template <typename T1, typename T2>			// 模板只对下面的第一个函数有效
T2 add(T1 a, T1 b)
{	T2 num;					// 模板提供的数据类型也可以在函数里面定义变量使用return a + b;
}int main()
{int num1 = 9;int num2 = 6;cout << func<char>() << endl;cout << func(num1, num2) << endl;cout << func(6, 9) << endl;			// 若用小数，必须每个值都用小数，∵T func(T a, T b)cout << add<int, int>(num1, num2) << endl;cout << add<float, float>(6, 9) << endl;return 0;
}

模板类

如果要 给模板类的成员函数 实现 类内声明类外定义，需要在类外定义的位置再重写一次模板，并且，类要使用显性调用模板来实现。

#include <iostream>
using namespace std;// 实现模板类
template <typename T>			// 可以使用 class，也可以使用 typename
class Complex
{T real;T vir;
public:Complex() { }Complex(T real, T vir):real(real), vir(vir) { }void set_(T real, T vir);  // 模板类中的成员函数，可以实现类内声明，类外定义，需要重写模板void show();			   // 模板类中的成员函数也可以在类内定义
};template <typename T>  		// 只对下面一个模板函数有效
void Complex<T>::set_(T real, T vir)
{this->real = real;this->vir = vir;
}template <typename T>		// 只对下面一个模板函数有效
void Complex<T>::show()
{cout << real << "+" << vir << "i" << endl;
}int main()
{Complex<int> com(3, 4);com.show();com.set_(5, 12);com.show();return 0;
}

STL 标准模板库（Standard Template Library）

https://en.cppreference.com/w/（👈，放心跳转）

标准模板库（Standard Template Library，STL）是惠普实验室开发的一系列软件的统称。虽说它主要出现到了 C++ 中，但是在被引入 C++ 之前该技术就已经存在了很长时间。
STL 的代码从广义上讲分为三类：algorithm（算法）、container（容器）和 iterator（迭代器），几乎所有的代码都采用了模板类和模板函数的方式，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。

C++ Iterators（迭代器）

迭代器是一个特殊的指针，主要用于元素的读写以及遍历。

找指定位置的迭代器

由于容器类只能找起始位置和结束位置的迭代器，所以只能在已有迭代器的位置上自增，和指针类似。访问元素需要解引用，但是不能像指针类型一样强转。

容器名<数据类型> ::iterator 迭代器名;

迭代器遍历

如果 迭代器不进行修改操作，建议使用只读迭代器 const_iterator，反之使用 iterator。

#include <iostream>
#include <array>
#include <vector>
#include <list>
#include <deque>
#include <map>using namespace std;int main()
{// stringstring s = "abcdefg";for(string::const_iterator iter = s.begin();iter != s.end(); iter++){cout << *iter;}cout << endl;cout << "-----------" << endl;// arrayarray<int, 5> arr = {21, 2, 4, 67, 3};for(array<int, 5>::const_iterator iter = arr.begin();iter != arr.end(); iter++){cout << *iter << " ";}cout << endl;cout << "-----------" << endl;// vectorvector<string> vec(6, "world");for(vector<string>::const_iterator iter = vec.begin();iter != vec.end(); iter++){cout << *iter << " ";}cout << endl;cout << "-----------" << endl;// listlist<string> lis(5, "hello");for(list<string>::const_iterator iter = lis.begin();iter != lis.end(); ++iter) 		// 等同于 iter++{cout << *iter << " ";}cout << endl;cout << "-----------" << endl;// dequedeque<string> de(6, "Hola~");for(deque<string>::const_iterator it = de.begin();it != de.end(); it++){cout << *it << " ";}cout << endl;cout << "-----------" << endl;// mapmap<string, int> ma;ma["waistline"] = 66;ma["type"] = 1;ma["height"] = 188;ma["asset"] = 202300;for(map<string, int>::const_iterator i = ma.begin();i != ma.end(); i++){// first 是键(key)，second 值(val)cout <<  i->first << " " << i->second << endl;}return 0;
}

容器（= 顺序容器 + 关联容器）

用来存储数据的集合，数据元素可以是任何类型（因为是使用模板进行实现的）。
容器类的使用，需要引入对应的头文件。

顺序容器

顺序容器中每个元素均有固定的位置并呈现线性排布，
除非使用删除或者插入的操作改变原来元素的位置。

Array 数组

array 数组是 C++11 新增的容器类型，与传统数组相比更加安全，易于使用。array 数组是定长的。

EXAMPLE

#include <iostream>
#include <string.h>
#include <array>  						// 头文件using namespace std;int main()
{// 创建一个长度为 5 的 int 数组array<int, 5> arr = {1, 2, 3}; 		// 后面两位补零cout << arr[0] << endl; 			// 1cout << arr[4] << endl; 			// 0cout << arr.at(2) << endl; 			// 3，推荐使用 at函数（安全）arr[3] = 200;cout << "------------" << endl;// for 循环遍历for(int i = 0; i < arr.size(); i++){cout << arr.at(i) << endl;}cout << "------------" << endl;// for each 遍历for(int i : arr){cout << i << endl;}return 0;
}

Vector 向量

vector 的行为和数组类似，可以理解为顺序表。
vector 内部是由数组实现的，比较适合进行随机的存取操作，不擅长插入和删除操作。
vector 不需要判满，动态分配内存：如果存入新的数据，会再开辟一片更大的空间，把原来的内容拷贝过去。

构造函数

Functions

bool empty();

size_type size();

TYPE at (size_type loc);

iterator begin();

iterator end();

void push_back (const TYPE &val);

size_type capacity();

void pop_back();

TYPE front();

TYPE back();

insert 函数

iterator insert (iterator loc, const TYPE &val);
void insert (iterator loc, size_type num, const TYPE &val);
void insert (iterator loc, input_iterator start, input_iterator end);

assign 函数

void assign (input_iterator start, input_iterator end);
void assign (size_type num, const TYPE &val);

EXAMPLE

#include <iostream>
#include <vector>
using namespace std;int main()
{vector<int> v1;   		// 调用 vector 的无参构造vector<int> v2(5, 3);vector<int> v3(v2);   	// 调用拷贝构造cout << v1.empty() << endl;		// 判断 v1 是否为空cout << "元素个数：" << v2.size() << endl;   	// 输出 v2 容器中元素的个数cout << "v2的大小：" << v2.capacity() << endl;  	// 5v2.push_back(89);				// 尾插cout << "元素个数：" << v2.size() << endl;cout << "v2的大小：" << v2.capacity() << endl;  // 插入一个元素后，是 10，二倍扩容cout << "V2中的元素：" << endl;v2.push_back(89);cout << "\t push 后元素个数：" << v2.size() << endl;v2.pop_back();cout << "\t pop 后元素个数：" << v2.size() << endl;cout << "v2的大小：" << v2.capacity() << endl;v2.front() = 45;v2.back() = 78;// 在第三个位置前插入元素，需要用到 insert 函数vector<int>::iterator pos = v2.begin()+2;v2.insert(pos, 29);vector<int>::iterator temp;   // 定义一个可以遍历 <int> 模板的 vector 容器的迭代器for (temp = v2.begin(); temp != v2.end(); temp++)cout << *temp << "\t";  //对迭代器解引用操作，访问到具体的元素cout << endl;cout << *(v2.end()-1) << endl;/*cout << v2.front() << endl;  		// 返回对象的引用cout << v2.back() << endl;*/cout << v2.size() << endl;pos = v2.begin()+4;  		// 和指针的操作相同，从第一个迭代器找下一个迭代器直接 +1temp = v2.end();v2.assign(pos, temp);for (temp = v2.begin(); temp != v2.end(); temp++){cout << *temp << "\t";  //对迭代器解引用操作，访问到具体的元素}cout << endl;return 0;
}

( begin / end ) v.s. ( front / back )

begin 和 end 成员函数，返回起始位置和结尾位置的迭代器；
front 和 back 成员函数，返回起始位置和结尾位置的引用。

vector 的二倍扩容

vector<int> v2(5, 3); // 第一次开辟 5 个 int 型 大小（5个3）
v2.push_back(89); // v2 容器中元素满，再插入 89，则再开辟 5 个 int 型 大小
// 若再满，再插入，则再开辟 10 个 int 型 大小。然后是 20，40…以此类推。

List 双向链表

list 内部有双向循环链表的实现，内存空间不连续，不支持下标。
可以进行高效的删除和添加操作，但是不适合随机存取。

#include <iostream>
#include <list> 				// 头文件
using namespace std;int main()
{// 创建一个默认无数值的 list// list<string> lis1;// 创建一个长度为 2 的列表，第一个元素 "hello"，第二个元素 "world"
//    list<string> lis2{"hello", "world"};
//    for(string s : lis2)
//    {
//        cout << s << endl;
//    }// 创建一个长度为 5 的列表，每个元素都是 "hello"list<string> lis(5, "hello");// 增lis.push_back("world"); 			// 向后追加单元素lis.push_front("hahaha"); 			// 向前追加单元素lis.insert(++lis.begin(), "222"); 	// 在第二个位置上插入"222"for (list<string>::iterator iter = lis.begin(); iter != lis.end(); iter++)cout << *iter << ", ";cout << endl << "----------------" << endl;// 删lis.pop_back(); 			// 删除最后一个元素lis.pop_front(); 			// 删除第一个元素// 迭代器list<string>::iterator iter = lis.begin();advance(iter, 1); 			// 移动迭代器指针到固定位置lis.insert(iter, "333");lis.push_back("world"); // 向后追加单元素// 删除最后一个元素iter = lis.end();iter--;lis.erase(iter);// 删除iter = lis.begin();advance(iter, 1);lis.erase(iter);// 返回最后一个元素cout << "The last: " << lis.back() << endl;// 返回第一个元素cout << "The first: " << lis.front() << endl;cout << "----------------" << endl;// 不能用普通循环遍历，因为不支持下标for(string s : lis){cout << s << endl;}cout << "Size = " <<lis.size() << endl;lis.clear();cout << "Size = " << lis.size() << endl;return 0;
}

Deque 双端队列

队列几乎支持所有 vector 的API，性能位于 vector 与 list 二者之间，是擅长两端存取的顺序容器。

#include <iostream>
#include <deque>			// 头文件
using namespace std;int main()
{//    deque<int> v(5);
//    for(int i : v)
//    {
//        cout << i << endl;
//    }// 创建一个长度为 5 的 int 向量deque<int> vec = {1, 2, 3, 4, 5};// 增// 向后追加一个元素vec.push_back(222);// cout << vec.size() << endl;// begin()可以返回指向第一个元素的迭代器指针，+2是在第三个位置上插入333vec.insert(vec.begin()+2, 333); // 1 2 333 3 4 5 222// 删// 删除最后一个元素vec.pop_back(); 				// 1 2 333 3 4 5// 删除第二个元素vec.erase(vec.begin() + 1);		// 1 333 3 4 5// 删除倒数第二个元素vec.erase(vec.end() - 2); 		// 1 333 3 5// 改vec.at(2) = 666; 				// 1 333 666 5vec[1] = 222;   				// 1 222 666 5// 查cout << vec.at(1) << endl;cout << vec[0] << endl;// 遍历for(int i :vec){cout << i << " ";}cout << endl;cout << "-----------" << endl;for(int i = 0; i < vec.size(); i++){cout << vec[i] << " " ;}cout << endl;cout << "-----------" << endl;// 判断是否为空，0:非空 1:空cout << vec.empty() << endl;// 清空vec.clear();cout << vec.empty() << endl;return 0;
}

关联容器

关联容器的各元素之间没有严格的顺序，虽然内部具有排序特点，但在使用时没有任何顺序相关接口。
最常见的关联容器就是 map —— 键值对映射。

Map

对于 map 而言，键具有唯一性，键通常使用字符串类型，
值可以是任何类型，通过键可以找到对应的值。

#include <iostream>
#include <map> 					// 头文件
using namespace std;int main()
{// 列表初始化创建 c++11 支持
//    map<string, int> ma1 = {{"年龄", 5}, {"身高", 200}};
//    cout << ma1.size() << endl; 					// 2// 创建一个元素为 0 的键值对对象map<string, int> ma;cout << ma.size() << endl;ma["height"] = 185; 							// 插入元素ma.insert(pair<string, int>("weight", 140)); 		// 插入元素// 查cout << "Height: " << ma["height"] << endl;cout << "Weight: " << ma["weight"] << endl;// 改ma["height"] = 188;cout << "Height: " << ma["height"] << endl;// 删if(ma.find("weight") == ma.end()){cout << "Cannot find the key named \"weight\"! "<< endl;}else{int re = ma.erase("weight");cout << "Succeeded or not: " << re << endl;}cout << ma.size() << endl;ma.clear();cout << ma.size() << endl;return 0;
}