向量容器与泛型算法

1、向量容器与泛型算法在数组生存期内，数组的大小是不会改变的，向量容器则可以在运行时动态地增长或缩小。向量是类模板，具有成员函数，例如可以使用size()方法动态地获得vector的当前大小。面向对象的向量vector是使用最广泛的一个容器。vector是同一种类型的对象的集合，每个对象都有一个对应的整数索引值。和string对象一样，标准库负责管理存储元素的相关内存。我们把vector称为容器，是因为它可以包含其他对象。一个容器中的所有对象都必须是同一种类型的。使用vector之前，必须包含相应的头文件。#include using std:vector; vector是一个类模板（class

2、template）。模板允许程序员编写单个类或函数定义，这个类和函数定义可用于不同的数据类型上。因此，我们可以定义保存string对象的vector，或保存int值的vector，又或是保存自定义的类类型对象（如Sales_item对象）的vector。声明从类模板产生的某种类型的对象，需要提供附加信息，信息的种类取决于模板。以vector为例，必须说明vector保存何种对象的类型，通过将类型放在类模板名称后面的尖括号中来指定类型：vector ivec; / ivec holds objects of type intvector Sales_vec; / holds Sales_item

3、s和其他变量定义一样，定义vector对象要指定类型和一个变量的列表。上面的第一个定义，类型是vector，该类型即是含有若干int类型对象的vector，变量名为ivec。第二个定义的变量名是Sales_vec，它所保存的元素是Sales_item类型的对象。vector对象的定义和初始化vector类定义了好几种构造函数，用来定义和初始化vector对象。下面列出了这些构造函数：vector v1; vector保存类型为T的对象。默认构造函数v1为空。vector v2(v1);v2是v1的一个副本。vector v3(n, i);v3包含n个值为i的元素。vector v4(n);v4

4、含有值初始化的元素的n个副本。1. 创建确定个数的元素若要创建非空的vector对象，必须给出初始化元素的值。当把一个vector对象复制到另一个vector对象时，新复制的vector中每一个元素都初始化为原vector中相应元素的副本。但这两个vector对象必须保存同一种元素类型:vector ivec1; / ivec1 holds objects of type intvector ivec2(ivec1); / ok: copy elements of ivec1 into ivec2vector svec(ivec1); / error: svec holds strings,

5、not ints可以用元素个数和元素值对vector对象进行初始化。构造函数用元素个数来决定vector对象保存元素的个数，元素值指定每个元素的初始值：vector ivec4(10, -1); / 10 elements, each initialized to -1vector svec(10, hi!); / 10 strings, each initialized to hi!关键概念：vector对象动态增长 vector对象（以及其他标准库容器对象）的重要属性就在于可以在运行时高效地添加元素。因为vector增长的效率高，在元素值已知的情况下，最好是动态地添加元素。虽然可以对给定元

6、素个数的vector对象预先分配内存，但更有效的方法是先初始化一个空vector对象，然后再动态地增加元素（我们随后将学习如何进行这样的操作）。2. 值初始化如果没有给出元素的初始化式，那么标准库将提供一个值初始化的（value initialized）元素初始化式。这个由库生成的初始值用于初始化容器中的每个元素。而元素初始化式的值取决于存储在vector中元素的数据类型。如果vector保存内置类型（如int类型）的元素，那么标准库将用0值创建元素初始化值：vector fvec(10); / 10 elements, each initialized to 0如果向量保存类类型（如stri

7、ng）的元素，标准库将用该类型的默认构造函数创建元素初始值：vector svec(10); / 10 elements, each an empty string还有第三种可能性：元素类型可能是没有定义任何构造函数的类类型。这种情况下，标准库仍产生一个带初始值的对象，这个对象的每个成员进行了值初始化。vector的操作v.empty()如果v为空，则返回true,否则返回false。v.size()返回v中元素的个数。v.push_back(t)在v的末尾增加一个值为t的元素。vn返回v中位置为n的元素。v1 = v2把v1的元素替换为v2中元素的副本。v1 = v2如果v1与v2相等，则返

8、回true。!=, , , =保持这些操作符惯有的含义。v.front()返回向量中的第一个对象v.back()返回向量中的最后一个对象1. vector对象的sizeempty和size操作类似于string类型的相关操作（节）。成员函数size返回相应vector类定义的size_type的值。 使用size_type类型时，必须指出该类型是在哪里定义的。vector类型总是包括vector的元素类型：vector:size_type / okvector:size_type / error2. 向vector添加元素push_back()操作接受一个元素值，并将它作为一个新的元素添加到v

9、ector对象的后面，也就是“插入（push）”到vector对象的“后面(back)”：/ read words from the standard input and store them as elements in a vectorstring word;vector text; / empty vectorwhile (cin word) text.push_back(word); / append word to text该循环从标准输入读取一系列string对象，逐一追加到vector对象的后面。首先定义一个空的vector对象text。每循环一次就添加一个新元素到vector对

