C++ STL的一些操作
阅读量：4306 次
发布时间：2019-06-06
本文共 4439 字，大约阅读时间需要 14 分钟。
priority_queue
最常用的当然是在dij的时候.
#include struct node { int x, dis; bool operator < (const node a) const { return a.dis < dis; } //需要注意的是这个地方要反着写，一定要反着写，也就是平常打cmp时的dis Q;
当然，这里有很多种打法，我现在习惯于用下面这种，不用去记那些什么const麻烦：
struct node { int x, dis; friend bool operator (node x, node y) { return x.dis < y.dis; }}priority_queue Q; Dijkstra这样打：
priority_queue Q; Q.push({i, 0}), mem(vis, 0), mem(dis, 7), dis[i] = 0;while (Q.size()) { k = Q.top().x; Q.pop(); if (vis[k]) continue; vis[k] = 1; for (x = las[k] ; x ; x = nex[x]) if (dis[tov[x]] > dis[k] + 1) dis[tov[x]] = dis[k] + 1, Q.push({tov[x], dis[tov[x]]});}
虽然priority_queue没有set那么好用，但毕竟set存不了实数，所以有时候优先队列也是略胜一筹的。
它还有这些基本操作：
priority_queue Q; //这样就定义了一个优先队列priority_queue Q; //这样也可以priority_queue Q; // 存储一个结构体，例如像上面的dijkstra时的结构体。//但如果不用结构体，我们可以这样子打，在定义的时候确定运算符：priority_queue
, less
> Q; //这样是从大到小的，也是C++默认的priority_queue
, greater
>Q; //这样是从小到大的
注意 vector<int>以及后面的> >不要连起来.
和普通队列一样，它有这些基本操作：q.size();//返回q里元素个数q.empty();//返回q是否为空，空则返回1，否则返回0q.push(k);//在q的末尾插入kq.pop();//删掉q的第一个元素---这个操作最重要。。。。q.top();//返回q的第一个元素
bitset
- bitset用来压位，使复杂度在原来的基础上除以\(32\).
#include bitset S; //这样就可以建一个bitset了S.set(); //全部变成1S.reset(); //全部变成0S.count(); // 返回1的个数S.flip(); // 把S每一位都取反S.flip(i); //仅把第i为取反S.any(); //返回是否有1S.none(); //返回是否没有1///表示并不知道这个看似牛逼的操作有什么用a.to_ulong() //转成一个unsigned long long的数.//bitset支持位运算操作，非常强大.如 a = a & b; a = a ^ b; a = a | b;
还需要注意的是，bitset支持左移、右移操作，得到一个新的bitset。
具体的，这个操作可以用在一些形如\(f_x=or_{f_{x+km}}\)的操作上，详细见： 这道题的DP优化。
vector
表示vector是个既能装逼，又实用的东西，但请注意： vector常数巨大，一般如果是存边的话，尽量用邻接表或者前向星.
#include vector d,a[N]; //都可以定义d.push_back(x) //在d这个vector里面插入一个x元素，注意，相当于数组的插入.printf("%d", d[i]) //询问插入的第i个元素，注意下标从0开始printf("%d", d.size() - 1) //返回插入元素个数d.front(); d.back(); //第一个，最后一个元素，好吧实际上没有用d.clear(); //清空把d排序：sort(d.begin(), d.end());struct node { int u, dis; bool operaotr < (node x) const { return dis < x.dis; }}当然，也可以定义结构体vector ，然后按上面的一样排序就可以了.d.insert(d.begin() + k, v) // 表示在第k个位置插入一个元素v，把k+1~d.end()的都往后移一个位置.//表示并不知道上面这个操作有什么用，并且当k=0时，插入550000个元素，它用了49.007s//插入100000个元素时，仅用了1.78sint v = upper_bound(d.begin(), d.end(), node{a, b}) - d.begin() - 1;//与普通的数组的upper_bound是类似的， 只不过有结构体时，需要operator.注意，upper_bound是返回第一个大于某数的迭代器lower_bound是返回第一个大于等于某数的迭代器，这两个操作很重要，在set里面也是一样的.
总结一下，vector里面这个upper_bound(a.begin(), a.end(), node{x,y}) - a.begin() - 1这个操作很重要.
然后就是vector虽然方便（比如说打点分树的时候，需要把每一个分治中心带的节点用结构体储存，这时候就超级好用），但是也牺牲了时间，它的常数比较大.
map
map也是一个炒鸡好用的STL。据cold_chair大佬所言，当元素很多的时候，map会变得很慢，或者说常数很大...
#include
map的用法还是很多的。
注意，一般来说，我们是定义
map h;
如果要在某个位置赋值，可以直接调用
h[x] = y;
但注意，因为几乎所有的STL容器我们都只能用
:: iterator it;
来得到位置，所以如果我们要把对应的值求出来，则要用
it -> first 或 it -> seond
两种操作。
最后还需要知道，map的实现是类似于set的，所以他也支持\(log\)的查找最小最大值。
具体来说，我们可以这样调用：
for (map :: iterator it = h.begin(); it != h.end(); it ++) { printf("%d\n",it->first) H[it->first] = 1;}
Set
很强大的一个功能。
#include set a; //这样就建好一个set了请务必注意：set是不可以支持重复元素的，想要有重复元素，可以使用multisetmultiset a; //这是可以支持重复元素插入的。a.insert(x); //表示在set里面插入一个x元素.a.erase(x); //表示把set里面所有为x的数的删掉.a.erase(a.find(x)); //这个表示只删除一个x.*a.begin() // 表示最小值*a.end() // 表示最大值的下一个位置*--a.end() //表示最大值// 因为返回的都是一个迭代器，所以具体数值要在前面加一个*号。可能有时候要多次用到某个迭代器，所以我们可以把他储存下来，用一个it来表示，其中it这样定义：multiset :: iterator it;//那么像上面的最小值，就可以这样表示it = a.begin(), printf("%d\n", *it).it ++就可以表示下一个位置的元素，当然不要滥用，因为这个++是需要log的时间复杂度的。。其中，set里面最重要的两个操作就是上面vector里面的两个操作，即lower_bound和upper_bound.it = a.lower_bound(x) //表示找到第一个大于等于x元素的迭代器it = a.upper_bound(x) //表示找到第一个大于x元素的迭代器
注意，如果合并两个map，我们可以用上面的\(log\)查找 + 对应位置赋值 实现。
但是set可以更方便的写成：
Set1.insert(Set2.begin(),Set2.end());
这样就把Set2插入到Set1中去了。
请注意，\(set\)和\(map\)都可以用来做启发式合并，且常数几乎一模一样。
ctime
srand(time(0)) //随机种子，没有这个东西，随机相当于没有随机.主要想说的是这个：int st = clock();// do sthprintf("%lf\n", (double) (clock() - st) / CLOCKS_PER_SEC) 总结