0x70 综合技巧与实践

算法竞赛不仅是一门动脑的学问，也是一门动手的艺术。除了算法、数据结构和题目模型的理论分析之外，如何简洁、高效地编写程序，并通过恰当的调试、检测保证其正确性，也是值得探究的要点。本章的主题是“综合技巧与实践”。0x71节介绍C++ STL，以及在使用STL时需要注意的问题，主要侧重与前面七章知识点的配合，不会从C++语言书的专业视角讲解其实现细节。0x72节介绍典型测试数据的随机生成，以及“对拍”等对程序正确性进行自我检测的方法。在平时解题中，读者可能长时间无法AC，且下载不到测试数据；在一些比赛规则下，选手无法获得实时的评分反馈；又或是想到有趣的构思，希望自己出一道题，必然需要对标准程序进行检验——这些都是数据生成与自我评估不可或缺的场景。

本节介绍STL中vector, queue, priority_queue, deque, set, multiset, map, bitset八种算法竞赛中比较常用的容器。另外，我们也会介绍algorithm头文件中包含的部分函数。建议读者按顺序依次阅读本节的每部分内容；以免错过大部分STL容器共通的背景知识，造成理解困难。对于更详尽的资源，请参见 $C++$ Primer等语言类书籍，或cplusplus.com。

include

vector 可理解为一个变长数组，它的内部实现基于倍增思想。按照下列思路可以大致实现一个 vector：设 $n$ 为 vector 的实际长度， $m$ 为 vector 的最大长度。向 vector 加入元素前，若 $n = m$ ，则在内存中申请 $2m$ 的连续空间，并把内容转移到新的地址上，再执行插入。从 vector 中删除元素后，若 $n \leq m / 2$ ，则释放一半的空间。

vector 支持随机访问，即对于任意的下标 $0 \leq i < n$ ，可以像数组一样用 $[i]$ 取值。但它不是链表，不支持在任意位置 O(1) 插入。为了保证效率，元素的增删一般应该在末尾进行。

声明

include<vector> 头文件  
vector<int> a; 相当于一个长度动态变化的int数组  
vector<int> b[233]; 相当于第一维长233，第二维长度动态变化的int数组  
struct rec{...};  
vector<rec> c; 自定义的结构体类型也可以保存在vector中

size/empty

size函数返回vector的实际长度(包含的元素个数)，empty函数返回一个bool类型，表明vector是否为空。二者的时间复杂度都是0(1)。

所有的STL容器都支持这两个方法，含义也都相同，之后我们就不再重复给出。

clear

clear函数把vector清空。

迭代器

迭代器就像STL容器的“指针”，可以用星号“*”操作符解除引用。

一个保存 int 的 vector 的迭代器声明方法为：

vector<int>::iterator it;

vector 的迭代器是“随机访问迭代器”，可以把 vector 的迭代器与一个整数相加减，其行为和指针的移动类似。可以把 vector 的两个迭代器相减，其结果也和指针相减类似，得到两个迭代器对应下标之间的距离。

begin/end

begin函数返回指向vector中第一个元素的迭代器。例如a是一个非空的vector，则*a.begin()与a[0]的作用相同。

所有的容器都可以视作一个“前闭后开”的结构，end函数返回vector的尾部，即第 $n$ 个元素再往后的“边界”。*a.end()与 $\mathsf{a}[n]$ 都是越界访问，其中 $n = a.\mathrm{size}()$

下面两份代码都遍历了 vector a，并输出它的所有元素。

for (int i = 0; i < a.size(); i++)  
    cout << a[i] << endl;  
for (vector<int>::iterator it = a.begin(); it != a.end(); it++)  
    cout << *it << endl;

front/back

front函数返回vector的第一个元素，等价于 *a.begin()和a[0]。

back函数返回vector的最后一个元素，等价于 $*\text{- - a. endO}$ 和a[a.sizeO-1]。

push_back/pop_back

