If you need to deal off both the top and the bottom, you can't beat a deque.
Introduction
The header <deque> defines the template class deque, yet another of the template container classes defined by the Standard Template Library (STL). So far, I have described template class vector and template class list, the two simplest containers. (See "Standard C/C++: Containers," CUJ, December 1996, "Standard C/C++: The Header <vector>," CUJ, January 1997, and "Standard C/C++: The Header <list>," CUJ, February 1997.) deque, by contrast is rather more ambitious.
As an aside, there seems to be two schools of thought as to how to pronounce "deque." I've always pronounced it as a homophone for "deck." It is indeed a queue that behaves much like a deck of cards — you can add or remove elements at either end with equal ease. But I've heard others pronounce it "DEE-queue," probably with an equally convincing rationale. Take your pick.
Table 1 shows the payoff for the added complexity in template class deque. It is the only container besides vector that supports random-access iterators. (You can tell this because accessing an arbitrary element, with the expression X[N], is a constant-time operation.) But it outperforms vector in one significant way — you can add or remove elements at the beginning of the controlled sequence in constant time. You can do the same at the end, of course, but this distinction is not so clear cut. There are circumstances under which appending to a vector can be a constant-time operation as well, as I discussed in the January 1997 installment.
A deque is thus as good as a list for implementing a first-in first-out (FIFO) queue or a last-in first-out (LIFO) queue, also known as a stack. It is not as good as a list for implementing a priority queue, because it takes longer on average to insert a new item at an arbitrary place — linear time versus constant time. If you need random access to the elements of a controlled sequence, however, a deque beats a list any day.
Table 1 raises an interesting question. A deque matches or exceeds a vector in the time complexity of all operations, so why should you ever use a vector? There are two answers. One is that a deque has greater storage overhead than a vector, averaging at least one additional pointer per element. That may or may not be important, depending on the amount of useful data stored in each element and the total number of elements simultaneously used by a given application.
A more important issue is the cost of each operation. Accessing an arbitrary element of a deque may be a constant-time operation, on average, but it is still rather more expensive than accessing an arbitrary element of a vector. A given application may not benefit sufficiently from the added flexibility of a deque to justify the added overheads in code space and execution time, compared to analogous operations on vectors.
In summary, you can look at a deque as an interesting compromise between a vector and a list. Choose one of these two simpler containers if it has acceptable time complexity for the most used operations, in a given application. Choose a deque when its unique balance of properties justifies the added complexity it introduces.
How to Stack a Deque
Template class deque stores a controlled sequence of length N as a two-level hierarchy:
- Deque elements are stored in fixed-size blocks, which are contiguous arrays of DEQUESIZ elements.
- Each block is designated by an element in a map, which is an array of pointers to blocks stored inside a larger containing array, which contains at least DEQUEMAPSIZ elements.
Needless to say, both DEQUESIZ and DEQUEMAPSIZ are parameters subject to tradeoffs. The smaller they are, the less storage wasted for short controlled sequences. The larger they are, the less time wasted in growing large controlled sequences. The implementation I show here endeavors to allocate blocks of at least 2-4 KB, and keeps maps as small as possible.
If Map is a pointer to the beginning of the map, then element N of the controlled sequence is essentially located by the expression:
Map[N / DEQUESIZ][N % DEQUESIZ]The actual logic is a bit messier, for a variety of reasons, but this is the principle underlying the data structure.
The blocks at the beginning and end of a deque can be partially filled. (A partial block at the beginning of a deque is one of the messy details I glossed over above.) Blocks at the end fill from front to back while those at the beginning fill from back to front. If no room exists to add a block, the deque object allocates another block and extends the map to point at the new block.
A deque object endeavors to leave room to extend the map at either end, and for a very good reason. Once the map has to grow past either end of the containing array in which it is stored, the deque object allocates a new containing array and copies over the map. You certainly don't want this to happen any more often than necessary. Otherwise, the time complexity of prepending elements to a deque can approach linear time, just as for a vector.
This raises an interesting issue. It looks like a deque simply replaces an array of elements with an array of pointers to those elements. It has to repeatedly reallocate and copy over those pointers as it grows, much as a vector has to repeatedly reallocate and copy over the elements. So it looks like the time complexity for growing a deque has to be linear, just as for a vector. You might save actual copying time if pointers are smaller than the blocks of elements they designate, or you might even lose time if pointers are bigger. What's the story here?
The essential trick lies in how the deque object grows the array that stores its map. Each newly allocated array is twice as large as the map it must initially hold. As the controlled sequence grows longer, the number of reallocations declines. And that bounds the average cost of growing the controlled sequence.
Consider the situation immediately after the deque object has grown a map containing M elements. (M is just ceil(N / DEQUESIZ), for a controlled sequence of N elements.) The deque object has performed log2(M) allocations, which should all take approximately the same time. More important, the number of pointer copies it has performed is:
M + M/2 + M/4 + ...which approaches 2 * M. The time complexity for prepending or appending elements one at a time is thus no worse than the time to construct the sequence all at once. Construction time is necessarily linear, so the average cost of prepending or appending does not depend on the length of the sequence.
As an added safeguard, the deque object copies the map to the middle of the newly allocated containing array. A map of length M subsequently has room to grow by M/4 pointers at either end. Absent any information about future growth patterns, this is a good compromise that preserves the desirable time complexity for that future growth.
Implementing Deque
Listing 1 shows template class deque from the header <deque>. Once again, I remind you that the /// comments indicate compromises needed for current compiler technology. Features required by the draft C++ Standard but not supported by many current compilers are commented out with a leading ///. Replacement code is "commented in," and flagged for later removal, with a trailing ///. And as with the containers discussed earlier, most of the rewriting of template class deque is to avoid using member templates, which are not yet widely supported.
To represent the controlled sequence, a deque object stores several objects:
- Map is a pointer to the beginning of the array that stores the map, or a null pointer if the deque is empty.
- Mapsize is the number of elements in the array pointed to by Map.
- Size counts the number of elements in the controlled sequence.
- First is an iterator that designates the first element in the controlled sequence.
- Last is an interator that designates the first element beyond the end of the controlled sequence.
A deque object also stores one or two allocator objects. Last month, I described in some detail the complexities involved in allocating and freeing storage for STL containers using allocator objects. (See "Standard C/C++: Allocators," CUJ, June 1996.) That's a long sermon, which I will not repeat in full here. Instead, I simply highlight the peculiarities that result from working with allocators.
The template parameter A describes an allocator that's eminently suited for allocating blocks. The deque object stores a protected object named allocator (unfortunately) of type A, and uses it for the intended purpose. But allocator is not, strictly speaking, suitable for allocating the array that contains the map. A proper implementation of template class deque thus also stores the allocator object Myal, which it uses to allocate map arrays. A rather large brick of code — including the functions Freemap, Freeptr, Getmap, Growmap, and Setptr — thus comes in two flavors, one standard conforming, the other practically realizable with today's compilers.
A related issue is the types of pointers to maps and blocks. All these creatures are addressable by rules dictated by the allocator class A. Thus, the code is careful to define element pointers (Tptr and Ctptr) and map pointers (Mapptr) in terms of types supplied by the allocator class. Mapptr has a particularly magical specification, as I discussed last month.
Everything you need to know about accessing elements in a deque you can learn by studying the nested types iterator and const_iterator. These perform the magic required to walk through a controlled sequence, leaping from block to block. Note the absence of any checking logic — walking an iterator off either end of the controlled sequence leads to disaster, pure and simple.
Everything you need to know about growing a deque you can learn by studying the four functions push_back, push_front, pop_back, and pop_front. These supply the unique properties I've outlined above. How they do so is worthy of some study.
The rest of Listing 1 looks remarkably like the innards of template class vector and template class list. I present them here for completeness. o
P.J. Plauger is senior editor of C/C++ Users Journal. He is the author of the Standard C++ Library shipped with Microsoft's Visual C++, v4.2. For eight years, he served as convener of the ISO C standards committee, WG14. He remains active on the C++ committee, WG21. His latest books are The Draft Standard C++ Library, Programming on Purpose (three volumes), and Standard C (with Jim Brodie), all published by Prentice-Hall. You can reach him at pjp@plauger.com.