set#
set 容器的功用就是维护一个集合，其中的元素默认升序排列。其底层由红黑树实现，insert、erase、find 操作的时间复杂度均为$O(logN)$。
自定义从大到小排序#
1
2
3
4
|
set<int, greater<>> st;
// 或者
auto func = [](const int& x, const int& y) { return x > y; };
set<int, decltype(func)> st(func);
|
map#
map 容器存储的都是 pair 对象，该容器会自动根据各键值对的键的大小，默认选用std::less<T>排序规则（其中 T 表示键的数据类型），其会根据键的大小对所有键值对做升序排序。其底层由红黑树实现。
自定义从大到小排序#
1
2
3
4
|
map<int, int, greater<>> mp;
// 或者
auto func = [](const int& x, const int& y) { return x > y; };
map<int, int, decltype(func)> mp(func);
|
priority_queue#
在优先队列中，优先级高的元素先出队列，并非按照先进先出的要求，类似一个堆。优先队列默认大根堆，重载方式与 sort、set、map 相反。
vector转priority_queue#
1
2
3
|
vector<int> nums = {3, 4, 1, 2, 5};
// vector快速建立大根堆
priority_queue<int> q(less<int>(), move(nums));
|
建立小根堆#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
// 方法1
priority_queue<int, vector<int>, greater<>> q;
// 方法2
auto func = [](const int& x, const int& y) { return x < y; };
priority_queue<int, vector<int>, decltype(func)> q(func);
// 方法3
struct edge{
int to, w;
edge(int _to, int _w): to(_to), w(_w) {}
// 运算符重载 让priority_queue<edge>为小顶堆
bool operator < (const edge& x) const { return w > x.w; }
};
|
erase和remove#
1
2
|
iterator erase(iterator position);
iterator erase(iterator first, iterator last);
|
erase()函数可以用于删除 vector 容器（或 string）中的一个或者一段元素，在删除一个元素的时候，其参数为指向相应元素的迭代器，而在删除一段元素的时候，参数为指向一段元素的开头的迭代器以及指向结尾元素的下一个元素的迭代器。
在进行单个元素删除后，传入的迭代器指向不变，仍然指向被删除元素的位置，而被删除元素之后的所有元素都向前移动一位，也就是该迭代器实际上是指向了原来被删除元素的下一个元素。
1
|
iterator remove(iterator first, iterator last, val);
|
remove()的作用是将等于 val 的元素放到 vector（或 string）的尾部，但并不减少 vector 的 size。执行 remove 之后返回新的 end() 迭代器，但是不改变原来数组的 end() 迭代器的值。也就是数组中新的 end() 至原 end() 范围内的值是原数组中等于 val 的值，但是这部分状态不可靠。begin() 到新的 end() 这部分是不等于 val 的值。
也就是说 erase 和 remove 的区别在于执行函数之后返回值不同，被执行的 vector 的大小会不会改变。
vector 中 erase 的作用是删除掉某个位置或一段区域中的元素，减少其 size，返回被删除元素下一个元素的位置。
vector 中 remove 的作用是将范围内为 val 的值都 remove 到后面，返回新的 end() 值（非 val 部分的end）,但传入的原 vector 的 end 并没有发生改变，因此 size 也就没有变化。
所以说remove()不是真正的删除，而是移除。erase()结合remove()能做到删除一段范围内的某个元素。
1
2
3
4
5
|
// 删除vector中值为x的元素
vec.erase(remove(vec.begin(), vec.end(), x), vec.end());
// 删除string中所有的'_'
s.erase(remove(s.begin(), s.end(), '_'), s.end());
|
图的存储方式#
常用的图的存储方式很多，例如邻接矩阵、邻接链表、链式前向星等，兼顾性能和效率，一般使用的最多的是邻接链表。
不需要保存权值#
当不需要保存边的权值信息（或每条边的权值固定）时，直接使用二维 vector 即可（假设有10000个结点，编号从1到10000）：
1
2
3
4
|
vector<vector<int>> G(10002, vector<int>());
G[i].emplace_back(j); // 表示有一条 i→j 的边
G[i].size(); // 表示结点 i 的出度
|
使用 pair#
使用 pair 能很方便地保存边的权值。
1
2
3
4
|
typedef pair<int, int> PII;
vector<PII> G[10002];
G[i].emplace_back(make_pair(j, 100)); // 表示有一条 i→j 的边，权值为100
|
需要进行排序的情况#
有时候需要按边权对结点进行排序，这时候我们可以使用以下存储结构：
1
2
3
4
5
6
7
8
9
|
struct edge{
int s, t, cost;
edge(int _s, int _t, int _cost): s(_s), t(_t), cost(_cost) {}
bool operator < (const edge& o) const { return cost < o.cost; }
};
vector<edge> G;
G.emplace_back(edge(i, j, 100)); //表示有一条 i→j 的边，权值为100
sort(G.begin(), G.end());
|
或者使用 tuple<int, int, int>：
1
2
3
4
5
6
7
8
9
|
vector<tuple<int, int, int>> edges; // 结点i 结点j 权值
edges.emplace_back(make_tuple(i, j, 100)); // 表示有一条 i→j 的边，权值为100
// 按权值从小到大排序
sort(edges.begin(), edges.end(), [](const auto& e1, const auto& e2) {
auto&& [x1, y1, v1] = e1;
auto&& [x2, y2, v2] = e2;
return v1 < v2;
});
|
__builtin系列#
以 __builtin 开头的函数，是一种相当神奇的位运算函数，熟练运用此类函数可以方便解决位运算相关问题。
__builtin_ctz(x)和__buitlin_clz(x)#
__builtin_ctz(x)返回 x 的二进制表示数末尾 0 的个数；
__builtin_clz(x)返回 x 的二进制表示数前导 0 的个数。
对应的 64 位长整型版本分别为：__builtin_ctzll(x)和__builtin_clzll(x)
1
2
3
4
5
|
cout << __builtin_ctz(128) << endl; // 7
cout << __builtin_ctz(128) << endl; // 24
cout << __builtin_ctzll(1024L) << endl; // 10
cout << __builtin_clzll(1024L) << endl; // 53
|
__builtin_popcount(x)#
返回 x 的二进制表示数 1 的个数。
1
|
cout << __builtin_popcount(15) << endl; // 4
|
__builtin_parity(x)#
判断 x 的二进制表示数 1 的个数的奇偶性(偶数返回 0，奇数返回 1)。
1
2
|
cout << __builtin_parity(14) << endl; // 1
cout << __builtin_parity(15) << endl; // 0
|
__builtin_ffs(x)#
返回 x 的二进制表示数的最后一个 1 在第几位（从后往前算）。
1
2
3
|
cout << __builtin_ffs(1024) << endl; // 11
cout << __builtin_ffs(6) << endl; // 2
cout << __builtin_ffs(0) << endl; // 0
|