c++STL

<vector>

可变长数组，倍增思想，支持随机访问，不支持任意位置O(1)插入

vector<int> a;
vector<int> b[233]; //第一维长233，第二维动态变化
struct rec{};
vector<rec> c;//自定义结构体

size/empty，clear，push_back/pop_back

begin/end，容器[)，end返回第n个元素再往后的边界

front/back，front = *a.bsgin()/a[0]；back = *–a.end()/a[size() - 1]

迭代器：指针

vector<int> ::iterator it;//保存int的迭代器

<queue>

循环队列<queue>

O(1)，push，pop，front，back

优先队列<priority_queue>

较大元素在堆顶

方法	复杂度
push	O(logn)
pop	O(logn)
top	O(1)

重载“<”运算符

用于使用自定义的结构体类型

懒惰删除法

先给要删除的数打一个标记，等它到堆顶的时候，删除

双端队列 <deque>

支持随机访问

方法	复杂度
front/back	O(1)
push_back	O(1)
push_front	O(1)
pop_front	O(1)
pop_back	O(1)
clear	O(n)

头文件<set>

set 有序集合

元素不重复

multiset 有序多重集

元素可重复

set<int> s;
struct rec{...};
set rec s;//必须定义“小于号”运算符
multiset<double> s;

双向迭代器：O(logn)，++指向下一名元素，不支持随机访问，支持*的解除引用

insert:O(logn)

find(x):找到x元素，返回指向该元素的迭代器，不存在就返回s.end()

lower_bound/upper_bound:O(logn)，查找>=x元素中最小/最大的一个

erase:

• 迭代器：删除该迭代器指向的元素O(logn)
• 元素：删除所有相同的元素O(logn+k)

count

<map>

key-value，以key为关键字的红黑树，key定义“小于号”运算符

map<key_type,vlue_type> name;

迭代器：双向访问迭代器

set/empty/clear/begin/end

insert/erase :

pair<key_type,vlue_type>//insert

map<int,int> h;
h.insert(meak_pair<1,2>),h.insert(meak_pair<2,3>);
map<int,int>::iterator it = h.begin();
pair<int,int> p = * it;
h.erase(it),h.erase(meak_pair(2,3));
cout << p.first << ' ' << p.second << endl;

[]操作符：O(logn) h[key],返回key映射的value的引用，可进行赋值操作。若查找的value不存在，则创建一个(ket,zero)。可以先用find查询key的存在性。

zero:广义0值

<bitset>

多位二进制数，8位一字节

bitset<10000> s;//1000位二进制数

~s：返回对bitsset s按位取反的结果

&,|,^：位数相同的bitset按位与，或，以或运算

>>,<<：右移/左移

==,!=：比较相等

s[k]：s的第k位，最低位为s[0]

count：返回有多少位为1

any/none：s所有位为0，s.none()=true;否则s.any()=true

set/reset/flip：

• s.set() 所有位置1
• s.set(k,v) s[k] = v
• s.reset(k) 第k位置0
• s.flip(k) 第k位取反

<algorithm>

用于序列

reverse 翻转

reberse(a.begin(),a.end());//也可放数组下标

unique 去重

返回去重之后末尾元素的下一个位置，用于离散化，指针加减计算去重后的个数

int m = unique(a.begin(),a.end()) - a.begin();

random_shuffle 随机打乱

用法同revsrse

next_permutation 下一个排列

两个指针的区域为一个排列，求这些元素构成的全排列中字典序排在下一个的序列，若不存在，返回false。prev_permutation同理。

sort 快排

sort(a+1,a+n+1,cmp);

lower_bound/upper_bound 二分

lower_bound返回指向>=x的元素位置的迭代器；

upper_bound返回指向=x的元素位置的迭代器。

两指针指定的部分应该是提前排序好的