大道至简：STL精解

vector是定义于名称空间（namespace）std内的模板，其定义在头文件＜vector＞中。

其原型为：

vector中的元素可以是任意型别T，必须具备可设置和可复制两个属性。模板的第2个参数是关于空间配置器设置的，用于定义内存模型，其默认内存模型是C＋＋ STL提供的al-locator，对于一般的程序员来说，可有可无。

vector是最简单的序列式容器，支持随机访问元素。这一属性使vector有时显得效率低一些。vector的“大小”与容量之间有重要差别。容量肯定是大于或等于其“大小”的。vector就像一个动态数组，是典型的“将元素置于动态数组中加以管理”的抽象概念。然而，C＋＋标准并未规定必须以动态数组来实现vector，仅规定了相应的条件和操作复杂度。在程序开发过程中，程序员使用vector作为动态数组是非常方便的。vector的迭代器是随机存取迭代器，对任何一个STL算法均奏效。尤其在容器末端或删除元素时，vector性能相当好。

vector可以实现数据结构中的队列、数组和堆栈的所有功能。一旦vector定义了类对象，就可以“装”东西了。

下面介绍vector类模板的使用。

1.vector类基础

在使用vector类模板，程序员需要定义该模板的对象，并对其初始化。vector容器对象的大小和容量也是使用的重要前提，就像使用数组一样，数组的大小决定了数组能否正常使用。

（1）vector对象定义

定义vector类对象，主要是使用std名称空间的vector类模板。详见例3-3。

例3-3

在例3-3中，语句vector＜string＞myvt使用了类模板vector定义类模板的对象myvt，容器myvt中所存储元素的数据类型是string。当然，也可以存储其他数据类型的元素，例如int、long、double等。命名空间std是类的包容器（或者叫“更大的容器”）。上述程序在编译时，会出现4个警告信息（warning），警告信息的编号为c4786。为避免出现警告信息，程序员可以在代码中添加语句“＃pragma warning（disable：4786）”。修改后的代码如下：

第一行代码的作用是消除警告信息c4786。

提示

注意上例中＃pragma语句的用法。

（2）vector类对象初始化

要对vector类对象实现初始化操作可以使用push_back（）函数。下面在例3-3中添加部分代码，以实现对vector类对象myvt的初始化。

上述代码执行之后，容器myvt中将包含4个字符串。push_back（）函数将对象放入容器中，有时会错误地把信息添加到容器中，此时可以使用pop_back（）函数将其弹出。

既然vector类模板实例化的对象是容器，那么按照“容器”的物理涵义，对于既定的容器，必然存在容器的容量。对于vector的对象，程序员可以使用reserve（）函数预先设置容器的容量。例如，

例3-3的执行效果如图3-3所示。

图3-3 例3-3的执行效果

myvt.reserve（4）语句可以实现设置容器的容量为4个字符串。一般情况下，定义vec-tor类的对象后，如果没有预先设置容器的容量，是不允许直接给容器中的元素赋值的，例如，若执行下面一段代码，程序会发生异常。

（3）容器的大小和容量

vector类模板定义了size（）和capacity（）两个函数，用以实现统计容器元素的目的；还定义了resize（）和reserve（）两个函数，用以实现设置容器大小的目的。

size（）函数和capacity（）函数可以统计容器中元素的数量。size（）函数返回容器中现有的元素数；capacity（）函数返回容器中实际能够容纳的元素数。max_size（）函数可以返回容器所能容纳的最大元素数。一般情况下，当元素数量超越capacity（）函数返回的数值时，vector有必要重新配置内部存储器。

reserve（）函数可以预先设置容器的容量；resize（）函数可以修改容器的大小。reserve（）函数可以保留适当的容量，避免重新配置内存。当然，在定义容器对象时，通过传递函数的形式，也可以实现设置vector的起始大小。

以上知识点，可参考完整的例3-3。

完整的例3-3的执行效果如图3-4所示。

图3-4 完整的例3-3的执行效果

提示

请关注例3-3中size（）、capacity（）、reserve（）和resize（）函数的用法。

2.vector类的基本应用函数

vector最基本的应用包括判断向量是否为空、遍历向量元素以及使用算法等。下面逐一介绍。

（1）判断向量是否为空