a.push_back(x) 把元素 $x$ 插入到 vector a 的尾部。

a.pop_back() 删除 vector a 的最后一个元素。

【实例】用vector代替邻接表保存有向图

const int MAX_EDGE = 100010;  
vector<int> ver[MAX_EDGE], edge[MAX_EDGE];  
//保存从x到y权值为z的有向边  
void add(int x, int y, int z) {  
    ver[x].push_back(y);  
    edge[x].push_back(z);  
}  
//遍历从x出发的所有边  
for (int i = 0; i < ver[x].size(); i++) {  
    int y = ver[x][i], z = edge[x][i];  
    //有向边(x,y,z)  
}

include

头文件 queue 主要包括循环队列 queue 和优先队列 priority_queue 两个容器。

声明

queue<int> q;   
struct rec{...}; queue<rec> q;   
priority_queue<int> q;   
priority_queue< pair<int,int> >q;

循环队列queue

读者可以回顾0x21节“树与图的遍历”的末尾“图的广度优先遍历”部分，或者0x61节“最短路”的“SPFA算法”部分，找到queue的运用实例。

优先队列priority_queue

priority_queue 可理解为一个大根二叉堆。

重载“<”运算符

priority_queue 中存储的元素类型必须定义“小于号”，较大的元素会被放在堆顶。内置的 int, string 等类型本身就可以比较大小。若使用自定义的结构体类型，则需要重载“<”运算符。

例如下面的 poi 结构体保存了二维平面上点的编号和坐标，比较大小时，先比横坐标，再比纵坐标，并且考虑了精度误差：

struct poi { int id; double x, y; };
const double eps = 1e-8;
bool operator < (const poi &a, const poi &b) {
    return a.x + eps < b.x || a.x < b.x + eps && a.y < b.y;
}

priority_queue 实现小根堆

priority_queue 实现小根二叉堆的方式一般有两种。

对于int等内置数值类型，可以把要插入的元素的相反数放入堆中。等从堆中取出元素时，再把它取相反数变回原来的元素。这样就相当于把小的放在堆顶。

例如要插入 1,2,3 三个数时，改为插入 $-1, -2, -3$ 。此时 $-1$ 最大，处于堆顶，把 $-1$ 取出后再变回 $-(1)$ ，相当于取出了最小的 1。

更为通用的解决方案是，建立自定义结构体类型，重载“小于号”，但是当作“大于号”来编写函数，例如：

struct rec { int id; double value; };

bool operator  $\ll$  (const rec &a, const rec &b) { return a.value > b.value; }

这样priority_queue会认为“大”的更“小”，“小”的更“大”，从而实现大根堆时，value较小的rec元素会被放在堆顶。

请读者回顾0x61节“最短路”中的“堆优化的Dijkstra算法”部分，参考程序使用priority_queue实现了一个小根二叉堆，用于在计算单源最短路径的过程中保存二元组：“与起点距离的相反数、节点编号”。

懒惰删除法

读者可能已经发现，0x17节讲解的“二叉堆”支持删除操作，但STL的“优先队列”却不支持删除堆中任意元素，这给我们带来了很多不便。

懒惰删除法（又称延迟删除法）就是一种应对策略。当遇到删除操作时，仅在优先队列之外做一些特殊的记录（例如记录元素的最新值），用于辨别那些堆中尚未清除的“过时”元素。当从堆顶取出最值时，再检查“最值元素”是不是“过时”的，若是，则重新取出下一个最值。换言之，元素的“删除”被延迟到堆顶进行。

我们仍然以0x61节“最短路”中“堆优化的Dijkstra算法”的参考程序为例：

当一个节点的距离值 $dist[y]$ 被更新时，暂时不从优先队列中删除 $y$ 对应的元素，而是直接把新的二元组 $(-dist[y], y)$ 插入优先队列。

当从堆顶取出二元组 $(val, x)$ 准备扩展时，再检查 $dist[x]$ 是否等于 val。如果不相等，那么说明 $(val, x)$ 这个元素是被删除过的， $(dist[x], x)$ 才是最新插入的。此时直接继续循环，取出下一个堆顶。

