C++STL常用总结
C++ 标准模板库（Standard Template Library，STL）是一套功能强大的 C++ 模板类和函数的集合，它提供了一系列通用的、可复用的算法和数据结构。下面简要介绍一些常用的模板类。
vector
vector 是一个序列容器，它允许用户在容器的末尾快速地添加或删除元素。与数组相比，vector 提供了更多的功能，如自动调整大小、随机访问等。使用vector需要包含头文件<vector>。
| 方法 | 含义 |
|---|---|
c.front() | 返回第一个数据O(1) |
c.back() | 返回数组中的最后一个数据O(1) |
c.pop_back() | 删除最后一个数据O(1) |
c.push_back(element) | 在尾部加一个数据O(1) |
c.size() | 返回实际数据个数（unsigned类型）O(1) |
c.clear() | 清除元素O(N)，N为元素个数 |
c.resize(n, v) | 改变数组大小为n, n个空间数值赋为v，如果没有默认赋值为0 |
c.insert(it, x) | 向任意迭代器it插入一个元素x ，O(N)，例：c.insert(c.begin() + 2,-1)，将-1插入c[2]的位置 |
c.erase(pos) | 删除迭代器pos位置的元素，并返回下一个元素的迭代器，如果pos是最后一个元素，返回end()迭代器 |
c.erase(first,last) | 删除[first,last)的所有元素，first和last都是迭代器，O(N) |
c.begin() | 返回首元素的迭代器O(1) |
c.end() | 返回最后一个元素的后一个位置的迭代器O(1) |
c.empty() | 判断是否为空，为空返回真，反之返回假O(1) |
stack
<stack> 实现了一个后进先出（LIFO，Last In First Out）的数据结构。这种数据结构非常适合于需要"最后添加的元素最先被移除"的场景。使用stack需要包含头文件<stack>。
| 方法 | 含义 |
|---|---|
s.push(e) | 元素e入栈O(1) |
s.pop() | 移除栈顶元素O(1) |
s.top() | 取得栈顶元素（但不删除）O(1) |
s.empty() | 检测栈内是否为空，空为真 O(1) |
s.size() | 返回栈内元素的个数O(1) |
queue
<queue> 提供了队列（Queue）数据结构的实现。队列是一种先进先出（FIFO, First In First Out）的数据结构，它允许在一端添加元素（称为队尾），并在另一端移除元素（称为队首）。使用queue需要包含头文件<queue>。
| 方法 | 含义 |
|---|---|
q.front() | 返回队首元素O(1) |
q.back() | 返回队尾元素O(1) |
q.push(element) | 尾部添加一个元素element进队O(1) |
q.pop() | 删除第一个元素，出队O(1) |
q.empty() | 判断是否为空，队列为空，返回true O(1) |
q.size() | 返回队列中元素个数，返回值类型unsigned int O(1) |
deque
<deque> 提供了双端队列（double-ended queue）的实现。双端队列是一种允许在两端进行插入和删除操作的线性数据结构。<deque> 是一个动态数组，它提供了快速的随机访问能力，同时允许在两端进行高效的插入和删除操作。这使得 <deque> 成为处理需要频繁插入和删除元素的场景的理想选择。使用 deque 需要包含头文件 <deque>。
| 方法 | 含义 |
|---|---|
dq.push_back(x)/dq.push_front(x) | 把x插入队尾/队首O(1) |
dq.back()/dq.front() | 返回队尾/队首元素O(1) |
dq.pop_back()/dq.pop_front() | 删除队尾/队首元素O(1) |
dq.erase(iterator it) | 删除双端队列中的某一个元素 |
dq.empty() | 判断dq是否空O(1) |
dq.size() | 返回dq中元素个数 O(1) |
dq.clear() | 清空deque |
priority_queue
<priority_queue> 用于实现优先队列。优先队列是一种特殊的队列，它允许我们快速访问队列中具有最高（或最低）优先级的元素。
在 C++ 中，priority_queue 默认是一个最大堆，这意味着队列的顶部元素总是具有最大的值。
priority_queue 是一个容器适配器，它提供了对底层容器的堆操作。它不提供迭代器，也不支持随机访问。使用priority_queue需要包含头文件<queue>。
| 方法 | 含义 |
|---|---|
q.top() | 访问队首元素O(1) |
q.push() | 入队O(logN) |
q.pop() | 堆顶（队首）元素出队 O(logN) |
q.empty() | 是否为空O(1) |
q.size() | 队列元素个数O(1) |
priority_queue<int> q1; // 默认大根堆, 即每次取出的元素是队列中的最大值
priority_queue<int, vector<int>, greater<int>> q2; // 小根堆, 每次取出的元素是队列中的最小值
参数解释：
- 第一个参数：就是优先队列中存储的数据类型
- 第二个参数：
vector<int>是用来承载底层数据结构堆的容器，若优先队列中存放的是double型数据，就要填vector<double>。同时也要改动第三个参数里面的对应类型。 - 第三个参数：
less<int>用于比较数据，返回较小的数据，相当于小于号。大根堆的实现就是若父节点比子节点小，就会把父节点换下去，得到的就是大根堆。同理，greater<int>相当于大于号，若父节点比子节点大，就会把父节点换下去，得到的就是小根堆。
如果是自定义的数据类型，如结构体，就要在结构体里重载小于号运算符。
struct node
{int x, y;bool operator < (const node &a) const {return x < a.x;//按x升序排列，x大的在堆顶}
};
set
C++ 标准库中的 <set> 是一个关联容器，它存储了一组唯一的元素，并按照升序进行排序。它是基于红黑树实现的，因此具有对数时间复杂度的查找、插入和删除性能。使用set需要包含头文件<set>。
<set> 容器中存储的元素类型必须满足以下条件：
- 元素类型必须可以比较大小。
- 元素类型必须可以被复制和赋值。
因此，在set里使用高级数据类型，例如结构体，需要重载结构体的运算符使得结构体之间可以比较大小。
| 方法 | 含义 |
|---|---|
s.begin() | 返回set容器的第一个元素的地址（迭代器）O(1) |
s.end() | 返回set容器的最后一个元素的下一个地址（迭代器）O(1) |
s.empty() | 判断set容器是否为空O(1) |
s.insert() | 插入一个元素 |
s.size() | 返回当前set容器中的元素个数O(1) |
s.clear() | 删除set容器中的所有的元素,返回unsigned int类型O(N) |
s.find(element) | 查找set中的某一元素，有则返回该元素对应的迭代器，无则返回结束迭代器 |
s.erase() | 删除指定值，可以是迭代器或具体值 |
s.lower_bound(k) | 返回大于等于k的第一个元素的迭代器O(logN) |
s.upper_bound(k) | 返回大于k的第一个元素的迭代器O(logN) |
unordered_set
<unordered_set> 提供了一种基于哈希表的容器，用于存储唯一的元素集合。与 set 不同，unordered_set 不保证元素的排序，但通常提供更快的查找、插入和删除操作。使用unordered_set需要包含头文件<unordered_set>。
使用方法与set类似。
pair
pair只含有两个元素，可以看作是只有两个元素的结构体，通常作为map键值对进行插入。pair的第一个元素称为first，第二元素称为second，使用点运算符即可访问。使用pair需要包含头文件<utility>。
//初始化
pair<string, int> s;
pair<string, int> p("abc", 123);//赋值
s = {"abc", 123};
s = make_pair("zhangsan", 111); // make_pair函数用于创建一个pair对象//访问
string str = s.first;
int a = s.second;
map
<map> 是标准模板库（STL）的一部分，它提供了一种关联容器，用于存储键值对（key-value pairs），底层使用红黑树实现。map中每个键只能出现一次。map 容器中的元素是按照键的顺序自动排序的，通常是升序，这使得它非常适合需要快速查找和有序数据的场景。使用map需要包含头文件<map>。
基本语法：
//声明 map 容器
map<key_type, value_type> myMap;
//插入元素
myMap[key] = value;
//访问元素
value = myMap[key];
//遍历 map
for (map<key_type, value_type>::iterator it = myMap.begin(); it != myMap.end(); ++it) {cout << it->first << " => " << it->second << endl;
}
| 方法 | 含义 |
|---|---|
mp.find(key) | 返回键为key的映射的迭代器。当数据存在时，返回数据所在位置的迭代器，数据不存在时，返回mp.end() |
mp.erase(it) | 删除迭代器对应的键值对O(1) |
mp.erase(key) | 根据映射的键删除键和值O(logN) |
mp.size() | 返回映射的对数O(1) |
mp.clear() | 清空map中的所有元素O(N) |
mp.insert() | 插入元素，插入时要构造键值对 |
mp.empty() | 如果map为空，返回true，否则返回false |
mp.begin() | 返回指向map第一个元素的迭代器（地址） |
mp.end() | 返回指向map尾部的迭代器（最后一个元素的下一个地址） |
mp.lower_bound() | 返回一个迭代器，指向键值>= key的第一个元素 |
mp.upper_bound() | 返回一个迭代器，指向键值> key的第一个元素 |
unordered_map
与 map 不同，<unordered_map> 提供了一种基于哈希表的键值对容器。因此，它不保证元素的排序，但使得它在查找、插入和删除操作中具有平均常数时间复杂度。使用unordered_map需要包含头文件<unordered_map>。
使用方法与map类似。