10、象，并将从输入读取的word值赋予该元素。当循环结束时，text就包含了所有读入的元素。3. vector的下标操作vector中的对象是没有命名的，可以按vector中对象的位置来访问它们。通常使用下标操作符来获取元素。vector的下标操作类似于string类型的下标操作(节)。vector的下标操作符接受一个值，并返回vector中该对应位置的元素。vector元素的位置从0开始。下例使用for循环把vector中的每个元素值都重置为0:/ reset the elements in the vector to zerofor (vector:size_type ix = 0; ix !

11、= ivec.size(); +ix) ivecix = 0;和string类型的下标操作符一样，vector下标操作的结果为左值，因此可以像循环体中所做的那样实现写入。另外，和string对象的下标操作类似，这里用size_type类型作为vector下标的类型。 在上例中，即使ivec为空，for循环也会正确执行。ivec为空则调用size返回0，并且for中的测试比较ix和0。第一次循环时，由于ix本身就是0，则条件测试失败，for循环体一次也不执行。4. 下标操作不添加元素初学C+的程序员可能会认为vector的下标操作可以添加元素，其实不然：vector ivec; / empty

12、vectorfor (vector:size_type ix = 0; ix != 10; +ix) ivecix = ix; / disaster: ivec has no elements上述程序试图在ivec中插入10个新元素，元素值依次为0到9的整数。但是，这里ivec是空的vector对象，而且下标只能用于获取已存在的元素。这个循环的正确写法应该是：for (vector:size_type ix = 0; ix != 10; +ix) ivec.push_back(ix); / ok: adds new element with value ix 必须是已存在的元素才能用下标操作符

13、进行索引。通过下标操作进行赋值时，不会添加任何元素。警告：仅能对确知已存在的元素进行下标操作 对于下标操作符(操作符)的使用有一点非常重要，就是仅能提取确实已存在的元素，例如：vector ivec; / empty vectorcout ivec0; / Error: ivec has no elements!vector ivec2(10); / vector with 10 elementscout ivec10; / Error: ivec has elements 0.9试图获取不存在的元素必然产生运行时错误。和大多数同类错误一样，不能确保执行过程可以捕捉到这类错误，运行程序的结果是

14、不确定的。由于取不存在的元素的结果是未定义的，因而不同的实现会导致不同的结果，但程序运行时几乎肯定会以某种有趣的方式失败。本警告适用于任何使用下标操作的时候，如string类型的下标操作，以及将要简要介绍的内置数组的下标操作。不幸的是，试图对不存在的元素进行下标操作是程序设计过程中经常会犯的严重错误。所谓的“缓冲区溢出”错误就是对不存在的元素进行下标操作的结果。这样的缺陷往往导致PC机和其他应用中最常见的安全问题。除了使用下标来访问vector对象的元素外，标准库还提供了另一种检测元素的方法：使用迭代器（iterator）。迭代器是一种允许程序员检查容器内元素，并实现元素遍历的数据类型。标准库

15、为每一种标准容器（包括vector）定义了一种迭代器类型。迭代器类型提供了比下标操作更一般化的方法：所有的标准库容器都定义了相应的迭代器类型，而只有少数的容器支持下标操作。因为迭代器对所有的容器都适用，现代C+程序更倾向于使用迭代器而不是下标操作访问容器元素，即使对支持下标操作的vector类型也这样。1. 容器的iterator类型每种容器类型都定义了自己的迭代器类型，如vector：vector:iterator iter;这条语句定义了一个名为iter的变量，它的数据类型是由vector定义的iterator类型。每个标准库容器类型都定义了一个名为iterator的成员，这里的itera

16、tor与迭代器实际类型的含义相同。术语：迭代器和迭代器类型 程序员首次遇到有关迭代器的术语时可能会困惑不解，产生困惑的原因之一是由于本书中同一个术语iterator表示两个不同的事物。一般性提及的是迭代器的概念；而特别提及的则是由容器定义的具体的iterator类型，如vector。重点要理解的是，定义了许多用作迭代器的类型，这些类型在概念上是相关的。若一种类型支持一组确定的行为（这些行为允许程序员遍历容器内的元素，并允许程序员访问这些元素值），我们就称这种类型为迭代器。不同的容器类定义了自己的iterator类型，用于访问容器内的元素。换句话说，每个容器定义了一种名为iterator的类型，

17、而这种类型支持（概念上的）迭代器的各种行为。 2. begin和end操作每种容器都定义了一对命名为begin和end的函数，用于返回迭代器。如果容器中有元素的话，由begin返回的迭代器指向第一个元素：vector:iterator iter = ivec.begin();上述语句把iter初始化为由名为begin的vector操作返回的值。假设vector不空，初始化后，iter即指该元素为ivec0。由end操作返回的迭代器指向vector的“末端元素的下一个”。通常称为超出末端迭代器(off-the-end iterator)，表明它指向了一个不存在的元素。如果vector为空，beg

