9.4. How a vector Grows

9.4. vector 容器的自增长

When we insert or push an element onto a container object, the size of that object increases by one. Similarly, if we resize a container to be larger than its current size, then additional elements must be added to the container. The library takes care of allocating the memory to hold these new elements.

在容器对象中 insert 或压入一个元素时，该对象的大小增加 1。类似地，如果 resize 容器以扩充其容量，则必须在容器中添加额外的元素。标准库处理存储这些新元素的内存分配问题。

Ordinarily, we should not care about how a library type works: All we should care about is how to use it. However, in the case of vectors, a bit of the implementation leaks into its interface. To support fast random access, vector elements are stored contiguouslyeach element is adjacent to the previous element.

一般来说，我们不应该关心标准库类型是如何实现的：我们只需要关心如何使用这些标准库类型就可以了。然而，对于 vector 容器，有一些实现也与其接口相关。为了支持快速的随机访问，vector 容器的元素以连续的方式存放——每一个元素都紧挨着前一个元素存储。

Given that elements are contiguous, let's think about what happens when we add an element to a vector: If there is no room in the vector for the new element, it cannot just add an element somewhere else in memory because the elements must be contiguous for indexing to work. Instead, the vector must allocate new memory to hold the existing elements plus the new one, copy the elements from the old location into the new space, add the new element, and deallocate the old memory. If vector did this memory allocation and deallocation each time we added an element, then performance would be unacceptably slow.

已知元素是连续存储的，当我们在容器内添加一个元素时，想想会发生什么事情：如果容器中已经没有空间容纳新的元素，此时，由于元素必须连续存储以便索引访问，所以不能在内存中随便找个地方存储这个新元素。于是，vector 必须重新分配存储空间，用来存放原来的元素以及新添加的元素：存放在旧存储空间中的元素被复制到新存储空间里，接着插入新元素，最后撤销旧的存储空间。如果 vector 容器在在每次添加新元素时，都要这么分配和撤销内存空间，其性能将会非常慢，简直无法接受。

There is no comparable allocation issue for containers that do not hold their elements contiguously. For example, to add an element to a list, the library only needs to create the new element and chain it into the existing list. There is no need to reallocate or copy any of the existing elements.

对于不连续存储元素的容器，不存在这样的内存分配问题。例如，在 list 容器中添加一个元素，标准库只需创建一个新元素，然后将该新元素连接在已存在的链表中，不需要重新分配存储空间，也不必复制任何已存在的元素。

One might conclude, therefore, that in general it is a good idea to use a list rather than a vector. However, the contrary is usually the case: For most applications the best container to use is a vector. The reason is that library implementors use allocation strategies that minimize the costs of storing elements contiguously. That cost is usually offset by the advantages in accessing elements that contiguous storage allows.

由此可以推论：一般而言，使用 list 容器优于 vector 容器。但是，通常出现的反而是以下情况：对于大部分应用，使用 vector 容器是最好的。原因在于，标准库的实现者使用这样内存分配策略：以最小的代价连续存储元素。由此而带来的访问元素的便利弥补了其存储代价。

The way vectors achieve fast allocation is by allocating capacity beyond what is immediately needed. The vector holds this storage in reserve and uses it to allocate new elements as they are added. Thus, there is no need to reallocate the container for each new element. The exact amount of additional capacity allocated varies across different implementations of the library. This allocation strategy is dramatically more efficient than reallocating the container each time an element is added. In fact, its performance is good enough that in practice a vector usually grows more efficiently than a list or a deque.

为了使 vector 容器实现快速的内存分配，其实际分配的容量要比当前所需的空间多一些。vector 容器预留了这些额外的存储区，用于存放新添加的元素。于是，不必为每个新元素重新分配容器。所分配的额外内存容量的确切数目因库的实现不同而不同。比起每添加一个新元素就必须重新分配一次容器，这个分配策略带来显著的效率。事实上，其性能非常好，因此在实际应用中，比起 list 和 deque 容器，vector 的增长效率通常会更高。

9.4.1. capacity and reserve Members

9.4.1. capacity 和 reserve 成员

The details of how vector handles its memory allocation are part of its implementation. However, a portion of this implementation is supported by the interface to vector. The vector class includes two members, capacity and reserve, that let us interact with the memory-allocation part of vector's implementation. The capacity operation tells us how many elements the container could hold before it must allocate more space. The reserve operation lets us tell the vector how many elements it should be prepared to hold.

vector 容器处理内存分配的细节是其实现的一部分。然而，该实现部分是由 vector 的接口支持的。vector 类提供了两个成员函数：capacity 和 reserve 使程序员可与 vector 容器内存分配的实现部分交互工作。capacity 操作获取在容器需要分配更多的存储空间之前能够存储的元素总数，而 reserve 操作则告诉 vector 容器应该预留多少个元素的存储空间。