向量模板vector＜T＞提供了一个empty（）函数。此函数可以判断向量容器中元素是否为0，如果向量为空，函数返回真；如果向量不为空，函数返回非真。empty（）函数的函数原型为：

下面举例说明empty（）函数的使用方法。在例3-4中，首先定义了结构体类型ST，其次定义了初始化Origin（）函数。Origin（）函数可以根据指定的参数，实现对向量的初始化，为向量添加内容。

例3-4

例3-4的执行效果如图3-5所示。

图3-5 例3-4的执行效果

请读者认真对照程序输出结果和源代码，以体会该函数的用法。

上面简单介绍了empty（）函数，这里顺便讲一下clear（）函数。clear（）函数可以将容器中的所有元素移出，将容器清空。

提示

请关注例3-4中empty（）函数在while循环中的用法。

（2）遍历vector型容器

要遍历vector中的元素，必须使用循环语句for或者while。可以使用迭代器实现遍历，也可以通过使用at（）函数和循环语句实现。下面举例说明。在例3-4中添加Iter_for（）和at_for（）两个函数。

修改main（）函数如下：

上述两种方法均较好地实现了对元素的遍历。

提示

请关注例3-4中如何遍历vector型容器中的元素。

程序修改后的执行效果如图3-6所示。

图3-6 遍历vector型容器

（3）使用算法

使用vector类模板，还可以通过使用部分算法，实现对vector的操作。下面以for_each（）和count（）两个函数为例进行说明。在例3-5中，定义了一个模板函数Original（）和两个全局函数out（）和greater95（）。通过例3-5，既复习了函数模板的用法，也提前了解算法的使用。

例3-5

例3-5的执行效果如图3-7所示。

图3-7 例3-5的执行效果

总结

请关注函数模板的使用以及for_each（）函数的使用。最重要的是关注如何定义for_each（）的子进程。对于算法的子进程，后面还会有更多的介绍。读者不必急于掌握其原理，应先“照葫芦画瓢”学会其使用方法。随着使用次数的增加，逐渐加深印象，进而深刻理解其内涵。

3.vector高级编程(www.xing528.com)

下面主要介绍vector容器相关的元素访问方法、迭代器相关函数、元素查找和搜索、字符串处理、元素排序、插入元素、删除元素、交换元素等内容。

（1）元素访问方法

按照C和C＋＋的惯例，第一个元素的下标为0，最后一个元素的下标为size（）-1，即第n个元素的下标为n-1。可以直接访问vector型容器中元素的操作方法主要包括at（）、［］、front（）和back（）。例如，

vector＜typenameT＞c；

其中，c.at（index）函数的返回值是引用类型。该函数既可以取出元素值，也可以对元素赋值。

c［index］的返回值是引用类型。该函数既可以取出元素，也可以对元素赋值，但必须确定下标是有效的。

c.front（）函数用于返回第一个元素。

c.back（）函数用于返回最后一个元素。

（2）迭代器相关函数

vector类模板提供部分常规函数来获取迭代器。迭代器是随机访问迭代器，它类似于一个指向vector中元素的指针通过迭代器甚至可以操作所有算法。和迭代器相关的函数主要包括begin（）、end（）、rbegin（）和rend（）。其中begin（）函数指向第一个元素；end（）函数指向最后元素的下一个位置；rbegin（）函数指向逆向迭代的第一个元素；rend（）函数指向逆向迭代的最后元素的下一位置。begin（）和end（）函数的返回值均为迭代器类型；rbegin（）和rend（）函数的返回值均为逆向迭代器类型。

（3）元素查找和搜索

若要查找和搜索vector型容器中的元素，可以使用STL的通用算法find（）函数。若要有条件地搜索相关元素，可以使用find_if（）算法函数。这两个算法函数均可以使用迭代器，两个迭代器参数决定了查找和搜索的范围。这两个函数的返回值均为迭代器类型。

find（）函数的原型为：

find_if（）函数的原型为：

下面先举例说明如何实现在vector型容器中的元素查找和搜索。

例3-6

例3-6的执行效果如图3-8所示。

图3-8 例3-6的执行效果

提示

读者应掌握find（）函数和find_if（）函数的使用，尤其注意find_if（）函数中条件表达式的使用。

