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左右】