C++ 常用STL及用法 - 速查文档

具体使用方法，先用现查即可！！！

相关文档推荐，

【文档：C++语法基础 第8讲 常用STL】

【文档：从c语言到c++（stl容器/stl函数总结）】

stirng 字符串

1
2
3
4
5
6
size()/length()  返回字符串长度
empty() 返回bool类型
clear()
    
substr(起始下标，(子串长度))  返回子串
c_str()  返回字符串所在字符数组的起始地址

vector 变长数组

倍增的思想

特点：系统为某一程序分配空间时，所需时间与空间大小无关，只与申请的次数有关。

1
2
3
4
5
6
7
8
9
10
11
12
size()  返回元素个数
empty()  返回是否为空
clear()   将清空

front()/back() // back()是返回最后一个元素
push_back()/pop_back() // 元素的增删，在末尾进行
begin()/end() 迭代器
[] // 支持随机寻址
    
reverse(res.begin(), res.end()); // 数组元素翻转

支持比较运算，按字典序

代码示例，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
std::vector<int> a(10, 3); // 数组初始化，指定元素个数及值

for(auto x : a) {
    std::cout << x << ' '; // 10个3
}
std::cout << std::endl;

for(int i = 0; i < a.size(); i++) { // vector的另外两种遍历方式
    std::cout << a[i] << ' ';
}
std::cout << std::endl;

for(std::vector<int>::iterator i = a.begin(); i != a.end(); i++) {
    std::cout << *i << ' ';
}
std::cout << std::endl;

pair<int, int> 二元组

类似结构体

1
2
3
4
first, 第一个元素
second, 第二个元素

支持比较运算，以first为第一关键字，以second为第二关键字（字典序）（帮我们实现了排序）

queue, 队列

(没有清空函数)

1
2
3
4
5
6
size()
empty()
push()  向队尾插入一个元素
front()  返回队头元素
back()  返回队尾元素
pop()  弹出队头元素

priority_queue, 优先队列

默认是大根堆(用堆；来实现的)

1
2
3
4
5
6
7
8
9
10
#include <queue> // 引入头文件
priority_queue<int> pq; // 默认是大根堆
size()
empty()
push()  插入一个元素
top()  返回堆顶元素
pop()  弹出堆顶元素
    
定义成小根堆的方式：
priority_queue<int, vector<int>, greater<int>> q;

stack, 栈

(优先队列跟栈类似)

1
2
3
4
5
size()
empty()
push()  向栈顶插入一个元素
top()  返回栈顶元素
pop()  弹出栈顶元素

deque, 双端队列

(加强版的vector)，但效率较低

头尾都可以插入或删除

1
2
3
4
5
6
7
8
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[] // 支持随机访问

set, map, multiset, multimap 哈希表

基于平衡二叉树（红黑树实现），动态维护有序序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
size()
empty()
clear()
begin()/end()
++, -- 返回前驱和后继，时间复杂度 O(logn)
````

----

### `set/multiset`

 区别：set不能有重复元素

```c++
insert()  插入一个数
find()  查找一个数
count()  返回某一个数的个数
    
erase() 
两种参数：
(1) 输入是一个数x，删除所有x   O(k + logn)， k是x的个数
(2) 输入一个迭代器，删除这个迭代器

lower_bound()/upper_bound()

1
2
lower_bound(x)  返回大于等于x的最小的数的迭代器  // 一般升序使用
upper_bound(x)  返回大于x的最小的数的迭代器

map/multimap

1
2
3
4
5
insert()  插入的数是一个pair,两个数
erase()  输入的参数是pair或者迭代器
find()
[]  注意multimap不支持此操作。 时间复杂度是 O(logn)
lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表

好处：和上面类似，增删改查的时间复杂度是 O(1)

区别：不支持 lower_bound()/upper_bound() 的排序操作， 迭代器的++，–

bitset, 圧位

（位存储，状态压缩），可以省存储空间（省8位空间，节省1/8存储）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bitset<10000> s;
~, &, |, ^
>>, <<
==, !=
[] // 取出来每一位

count()  返回有多少个1

any()  判断是否至少有一个1
none()  判断是否全为0

set()  把所有位置成1
set(k, v)  将第k位变成v
reset()  把所有位变成0
    
flip()  等价于~
flip(k) 把第k位取反

参考资料

【文档：C++语法基础 第8讲 常用STL】

【文档：从c语言到c++（stl容器/stl函数总结）】

【视频：1.8 STL、位运算、常用库函数 - 49min左右】

【视频：第二章 数据结构（三）常用STL 1h10min左右】