C++比C更为实用的一点就是C++中提供了一系列封装好的常用模板，我们称之为标准模板库（Standard Template Library, STL）。STL分为容器（container）、迭代器（iterator）、空间配置器（allocator）、算法（algorithm）、配接器（adapter）和仿函数（functor）六个部分。由于STL是针对Intel的CPU进行的底层优化，因此能合理的在代码中使用STL将会有助于生成目标程序执行效率的提升，同时也降低了程序设计者编写代码的难度和复杂度。本文主要介绍一些在算法竞赛中常用的STL中的容器以及算法。
<1> sort
顾名思义，sort所封装的功能是排序，使用时需要引用algorithm库以及命名空间std。sort可以实现对于一段无序序列[a,b]排序使其有序，默认情况下将原有序列改变为从小到大排列。sort在内部封装了快速排序、希尔排序等多种排序算法，调用时将会依据数据规模选取一种最优的算法。
|
1 2 3 4 5 6 7 8 9 10 11 |
#include <cstdio> #include <algorithm> using namespace std; int data[10] = {2, 1, 5, 7, 9, 4, 3, 6, 10, 8}; int main(int argc, char const *argv[]) { sort(data, data + 10); for(int i = 0; i < 10; i++) printf("%d ", data[i]); return 0; } |
以上程序段的输出结果为1 2 3 4 5 6 7 8 9 10
当然，这是默认是排序规则。我们也可以在sort中引入第三个参数来自定义排序规则。例如：
|
1 2 3 4 5 6 7 8 9 10 11 12 |
#include <cstdio> #include <algorithm> using namespace std; int data[10] = {2, 1, 5, 7, 9, 4, 3, 6, 10, 8}; bool compare(int x, int y) { return x > y; } int main(int argc, char const *argv[]) { sort(data, data + 10, compare); for(int i = 0; i < 10; i++) printf("%d ", data[i]); return 0; } |
这个程序段的输出结果为10 9 8 7 6 5 4 3 2 1
原因在于修改了sort的排序规则为compare，即从大到小排序。由此，我们可以进一步定义排序规则。举个栗子：在Online Judge评测的时候，排序的方法是得分高者靠前，其次是程序用时短者，再次是程序占用内存少者。我们可以通过定义一个多关键字的排序规则来实现，代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include <cstdio> #include <algorithm> using namespace std; const int maxn = 1e5 + 5; int user_number; struct Rank_list { int score, time_use, memory_use, rank; } user[maxn] bool compare(Rank_list x, Rank_list y) { if(x.score != y.score) return x.score > y.score; else if(x.time_use != y.time_use) return x.time_use < y.time_use; else return x.memory_use < y.memory_use; } int main(int argc, char const *argv[]) { scanf("%d", &user_number); for(int i = 1; i <= user_number; i++) { scanf("%d", &user[i].score); scanf("%d", &user[i].time_use); scanf("%d", &user[i].memory_use); user[i].rank = i; } sort(user + 1, user + user_number + 1, compare); for(int i = 1; i <= user_number; i++) printf("%d ", user[i].rank); return 0; } |
您可以自行输入数据来验证以上程序段的正确性，这里不再赘述。
<2> max_element & min_element
max_element 和 min_element 封装的功能是求出一段序列[a,b]中的最大元素和最小元素，调用前需要引用algorithm库和命名空间std。由于二者操作相同，下面以max_element为例进行介绍。我们来以一个程序为例：
|
1 2 3 4 5 6 7 8 9 10 11 |
#include <cstdio> #include <algorithm> using namespace std; int data[10] = {2, 1, 5, 7, 9, 4, 3, 6, 10, 8}; int main(int argc, char const *argv[]) { printf("%d", *max_element(data, data + 10)); printf(" %d", *max_element(data + 2, data + 6)); printf(" %ld\n", max_element(data, data + 10) - data); return 0; } |
这个程序的输出为10 9 8
为什么呢？首先，max_element的操作对象的地址，也就是说max_element会寻找到你所查找的范围中的最大元素的地址，因此想要输出最大元素的具体值，我们就要用指针指向这个地址。第二个输出也不难解释，9是区间[2,6]中的最大值。第三个输出为8，指的是在区间[1,10]中最大元素所在位置为8，因为max_element操作的对象是地址，并且数组的名称即为该数组的头指针，所以这个输出也不难解释了。
和sort相同，max_element也支持自定义一个规则。这里不再赘述，请类比于sort多关键字排序的实现。
<3> unique
unique所封装的功能是将序列[a,b]中所有重复的元素移除，调用前需要引用algorithm库和命名空间std，其所返回的值是去重之后不在非重复序列中的第一个元素的地址。这样说大概也许很抽象与模糊，我们还是看更为直观的代码段和输出结果。
|
1 2 3 4 5 6 7 8 9 |
#include <cstdio> #include <algorithm> using namespace std; int data[10] = {1, 1, 1, 2, 2, 4, 3, 6, 10, 8}; int main(int argc, char const *argv[]) { printf("%d\n", *unique(data, data + 10)); return 0; } |
以上程序的输出为6
什么意思？为什么会是这个输出？我为什么看了代码实现还是没有明白？不要紧的，我们把操作前后data数组中的元素全部输出，看看到底发生了什么变化。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#include <cstdio> #include <algorithm> using namespace std; int data[10] = {1, 1, 1, 2, 2, 4, 3, 6, 10, 8}; int main(int argc, char const *argv[]) { for(int i = 0; i < 10; i++) printf("%d ", data[i]); putchar('\n'); printf("%d\n", *unique(data, data + 10)); for(int i = 0; i < 10; i++) printf("%d ", data[i]); putchar('\n'); return 0; } |
这个程序的输出为
1 1 1 2 2 4 3 6 10 8
6
1 2 4 3 6 10 8 6 10 8
看到这个输出结果，*unique(data, data + 10)为6似乎就可以理解了。进行unique操作的时候，是将重复的元素从序列中移除，后面的元素整体前移，那么，有多少个重复的元素，剩余元素就会整体前移多少次，在原有序列的末尾就会空出多少个空间。从输出我们可以得知，这几个空间并不是没有元素，而是这个空间初始的元素仍然存在。这样，我们一开始所讲的unique返回的是“去重之后不在非重复序列中的第一个元素的地址”就可以理解了。
我们已经知道，数组名称即为该数组的头指针，所以下面一条语句可以求出unique去重之后所剩元素组成的序列的长度。
|
1 |
unique(data, data + 10) - data; |