#include <vector>

using std::vector;

vector 是一个 类模板 （ class template ）。模板允许程序员编写单个类或函数定义，这个类和函数定义可用于不同的数据类型上。因此，我们可以定义保存 string 对象的 vector ，或保存 int 值的 vector ，又或是保存自定义的类类型对象（如 Sales_item 对象）的 vector 。将在第 16 章介绍如何定义程序员自己的类模板。幸运的是，使用类模板时只需要简单了解类模板是如何定义的就可以了。

声明从类模板产生的某种类型的对象，需要提供附加信息，信息的种类取决于模板。以 vector 为例，必须说明 vector 保存何种对象的类型，通过将类型放在类模板名称后面的尖括号中来指定类型：

vector<int> ivec;                 // ivec holds objects of type int

vector<Sales_item> Sales_vec;  // holds Sales_items

和其他变量定义一样，定义 vector 对象要指定类型和一个变量的列表。上面的第一个定义，类型是 vector<int> ，该类型即是含有若干 int 类型对象的 vector ，变量名为 ivec 。第二个定义的变量名是 Sales_vec ，它所保存的元素是 Sales_item 类型的对象。

vector 不是一种数据类型，而只是一个类模板，可用来定义任意多种数据类型。 vector 类型的每一种都指定了其保存元素的类型。因此， vector<int> 和 vector <string> 都是数据类型。

3.3.1  vector 对象的定义和初始化

vector 类定义了好几种构 造函数（ 2. 3. 3 节） ，用来定义和初始化 vector 对象。表 3 - 4 列出了这些构造函数：

表 3-4  几种初始化 vector 对象的方式

vector <T >  v1 ;

vector 保存类型为 T 的对象。默认构造函数 v1 为空。

vector < T > v2 ( v1 );

v2 是 v1 的一个副本。

vector < T > v3 ( n , i );

v3 包含 n 个值为 i 的元素。

vector < T > v4 ( n );

v4 含有值初始化的元素的 n 个副本。

1. 创建确定个数的元素

若要创建非空的 vector 对象，必须给出初始化元素的值。当把一个 vector 对象复制到另一个 vector 对象时，新复制的 vector 中每一个元素都初始化为原 vector 中相应元素的副本。但这两个 vector 对象必须保存同一种元素类型 :

vector<int> ivec1;                // ivec1 holds objects of type int

vector<int> ivec2(ivec1);       // ok: copy elements of ivec1 into ivec2

vector<string> svec(ivec1);    // error: svec holds strings, not ints

可以用元素个数和元素值对 vector 对象进行初始化。构造函数用元素个数来决定 vector 对象保存元素的个数，元素值指定每个元素的初始值：

vector<int> ivec4(10, -1);     // 10 elements, each initialized to -1

vector<string> svec(10, "hi!"); // 10 strings, each initialized to "hi!"

关键概念： vector 对象动态增长

vector 对象（以及其他标准库容器对象）的重要属性就在于可以在运行时高效地添加元素。因为 vector 增长的效率高，在元素值已知的情况下，最好是动态地添加元素。

正如第 4 章将介绍的，这种增长方式不同于 C 语言中的内置数据类型，也不同于大多数其他编程语言的数据类型。特别地，如果读者习惯了 C 或 Java 的风格，由于 vector 元素连续存储，可能希望最好是预先分配合适的空间。但事实上，为了达到连续性， C ++ 的做法恰好相反，具体原因将在第 9 章探讨。

虽然可以对给定元素个数的 vector 对象预先分配内存，但更有效的方法是先初始化一个空 vector 对象，然后再动态地增加元素（我们随后将学习如何进行这样的操作）

2. 值初始化

如果没有给出元素的初始化式，那么标准库将提供一个 值初始化的 （ value initialized ）元素初始化式。这个由库生成的初始值用于初始化容器中的每个元素。而元素初始化式的值取决于存储在 vector 中元素的数据类型。

如果 vector 保存内置类型（如 int 类型） 的元素，那么标准库将用 0 值创建元素初始 化值：

vector<string> fvec(10); // 10 elements, each initialized to 0

