Section 9.5. Deciding Which Container to Use


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 costs to add or delete elements from the middle of the container

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

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.

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.

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.

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:

  • Like vector, it is inefficient to insert or erase elements in the middle of the deque.

  • Unlike vector, a deque offers efficient insert and erase at the front as well as at the back.

  • Unlike list and like vector, a deque supports fast random access to any element.

  • Inserting elements at the front or back of a deque does not invalidate any iterators. Erasing the front or back element invalidates only iterators referring to the element(s) erased. Inserting or erasing anywhere else in the deque invalidates all iterators referring to elements of the deque.

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.

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



Hints on Selecting Which Container to Use

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

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

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

  3. 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.

  4. 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.

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.

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.





C++ Primer
C Primer Plus (5th Edition)
ISBN: 0672326965
EAN: 2147483647
Year: 2006
Pages: 223
Authors: Stephen Prata

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net