常用STL

vector

变长数组（数组长度变化），倍增思想

初始化:

1
2
3

vector<int>a;//定义一个普通vector
vector<int>a(10);//定义一个长度为10的vector
vector<int>a(10,3);//定义一个长度为10，每个元素为3的vector

size():返回元素个数

empty()：返回是否为空

clear()：清空

front()/back():返回第一/最后一个数

push_back()/pop_back():在末尾插入/删除一个数

begin()/end():返回开头/结尾的迭代器

支持随机访问

支持比较运算，按字典序

pair

定义:

1

pair<int,int>//数据类型可换

first:第一个元素

second:第二个元素

支持比较运算，以first为第一关键字，second为第二关键字(字典序)

构造:

1
2

p=make_pair(a,b);
p={a,b};

string

字符串

size():返回元素个数

empty()：返回是否为空

clear()：清空

substr(pos,len):从下标$pos$开始复制长度为$len$的字符串，若$len$特别大或省略，则返回从$pos$开始的整个字符串

c_str():返回字符串存储的起始地址

queue

队列

size():返回元素个数

empty()：返回是否为空

push():向队尾插入一个元素

front():返回队头元素

back():返回队尾元素

pop():弹出队头元素

priority_queue

优先队列

push():插入一个元素

top():返回堆顶元素

pop():弹出堆顶元素

默认为大根堆(堆顶为最大值)

小根堆定义方法：

1. 插入元素$x$时插入$-x$
2. 定义小根堆：priority_queue<int,vector<int>,greater<int> >q

stack

栈

size():返回元素个数

empty()：返回是否为空

push():向栈顶插入一个元素

top():返回栈顶元素

pop():弹出栈顶元素

deque

双端队列

size():返回元素个数

empty()：返回是否为空

clear()：清空

front()/back():返回第一/最后一个数

push_front()/pop_front():在开头插入/删除一个数

push_back()/pop_back():在末尾插入/删除一个数

begin()/end():返回开头/结尾的迭代器

支持随机访问

set,multiset

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

size():返回元素个数

empty():返回是否为空

clear():清空

begin()/end():返回开头/结尾的迭代器

insert():插入一个数

find():查找一个数

count():返回一个数的个数

erase()

1. 输入是一个数$x$，删除所有的$x$
2. 输入一个迭代器，删除这个迭代器

lower_bound(x):返回大于等于$x$的最小的数的迭代器

upper_bound(x):返回大于$x$的最小的数的迭代器

区别：$set$不支持重复元素，$multiset$支持重复元素

map,multimap

size():返回元素个数

empty()：返回是否为空

clear()：清空

insert():插入一个$pair$

find():查找一个$pair$

erase()

1. 输入是一个$pair$,删除所有的$pair$
2. 输入一个迭代器，删除这个迭代器

支持像数组一样的操作[] (时间复杂度$O(logn)$)

支持$lower_bound/upper_bound$

unordered_set,unordered_map,unordered_multiset,unordered_multimap

基于哈希表

类似上面的操作（时间复杂度$O(1)$）

不支持$lower_bound/upper_bound$

bitset

压位

定义：bitset<10000>s

支持~,&,|,^,>>,<<,==,!=,[]

count():返回有多少个$1$

any():判断是否至少有一个$1$

none():判断是否全为$0$

set():把所有位变成$1$

set(k,v):把第$k$位变成$v$

reset():把所有位变成$0$

flip():取反，等价于$\sim$

flip(k):把第$k$位取反