C++标准模板库STL

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

vector 常见用法

特点

动态数组

定义 vector

1
vector<type> name;

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

1
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 方法:

1
2
3
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

1
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

1
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 为例

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

其中多出来的两个参数:

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

结构体

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

1
2
3
4
5
6
7
struct struct_name {
string name;
int value;
friend bool operator < (struct_name& s1, struct_name& s2) {
return f1.value < f2.value;
}
}

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

1
priority_queue<struct_name> name;

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

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

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

1
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

1
pair<type1, type2> name;

元素访问

通过 name.firstname.second 访问

常用函数

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

常见用途

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

algorithm 常用函数

max()、min() 和 abs()

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

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

swap()

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

reverse()

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

next_permutation()

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

fill()

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

sort()

sort 的使用方法为:

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

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

1
2
3
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))


C++标准模板库STL
https://infiniture.cn/2019/09/30/C++标准模板库STL/
作者
NickHopps
发布于
2019年9月30日
许可协议