当然，因为在无负权的图上，每个节点第一次被取出时，就已经得到了它的最短路，所以每个节点只需要扩展一次。因此，我们没有执行上述检查，而是用一个 bool 数组进行了“是否扩展过”的标记，其本质还是懒惰删除法的应用。

include

双端队列 deque 是一个支持在两端高效插入或删除元素的连续线性存储空间。它就像是 vector 和 queue 的结合。与 vector 相比，deque 在头部增删元素仅需要 O(1) 的时间；与 queue 相比，deque 像数组一样支持随机访问。

include

头文件 set 主要包括 set 和 multiset 两个容器，分别是“有序集合”和“有序多重集”，即前者的元素不能重复，而后者可以包含若干个相等的元素。set 和 multiset 的内部实现是一棵红黑树（平衡树的一种），它们支持的函数基本相同。

声明

set<int> s;  
struct rec {...}; set<rec> s;  
multiset<double> s;

与优先队列一样，set和multiset存储的元素必须定义“小于号”运算符。

size/empty/clear

与 vector 类似, 分别为元素个数、是否为空、清空。前两者的时间复杂度为 $O(1)$ 。

迭代器

set和multiset的迭代器称为“双向访问迭代器”，不支持“随机访问”，支持星号(*)解除引用，仅支持“++”和“--”两个与算术相关的操作。

设it是一个迭代器，例如set::iterator it;

若把 $\mathrm{it}++$ ，则 it 将会指向“下一个”元素。这里的“下一个”是指在元素从小到大排序的结果中，排在 it 下一名的元素。同理，若把 it--，则 it 将会指向排在“上一个”的元素。

请注意，执行“++”和“--”操作的时间复杂度都是 $O(\log n)$ 。执行操作前后，务必仔细检查，避免迭代器指向的位置超出首、尾迭代器之间的范围。

begin/end

返回集合的首、尾迭代器，时间复杂度为 $O(1)$ 。

s.begin() 是指向集合中最小元素的迭代器。

s.end() 是指向集合中最大元素的下一个位置的迭代器。换言之，就像 vector 一

样，是一个“前闭后开”的形式。因此 --s.end() 是指向集合中最大元素的迭代器。

insert

s.insert(x) 把一个元素 $x$ 插入到集合 $s$ 中，时间复杂度为 $O(\log n)$ 。

在 set 中，若元素已存在，则不会重复插入该元素，对集合的状态无影响。

下面的代码把 $n$ 个整数插入有序多重集 multiset，并从小到大输出，时间复杂度为 $O(n\log n)$ ，相当于进行了一次排序。假设 $n$ 个整数目前存储在数组 $a[1\sim n]$ 中。

multiset<int> s;  
for (int i = 1; i <= n; i++) s.insert(a[i]);  
for (multiset<int>::iterator it = s.begin(); it != s.end(); it++)  
cout << *it << endl;

find

s.find(x) 在集合 s 中查找等于 x 的元素, 并返回指向该元素的迭代器。若不存在, 则返回 s.end()。时间复杂度 $O(\log n)$ 。

lower_bound/upper_bound

这两个函数的用法与 find 类似，但查找的条件略有不同，时间复杂度 $O(\log n)$ 。

