我们相距十万光年

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

11/23
13:24
Learning Note

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

C++C更为实用的一点就是C++中提供了一系列封装好的常用模板,我们称之为标准模板库(Standard Template Library, STL)。STL分为容器(container)、迭代器(iterator)、空间配置器(allocator)、算法(algorithm)、配接器(adapter)和仿函数(functor)六个部分。由于STL是针对IntelCPU进行的底层优化,因此能合理的在代码中使用STL将会有助于生成目标程序执行效率的提升,同时也降低了程序设计者编写代码的难度和复杂度。本文主要介绍一些在算法竞赛中常用的STL中的容器以及算法。

<1> sort
顾名思义,sort所封装的功能是排序,使用时需要引用algorithm库以及命名空间stdsort可以实现对于一段无序序列[a,b]排序使其有序,默认情况下将原有序列改变为从小到大排列。sort在内部封装了快速排序、希尔排序等多种排序算法,调用时将会依据数据规模选取一种最优的算法。

以上程序段的输出结果为1 2 3 4 5 6 7 8 9 10
当然,这是默认是排序规则。我们也可以在sort中引入第三个参数来自定义排序规则。例如:

这个程序段的输出结果为10 9 8 7 6 5 4 3 2 1
原因在于修改了sort的排序规则为compare,即从大到小排序。由此,我们可以进一步定义排序规则。举个栗子:在Online Judge评测的时候,排序的方法是得分高者靠前,其次是程序用时短者,再次是程序占用内存少者。我们可以通过定义一个多关键字的排序规则来实现,代码如下:

您可以自行输入数据来验证以上程序段的正确性,这里不再赘述。

<2> max_element & min_element

max_elementmin_element 封装的功能是求出一段序列[a,b]中的最大元素和最小元素,调用前需要引用algorithm库和命名空间std。由于二者操作相同,下面以max_element为例进行介绍。我们来以一个程序为例:

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

以上程序的输出为6
什么意思?为什么会是这个输出?我为什么看了代码实现还是没有明白?不要紧的,我们把操作前后data数组中的元素全部输出,看看到底发生了什么变化。

这个程序的输出为
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去重之后所剩元素组成的序列的长度。