STL常用组件

前言

该篇博客旨在忘记STL用法时查询

---

正文

pair

二元组，可以组合任意两个不同类型（或相同类型）的元素。

#include<utility>

成员变量

变量名	内容
first	第一个值
second	第二个值

---

stack

栈。只允许在栈顶进行插入和删除操作。

#include<stack>

定义与初始化

std::stack<int> s;
// s = {}

成员函数

函数名	功能
top()	返回栈顶元素
empty()	返回是否为空
size()	返回元素个数
push(value)	在栈顶插入 value
pop()	删除栈顶元素

---

queue

队列。只允许在队尾插入元素，在队头删除元素

#include<queue>

定义与初始化

std::queue<int> q;
// q = {}

成员函数

函数名	功能
front()	返回队头元素
back()	返回队尾元素
empty()	返回是否为空
size()	返回元素个数
push(value)	在队尾插入元素 value
pop()	删除队头元素

---

priority_queue

优先队列。会自动排序，但其内部元素不可见，只允许访问最大的元素。

#include<queue>

定义和初始化

std::priority_queue<int> pq

priority_queue默认为大根堆（只允许访问最大的元素）。以下是小根堆的写法：

#include<vector>
std::priority_queue<int, std::vector<int>, std::greater<int>> pq

成员函数

函数名	功能
top()	返回最大的元素
empty()	返回是否为空
size()	返回元素个数
push(value)	往堆中插入 value
pop()	删除最大的元素

---

vector

动态数组。能根据需要自动扩容，也能手动调整容量。

#include<vector>

定义与初始化

using namespace std;
vector<int> v1;
// v = {}

vector<int> v2(n + 5);

vector<vector<int>> v3(n + 5, vector<int>(n + 5));

成员函数

函数名	功能
at(pos)	返回第 pos 个元素
operater [pos]	返回第 pos 个元素
assign(count, value)	初始化为 count 个 value
front()	返回第一个元素
back()	返回最后一个元素
begin()	返回头部迭代器
end()	返回尾部迭代器
empty()	返回是否为空
size()	返回元素个数
clear()	清空
push_back(value)	在尾部插入 value
pop_back()	删除尾部元素
resize(count)	将容量调整为 count

STL中的 begin() 均指向头部元素； end() 指向尾部元素的后继，而非尾部元素。

实例

以下是遍历 vector a，并输出所有元素的三种方式

for(int i = 0;i < a.size();i ++)
    cout << a[i] << " ";
for(vector<int>::iterator it = a.begin();it != a.end();it ++)
    cout << a[i] << " ";
for(int v : a[n])
    cout << a[i] << " ";

用vector代替邻接表保存有向图

const int MAX_EDGES = 100010;
vector<int> ver[MAX_EDGES], edge[MAX_EDGES];

//保存从 u 到 v 权值为 val 的有向边
void add(int u, int v, int val) {
    ver[u].push_back(v);
    edge[u].push_back(val);
}
//遍历从 x 出发的所有边
for(int i = 0;i < ver[u].size();i ++){
    int v = ver[u][i], val = edge[u][i];
    //有向边 (u, v, val)
}

---

map

映射。相当于 [] 内可填任意键值（可以是 int , double 等任意类型的对象）的数组

#incldue<map>

定义和初始化

std::map<int, int> m1;

std::map<char, int> m2 = { {'a', 3}, {'b', 2}, {'c', 1} };
m2 = { {'a', 3}, {'b', 2}, {'c', 1} }

成员函数

函数名	功能
at(key)	返回 key 映射的元素
operator[key]	返回 key 映射的元素，若没有则创造键
begin()	返回头部迭代器
end()	返回尾部迭代器
empty()	返回是否为空
size()	返回元素个数
clear()	清空
count(key)	返回 key 映射的元素的个数
insert({key, value})	创建从 key 到 value 的映射
erase(key)	删除从 key 出发的映射

---

set

集合。插入其中的每种元素都只保留其一，并自动升序排序。

STL 提供 multiset (多重集)，相同的元素允许存在多个，其他功能与 set 一致

#include<set> 

定义和初始化

std::set<int> s1;
//s1 = {}

std::set<int> s2 = {'a', 'p', 'p', 'l', 'e'};
//s2 = {'a', 'e', 'l', 'p'}

成员函数

函数名	功能
begin()	返回头部迭代器
end()	返回尾部迭代器
empty()	返回是否为空
size()	返回元素个数
clear()	清空
insert(value)	插入 value
pop(value)	删除 value
count(value)	返回 value 的个数

---

后记

由于C++容器库包含的容器太多，在此处不一一赘述，更详细的教程请在此处查找。
后续还会补充一些常用容器。