s(lower_bound(x) 查找 $\geq x$ 的元素中最小的一个，并返回指向该元素的迭代器。

s-upper_bound(x) 查找 $>x$ 的元素中最小的一个，并返回指向该元素的迭代器。

erase

设 $it$ 是一个迭代器，s.erase(it) 从 s 中删除迭代器 $it$ 指向的元素，时间复杂度为 $O(\log n)$ 。

设 $x$ 是一个元素，s.erase(x) 从 s 中删除所有等于 $x$ 的元素，时间复杂度为 $O(k + \log n)$ ，其中 $k$ 为被删除的元素个数。

如果想从multiset中删掉至多1个等于 $x$ 的元素，可以执行：

if ((it = s.find(x)) != s.end()) s erase(it);

count

s.count(x) 返回集合 s 中等于 x 的元素个数，时间复杂度为 $O(k + \log n)$ ，其中 k 为元素 x 的个数。

include

map 容器是一个键值对 (key-value) 映射。其内部实现是一棵以 key 为关键码的红黑树。map 的 key 和 value 可以是任意类型, 其中 key 必须定义 “小于号” 运算符, 声明方法为:

map<key_type, value_type> name;

例如：

map<long long, bool> vis;

map<string, int> hash;

map< pair<int, int>, vector<int> > test;

在很多时候，map 容器被当作 Hash 表使用，建立从复杂信息 key（如字符串）到简单信息 value（如一定范围内的整数）的映射。

因为 map 基于平衡树实现，所以它的大部分操作的时间复杂度都在 $O(\log n)$ 级别，略慢于使用 Hash 函数实现的传统 Hash 表。从 $\mathrm{C}++11$ 开始，STL 中新增了 unordered_map 等基于 Hash 的容器，但部分算法竞赛并不支持 $\mathrm{C}++11$ 标准，这里就不再介绍这些新容器。

size/empty/clear/begin/end

与 set 类似，分别为元素个数、是否为空、清空、首选代器、尾迭代器。

迭代器

map 的迭代器与 set 一样，也是“双向访问迭代器”。对 map 的迭代器解除引用后，将得到一个二元组 pair<key_type, value_type>。

insert/erase

与 set 类似，分别为插入、删除。insert 的参数是 pair<key_type, value_type>, erase 的参数可以是 pair 或者迭代器。

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

find

h.find(x)在变量名为h的map中查找key为 $x$ 的二元组，并返回指向该二元组

的迭代器。若不存在，返回h.endO。时间复杂度为 $O(\log n)$

[]操作符

h[key]返回key映射到的value的引用，时间复杂度为 $O(\log n)$ 。

[] 操作符是 map 最吸引人的地方。我们可以很方便地通过 h[key] 来得到 key 对应的 value，还可以对 h[key] 进行赋值操作，改变 key 对应的 value。

需要特别注意的是，若查找的 key 不存在，则执行 h[key]后，h 会自动新建一个二元组 (key, zero)，并返回 zero 的引用。这里 zero 表示一个广义“零值”，如整数 0、空字符串等。如果查找之后不对 h[key]进行赋值，那么时间一长，h 会包含很多无用的“零值二元组”，白白地占用了空间，降低了程序运行效率。强烈建议读者在用 [] 操作符查询之前，先用 find 方法检查 key 的存在性。

【实例】用map统计字符串出现的次数

给定 $n$ 个字符串， $m$ 个问题，每个问题询问一个字符串出现的次数。

$n \leq 20000, m \leq 20000$ ，每个字符串的长度都不超过20。

map<string, int> h;   
char str[25];   
for (int i = 1; i <= n; i++) { scanf("%s", str); h[str]++;   
}   
for (int i = 1; i <= m; i++) { scanf("%s", str); if (h.find(str) == h.end()) puts("0"); else printf("%d\n", h[str]);   
}

include

bitset 可看作一个多位二进制数，每 8 位占用 1 个字节，相当于采用了状态压缩的二进制数组，并支持基本的位运算。在估算程序运行的时间时，我们一般以 32 位整数的运算次数为基准，因此 $n$ 位 bitset 执行一次位运算的复杂度可视为 $n / 32$ ，效率较高。

声明

bitset<10000>s;

表示一个10000位二进制数，<>中填写位数。下面把位数记为 $n$ 。

位运算操作符

$\sim s$ ：返回对 bitsets 按位取反的结果。

&, |, ^: 返回对两个位数相同的 bitset 执行按位与、或、异或运算的结果。

,<<:返回把一个bitset右移、左移若干位的结果。

$= =, !=$ ：比较两个bitset代表的二进制数是否相等。

[]操作符

$s[k]$ 表示 $s$ 的第 $k$ 位，既可以取值，也可以赋值。

在10000位二进制数中，最低位为s[0]，最高位为s[9999]。

count

s.count()返回有多少位为1。

any/none

若s所有位都为0，则s.any()返回false，s.NONE()返回true。

若s至少一位为1，则s.any()返回true，s.none()返回false。

set/set/flip

s.set() 把 s 所有位变为 1。

s.set $(k,v)$ 把s的第 $k$ 位改为 $v$ ，即 $s[k] = v$ 。

s.reset() 把 s 所有位变为 0。

s.reset $(k)$ 把s的第 $k$ 位改为0，即 $s[k] = 0$

s flop() 把 s 的所有位取反，即 $s = \sim s$ 。

s.flip $(k)$ 把 $s$ 的第 $k$ 位取反，即 $s[k]^{\wedge} = 1$

include

下面介绍的几个函数都作用在序列上，接受两个迭代器（或指针） $l, r$ ，对下标处于前闭后开区间 $[l, r)$ 中的元素执行一系列操作。

reverse翻转

翻转一个 vector:

reverse(a.begin(), a.end());

翻转一个数组，元素存放在下标 $1 \sim n$ ：

reverse(a+1, a+n+1);

unique 去重

返回去重之后的尾迭代器（或指针），仍然为前闭后开，即这个尾迭代器是去重之后末尾元素的下一个位置。该函数常用于离散化，利用迭代器（或指针）的减法，可计算出去重后的元素个数 $m$ 。

把一个 vector 去重：

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

把一个数组去重，元素存放在下标 $1\sim n$

int m = unique(a+1, a+n+1) - (a+1);

random Shuffle 随机打乱

用法与 reverse 相同。

next.permutation下一个排列

把两个迭代器（或指针）指定的部分看作一个排列，求出这些元素构成的全排列中，字典序排在下一个的排列，并直接在序列上更新。另外，若不存在排名更靠后的排列，则返回 false，否则返回 true。同理，也有 prev.permutation 函数。

下面的程序按字典序输出 $1 \sim n$ 的 $n!$ 种全排列：

for (int i = 1; i <= n; i++) a[i] = i;  
do {  
    for (int i = 1; i < n; i++) cout << a[i] << ' "; cout << a[n] << endl; } while (next_permutation(a+1, a+n+1));

sort 快速排序

对两个迭代器（或指针）指定的部分进行快速排序。可以在第三个参数传入定义大小比较的函数，或者重载“小于号”运算符。

把一个int数组（元素存放在下标 $1\sim n$ ）从大到小排序，传入比较函数：

int a[MAX_SIZE];  
bool cmp(int a, int b) { return a > b; }  
sort(a+1, a+n+1, cmp);

把自定义的结构体 vector 排序，重载“小于号”运算符：

struct rec{ int id, x, y; };
vector<rec> a;
bool operator < (const rec &a, const rec &b) {

return a.x < b.x || a.x == b.x && a.y < b.y;  
}  
sort(a.begin(), a.end());

lower_bound/upper_bound 二分

lower_bound 的第三个参数传入一个元素 $x$ ，在两个迭代器（或指针）指定的部分上执行二分查找，返回指向第一个大于等于 $x$ 的元素的位置的迭代器（或指针）。

upper_bound 的用法和 lower_bound 大致相同，唯一的区别是查找第一个大于 $x$ 的元素。当然，两个迭代器（或指针）指定的部分应该是提前排好序的。

在有序int数组（元素存放在下标 $1\sim n$ ）中查找大于等于 $\pmb{x}$ 的最小整数的下标：

int i = lower_bound(a+1, a+n+1, x) - a;

在有序 vector中查找小于等于 $x$ 的最大整数（假设一定存在）：

int y = *--upper_bound(a.begin(), a.end(), x);