9.1. Overview of the Sequential Containers

The sequential containers, which are listed in Table 9.1, all provide fast sequential access to their elements. However, these containers offer different performance trade-offs relative to

• The costs to add or delete elements to the container

• The costs to perform nonsequential access to elements of the container

Table 9.1. Sequential Container Types

With the exception of array, which is a fixed-size container, the containers provide efficient, flexible memory management. We can add and remove elements, growing and shrinking the size of the container. The strategies that the containers use for storing their elements have inherent, and sometimes significant, impact on the efficiency of these operations. In some cases, these strategies also affect whether a particular container supplies a particular operation.

For example, string and vector hold their elements in contiguous memory. Because elements are contiguous, it is fast to compute the address of an element from its index. However, adding or removing elements in the middle of one of these containers takes time: All the elements after the one inserted or removed have to be moved to maintain contiguity. Moreover, adding an element can sometimes require that additional storage be allocated. In that case, every element must be moved into the new storage.

The list and forward_list containers are designed to make it fast to add or remove an element anywhere in the container. In exchange, these types do not support random access to elements: We can access an element only by iterating through the container. Moreover, the memory overhead for these containers is often substantial, when compared to vector, deque, and array.

A deque is a more complicated data structure. Like string and vector, deque supports fast random access. As with string and vector, adding or removing elements in the middle of a deque is a (potentially) expensive operation. However, adding or removing elements at either end of the deque is a fast operation, comparable to adding an element to a list or forward_list.

The forward_list and array types were added by the new standard. An array is a safer, easier-to-use alternative to built-in arrays. Like built-in arrays, library arrays have fixed size. As a result, array does not support operations to add and remove elements or to resize the container. A forward_list is intended to be comparable to the best handwritten, singly linked list. Consequently, forward_list does not have the size operation because storing or computing its size would entail overhead compared to a handwritten list. For the other containers, size is guaranteed to be a fast, constant-time operation.

Note

For reasons we’ll explain in § 13.6 (p. 531), the new library containers are dramatically faster than in previous releases. The library containers almost certainly perform as well as (and usually better than) even the most carefully crafted alternatives. Modern C++ programs should use the library containers rather than more primitive structures like arrays.

Deciding Which Sequential Container to Use

Tip

Ordinarily, it is best to use vector unless there is a good reason to prefer another container.

There are a few rules of thumb that apply to selecting which container to use:

• Unless you have a reason to use another container, use a vector.

• If your program has lots of small elements and space overhead matters, don’t use list or forward_list.

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

• If the program needs to insert or delete elements in the middle of the container, use a list or forward_list.

• If the program needs to insert or delete elements at the front and the back, but not in the middle, use a deque.

• If the program needs to insert elements in the middle of the container only while reading input, and subsequently needs random access to the elements:

– First, decide whether you actually need to add elements in the middle of a container. It is often easier to append to a vector and then call the library sort function (which we shall cover in § 10.2.3 (p. 384)) to reorder the container when you’re done with input.

– If you must insert into the middle, consider using a list for the input phase. Once the input is complete, copy the list into a vector.

What if the program needs random access and needs to insert and delete elements in the middle of the container? This decision will depend on the relative cost of accessing the elements in a list or forward_list versus the cost of 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) will determine the choice of container type. In such cases, performance testing the application using both containers will probably be necessary.

Best Practices

If you’re not sure which container to use, 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. That way it will be easy to use either a vector or a list as necessary.

Exercises Section 9.1

Exercise 9.1: Which is the most appropriate—a vector, a deque, or a list—for the following program tasks? Explain the rationale for your choice. If there is no reason to prefer one or another container, explain why not.

(a) Read a fixed number of words, inserting them in the container alphabetically as they are entered. We’ll see in the next chapter that associative containers are better suited to this problem.

(b) Read an unknown number of words. Always insert new words at the back. Remove the next value from the front.

(c) Read an unknown number of integers from a file. Sort the numbers and then print them to standard output.