STL

vector, 变长数组，倍增的思想

1
2
3
4
5
6
7
8

size() 返回元素个数
empty() 返回是否为空
clear() 清空
front()/back() 返回第一个数/最后一个数
push_back() / pop_back() 向vector插入一个数/ 把vector的最后一个数删掉
begin() / end() begin是vector的第一个数，end()是vector的最后一个数的后一个
[] 随机存取
支持比较运算，按字典序

pair<int, int> , 存储一个二元组

1
2
3
4
5

first , 第一个元素
second , 第二个元素
支持比较运算，按字典序，以first为第一关键字，以second为第二关键字
make_pair(k， v) 构建一个字典序
pair<int, pair<int, int>> p 存储三个属性

string，字符串，

1
2
3
4
5
6

size()/ length() 返回字符串长度
empty() 返回是否为空
clear() 把字符串清空
`+` 字符串拼接
substr(begin_index, len) 返回下标从begin_index, 长度为len的子串
c_str() 返回string数组的首地址，用于%s格式的输出

queue, 队列，

1
2
3
4
5
6
7

size() 返回队列长度
empty() 返回队列是否为空
push() 向队尾插入一个元素
front() 返回对头元素
back() 返回队尾元素
pop() 弹出对头元素
q = queue<int> (); 清空q队列，无clear()函数

priority_queue ,优先队列（堆），默认是大根堆

1
2
3
4
5
6

empty()
size()
push() 向堆中插入元素
top（）返回堆顶元素
pop() 弹出堆顶元素
priority_queue<int, vector<int>, greeter<int>> heap; 定义小根堆

stack，栈

1
2
3
4
5

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

deque，双端队列(加强版的vector)， 效率比较低

1
2
3
4
5
6
7
8
9

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

size() 
empty()
clear()
begin()/end(), ++, -- 返回前驱和后继 O(logn)

set/ multiset 
    insert() 支持插入一个数
    find() 查找一个数
    count() 返回某一个数的个数
    erase()
        (1) 输入是一个数x，删除所有x	O(K + logn)
        (2) 输入一个迭代器，删除这个迭代器
    lower_bound()/ upper_bound()
    lower_bound(x) 返回大于等于x的最小数的迭代器
    upper_bound(x) 返回大于x的最小的迭代器		
map/multimap
    insert() 插入的数是一个pair
    erase() 输入的参数是pair或者迭代器
    find() 
    [] 时间复杂去O(logn)
    lower_bound()/ upper_bound()

unordered_set, unorderd_map, unordered_multiset, unordered_multimap，基于哈希表实现

1
2

和上面类似，增删改查时间复杂度是O(1)
不支持lower_bound()/ upper_bound()，不支持迭代器的++，--

bitset，压位

 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位取反

基本用法类似

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
	// vector<int> a;
	// vector<int> a(10);
	vector<int> a(10, 3); // 定义一个长度为10的vector，里面每个数的长度都是3
	int size = a.size(); // 返回的是verctor(和所有容器都包含)里面元素的个数
	bool b = a.empty(); // 返回verctor(和所有容器都包含)是否为空（true）
	
}