Deciding Which Sequential Container to Use

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.