Section 9.5. Deciding Which Container to Use

As we saw in the previous section, allocating memory to hold elements in contiguous storage has impacts on the memory allocation strategies and overhead of a container. By using clever implementation techniques, library authors minimize this allocation overhead. Whether elements are stored contiguously has other significant impacts on:

在前面的章节中可见，分配连续存储元素的内存空间会影响内存分配策略和容器对象的开销。通过巧妙的实现技巧，标准库的实现者已经最小化了内存分配的开销。元素是否连续存储还会显著地影响：

The degree to which a program does these operations should be used to determine which type of container to use. The vector and deque types provide fast non-sequential access to elements at the cost of making it expensive to add or remove elements anywhere other than the ends of the container. The list type supports fast insertion and deletion anywhere but at the cost of making nonsequential access to elements expensive.

程序使用这些操作的程序将决定应该选择哪种类型的容器。vector 和 deque 容器提供了对元素的快速随机访问，但付出的代价是，在容器的任意位置插入或删除元素，比在容器尾部插入和删除的开销更大。list 类型在任何位置都能快速插入和删除，但付出的代价是元素的随机访问开销较大。

How Insertion Affects Choice of Container

插入操作如何影响容器的选择

A list represents noncontiguous memory and allows for both forward and backward traversal one element at a time. It is efficient to insert or erase an element at any point. Inserting or removing an element in a list does not move any other elements. Random access, on the other hand, is not supported. Accessing an element requires traversing the intervening elements.

list 容器表示不连续的内存区域，允许向前和向后逐个遍历元素。在任何位置都可高效地 insert 或 erase 一个元素。插入或删除 list 容器中的一个元素不需要移动任何其他元素。另一方面，list 容器不支持随机访问，访问某个元素要求遍历涉及的其他元素。

Inserting (or removing) anywhere except at the back of a vector requires that each element to the right of the inserted (or deleted) element be moved. For example, if we have a vector with 50 elements and we wish to erase element number 23, then each of the elements after 23 have to be moved forward by one position. Otherwise, there'd be a hole in the vector, and the vector elements would no longer be contiguous.

对于 vector 容器，除了容器尾部外，其他任何位置上的插入（或删除）操作都要求移动被插入（或删除）元素右边所有的元素。例如，假设有一个拥有 50 个元素的 vector 容器，我们希望删除其中的第 23 号元素，则 23 号元素后面的所有元素都必须向前移动一个位置。否则， vector 容器上将会留下一个空位（hole），而 vector 容器的元素就不再是连续存放的了。

A deque is a more complicated data structure. We are guaranteed that adding or removing elements from either end of the deque is a fast operation. Adding or removing from the middle will be more expensive. A deque offers some properties of both list and vector:

deque 容器拥有更加复杂的数据结构。从 deque 队列的两端插入和删除元素都非常快。在容器中间插入或删除付出的代价将更高。 deque 容器同时提供了 list 和 vector 的一些性质：

How Access to the Elements Affects Choice of Container

元素的访问如何影响容器的选择

Both vector and deque support efficient random access to their elements. That is, we can efficiently access element 5, then 15, then 7, and so on. Random access in a vector can be efficient because each access is to a fixed offset from the beginning of the vector. It is much slower to jump around in a list. the only way to move between the elements of a list is to sequentially follow the pointers. Moving from the 5th to the 15th element requires visiting every element between them.

vector 和 deque 容器都支持对其元素实现高效的随机访问。也就是说，我们可以高效地先访问 5 号元素，然后访问 15 号元素，接着访问 7 号元素，等等。由于 vector 容器的每次访问都是距离其起点的固定偏移，因此其随机访问非常有效率。在 list 容器中，上述跳跃访问会变得慢很多。在 list 容器的元素之间移动的唯一方法是顺序跟随指针。从 5 号元素移动到 15 号元素必须遍历它们之间所有的元素。

In general, unless there is a good reason to prefer another container, vector is usually the right one to use.

通常来说，除非找到选择使用其他容器的更好理由，否则 vector 容器都是最佳选择。

Hints on Selecting Which Container to Use

选择容器的提示

If the program requires random access to elements, use a vector or a deque.

如果程序要求随机访问元素，则应使用 vector 或 deque 容器。
If the program needs to insert or delete elements in the middle of the container, use a list.

如果程序必须在容器的中间位置插入或删除元素，则应采用 list 容器。
If the program needs to insert or delete elements at the front and the back, but not in the middle, of the container, use a deque.

如果程序不是在容器的中间位置，而是在容器首部或尾部插入或删除元素，则应采用 deque 容器。
If we need to insert elements in the middle of the container only while reading input and then need random access to the elements, consider reading them into a list and then reordering the list as appropriate for subsequent access and copying the reordered list into a vector.

如果只需在读取输入时在容器的中间位置插入元素，然后需要随机访问元素，则可考虑在输入时将元素读入到一个 list 容器，接着对此容器重新排序，使其适合顺序访问，然后将排序后的 list 容器复制到一个 vector 容器。

What if the program needs to randomly access and insert and delete elements in the middle of the container?

如果程序既需要随机访问又必须在容器的中间位置插入或删除元素，那应该怎么办呢？

This decision will depend on the relative cost of doing random access to list elements versus the cost of copying elements when inserting or deleting elements in a vector or deque. In general, the predominant operation of the application (whether it does more access or more insertion or deletion) should determine the choice of container type.

此时，选择何种容器取决于下面两种操作付出的相对代价：随机访问 list 容器元素的代价，以及在 vector 或 deque 容器中插入／删除元素时复制元素的代价。通常来说，应用中占优势的操作（程序中更多使用的是访问操作还是插入／删除操作）将决定应该什么类型的容器。

Deciding which container to use may require profiling the performance of each container type doing the kinds of operations the application requires.

决定使用哪种容器可能要求剖析各种容器类型完成应用所要求的各类操作的性能。

When you are not certain which container the application should use, try to write your code so that it uses only operations common to both vectors and lists: Use iterators, not subscripts, and avoid random access to elements. By writing your programs this way, it will be easier to change the container from a vector to a list if necessary.

如果无法确定某种应用应该采用哪种容器，则编写代码时尝试只使用 vector 和 lists 容器都提供的操作：使用迭代器，而不是下标，并且避免随机访问元素。这样编写，在必要时，可很方便地将程序从使用 vector 容器修改为使用 list 的容器。

9.5. Deciding Which Container to Use