STL

vector 变长数组

倍增思想

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

因此vector的扩容是通过每次开辟一个长度为原数组两倍的数组，再将原数组内容拷贝到新数组。

vector支持比较运算，按字典序比较。

Pair

常用于储存一个事物的两种属性，比二元组结构体更方便

String

substr、c_str

Queue

queue没有clear函数，那如何实现清空？

queue<int> q;
q = queue<int>();

Priority_queue

priority_queue<int> p; // 默认大根堆
priority_queue<int, vector<int>, greater<int>> h // 小根堆

Stack

Deque

deque效率较低

Set、Multiset

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

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

Bitset

可以省八位空间，每一位表示一个布尔变量。

bitset<10000> s;

支持位运算、==、!=、[ ]

count( ) 返回有多少个1

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

none( ) 判断是否全为0

set( ) 所有位置成1

set(k, v) 将第k位变成v

reset( ) 所有位变成0

flip( ) 每一位翻转

flip(k) 翻转第k位