我们相距十万光年

晨露正葱茏，来日盛景定无穷

11/23
13:24
Algorithm

[STL] C++ 标准模板库选讲

saruka 撰写 无回复

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在内部封装了快速排序、希尔排序等多种排序算法，调用时将会依据数据规模选取一种最优的算法。

C++
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中引入第三个参数来自定义排序规则。例如：

C++
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评测的时候，排序的方法是得分高者靠前，其次是程序用时短者，再次是程序占用内存少者。我们可以通过定义一个多关键字的排序规则来实现，代码如下：

C++
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为例进行介绍。我们来以一个程序为例：

C++
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，其所返回的值是去重之后不在非重复序列中的第一个元素的地址。这样说大概也许很抽象与模糊，我们还是看更为直观的代码段和输出结果。

C++
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数组中的元素全部输出，看看到底发生了什么变化。

C++
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去重之后所剩元素组成的序列的长度。

C++
1
unique(data, data + 10) - data;