vector容器的自增长外文翻译

1、vector 容器的自增长 Addison Wesley Professional ， C+ Primer, Fourth Edition在容器对象中 insert 或压入一个元素时，该对象的大小增加 1。类似地，如果 resize 容器以扩充其容量，则必须在容器中添加额外的元素。标准库处理存储这些新元素的内存分配问题。一般来说，我们不应该关心标准库类型是如何实现的：我们只需要关心如何使用这些标准库类型就可以了。然而，对于 vector 容器，有一些实现也与其接口相关。为了支持快速的随机访问，vector 容器的元素以连续的方式存放每一个元素都紧挨着前一个元素存储。已知元素是连续存储的，当我们

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

3、存储空间，也不必复制任何已存在的元素。由此可以推论：一般而言，使用 list 容器优于 vector 容器。但是，通常出现的反而是以下情况：对于大部分应用，使用 vector 容器是最好的。原因在于，标准库的实现者使用这样内存分配策略：以最小的代价连续存储元素。由此而带来的访问元素的便利弥补了其存储代价。为了使 vector 容器实现快速的内存分配，其实际分配的容量要比当前所需的空间多一些。vector 容器预留了这些额外的存储区，用于存放新添加的元素。于是，不必为每个新元素重新分配容器。所分配的额外内存容量的确切数目因库的实现不同而不同。比起每添加一个新元素就必须重新分配一次容器，这个分配策

4、略带来显著的效率。事实上，其性能非常好，因此在实际应用中，比起 list 和 deque 容器，vector 的增长效率通常会更高。capacity 和 reserve 成员vector容器处理内存分配的细节是其实现的一部分。然而，该实现部分是由 vector的接口支持的。vector 类提供了两个成员函数：capacity和reserve使程序员可与 vector 容器内存分配的实现部分交互工作。capacity操作获取在容器需要分配更多的存储空间之前能够存储的元素总数，而reserve操作则告诉 vector容器应该预留多少个元素的存储空间。注意: 弄清楚容器的capacity（容量）与s

5、ize（长度）的区别非常重要。size 指容器当前拥有的元素个数；而capacity则指容器在必须分配新存储空间之前可以存储的元素总数。为了说明 size（长度）和 capacity（容量）的交互作用，考虑下面的程序：vector<int> ivec; / size should be zero; capacity is implementation defined(长度应该为0；容量则是定义工具) cout << "ivec: size: " << ivec.size() << " capacity: "

6、 << ivec.capacity() << endl; / give ivec 24 elements (给ivec24个元素) 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 (长度应该为24；容量将会>=24，并且是定义工具) cout << "ivec: size: "

7、<< ivec.size() << " capacity: " << ivec.capacity() << endl;在我们的系统上运行该程序时，得到以下输出结果： ivec: size: 0 capacity: 0 /(ivec:长度是0；容量是0) ivec: size: 24 capacity: 32 /(ivec:长度是24；容量是32)由此可见，空 vector 容器的 size 是 0，而标准库显然将其 capacity 也设置为 0。当程序员在 vector 中插入元素时，容器的 size 就是所添加的元素个数，

8、而其 capacity 则必须至少等于 size，但通常比 size 值更大。在上述程序中，一次添加一个元素，共添加了 24 个元素，结果其 capacity 为 32。 容器的当前状态如下图所示：01223Reserver capacityivec.size()ivec.capacity()现在，可如下预留额外的存储空间： ivec.reserve(50); / sets capacity to at least 50; might be more(容量至少设置50，或者更多) / size should be 24; capacity will be >= 50 and is imp

9、lementation defined(长度应该为24；容量将会>=50，并且是定义工具) cout << "ivec: size: " << ivec.size() << " capacity: " << ivec.capacity() << endl;正如下面的输出结果所示，该操作保改变了容器的 capacity，而其 size 不变： ivec: size: 24 capacity: 50 /(ivec:长度是24；容量是50)下面的程序将预留的容量用完： /add elements

10、 to use up the excess capacity(增加元素用尽超额容量) while (ivec.size() != ivec.capacity() ivec.push_back(0); / size should be 50; capacity should be unchanged(长度应该为50；容量应该未被改变) cout << "ivec: size: " << ivec.size() << " capacity: " << ivec.capacity() << endl;

11、由于在该程序中，只使用了预留的容量，因此 vector 不必做任何的内存分配工作。事实上，只要有剩余的容量，vector 就不必为其元素重新分配存储空间。其输出结果表明：此时我们已经耗尽了预留的容量，该容器的 size 和 capacity 值相等： ivec: size: 50 capacity: 50 /(ivec:长度是50；容量是50)此时，如果要添加新的元素，vector 必须为自己重新分配存储空间： ivec.push_back(42); / add one more element(增加更多的元素) / size should be 51; capacity will be &g

12、t;= 51 and is implementation defined(长度应该为51；容量将会>=51，并且是定义工具) cout << "ivec: size: " << ivec.size() << " capacity: " << ivec.capacity() << endl;这段程序的输出：ivec: size: 51 capacity: 100 /(ivec:长度是51；容量是100)表明：每当 vector 容器不得不分配新的存储空间时，以加倍当前容量的分配策略实现重新分

13、配。注意:vector 的每种实现都可自由地选择自己的内存分配策略。然而，它们都必须提供 vector 和 capacity 函数，而且必须是到必要时才分配新的内存空间。分配多少内存取决于其实现方式。不同的库采用不同的策略实现。此外，每种实现都要求遵循以下原则：确保 push_back 操作高效地在 vector 中添加元素。从技术上来说，在原来为空的 vector 容器上 n 次调用 push_back 函数，从而创建拥有 n 个元素的 vector 容器，其执行时间永远不能超过 n 的常量倍。7 / 7文档可自由编辑打印How a vector GrowsWhen we insert or

14、 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.Ordinarily,

15、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.

16、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 m

17、ust 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 unacc

18、eptably slow.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

19、 elements.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 c

20、osts of storing elements contiguously. That cost is usually offset by the advantages in accessing elements that contiguous storage allows.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 alloc

21、ate 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 contain

22、er 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.capacity and reserve MembersThe details of how vector handles its memory allocation are part of its implementation. However, a portion of this imp

23、lementation 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 mo

24、re space. The reserve operation lets us tell the vector how many elements it should be prepared to hold.NOTE: 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 allocate

25、d.To illustrate the interaction between size and capacity, consider the following program:vector<int> ivec; / size should be zero; capacity is implementation defined cout << "ivec: size: " << ivec.size() << " capacity: " << ivec.capacity() << e

26、ndl; / 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()

27、<< endl;When run on our system, this program produces the following output:ivec: size: 0 capacity: 0 ivec: size: 24 capacity: 32We 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

28、 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 as01223Reserver capacity

29、ivec.capacity()ivec.size() 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: &qu

30、ot; << ivec.capacity() << endl;As the output indicates, doing so changes the capacity but not the size:ivec: size: 24 capacity: 50We 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);

31、/ 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 ther

32、e is excess capacity, the vector must not reallocate its elements.The output indicates that at this point we've used up the reserved capacity, and size and capacity are equal: ivec: size: 50 capacity: 50If we now add another element, the vector will have to reallocate itself: ivec.push_back(42); / add one more ele