如果向量保存类类型（如 string ）的元素，标准库将用该类型的默认构造函数 创建 元素初始值：

vector<string> svec(10); // 10 elements, each an empty string

第 12 章将介绍一些有自定义构造函数但没有默认构造函数的类，在初始化这种类型的 Vector 对象时，程序员就不能仅提供元素个数，还需要提供元素初始值。

还有第三种可能性：元素类型可能是没有定义任何构造函数的类类型。这种情况下，标准库仍产生一个带初始值的对象，这个对象的每个成员进行了值初始化。

习题

习题 3.11   下面哪些 vector 定义不正确？

( a ) vector < vector < int > > ivec ;

( b ) vector < string > svec = ivec ;

( c ) vector < string > svec ( 10 ,” null ”);

习题 3.12   下列每个 vector 对象中元素个数是多少？各元素的值是什么？

(a) vector<int> ivec1;

(b) vector<int> ivec2(10);

(c) vector<int> ivec3(10,42);

(d) vector<string> svec1;

(e) vector<string> svec2(10);

(f) vector<string> svec3(10,”hello”);

3.3.2   vector 的操作

vector 标准库提供许多类似于 string 对象的操作，表 3 - 5 列出了几种最重要的 vector 操作。

表 3-5  vector 操作

v. empty()

如果 v 为空，则返回 true, 否则返回 false 。

v . size ()

返回 v 中元素的个数。

v . push _ back ( t )

在 v 的末尾增加一个值为 t 的元素。

v [ n ]

返回 v 中位置为 n 的元素。

v1 = v2

把 v1 的元素替换为 v2 中元素的副本。

v1 == v2

如果 v1 与 v2 相等，则返回 true 。

!=, <, <=, >, >=

保持这些操作符惯有的含义。

1. vector 对象的 size

empty 和 size 操作类似于 string 类型的相关操作（ 3 . 2 . 3 节）。成员函数 size 返回相应 vector 类定义的 size_type 的值。

使用 size_type 类型时，必须指出该类型是在哪里定义的。 vector 类型总是 包括 vector 的元素类型：

vector<int>::size_type        // ok

vector::size_type          // error

2. 向 vector 添加元素

push_back() 操作接受一个元素值，并将它作为一个新的元素添加到 vector 对象的后面，也就是“ 插入 （ push ）” 到 vector 对象的 “ 后面 ( back ) ” ：

// read words from the standard input and store them as elements in a vector

string word;

vector<string> text;        // empty vector

while (cin >> word) {

text.push_back(word);  // append word to text

}

该循环 从标准输入读取一系列 string 对象，逐一追加到 vector 对象的后面。首先定义一个空的 vector 对象 text 。每循环一次就添加一个新元素到 vector 对象，并将从 输入 读取的 word 值赋予该元素。当循环结束时， text 就包含了所有读入的元素。

3. vector 的下标操作

vector 中的对象是没有命名的，可以按 vector 中对象的位置来访问它们。通常使用下标操作符来获取元素。 vector 的下标操作类似于 string 类型的下标操作 ( 3 .2 .3 节 ) 。

vector 的下标操作符接受一个值，并返回 vector 中该对应位置的元素。 vector 元素的位置从 0 开始。下例使用 for 循环把 vector 中的每个元素值都重置为 0 :

// reset the elements in the vector to zero

for (vector<int>::size_type ix = 0; ix != ivec.size(); ++ix)

ivec[ix] = 0;

和 string 类型的下标操作符一样， vector 下标操作的结果为左值，因此可以像循环体中所做的那样实现写入。另外，和 string 对象的下标操作类似，这里用 size_type 类型作为 vector 下标的类型。

在上例中，即使 ivec 为空， for 循环也会正确执行。 ivec 为空则调用 size 返回 0 ，并且 for 中的测试比较 ix 和 0 。第一次循环时，由于 ix 本身就是 0 ，则条件测试失败， for 循环体一次也不执行。

关键概念：安全的泛型编程

