3.3. Library vector Type

3.3. 标准库 vector 类型

A vector is a collection of objects of a single type, each of which has an associated integer index. As with strings, the library takes care of managing the memory associated with storing the elements. We speak of a vector as a container because it contains other objects. All of the objects in a container must have the same type. We'll have much more to say about containers in Chapter 9.

vector 是同一种类型的对象的集合，每个对象都有一个对应的整数索引值。和 string 对象一样，标准库将负责管理与存储元素相关的内存。我们把 vector 称为容器，是因为它可以包含其他对象。一个容器中的所有对象都必须是同一种类型的。我们将在第九章更详细地介绍容器。

To use a vector, we must include the appropriate header. In our examples, we also assume an appropriate using declaration is made:

使用 vector 之前，必须包含相应的头文件。本书给出的例子，都是假设已作了相应的 using 声明：

     #include <vector>
     using std::vector;

A vector is a class template. Templates let us write a single class or function definition that can be used on a variety of types. Thus, we can define a vector that holds strings, or a vector to hold ints, or one to hold objects of our own class types, such as Sales_items. We'll see how to define our own class templates in Chapter 16. Fortunately, we need to know very little about how templates are defined in order to use them.

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

To declare objects of a type generated from a class template, we must supply additional information. The nature of this information depends on the template. In the case of vector, we must say what type of objects the vector will contain. We specify the type by putting it between a pair of angle brackets following the template's name:

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

     vector<int> ivec;               // ivec holds objects of type int
     vector<Sales_item> Sales_vec;   // holds Sales_items

As in any variable definition, we specify a type and a list of one or more variables. In the first of these definitions, the type is vector<int>, which is a vector that holds objects of type int. The name of the variable is ivec. In the second, we define Sales_vec to hold Sales_item objects.

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

3.3.1. Defining and Initializing vectors

3.3.1. vector 对象的定义和初始化

The vector class defines several constructors (Section 2.3.3, p. 49), which we use to define and initialize vector objects. The constructors are listed in Table 3.4.

vector 类定义了好几种构造函数（2.3.3 节），用来定义和初始化 vector 对象。表 3.4 列出了这些构造函数。

Table 3.4. Ways to Initialize a vector

vector<T> v1;	vector that holds objects of type T;
	Default constructor v1 is empty
	vector 保存类型为 T 对象。
	默认构造函数 v1 为空。
vector<T> v2(v1);	v2 is a copy of v1 v2 是 v1 的一个副本。
vector<T> v3(n, i);	v3 has n elements with value i v3 包含 n 个值为 i 的元素。
vector<T> v4(n);	v4 has n copies of a value-initialized object v4 含有值初始化的元素的 n 个副本。

Creating a Specified Number of Elements

创建确定个数的元素

When we create a vector that is not empty, we must supply value(s) to use to initialize the elements. When we copy one vector to another, each element in the new vector is initialized as a copy of the corresponding element in the original vector. The two vectors must hold the same element type:

若要创建非空的 vector 对象，必须给出初始化元素的值。当把一个 vector 对象复制到另一个 vector 对象时，新复制的 vector 中每一个元素都初始化为原 vectors 中相应元素的副本。但这两个 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

We can initialize a vector from a count and an element value. The constructor uses the count to determine how many elements the vector should have and uses the value to specify the value each of those elements will have:

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

     vector<int> ivec4(10, -1);       // 10 elements, each initialized to -1
     vector<string> svec(10, "hi!");  // 10 strings, each initialized to "hi!"