It is important to understand the difference between capacity and size. The size is the number of elements in the vector; capacity is how many it could hold before new space must be allocated. 弄清楚容器的 capacity（容量）与 size（长度）的区别非常重要。size 指容器当前拥有的元素个数；而 capacity 则指容器在必须分配新存储空间之前可以存储的元素总数。

To illustrate the interaction between size and capacity, consider the following program:

为了说明 size 和 capacity 的交互作用，考虑下面的程序：

     vector<int> ivec;

     // size should be zero; capacity is implementation defined
     cout << "ivec: size: " << ivec.size()
          << " capacity: "  << ivec.capacity() << endl;

     // give ivec 24 elements
     for (vector<int>::size_type ix = 0; ix != 24; ++ix)
          ivec.push_back(ix);

     // size should be 24; capacity will be >= 24 and is implementation defined
     cout << "ivec: size: " << ivec.size()
          << " capacity: "  << ivec.capacity() << endl;

When run on our system, this program produces the following output:

在我们的系统上运行该程序时，得到以下输出结果：

     ivec: size: 0 capacity: 0
     ivec: size: 24 capacity: 32

We know that the size of an empty vector is zero, and evidently our library also sets capacity of an empty vector to zero. When we add elements to the vector, we know that the size is the same as the number of elements we've added. The capacity must be at least as large as size but can be larger. Under this implementation, adding 24 elements one at a time results in a capacity of 32. Visually we can think of the current state of ivec as

由此可见，空 vector 容器的 size 是 0，而标准库显然将其 capacity 也设置为 0。当程序员在 vector 中插入元素时，容器的 size 就是所添加的元素个数，而其 capacity 则必须至少等于 size，但通常比 size 值更大。在上述程序中，一次添加一个元素，共添加了 24 个元素，结果其 capacity 为 32。 容器的当前状态如下图所示：

We could now reserve some additional space:

现在，可如下预留额外的存储空间：

     ivec.reserve(50);  // sets capacity to at least 50; might be more
     // size should be 24; capacity will be >= 50 and is implementation defined
     cout << "ivec: size: " << ivec.size()
          << " capacity: "  << ivec.capacity() << endl;

As the output indicates, doing so changes the capacity but not the size:

正如下面的输出结果所示，该操作保改变了容器的 capacity，而其 size 不变：

     ivec: size: 24 capacity: 50

We might next use up that reserved capacity as follows:

下面的程序将预留的容量用完：

     // add elements to use up the excess capacity
     while (ivec.size() != ivec.capacity())
          ivec.push_back(0);
     // size should be 50; capacity should be unchanged
     cout << "ivec: size: " << ivec.size()
          << " capacity: "  << ivec.capacity() << endl;

Because we used only reserved capacity, there is no need for the vector to do any allocation. In fact, as long as there is excess capacity, the vector must not reallocate its elements.

由于在该程序中，只使用了预留的容量，因此 vector 不必做任何的内存分配工作。事实上，只要有剩余的容量，vector 就不必为其元素重新分配存储空间。

The output indicates that at this point we've used up the reserved capacity, and size and capacity are equal:

其输出结果表明：此时我们已经耗尽了预留的容量，该容器的 size 和 capacity 值相等：

     ivec: size: 50 capacity: 50

If we now add another element, the vector will have to reallocate itself:

此时，如果要添加新的元素，vector 必须为自己重新分配存储空间：

     ivec.push_back(42); // add one more element
     // size should be 51; capacity will be >= 51 and is implementation defined
     cout << "ivec: size: " << ivec.size()
          << " capacity: "  << ivec.capacity() << endl;

The output from this portion of the program

这段程序的输出：

     ivec: size: 51 capacity: 100

indicates that this vector implementation appears to follow a strategy of doubling the current capacity each time it has to allocate new storage.

表明：每当 vector 容器不得不分配新的存储空间时，以加倍当前容量的分配策略实现重新分配。

Each implementation of vector is free to choose its own allocation strategy. However, it must provide the reserve and capacity functions, and it must not allocate new memory until it is forced to do so. How much memory it allocates is up to the implementation. Different libraries will implement different strategies. vector 的每种实现都可自由地选择自己的内存分配策略。然而，它们都必须提供 vector 和 capacity 函数，而且必须是到必要时才分配新的内存空间。分配多少内存取决于其实现方式。不同的库采用不同的策略实现。

Moreover, every implementation is required to follow a strategy that ensures that it is efficient to use push_back to populate a vector. Technically speaking, the execution time of creating an n-element vector by calling push_back n times on an initially empty vector is never more than a constant multiple of n.

此外，每种实现都要求遵循以下原则：确保 push_back 操作高效地在 vector 中添加元素。从技术上来说，在原来为空的 vector 容器上 n 次调用 push_back 函数，从而创建拥有 n 个元素的 vector 容器，其执行时间永远不能超过 n 的常量倍。