（4）字符串处理

使用vector管理字符串，可以处理字符串中的每个字符，并且可以自动管理内存。将字符串中的每一个字符作为vector型容器中的元素，使用容器的所有成员函数就可以便捷地完成字符串的操作读者可参考本书第2章中关于字符串的内容，此处不再赘述。

（5）元素排序

若要实现对vector型容器中元素的排序，需要使用算法函数sort（）或其他排序算法。有些容器支持对特殊算法的实现，而使用算法排序有助于提高计算性能。但vector类模板没有提供具有排序算法的成员函数。下面简要介绍使用sort（）算法函数实现对vector型容器中元素排序的方法。

例3-7

例3-7重点讲述了如何使用sort（）算法函数实现对vector型容器中的元素进行排序。在使用sort（）算法函数时，针对元素的特点实现了四种排序，即分别对name和score进行了从大到小和从小到大排序。

程序执行结果如下：

提示

读者应掌握sort（）算法函数的使用，并学会定义其子进程。

（6）插入元素

若要向现有的vector型容器中插入一个新的元素，可以使用push_back（）函数将元素加入至vector型对象（容器）的末尾；可以使用insert（）函数将元素插入至vector型容器中的任意位置，即insert（）函数可以实现在迭代器指向位置插入元素，其中insert（）函数返回值为迭代器类型，指向刚插入的元素；可以在迭代器指定位置插入多个连续的不同元素；可以插入多个值相同的元素。push_back（）函数和insert（）函数的原型为：

下面通过例3-8说明push_back（）和insert（）函数的使用方法。

例3-8

例3-8的执行效果如图3-9所示。请读者对照源代码和执行效果深刻理解插入元素的方法。

图3-9 例3-8的执行效果

（7）删除元素

在定义vector型容器时，需要初始化其元素，并且需要同时使用其他STL容器中的区间数据来进行初始化操作。该STL容器不必是vector型，只要元素的类型相同即可。例如，

若要删除容器中的元素，可以使用三个成员函数：pop_back（）、erase（）和clear（）。还可以使用算法库的remove（）算法函数来实现。

pop_back（）函数可以删除最后1个元素；erase（）函数可以删除由迭代器指定的元素，也可删除区间范围的元素。clear（）函数可以删除vector型容器中的所有元素，相当于erase（begin（），end（））。这三个函数的使用方法详见例3-9。

例3-9

例3-9的执行效果如图3-10所示。

图3-10 例3-9的执行效果

（8）对象交换

vector类模板还提供了成员swap（）函数，以实现两个vector型容器之间的元素互换。如果两个参与交换的vector类型相同，对象交换会瞬间完成；如果两个参与交换的vector对象中元素类型不同，在实现对象交换的过程中，需要执行非常复杂的操作。swap（）函数的原型为：

例3-10

例3-10的执行效果如图3-11所示。

图3-11 例3-10的执行效果

（9）vector＜bool＞类

C＋＋STL专门针对元素型别为bool的vector设计了特殊版本，目的是获取优化的vec_- tor。其所占用的内存空间远小于一般的vector模板实例化的bool型向量（容器）。普通的vector类模板会分配1个Byte空间，而vector＜bool＞只占用1个bit存储单个元素，所占内存空间是空间的1/8。而C＋＋的最小寻址通常以Byte为单位，在类vector＜bool＞中需针对reference和iterator进行特殊考虑。类vector＜bool＞的操作要比普通的vector慢很多，所有元素操作必须转换为bit操作。后面章节还会介绍bitset的使用，程序员应该优先使用bitset，而不是vector＜bool＞。

vector＜bool＞类不仅仅是向量型的容器类，还提供位操作——非常方便的操作“位”和“标志”。所有用于元素存取的函数，返回值均为引用型（reference）。

vector＜bool＞类提供了位取反函数flip（），可以实现对容器中的所有元素取反，还可以对某“位”取反。下面以例3-11进行说明。

例3-11

例3-11的执行效果如图3-12所示。

图3-12 例3-11的执行效果

提示

本小节主要讲述了vector模板类、vector模板类（容器）的定义和容量、基本成员函数使用方法以及vector容器的高级编程。在学习使用vector容器的同时，本小节还讲述了部分算法的学习。