习惯于 C 或 Java 编程的 C ++ 程序员可能会觉得难以理解， for 循环的判断条件用 != 而不是用 < 来测试 vector 下标值是否越界。 C 程序员难以理解的还有，上例中没有在 for 循环之前就调用 size 成员函数并保存其返回的值，而是在 for 语句头中调用 size 成员函数。

C ++ 程序员习惯于优先选用 != 而不是 < 来编写循环判断条件。在上例中，选用或不用某种操作符并没有特别的取舍理由。学习完本书第二部分的泛型编程后，你将会明白这个习惯的合理性。

调用 size 成员函数而不保存它返回的值，在这个例子中同样不是必需的，但这反映了一个良好的编程习惯。在 C ++ 中，有些数据结构（如 vector ）可以动态增长。上例中循环仅需要读取元素，而不需要增加新的元素。但是，循环可以容易地增加新元素，如果确实增加了新元素的话，那么测试已保存的 size 值作为循环的结束条件就会有问题，因为没有将新加入的元素计算在内。所以我们倾向于在每次循环中测试 size 的当前值，而不是在进入循环时，存储 size 值的副本。

我们将在第 7 章学习到， C ++ 中有些函数可以声明为内联（ inline ）函数。编译器遇到内联函数时就会直接扩展相应代码，而不是进行实际的函数调用。像 size 这样的小库函数几乎都定义为内联函数，所以每次循环过程中调用它的运行时代价是比较小的。

4. 下标操作不添加元素

初学 C ++ 的程序员可能会认为 vector 的下标操作可以添加元素，其实不然：

vector<int> ivec;   // empty vector

for (vector<int>::size_type ix = 0; ix != 10; ++ix)

ivec[ix] = ix; // disaster: ivec has no elements

上述程序试图在 ivec 中插入 10 个新元素，元素值依次为 0 到 9 的整数。但是，这里 ivec 是空的 vector 对象，而且下标只能用于获取已存在的元素。

这个循环的正确写法应该是：

for (vector<int>::size_type ix = 0; ix != 10; ++ix)

ivec.push_back(ix);  // ok: adds new element with value ix

必须是已存在的元素才能用下标操作符进行索引。通过下标操作进行赋值时，不会添加任何元素。

警告：仅能对确知已存在的元素进行下标操作

对于下标操作符 ( [] 操作符 ) 的使用有一点非常重要，就是仅能提取确实已存在的元素，例如：

vector<int> ivec;      // empty vector

cout << ivec[0];        // Error: ivec has no elements!

vector<int> ivec2(10); // vector with 10 elements

cout << ivec[10];      // Error: ivec has elements 0...9

试图获取不存在的元素必然产生运行时错误。和大多数同类错误一样，不能确保执行过程可以捕捉到这类错误，运行程序的结果是不确定的。由于取不存在的元素的结果是未定义的，因而不同的实现会导致不同的结果，但程序运行时几乎肯定会以某种有趣的方式失败。

本警告适用于任何使用下标操作的时候，如 string 类型的下标操作，以及将要简要介绍的内置数组的下标操作。

不幸的是，试图对不存在的元素进行下标操作是程序设计过程中经常会犯的严重错误。所谓的“缓冲区溢出”错误就是对不存在的元素进行下标操作的结果。这样的缺陷往往导致 PC 机和其他应用中最常见的安全问题。

习题

习题 3.13  读一组整数到 vector 对象，计算并输出每对相邻元素的和。如果读入元素个数为奇数，则提示用户最后一个元素没有求和，并输出其值。然后修改程序：头尾元素两两配对（第一个和最后一个，第二个和倒数第二个，以此类推），计算每对元素的和，并输出。

习题 3.14  读入一段文本到 vector 对象，每个单词存储为 vector 中的一个元素。把 vector 对象中每个单词转化为大写字母。输出 vector 对象中转化后的元素，每八个单词为一行输出。

习题 3.15  下面程序合法吗？如果不合法，如何更正？

vector <int > ivec ;

ivec [0 ] = 42 ;

习题 3.16   列出三种定义 vector 对象的方法，给定 10 个元素，每个元素值为 42 。指出是否还有更好的实现方法，并说明为什么。