Deque

The deque container is a basic sequence optimized for adding and removing elements from either end. It also allows for reasonably fast random access?it has an operator[ ] like vector. However, it does not have vector?s constraint of keeping everything in a single sequential block of memory. Instead, a typical implementation of deque uses multiple blocks of sequential storage (keeping track of all the blocks and their order in a mapping structure). For this reason, the overhead for a deque to add or remove elements at either end is low. In addition, it never needs to copy and destroy contained objects during a new storage allocation (like vector does), so it is far more efficient than vector if you are adding an unknown quantity of objects. This means that vector is the best choice only if you have a good idea of how many objects you need. In addition, many of the programs shown earlier in this book that use vector and push_back( ) might be more efficient with a deque. The interface to deque is only slightly different from a vector (deque has a push_front( ) and pop_front( ) while vector does not, for example), so converting code from using vector to using deque is almost trivial. Consider StringVector.cpp, which can be changed to use deque by replacing the word ?vector? with ?deque? everywhere. The following program adds parallel deque operations to the vector operations in StringVector.cpp and performs timing comparisons:

Knowing now what you do about the inefficiency of adding things to vector because of storage reallocation, you might expect dramatic differences between the two. However, on a 1.7MB text file, one compiler?s program produced the following (measured in platform/compiler specific clock ticks, not seconds):

Read into vector: 8350
Read into deque: 7690
Indexing vector: 2360
Indexing deque: 2480
Iterating vector: 2470
Iterating deque: 2410

A different compiler and platform roughly agreed with this. It?s not so dramatic, is it? This points out some important issues:

1. We (programmers) are typically bad at guessing where inefficiencies occur in our programs.
2. Efficiency comes from a combination of effects. Here, reading the lines in and converting them to strings may dominate over the cost of the vector vs. deque.
3. The string class is probably fairly well designed in terms of efficiency.
Of course, this doesn?t mean you shouldn?t use a deque rather than a vector when you know that an uncertain number of objects will be pushed onto the end of the container. On the contrary, you should?when you?re tuning for performance. But you should also be aware that performance issues are usually not where you think they are, and the only way to know for sure where your bottlenecks are is by testing.

Share
Tweet
Share
Pin