STL容器

  1. 常数巨大(without O2)
  2. 动态内存,unfriendly for cena


queue/stack/priority_queue

1
2
3
头文件:<queue/stack>
定义:queue<data> x;
小根堆:priority_queue<int,vector<int>,greater<int> >q;

操作

1
2
3
x.push(key) x.pop(key)
x.front() x.top()
x.size() x.empty()


pair

1
2
头文件:<iostream>
定义:pair<data,data> x;

操作

1
2
3
.first .second//访问
make_pair(x,y)//构造
重载了<,以first为第一关键字,second为第二关键字升序


set/multiset/hash_set/unordered_set

1
2
3
头文件:<set/unordered_set>//unordered_set was defined in C++11
定义:set<data> x;
迭代器:set<data>::iterator it;

操作

1
2
3
4
5
6
7
8
9
10
11
x.clear()
x.insert(key)//插入一个值key
x.erase(key)//删除键值为key的元素(multiset会全部删除)
x.erase(it)//删除迭代器为it的元素
x.erase(l,r)//删除地址[l,r)的元素,l,r为两个迭代器指针
x.begin() x.end()
x.size() x.empty()
x.find(key)//返回key的迭代器指针
x.count(key)//返回键值等于key的元素的个数(multiset中使用)
x.lower_bound(key)
x.upper_bound(key)


map/multimap/hash_map/unordered_map

1
2
3
头文件:<map/unordered_map>//unordered_map was defined in C++11
定义:map<data> x;
迭代器:map<data>::iterator it;

操作

1
2
3
4
5
6
7
8
9
10
11
12
13
x.clear()
mp[x]=key//插入元素
it->first it->second//迭代器访问
x.erase(key)//删除键值为key的元素(multimap会全部删除)
x.erase(it)//删除迭代器为it的元素
x.erase(l,r)//删除地址[l,r)的元素,l,r为两个迭代器指针
x.swap(x2)//交换x,x2
x.begin() x.end()
x.size() x.empty()
x.find(key)//返回key的迭代器指针
x.count(key)//返回键值等于key的元素的个数(multimap中使用)
x.lower_bound(key)
x.upper_bound(key)

应用

树套树(雾


vector

1
2
3
头文件:<vector>
定义:vector<data> x;
迭代器:vector<data>::iterator it;

操作

1
2
3
4
5
6
7
8
9
10
11
x.clear()
x.push_back(key)
x.insert(pos,key)//在迭代器指针pos处插入一个值key
x.erase(it)//删除迭代器为it的元素,use it=v.erase(it) instead of it++
x.erase(l,r)//删除地址[l,r)的数,l,r为两个迭代器指针
x.swap(x2)//交换x,x2
x.reverse(l,r) 翻转地址[l,r)的数,l,r为两个迭代器指针
x.begin() x.end()
x.size() x.empty()
x.lower_bound(key)
x.upper_bound(key)


string

1
2
3
头文件:<string>
定义:string x;
迭代器:string::iterator it;

操作

1
2
3
4
5
6
7
8
x.insert(pos,p)//在pos插入一个串p
x.erase(pos,l)//删除从pos开始l个位置
x.replace(pos,l,s)//将从pos开始l个位置替换成串s
x.length() x.size()
x.substr(pos,l)//截取从pos开始,长为l的子串
x.find(s2)//在s中匹配s2,返回位置,不存在返回-1,类似strstr
<< >>输入输出流
+ 拼接 < 字典序


rope

1
2
3
头文件:<ext/rope>//can't be used in cena
声明:using namespace __gnu_cxx;
定义:crope x;

操作

1
2
3
4
5
6
7
8
9
x.push_back(ch)//在末尾添加字符ch
x.insert(pos,s)//在pos位置插入字符ch
x.erase(pos,x)//从pos位置开始删除x个字符
x.replace(pos,ch)//将位置为pos的字符换成ch
x.substr(pos,x)//截取从pos开始,长为l的子串
x.length() x.size()
<< >>输入输出流
->at(x)/[x]//访问
+ 拼接 < 字典序

应用

区间翻转

同时维护一正一反两个rope……反转即交换两个子串……Orz……

区间循环位移

拆成多个子串连起来就好了……

可持久化

1
2
3
4
//可持久化并查集
fa[0]=new rope<int>(a,a+n+1);fa[i]=new rope<int>(*fa[i-1]);
它可以实现O(1)的拷贝历史版本,由于rope的底层是平衡树,copy时copy根节点就行了
用它就可以轻松实现可持久化数组


bitset

1
2
头文件:<bitset>
定义:bitset<M> x;//M:长度

操作

1
2
3
4
5
6
7
x.set()//按位清1
x.reset()//按位清0
x.flip()//逐位取反
x.any()//x中存在为1的二进制位返回1
x.count()//x中为1的二进制位数
x.to_ullong()//把x转为类型为unsigned long long的数
支持位运算
分享到: