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.
If you’re not sure which container to use, write your code so that it uses only operations common to both vector
s and list
s: 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.
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.