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; |
Thanks for another magnificent post. Where else could anyone get that type of info in such an ideal way of writing? I’ve a presentation next week, and I’m on the look for such information.