18、in返回的迭代器与end返回的迭代器相同。 由end操作返回的迭代器并不指向vector中任何实际的元素，相反，它只是起一个哨兵（sentinel）的作用，表示我们已处理完vector中所有元素。3. vector迭代器的自增和解引用运算迭代器类型定义了一些操作来获取迭代器所指向的元素，并允许程序员将迭代器从一个元素移动到另一个元素。迭代器类型可使用解引用操作符（*操作符）来访问迭代器所指向r 元素：*iter = 0;解引用操作符返回迭代器当前所指向的元素。假设iter指向vector对象ivec的第一个元素，那么*iter和ivec0就是指向同一个元素。上面这个语句的效果就是把这个元素的值

19、赋为0。迭代器使用自增操作符（节）向前移动迭代器指向容器中下一个元素。从逻辑上说，迭代器的自增操作和int型对象的自增操作类似。对int对象来说，操作结果就是把int型值“加1”，而对迭代器对象则是把容器中的迭代器“向前移动一个位置”。因此，如果iter指向第一个元素，则+iter指向第二个元素。 由于end操作返回的迭代器不指向任何元素，因此不能对它进行解引用或自增操作。4. 迭代器的其他运算另一对可执行于迭代器的操作就是比较：用=或!=操作符来比较两个迭代器，如果两个迭代器对象指向同一个元素，则它们相等，否则就不相等。5. 迭代器应用的程序示例假设已声明了一个vector型的ivec变量，

20、要把它所有元素值重置为0，可以用下标操作来完成：/ reset all the elements in ivec to 0for (vector:size_type ix = 0; ix != ivec.size(); +ix) ivecix = 0;上述程序用for循环遍历ivec的元素，for循环定义了一个索引ix，每循环迭代一次ix就自增1。for循环体将ivec的每个元素赋值为0。更典型的做法是用迭代器来编写循环：/ equivalent loop using iterators to reset all the elements in ivec to 0for (vector:ite

21、rator iter = ivec.begin(); iter != ivec.end(); +iter) *iter = 0; / set element to which iter refers to 0for循环首先定义了iter，并将它初始化为指向ivec的第一个元素。for循环的条件测试iter是否与end操作返回的迭代器不等。每次迭代iter都自增1，这个for循环的效果是从ivec第一个元素开始，顺序处理vector中的每一元素。最后，iter将指向ivec中的最后一个元素，处理完最后一个元素后，iter再增加1，就会与end操作的返回值相等，在这种情况下，循环终止。for循环体

22、内的语句用解引用操作符来访问当前元素的值。和下标操作符一样，解引用操作符的返回值是一个左值，因此可以对它进行赋值来改变它的值。上述循环的效果就是把ivec中所有元素都赋值为0。通过上述对代码的详细分析，可以看出这段程序与用下标操作符的版本达到相同的操作效果：从vector的第一个元素开始，把vector中每个元素都置为0。 本节给出的例子程序和 vector的下标操作的程序一样，如果vector为空，程序是安全的。如果ivec为空，则begin返回的迭代器不指向任何元素，由于没有元素，所以它不能指向任何元素在这种情况下，从begin操作返回的迭代器与从end操作返回的迭代器的值相同，因此for

23、语句中的测试条件立即失败。6. const_iterator前面的程序用vector:iterator改变vector中的元素值。每种容器类型还定义了一种名为const_iterator的类型，该类型只能访问容器内元素，但不能改变其值。当我们对普通iterator类型解引用时，得到对某个元素的非const引用（2.5节）。而如果我们对const_iterator类型解引用时，则可以得到一个指向const对象的引用（2.4节），如同任何常量一样，该对象不能进行重写。例如，如果text是vector类型，程序员想要遍历它，输出每个元素,可以这样编写程序：/ use const_iterator b

24、ecause we wont change the elementsfor (vector:const_iterator iter = text.begin(); iter != text.end(); +iter) cout *iter endl; / print each element in text除了是从迭代器读取元素值而不是对它进行赋值之外，这个循环与前一个相似。由于这里只需要借助迭代器进行读，不需要写，这里把iter定义为const_iterator类型。当对const_iterator类型解引用时，返回的是一个const值。不允许用const_iterator进行赋值：for

25、(vector:const_iterator iter = text.begin(); iter != text.end(); + iter) *iter = ; / error: *iter is const使用const_iterator类型时，我们可以得到一个迭代器，它自身的值可以改变，但不能用来改变其所指向的元素的值。可以对迭代器进行自增以及使用解引用操作符来读取值，但不能对该元素值赋值。不要把const_iterator对象与const的iterator对象混淆起来。声明一个const迭代器时，必须初始化迭代器。一旦被初始化后，就不能改变它的值：vector nums(10); /

26、nums is nonconstconst vector:iterator cit = nums.begin();*cit = 1; / ok: cit can change its underlying element+cit; / error: cant change the value of citconst_iterator对象可以用于const vector或非const vector，因为不能改写元素值。const迭代器这种类型几乎没什么用处：一旦它被初始化后，只能用它来改写其指向的元素，但不能使它指向任何其他元素：const vector nines(10, 9); / cann

27、ot change elements in nines/ error: cit2 could change the element it refers to and nines is constconst vector:iterator cit2 = nines.begin();/ ok: it cant change an element value, so it can be used with a const vectorvector:const_iterator it = nines.begin();*it = 10; / error: *it is const+it; / ok: it isnt const so we can change its va