Key Concept: vectorS Grow Dynamically 关键概念：vector 对象动态增长 A central property of vectors (and the other library containers) is that they are required to be implemented so that it is efficient to add elements to them at run time. Because vectors grow efficiently, it is usually best to let the vector grow by adding elements to it dynamically as the element values are known. vector 对象（以及其他标准库容器对象）的重要属性就在于可以在运行时高效地添加元素。因为 vector 增长的效率高，在元素值已知的情况下，最好是动态地添加元素。 As we'll see in Chapter 4, this behavior is distinctly different from that of built-in arrays in C and for that matter in most other languages. In particular, readers accustomed to using C or Java might expect that because vector elements are stored contiguously, it would be best to preallocate the vector at its expected size. In fact, the contrary is the case, for reasons we'll explore in Chapter 9. 正如第四章将介绍的，这种增长方式不同于 C 语言中的内置数据类型，也不同于大多数其他编程语言的数据类型。具体而言，如果读者习惯了 C 或 Java 的风格，由于 vector 元素连续存储，可能希望最好是预先分配合适的空间。但事实上，为了达到连续性，C++ 的做法恰好相反，具体原因将在第九章探讨。 Although we can preallocate a given number of elements in a vector, it is usually more efficient to define an empty vector and add elements to it (as we'll learn how to do shortly). 虽然可以对给定元素个数的 vector 对象预先分配内存，但更有效的方法是先初始化一个空 vector 对象，然后再动态地增加元素（我们随后将学习如何进行这样的操作）。

Value Initialization

值初始化

When we do not specify an element initializer, then the library creates a value initialized element initializer for us. This library-generated value is used to initialize each element in the container. The value of the element initializer depends on the type of the elements stored in the vector.

如果没有指定元素的初始化式，那么标准库将自行提供一个元素初始值进行值初始化（value initializationd）。这个由库生成的初始值将用来初始化容器中的每个元素，具体值为何，取决于存储在 vector 中元素的数据类型。

If the vector holds elements of a built-in type, such as int, then the library creates an element initializer with a value of 0:

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

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

If the vector holds elements of a class type, such as string, that defines its own constructors, then the library uses the value type's default constructor to create the element initializer:

如果 vector 保存的是含有构造函数的类类型（如 string）的元素，标准库将用该类型的默认构造函数创建元素初始化式：

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

There is a third possibility: The element type might be of a class type that does not define any constructors. In this case, the library still creates a value-initialized object. It does so by value-initializing each member of that object.

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

Exercises Section 3.3.1 Exercise 3.11: Which, if any, of the following vector definitions are in error? 下面哪些 vector 定义不正确？ (a) vector< vector<int> > ivec; (b) vector<string> svec = ivec; (c) vector<string> svec(10, "null"); Exercise 3.12: How many elements are there in each of the following vectors? What are the values of the elements? 下列每个 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. Operations on vectors

3.3.2. vector 对象的操作

The vector library provides various operations, many of which are similar to operations on strings. Table 3.5 lists the most important vector operations.

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

Table 3.5. vector Operations

v.empty()	Returns true if v is empty; otherwise returns false 如果 v 为空，则返回 true，否则返回 false。
v.size()	Returns number of elements in v 返回 v 中元素的个数。
v.push_back(t)	Adds element with value t to end of v 在 v 的末尾增加一个值为 t 的元素。
v[n]	Returns element at position n in v 返回 v 中位置为 n 的元素。
v1 = v2	Replaces elements in v1 by a copy of elements in v2 把 v1 的元素替换为 v2 中元素的副本。
v1 == v2	Returns true if v1 and v2 are equal 如果 v1 与 v2 相等，则返回 true。
!=, <, <=, >, and >=	Have their normal meanings 保持这些操作符惯有的含义。

The size of a vector

vector 对象的 size

The empty and size operations are similar to the corresponding string operations (Section 3.2.3, p. 83). The size member returns a value of the size_type defined by the corresponding vector type.

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

     vector<int>::size_type        // ok
     vector::size_type            // error

Adding Elements to a vector

向 vector 添加元素

push_back operation takes an element value and adds that value as a new element at the back of a vector. In effect it "pushes" an element onto the "back" of the 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
     }

This loop reads a sequence of strings from the standard input, appending them one at a time onto the back of the vector. We start by defining text as an initially empty vector. Each trip through the loop adds a new element to the vector and gives that element the value of whatever word was read from the input. When the loop completes, text will have as many elements as were read.

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

Subscripting a vector

vector 的下标操作

Objects in the vector are not named. Instead, they can be accessed by their position in the vector. We can fetch an element using the subscript operator. Subscripting a vector is similar to subscripting a string (Section 3.2.3, p. 87).

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

The vector subscript operator takes a value and returns the element at that position in the vector. Elements in a vector are numbered beginning with 0. The following example uses a for loop to reset each element in the vector to 0:

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;

Like the string subscript operator, the vector subscript yields an lvalue so that we may write to it, which we do in the body of the loop. Also, as we do for strings, we use the size_type of the vector as the type for the subscript.

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

Subscripting Does Not Add Elements

下标操作不添加元素

Programmers new to C++ sometimes think that subscripting a vector adds elements; it does not:

初学 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

