参考自菜鸟教程，用于熟悉C++常用容器刷题应用
C++ STL
- STL核心组件：
- 容器（Containers）：向量（vector）、链表（list）、队列（queue）、栈（stack）、集合（set）、映射（map）等；
- 序列容器：存储元素的序列，允许双向遍历
- std::vector：动态数组，支持快速随机访问。
- std::deque：双端队列，支持快速插入和删除。
- std::list：链表，支持快速插入和删除，但不支持随机访问。
- 关联容器：存储键值对，每个元素都有一个键（key）和一个值（value），并且通过键来组织元素
- std::set：集合，不允许重复元素。
- std::multiset：多重集合，允许多个元素具有相同的键。
- std::map：映射，每个键映射到一个值。
- std::multimap：多重映射，允许多个键映射到相同的值。
- 无序容器（C++11 引入）：哈希表，支持快速的查找、插入和删除
- std::unordered_set：无序集合。
- std::unordered_multiset：无序多重集合。
- std::unordered_map：无序映射。
- std::unordered_multimap：无序多重映射。
- 序列容器：存储元素的序列，允许双向遍历
- 算法（Algorithms）：排序、搜索、复制、移动、变换等；
- 迭代器（iterators）：随机访问迭代器、双向迭代器、前向迭代器和输入输出迭代器等；
- 函数对象（Function Objects）：可以像函数一样调用的对象，可用于算法中的各种操作。包括一元函数对象、二元函数对象、谓词等。
- 适配器（Adapters）：用于将一种容器或迭代器适配成另一种容器或迭代器，以满足特定的需求，包括栈适配器（stack adapter）、队列适配器（queue adapter）和优先队列适配器（priority queue adapter）等。
- 容器（Containers）：向量（vector）、链表（list）、队列（queue）、栈（stack）、集合（set）、映射（map）等；
容器
<array>: 定长数组容器
- 基本语法：
std::array<T, N> array_name;
<vector>: 动态数组容器
- 声明：
std::vector<int> myVector;
- 访问元素：
int x = myVector[0]; // 获取第一个元素
int y = myVector.at(1); // 获取第二个元素
- 添加元素：
myVector.push_back(10);
- 删除元素：
myVector.pop_back()；// 删除末尾元素myVector.erase(myVector.begin() + 2); // 根据迭代器删除指定元素
- 迭代访问：
for (auto it = myVector.begin(); it != myVector.end(); ++it) {std::cout << *it << " ";
}
- 清空：
myVector.clear(); // 清空 vector
- 获取元素数量：
size_t size = myVector.size();
- 判断是否为空：
myVector.empty();
<deque>: 双端队列容器
- 声明：
std::deque<int> myDeque;
- 访问元素：
myDeque[i];myDeque.at(i)
- 返回第一个/最后一个元素的引用：
myDeque.front();myDeque.back();
- 返回指向第一个/最后一个元素后一位置的迭代器：
myDeque.begin();myDeque.end();
- 检查是否为空：
myDeque.empty();
- 获取元素个数：
myDeque.size();
- 添加元素：
myDeque.push_back(const T& value);// 队尾myDeque.push_front(const T& value);// 队头
- 移除元素：
myDeque.pop_back();// 队尾myDeque.pop_front();// 队头erase(iterator pos);// 移除 pos 位置的元素
- 清空：
myDeque.clear();
- 调整容器大小：
myDeque.resize(size_type count);
<list>: 双向链表容器
- 声明：
std::list<T> mylist;
- 插入：
mylist.push_back(value);
- 删除：
mylist.pop_back();mylist.erase(iterator);// 根据迭代器删除指定位置节点
- 访问：
mylist.front();mylist.back();
- 遍历：
for (auto it = mylist.begin(); it != mylist.end(); ++it){...
}
<forward_list>: 单向链表容器
std::forward_list是单向链表，只能从前往后遍历，不能反向遍历；- 声明：
std::forward_list<int> fl;
- 插入：
void push_front(const T& value);// 特别适合于需要在列表前端进行频繁插入和删除操作的场景
- 移除：
void pop_front();
- 返回迭代器：
iterator before_begin();// 返回指向列表前端之前的迭代器
iterator begin();// 返回指向列表前端的迭代器
iterator end();// 返回指向列表末尾的迭代器
<stack>: 栈容器适配器
<stack>容器适配器提供了一个栈的接口，它基于其他容器（如 deque 或 vector）来实现;- 基本操作：
std::stack<int> s;// 声明push();// 在栈顶添加一个元素。
pop();// 移除栈顶元素。
top();// 返回栈顶元素的引用，但不移除它。
empty();// 检查栈是否为空。
size();// 返回栈中元素的数量。
<queue>: 队列容器适配器
- 队列的实现通常使用链表或动态数组，这取决于具体的实现；
- 基本操作：
// 声明队列
std::queue<Type> q;empty();// 检查队列是否为空。
size();// 返回队列中的元素数量。
front();// 返回队首元素的引用。
back();// 返回队尾元素的引用。
push();// 在队尾添加一个元素。
pop();// 移除队首元素。
<priority_queue>: 优先队列容器适配器
- priority_queue 是一个容器适配器，优先队列是一种特殊的队列，它允许我们快速访问队列中具有最高（或最低）优先级的元素；
- priority_queue 默认是一个最大堆；
- 基本语法：
// 声明
priority_queue<int> pq;;empty();// 检查队列是否为空。
size();// 返回队列中的元素数量。
top();// 返回队列顶部的元素（不删除它）。
push();// 向队列添加一个元素。
pop();// 移除队列顶部的元素。
- 自定义优先队列排序规则：
// 声明一个自定义类型的优先队列，需要提供比较函数
struct compare {bool operator()(int a, int b) {return a > b; // 这里定义了最小堆}
};
priority_queue<int, vector<int>, compare> pq_min;
- note：优先级队列的排序规则和其他排序规则如查找函数、set、map不同
- 正常返回a>b指定为降序，而优先级队列会指定为升序；
- 通常默认优先级队列为降序，而set、map默认为升序。
<set>: 集合容器（基于平衡二叉树）
- 基于红黑树实现，特别适合需要快速查找、插入和删除操作的场景。
- 基本语法：
// 声明一个整型 set 容器
std::set<int> mySet;insert(元素);// 插入一个元素。
erase(元素);// 删除一个元素。
find(元素);// 查找一个元素——返回迭代器，如果未找到返回 mySet.end()。
size();// 返回容器中元素的数量。
empty();// 检查容器是否为空。
<unordered_set>: 无序集合容器（基于哈希表）
- unordered_set 不保证元素的排序，但通常提供更快的查找、插入和删除操作；
- 基本语法：
// 声明
std::unordered_set<int> uset;insert(元素);// 插入一个元素。
erase(元素);// 删除一个元素。
find(元素);// 查找一个元素——返回迭代器，如果未找到返回 uset.end()。
size();// 返回容器中元素的数量。
empty();// 检查容器是否为空。
clear();// 清空。
<map>: 映射容器（键值对，基于平衡二叉树）
- map用于存储键值对，单个元素可以看作为一个pair，一个map包含多个数对pair，因此for each遍历可以用pair取map的每个元素；
- map 中的元素按照键的顺序自动排序，通常是升序；
- 基本语法：
// 声明
std::map<key_type, value_type> myMap;// 插入元素
myMap[key] = value;// 访问元素
value = myMap[key];// 遍历map
for (std::map<key_type, value_type>::iterator it = myMap.begin(); it != myMap.end(); ++it) {std::cout << it->first << " => " << it->second << std::endl;
}// 检查键是否存在
if (myMap.find(key) != myMap.end()) {// 键存在
}// 删除元素
myMap.erase(key);// 清空map
myMap.clear();// 获取map大小
size_t size = myMap.size();
<unordered_map>: 无序映射容器（基于哈希表）
- 基本语法：
// 声明
std::unordered_map<int, std::string> myMap;// 插入元素
myMap[key] = value;
myMap.insert({key, value});// 访问元素
value = myMap[key];// 遍历map
for (std::map<key_type, value_type>::iterator it = myMap.begin(); it != myMap.end(); ++it) {std::cout << it->first << " => " << it->second << std::endl;
}
for (const auto& pair : myMap) {std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
}// 检查键是否存在
if (myMap.find(key) != myMap.end()) {// 键存在
}// 删除元素
myMap.erase(key);
<bitset>: 二进制位容器
算法和迭代器
<algorithm>: 常用算法（如排序、查找等）
- 基本语法：
algorithm_name(container.begin(), container.end(), ...);
排序
- 基本语法：
sort(container.begin(), container.end(), compare_function);
- 其中 compare_function 是一个可选的比较函数，用于自定义排序方式
搜索
- 基本语法：
auto it = find(container.begin(), container.end(), value);
复制
- 基本语法：
copy(source_begin, source_end, destination_begin);
比较
- 基本语法：
bool result = equal(first1, last1, first2);// 或bool result = equal(first1, last1, first2, compare_function);
<iterator>: 迭代器
- 迭代器是一个对象，它提供了一种方法来遍历容器中的元素。迭代器可以被视为指向容器中元素的指针，但它比指针更加灵活和强大。迭代器可以用于访问、修改容器中的元素，并且可以与 STL 算法一起使用。
- 分类：
- 输入迭代器（Input Iterator）：只能进行单次读取操作，不能进行写入操作。
- 输出迭代器（Output Iterator）：只能进行单次写入操作，不能进行读取操作。
- 正向迭代器（Forward Iterator）：可以进行读取和写入操作，并且可以向前移动。
- 双向迭代器（Bidirectional Iterator）：除了可以进行正向迭代器的所有操作外，还可以向后移动。
- 随机访问迭代器（Random Access Iterator）：除了可以进行双向迭代器的所有操作外，还可以进行随机访问，例如通过下标访问元素。
- 常用语法：
// 使用迭代器遍历容器
for (ContainerType::iterator it = container.begin(); it != container.end(); ++it) {// 访问元素 *it
}
函数对象和绑定
<functional>: 定义函数对象及相关工具
- 函数对象是那些重载了 operator() 的对象，它们可以像普通函数一样被调用;
- 常用的函数对象:
- std::function：一个通用的多态函数封装器。
- std::bind：用于绑定函数的参数。
- std::plus、std::minus、std::multiplies、std::divides、std::modulus：基本的算术操作。
- std::equal_to、std::not_equal_to、std::greater、std::less、std::greater_equal、std::less_equal：比较操作。
- std::unary_negate、std::binary_negate：逻辑否定操作。
- std::logical_and、std::logical_or、std::logical_not：逻辑操作。
字符串和正则表达式
<string>: 标准字符串类
- 常用语法：
// 声明
std::string str;// 使用 + 连接字符串
std::string result = str1 + str2;// 常用成员函数
size();// 返回字符串的长度。empty();// 检查字符串是否为空。operator[];// 通过索引访问字符串中的字符。
at();// 访问字符串中指定位置的字符（带边界检查）substr();// 获取子字符串。
std::string sub = str.substr(0, 5);find();// 查找子字符串在主字符串中的位置。replace();// 替换字符串中的某些字符。
str.replace(pos, length, "new_substring");append();// 在字符串末尾添加内容
str.append(" more");insert();// 在指定位置插入内容。
str.insert(pos, "inserted");erase();// 删除指定位置的字符或子字符串。
str.erase(pos, length);clear();// 清空字符串。
str.clear();
<regex>: 正则表达式
- 正则表达式的基本组成
- 字符类：如 [abc] 表示匹配 a、b 或 c 中的任意一个字符。
- 量词：如 *（零次或多次）、+（一次或多次）、?（零次或一次）。
- 边界匹配：如 ^（行的开始）、$（行的结束）。
- 分组：使用圆括号 () 来创建一个分组。
