C++标准模板库STL

由于在算法题中常用 C 或者 C++ 来作为解题语言，而 STL 又提供了现成好用的工具，因此本篇文章的目的就是简要地介绍 STL 里面常用的各种数据结构以及工具。

vector 常见用法

特点

动态数组

定义 vector

vector<type> name;

如果 type 也是一个 STL 容器，定义时需要注意“>>”之间要加空格：

vector<vector<int> > name;

元素访问

1. 通过下标直接访问: v[index]
2. 通过迭代器访问：vector<type>::iterator it

常用函数

1. push_back(x)：元素后新增一个元素，复杂度为O(1)
2. pop_back(x)：删除容器的尾元素，复杂度为O(1)
3. size()：获得容器中的元素个数，复杂度为O(1)
4. clear()：清空容器中所有元素，复杂度为O(N)
5. insert(it, x)：在容器任意迭代器处插入元素，复杂度为O(N)
6. erase(it)[erase(it1, it2)]：删除容器中单个元素或者某一范围中的元素，复杂度为O(N)

set 常见用法

特点

1. 内部自动有序
2. 不含重复元素

定义 set

和 vector 类似

元素访问

set 只能通过迭代器访问，遍历 set 方法：

for (set<type>::iterator it = st.begin(); it != st.end(); ++it) {
  ...
}

常用函数

1. insert(x)：插入容器并自动递增排序和去重，复杂度为O(logN)
2. find(val)：返回容器中对应值为 val 的迭代器，复杂度为O(logN)
3. erase(it[val])[erase(it1, it2)]：删除容器中元素，删除单个元素复杂度为O(1)或者O(logN)，删除多个元素复杂度为O(it1\sim it2)
4. size()：获得容器中元素的个数，复杂度为O(1)
5. clear()：清空容器中的元素，复杂度为O(N)

string 常见用法

定义 string

string s = "xxx";

元素访问

1. 通过下标
2. 通过迭代器：string::iterator it

常用函数

1. +=：可以将两个 string 拼接起来
2. ==/!=/>/<...：通过字典序比较两个 string 的大小
3. length()/size()：返回 string 的长度，复杂度为O(1)
4. insert(n, string)[insert(it, it1, it2)]：将 string 插入 n 位置，或将另一 string 的 it1 到 it2 插入到当前 string 的 it 处，复杂度为O(N)
5. erase(it)[erase(it1, it2)][erase(n, length)]：删除容器中元素，复杂度为O(N)
6. clear()：清空容器中的元素，复杂度为O(1)
7. substr(n, len)：返回从 n 开始，长度为 len 的子串，复杂度为O(len)
8. string::npos：find 函数失配时的返回值
9. find(str)[find(str, n)]：从头或从 n 处开始匹配 str，复杂度为O(nm)，其中 n 为主串的长度，m 为 str 的长度
10. replace(n, len, str)[replace(it1, it2, str)]：将主串某一范围内的子串替换为 str，复杂度为O(L)，L 为主串的长度

map 常见用法

特点

1. 提供多类型键值对映射

定义 map

map<type1, type2> name;

元素访问

1. 通过下标
2. 通过迭代器：map<type1, type2>::iterator it，其中 it->first 是键，it->second 是值

常用函数

1. find(key)：返回键为 key 的映射的迭代器，复杂度为O(logN)
2. erase(it)[erase(key)][erase(it1, it2)]：删除元素，删除单个元素，迭代器复杂度为O(1)，通过键删除复杂度为O(logN)，删除所有元素复杂度为O(it1\sim it2)
3. size()：获得映射的对数，复杂度为O(1)
4. clear()：清空容器中所有元素，复杂度为O(1)

queue 常见用法

定义 queue

和上述容器类似

元素访问

1. 通过 front() 访问队首
2. 通过 back() 访问队尾

常用函数

1. push(x)/pop(x)：入队出队，复杂度都为O(1)
2. front()/back()：获得队首、队尾元素，复杂度都为O(1)
3. empty()：判断队列是否为空，复杂度为O(1)
4. size()：返回队列中元素个数，复杂度为O(1)

priority_queue 常见用法

特点

1. 底层用堆实现
2. 队首元素一定是当前队列中优先级最高的

定义 priority_queue

和上述容器类似

元素访问

只能通过 top() 访问队首元素

常用函数

1. push(x)/pop(x)：入队出队，复杂度都为O(logN)
2. top()：获得队首元素，复杂度为O(1)
3. empty()：判断队列是否为空，复杂度为O(1)
4. size()：返回队列中元素个数，复杂度为O(1)

元素优先级设置

基本数据类型

以 int 为例

priority_queue<int, vector<int>, less<int> > name;

其中多出来的两个参数：

• vector<int>：承载底层数据结构堆的容器
• less<int>：对第一个参数的比较类，less 表示数字大的优先级大，greater 表示数字小的优先级大

结构体

首先在结构体中重载运算符（使用 & 引用提高效率）

struct struct_name {
  string name;
  int value;
  friend bool operator < (struct_name& s1, struct_name& s2) {
    return f1.value < f2.value;
  }
}

接着直接定义 struct_name 类型的优先队列

priority_queue<struct_name> name;

或者可以把重载函数写在结构体外面

struct cmp {
  bool operator () (struct_name& s1, struct_name& s2) {
    return f1.value < f2.value;
  }
}

这时定义优先队列的方法为

priority_queue<int, vector<int>, cmp > name;

stack 常见用法

定义 stack

和上述容器类似

元素访问

只能通过 top() 访问栈顶元素

常用函数

1. push(x)/pop(x)：入栈出栈，复杂度都为O(1)
2. top()：获得栈顶元素，复杂度为O(1)
3. empty()：判断队列是否为空，复杂度为O(1)
4. size()：返回队列中元素个数，复杂度为O(1)

pair 常见用法

特点

方便地绑定两个元素

定义 pair

pair<type1, type2> name;

元素访问

通过 name.first 和 name.second 访问

常用函数

1. ==/!=/>/<...：比较，先比较 first，当 first 相等时再比较 second

常见用途

1. 用来替代二元结构体，节省时间
2. 作为 map 的键值对进行插入

algorithm 常用函数

max()、min() 和 abs()

max(x, y)/min(x, y) 用来返回 x 和 y 中的最大值/最小值，abs(x) 返回 x 的绝对值，如果需要返回三个数的最大值，可使用

max(x, max(y, z));

swap()

swap(x, y) 用来交换 x 和 y 的值

reverse()

reverse(it1, it2) 将 it1 到 it2 之间的元素反转，it 可以是数组指针或者容器的迭代器

next_permutation()

用来给出一个序列在全排列中的下一个序列

fill()

用来把数组或容器中的某一段区间赋为某个相同的值

sort()

sort 的使用方法为：

sort(首元素地址, 尾元素的下一个地址， [比较函数])

不填写比较函数时，默认进行递增排序，而比较函数的构造方法为：

bool cmp(type a, type b) {
  return a > b;
}

lower_bound() 和 upper_bound()

二者需要用在有序数组或者容器中，其中

1. lower_bound(it1, it2, val) 用来寻找在数组或者容器中 [it1, it2) 范围内第一个大于或等于 val 的元素的位置
2. upper_bound(it1, it2, val) 用来寻找在数组或者容器中 [it1, it2) 范围内第一个大于 val 的元素的位置

它们的复杂度均为 O(log(it1 - it2))