Key Concept: Safe, Generic Programming 关键概念：安全的泛型编程 Programmers coming to C++ from C or Java might be surprised that our loop used != rather than < to test the index against the size of the vector. C programmers are probably also suprised that we call the size member in the for rather than calling it once before the loop and remembering its value. 习惯于 C 或 Java 编程的 C++ 程序员可能会觉得难以理解，for 循环的判断条件用 != 而不是用 < 来测试 vector 下标值是否越界。C 程序员难以理解的还有，上例中没有在 for 循环之前就调用 size 成员函数并保存其返回的值，而是在 for 语句头中调用 size 成员函数。 C++ programmers tend to write loops using != in preference to < as a matter of habit. In this case, there is no particular reason to choose one operator or the other. We'll understand the rationale for this habit once we cover generic programming in Part II. C++ 程序员习惯于优先选用 != 而不是 < 来编写循环判断条件。在上例中，选用或不用某种操作符并没有特别的取舍理由。学习完本书第二部分的泛型编程后，你将会明白这种习惯的合理性。 Calling size rather than remembering its value is similarly unnecessary in this case but again reflects a good habit. In C++, data structures such as vector can grow dynamically. Our loop only reads elements; it does not add them. However, a loop could easily add new elements. If the loop did add elements, then testing a saved value of size would failour loop would not account for the newly added elements. Because a loop might add elements, we tend to write our loops to test the current size on each pass rather than store a copy of what the size was when we entered the loop. 调用 size 成员函数而不保存它返回的值，在这个例子中同样不是必需的，但这反映了一种良好的编程习惯。在 C++ 中，有些数据结构（如 vector）可以动态增长。上例中循环仅需要读取元素，而不需要增加新的元素。但是，循环可以容易地增加新元素，如果确实增加了新元素的话，那么测试已保存的 size 值作为循环的结束条件就会有问题，因为没有将新加入的元素计算在内。所以我们倾向于在每次循环中测试 size 的当前值，而不是在进入循环前，存储 size 值的副本。 As we'll see in Chapter 7, in C++ functions can be declared to be inline. When it can do so, the compiler will expand the code for an inline function directly rather than actually making a function call. Tiny library functions such as size are almost surely defined to be inline, so we expect that there is little run-time cost in making this call on each trip through the loop. 我们将在第七章学习到，C++ 中有些函数可以声明为内联（inline）函数。编译器遇到内联函数时就会直接扩展相应代码，而不是进行实际的函数调用。像 size 这样的小库函数几乎都定义为内联函数，所以每次循环过程中调用它的运行时代价是比较小的。

This code intended to insert new 10 elements into ivec, giving the elements the values from 0 through 9. However, ivec is an empty vector and subscripts can only be used to fetch existing elements.

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

The right way to write this loop would be

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

     for (vector<int>::size_type ix = 0; ix != 10; ++ix)
         ivec.push_back(ix);  // ok: adds new element with value ix

Caution: Only Subscript Elements that Are Known to Exist! 警告：仅能对确知已存在的元素进行下标操作 It is crucially important to understand that we may use the subscript operator, (the [] operator), to fetch only elements that actually exist. For example, 对于下标操作符（[] 操作符）的使用有一点非常重要，就是仅能提取确实已存在的元素，例如： 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 Attempting to fetch an element that doesn't exist is a run-time error. As with most such errors, there is no assurance that the implementation will detect it. The result of executing the program is uncertain. The effect of fetching a nonexisting element is undefinedwhat happens will vary by implementation, but the program will almost surely fail in some interesting way at run time. 试图获取不存在的元素必须产生运行时错误。和大多数同类错误一样，不能确保执行过程可以捕捉到这类错误，运行程序的结果是不确定的。由于取不存在的元素的结果标准没有定义，因而不同的编译器实现会导致不同的结果，但程序运行时几乎肯定会以某种有趣的方式失败。 This caution applies any time we use a subscript, such as when subscripting a string and, as we'll see shortly, when subscripting a built-in array. 本警告适用于任何使用下标操作的时候，如 string 类型的下标操作，以及将要简要介绍的内置数组的下标操作。 Attempting to subscript elements that do not exist is, unfortunately, an extremely common and pernicious programming error. So-called "buffer overflow" errors are the result of subscripting elements that don't exist. Such bugs are the most common cause of security problems in PC and other applications. 不幸的是，试图对不存在的元素进行下标操作是程序设计过程中经常会犯的严重错误。所谓的“缓冲区溢出”错误就是对不存在的元素进行下标操作的结果。这样的缺陷往往导致 PC 机和其他应用中最常见的安全问题。

Exercises Section 3.3.2 Exercise 3.13: Read a set of integers into a vector. Calculate and print the sum of each pair of adjacent elements in the vector. If there is an odd number, tell the user and print the value of the last element without summing it. Now change your program so that it prints the sum of the first and last elements, followed by the sum of the second and second-to-last and so on. 读一组整数到 vector 对象，计算并输出每对相邻元素的和。如果读入元素个数为奇数，则提示用户最后一个元素没有求和，并输出其值。然后修改程序：头尾元素两两配对（第一个和最后一个，第二个和倒数第二个，以此类推），计算每对元素的和，并输出。 Exercise 3.14: Read some text into a vector, storing each word in the input as an element in the vector. transform each word into uppercase letters. Print the transformed elements from the vector, printing eight words to a line. 读入一段文本到 vector 对象，每个单词存储为 vector 中的一个元素。把 vector 对象中每个单词转化为大写字母。输出 vector 对象中转化后的元素，每八个单词为一行输出。 Exercise 3.15: Is the following program legal? If not, how might you fix it? 下面程序合法吗？如果不合法，如何更正？ vector<int> ivec; ivec[0] = 42; Exercise 3.16: List three ways to define a vector and give it 10 elements, each with the value 42. Indicate whether there is a preferred way to do so and why. 列出三种定义 vector 对象的方法，给定 10 个元素，每个元素值为 42。指出是否还有更好的实现方法，并说明为什么。