1. 模（mú）板 template（掌握）
1.1 基本概念
模板让程序员编写与类型无关的代码，可以让程序员专注于算法设计，因为运行过程中可以是任何类型，共用这一套算法。
模板是泛型编程的基础，泛型编程的目的是发明一种语言机制，能够帮助实现一个通用的标准模板库STL。
模板通常有两种形式：
- 函数模板
- 类模板
1.2 函数模板
#include <iostream>
using namespace std;
template <class T>
T add(T a,T b)
{
return a+b;
}
int main()
{
// 可以是int类型
cout << add(2,3) << endl;
cout << add(2.2,3.3) << endl;
string s1 = "AAA";
string s2 = "BBB";
cout << add(s1,s2) << endl;
// 但是有可能出出现类型和算法不匹配的问题
cout << add("AAA","BBB") << endl; // 第8行报错
return 0;
}
通常使用函数模板要确保算法的通用性。
1.3 类模板
#include <iostream>
using namespace std;
template <typename T>
class Demo
{
private:
T value;//T value; 存储实际的值，类型由模板参数 T 决定
public:
Demo(T v):value(v){}
T get_value() const//返回存储的值，const 修饰确保不修改对象。
{
return value;
}
void set_value(T v)//修改存储的值。
{
value = v;
}
};
//实现方式：模板类的成员函数必须在定义时重复模板声明 template //<typename T>。
//类名指定：使用 Demo<T>:: 表示函数属于模板类 Demo 的特定实例。
//class vs typename：第三行的 template <class T> 与 template //<typename T> 等价，class 是早期 C++ 标准的写法。
int main()
{
Demo<int> d1(1234); // 实例化Demo<int>
cout << sizeof(d1) << endl; // 输出: 4（int的大小）
cout << d1.get_value() << endl; // 输出: 1234
d1.set_value(3333); // 修改值为3333
cout << d1.get_value() << endl; // 输出: 3333
Demo<double> d2(12.34); // 实例化Demo<double>
cout << sizeof(d2) << endl; // 输出: 8（double的大小）
cout << d2.get_value() << endl; // 输出: 12.34
d1.set_value(33.33); // 错误：d1是Demo<int>，无法接受double参数
cout << d2.get_value() << endl; // 输出: 12.34（未被修改）
return 0;
}
上面的写法也可以变成类内声明类外定义的格式：
#include <iostream>
using namespace std;
template <typename T>
class Demo
{
private:
T value;
public:
Demo(T v);
T get_value() const;
void set_value(T v);
};
template <typename T>
Demo<T>::Demo(T v)
{
value = v;
}
template <typename T>
T Demo<T>::get_value() const
{
return value;
}
template <class T>
void Demo<T>::set_value(T v)
{
value = v;
}
int main()
{
Demo<int> d1(1234); // 4
cout << sizeof(d1) << endl;
cout << d1.get_value() << endl;
d1.set_value(3333);
cout << d1.get_value() << endl;
Demo<double> d2(12.34);
cout << sizeof(d2) << endl;
cout << d2.get_value() << endl;
d1.set_value(33.33);
cout << d2.get_value() << endl;
return 0;
}
2. 容器 container
2.1 标准模板库 STL（掌握）
标准模板库（Standard Template Library，STL）是惠普实验室开发的一系列软件的统称。虽说它主要表出现到C++中，但在被引入C++之前该技术就已经存在了很长时间。
STL的代码从广义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器），几乎所有的代码都采用了模板类和模板函数的方式，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。
2.2 容器概念（掌握）
容器用来存储数据的集合，数据可以是用户自定义类型，也可以是预定义类型。
C++中有两种类型的容器：顺序容器和关联容器。
容器类自动申请和释放内存，无需new和delete操作。所有容器类的使用都需要引入对应的头文件，因为这些类型都是std名字空间下的类。
2.3 顺序容器
是一种各元素之间有顺序关系的线性表，是一种线性结构的可序群集。
顺序性容器中的每个元素均有固定的位置，除非用删除或者插入的操作改变这个位置。
2.3.1 array 数组（熟悉）
在C++11中引入array类型代替传统数组，相比于内置的传统数组，array更加安全和易于使用。
#include <iostream>
#include <array> // 头文件
using namespace std;
int main()
{
// 创建一个长度为5的int数组
array<int,5> arr = {1,2,3};
// 修改数据
arr[0] = 111;
arr.at(1) = 222;
// 遍历输出
for(int i:arr)
cout << i << endl;
// 给所有元素赋一个统一的值
arr.fill(-1);
//fill()是std::array的成员函数，用于批量赋值。
// for循环
for(int i = 0;i<arr.size();i++)
{
cout << arr.at(i) << endl;
}
return 0;
}
2.3.2 vector 向量（重点）
vector相比于array是动态的长度，即支持插入删除的等操作，内部使用数组实现，因此元素的空间地址是连续的，因此随机存取的效率很高，插入删除的效率较低。
std::vector 位于 <vector> 头文件中，本质是一个类模板，其核心特点：
动态大小：无需预先指定数组长度，可随时添加或删除元素。
连续存储：元素在内存中连续排列，支持高效的随机访问（时间复杂度 O (1)）。
类型安全：通过模板参数指定元素类型，编译时检查类型匹配。
#include <iostream>
#include <vector> // 头文件
using namespace std;
int main()
{
// 创建一个长度为5的向量
vector<int> vec(5); // 创建包含5个元素的vector，初始值为0
cout << vec.size() << endl; // 输出: 5（容器大小）
// 修改元素
vec[0] = 111;
vec.at(1) = 222;
// 在第一个位置插入数据101
// vec.begin()可以返回一个迭代器指针，指向第一个元素
vec.insert(vec.begin(),101);
// 在第三个位置插入数据333
vec.insert(vec.begin()+2,333);
// 在最后的位置插入数据-1
vec.push_back(-1);
// 新插入的数据是倒数第三个，插入数据为-333
// vec.end()可以返回一个迭代器指针，指向最后一个元素的后面
vec.insert(vec.end()-2,-333);
// 删除最后一个数据
vec.pop_back();
// 删除第四个数据
vec.erase(vec.begin()+3);
// 删除倒数第四个数据
vec.erase(vec.end()-4);
// 遍历
for(int i:vec)
cout << i << " ";
cout << endl;
vec.clear(); // 清空
cout << vec.empty() << endl; // 1
for(int i=0;i<vec.size();i++)
cout << vec.at(i) << " ";
cout << endl;
return 0;
}
2.3.3 list 列表（重点）
list内部使用双向链表实现，因此list更擅长插入和删除操作，但是由于元素之间的地址不连续，随机存取的能力较差，因此也不支持下标。
优点：插入和删除操作效率高（O (1)），不涉及内存重新分配。
缺点：不支持随机访问（如lis[2]），只能通过迭代器顺序访问。
迭代器特性：
begin()：指向第一个元素。
end()：指向最后一个元素的下一个位置（哨兵节点）。不要删
不支持iter + n（随机访问），需使用advance()移动。
#include <iostream>
#include <list> // 头文件
using namespace std;
int main()
{
// 创建一个长度为5的列表
list<int> lis(5);
cout << lis.size() << endl;
// 迭代器iterator是一种特殊的指针，高度封装
list<int>::iterator iter = lis.begin();
// 修改元素
*iter = 111; // 把第一个元素改为111
iter++; // 移动到第二个位置
*iter = 222;
lis.push_front(101); // 在头部插入101
advance(iter, 2); // 迭代器向后移动2步
lis.insert(iter, 333); // 在第三个位置插入333
lis.push_back(-1); // 在尾部插入-1
iter = lis.end();
advance(iter,-2); // 向前移动2个位置
// 新插入的数据是倒数第三个，插入数据为-333
lis.insert(iter,-333);
// 删除最后一个数据
lis.pop_back();
// 删除第一个数据
lis.pop_front();
// 删除第四个数据
iter = lis.begin();
advance(iter,3);
lis.erase(iter);
// 删除倒数第四个数据
iter = lis.end();
advance(iter,-4);
lis.erase(iter);
// 排序（前提是存储的数据支持排序）
lis.sort();
//sort() 方法：
//链表内置的排序算法，时间复杂度 O (n log n)。
//要求元素类型支持<运算符（或自定义比较函数）。
//clear() 方法：
//清空所有元素，链表大小变为 0，但内存不会立即释放（由系统回收）。
// 清空
lis.clear();
cout << lis.empty() << endl;
// for-each
for(int i:lis)
cout << i << " ";
cout << endl;
return 0;
}
advance() 函数：用于移动迭代器，advance(iter, n)
等价于：正向移动：for(int i=0; i<n; i++) iter++;
逆向移动（仅双向迭代器支持）：for(int i=0; i<n; i++) iter--;
迭代器失效规则：
插入操作仅使被插入位置的迭代器失效。
删除操作使被删除位置及之后的迭代器失效。
2.3.4 deque 队列（熟悉）
deque是一种均衡的容器，从接口设计上几乎兼容vector和list的功能，性能介于二者之间，代码略。
没有排序，其他相同，直接替换掉vector和list就是deque代码。
2.4 关联容器（掌握）
主要讲解map：键值对映射
关联容器的元素没有严格的顺序关系，但是内部有排序，因此才可以被迭代器遍历。
每个元素的数据被称为值（value），每个元素拥有一个独一无二的名称：键（key），所以一个完整的元素被称为键值对。
特性：
有序存储：基于红黑树（平衡二叉搜索树）实现，键按字典序排列。
唯一性：每个键只能出现一次，重复插入会被忽略。
高效查找：插入、删除、查找操作的时间复杂度均为 O (log n)。
#include <iostream>
#include <map> // 头文件
using namespace std;
int main()
{
map<string, int> ma; // 创建一个键为string，值为int的映射
cout << ma.empty() << endl; // 1
// 插入数据
ma["height"] = 180;
ma["salary"] = 17999;
ma["salary"] = 18000; // 因为之前有这个键了，变为修改
ma.insert(pair<string,int>("age",28));// 使用pair插入
ma.insert(pair<string,int>("weight",78));
ma.insert(pair<string,int>("weight",79)); // 之前有此键，不改
ma["comm"] = 2000; // 下标插入
cout << ma.size() << endl; // 5
// 取出元素
cout << ma["weight"] << endl; // 78
cout << ma["salary"] << endl; // 18000
// 判断一个元素是否存在// 安全查找：使用find()
map<string,int>::iterator iter = ma.find("name"); // 拿到迭代器指针
if(iter == ma.end()) // 没有此键
{
cout << "没有name键" << endl;
}
// find() 方法：
//若找到，返回指向该元素的迭代器。若未找到，返回ma.end()。
// 删除一个元素
// 返回值表示删除结果
// ==0：删除失败 >0：删除成功
int result = ma.erase("age");
if(result)
{
cout << "删除成功" << endl;
}else
{
cout << "删除失败" << endl;
}
result = ma.erase("age");// 再次删除已不存在的键
if(result)
{
cout << "删除成功" << endl;
}else
{
cout << "删除失败" << endl;
}
ma.clear();
cout << ma.size() << endl; // 0
return 0;
}
与unordered_map的对比：
map：有序，基于红黑树，插入 / 查找 O (log n)。
unordered_map：无序，基于哈希表，平均插入 / 查找 O (1)。
2.5 迭代器 iterator（掌握）
迭代器（Iterator）是一种设计模式和编程工具，用于遍历和访问容器（如数组、链表、集合等）中的元素，而无需暴露容器的内部实现细节。迭代器提供了一种统一的方式来处理不同类型的容器，使得算法可以独立于容器类型运行，增强了代码的通用性和可复用性。
容器的遍历通常都是使用迭代器进行的，C++标准库为每一种容器提供了对应的迭代器类型。
迭代器如同一个指针，但是迭代器又不仅仅是指针。
迭代器的基本概念
作用：迭代器是一种抽象的指针，用于遍历容器中的元素，提供了访问容器元素的统一接口。
接口：迭代器通常支持以下操作：
*it：解引用操作符，返回当前位置的元素。
++it：前置递增操作符，将迭代器移动到下一个元素。
it++：后置递增操作符，返回当前迭代器，然后将其移动到下一个元素。
it == other 和 it != other：比较两个迭代器是否指向同一位置。
每种容器都定义了特殊的函数，用于返回所需类型的迭代器，通常情况下使用begin函数获得顺序迭代器类型。
另外，还有const_interator类型，表示只读。
注意删除时：
#include <iostream>
#include <string>
#include <array>
#include <vector>
#include <list>
#include <deque>
#include <map> // 头文件
using namespace std;
int main()
{
string str = "ABJFG";
for(string::const_iterator iter = str.begin();iter != str.end();iter++)
cout << *iter << " ";
cout << endl;
array<string,5> arr = {"fdsf","fdf","sd","tr","xx"};
for(array<string,5>::const_iterator iter = arr.begin();iter != arr.end();iter++)
cout << *iter << " ";
cout << endl;
vector<string> vec(6,"哈哈哈");
vector<string>::const_iterator iter = vec.begin();
while(iter != vec.end())
{
cout << *iter << " ";
iter++;
}
cout << endl;
list<string> lis(6,"呵呵呵");
for(list<string>::iterator iter = lis.begin();iter != lis.end();iter++)
cout << *iter << " ";
cout << endl;
deque<double> deq(5);
for(deque<double>::iterator iter = deq.begin();iter != deq.end();iter++)
cout << *iter << " ";
cout << endl;
map<string,int> map1;
for(map<string,int>::iterator iter = map1.begin();iter!=map1.end();iter++)
{
cout << iter->first << " " << iter->second << endl;
}
return 0;
}
练习
写一个函数show_array，要求传入两个参数 void show_array(T t,int len)
第一个参数为数组默认值，第二个参数为数组的长度
此函数的功能为创建一个长度为len类型为T，默认值为t的数组并输出
#include <iostream>
#include <array> // 头文件
#include <vector>
using namespace std;
template <typename T>
void show_array(T t,int len)
{
vector<T> vec(len,t);
vector<T>::const_iterator iter = vec.begin();
// typename vector<T>::const_iterator iter = vec.begin();
while(iter != vec.end())
{
cout << *iter << " ";
iter++;
}
cout << endl;
}
int main()
{
show_array(5, 3); // 输出: 5 5 5
show_array('A', 4); // 输出: A A A A
show_array(3.14, 2); // 输出: 3.14 3.14
return 0;
}