C/C++ Contributing Editors

Standard C/C++: A Better deque

P. J. Plauger

You can't just write a good library once and for all. You have to keep rewriting it as you learn better techniques — from customers, competitors, or even other programming languages.

Introduction

My first serious exposure to the Standard Template Library came in 1994. It could have come in late 1993, but I skipped the presentation Alex Stepanov made to the C++ standards committees at the November 1993 meeting. Everyone had agreed earlier that year to stop holding evening seminars on new technology to add to the draft C++ Standard, in the interest of getting it finished as planned in 1994. But somehow, the STL presentation happened anyway. I skipped Stepanov's talk partly out of exhaustion and partly out of exasperation. (A mere four years later, the C++ Standard was finally completed, including STL as a significant addition.)

So I didn't start studying STL in earnest until mid 1994, when it became obvious that the draft Standard C++ library was going to absorb it, willy nilly. My knowledge of templates was still pretty raw. The library I had written in early 1993, and henceforth kept current with the evolving draft, used templates only in simple ways, as befitting the state of compilers at that point in time. I certainly wasn't ready for all the not-so-stupid template tricks that Stepanov, Meng Lee, and David Musser had developed in converting STL from Ada to C++. Put simply, I was in over my head, and I remained that way for many weeks of rapid self-education.

Just to get everybody on the same page, let me briefly recap what STL is and is not. It began as a comprehensive collection of template classes and template functions, developed primarily at Hewlett-Packard Labs by Stepanov and Lee. That in turn was the latest incarnation of years of work in earlier languages by Stepanov (now at Silicon Graphics) and Musser (still at Rensslaer Polytechnic).

Part of STL is a set of generic containers, template classes that implement common data structures such as extensible vectors, lists, ordered trees, etc. As templates, these classes can be specialized to store sequences of elements of whatever type you specify. They are well designed and well written. Chances are, you can't do better by writing a custom version of an STL container class.

Another part of STL is a large set of algorithms, template functions that implement common operations on sequences of homogeneous elements such as sorting, searching, permuting, etc. Templates once again adapt the code for whatever element type you specify. The algorithms encapsulate the best known approaches. Chances are, you can't do better by writing a custom version of one of these functions.

The glue that holds STL together is the concept of an iterator, a generalization of an object pointer in C or C++. Iterators isolate algorithms from containers. A function using iterators need not know whether it is operating on a sequence stored in a container, stored in an array, or generated on the fly by reading a file. Iterators come in half a dozen flavors, or categories, with varying degrees of flexibility. Some algorithms adapt their behavior to best suit the category of iterators they are called with.

Containers, algorithms, and iterators make up the bulk of STL. The result is a library that is at once coherent and extensible. But STL is just a part, however significant, of the full Standard C++ library. (A common misnomer these days is to refer to the full library as STL.) Note also that STL is not an object-oriented library, even though much of the full library can be characterized as such. Rather, it is an example of generic programming, a different approach to reusability that is powerful in its own right.

STL can also be very concise. Here is an excerpt from a program presented in an article by Bjarne Stroustrup last month:

vector<string> buf;
fstream fin(file, ios::in);
string d;
while (getline(fin, d))
    buf.push_back(d)
sort(buf.begin(), buf.end());

(See Bjarne Stroustrup, "Learning Standard C++ as a New Language," CUJ, May 1999.) You would be hard pressed to find a better way to read in an arbitrary-length file of arbitrary-length text lines and sort the result in place. Yet, as Bjarne showed, you sacrifice little or no efficiency by using STL to code at this higher level of abstraction. The result is often more efficient than hand-crafted code, and certainly much more likely to work correctly.

A Library for All Seasons

I recite this brief history to underscore several important design goals behind STL. All parts of it must be as flexible and as efficient as possible, for a wide range of user-supplied element types. Otherwise, word will spread and programmers will continue their age-old practice of writing custom versions of the common data structures and algorithms. At the same time, it must adhere rigorously to its own rules, lest programmer-supplied extensions to STL fail to work properly with existing components. All software libraries are designed to be highly reusable, but STL sets new standards of reusability, by practically any metric.

Hewlett-Packard Labs did the C++ community a tremendous favor by allowing unrestricted use of their STL implementation, with no paperwork and no royalties. It did not take long for several C++ compiler vendors, and third-party library suppliers, to repackage H-P STL for a number of popular environments. Even today, your typical C++ library traces the origins of its STL component rather directly to the H-P implementation.

But I was a bit more ambitious. One way I learn new concepts is by reimplementing designs of proven worth. How hard I work to make a "clean" product depends strongly on my commercial goals. In this case, I was adding STL functionality to a library that I owned outright, and I wanted to keep it that way. But given Hewlett-Packard's generous terms — not to mention my profound ignorance of STL — I didn't aim to be too fastidious. I completely reexpressed STL as I learned it, but I freely acknowledge my intellectual debt to H-P by including the notice they request in my code.

Nothing stands still. Other companies besides mine license Standard C++ libraries for profit. In the area of STL, however, my principal competitor is Silicon Graphics. They continue to improve the code from H-P. They make it faster and more robust, they adapt it to the needs of newer compilers, and they bring it ever closer to the final C++ Standard. And they give their work away for free, just like H-P.

I have competed with free software for two decades now. That's not the hard part, since the cost of software has many dimensions. What keeps me hopping is all the new features and improvements that keep bubbling up, from SGI and other sources. As Stroustrup observed last month, the world needs Standard C++ libraries that are uniformly good, and as good as possible. I'm in the business of supplying good libraries, and I want to stay in that business for the foreseeable future.

My focus this month is on one aspect of STL that has seen quite a lot of change over the past few years. It is the template container deque, defined in the header <deque>. It was in many ways the hardest of the containers for me to understand from the beginning. I have shipped more than one version with bugs, sad to say. And I've had the devil's own time eliminating those bugs. Nevertheless, I am pretty happy with the latest incarnation of deque, mostly because of the lessons I've learned in rewriting it in Java.

Why a Deque?

The term deque either derives from Double Ended QUEue, in which case it should be pronounced "DEE-queue," or it is a queue that behaves like a deck of cards, in which case it should be pronounced just like "deck." I've heard both, but favor the latter. In either case, it has two salient properties in STL:

1) You can push and pop elements at either end in constant time.

2) You can access an arbitrary element N in constant time, independent of the length of the sequence.

I described this container at some length a couple of years ago. (See "Standard C/C++: The Header deque," CUJ, March 1997.)

To get these properties, the template container stores elements in blocks of length B. You reach these blocks through a map, which is an array of block pointers Map. So in principle, you can access element N with the expression:

Map[N / B][N % B]

In practice, the container has to provide for growth at both ends. So it begins the active contents at some offset Off, and it stores the number of active elements (the length of the sequence) as another integer Size. Replace N with N + Off in the expression above and you'll get a more realistic recipe for finding element N.

Reality is still not that simple. An STL deque has an additional promise:

3) An iterator continues to designate the same element even as you push and pop elements at either end, provided you perform no internal inserts or erases (removals) within the controlled sequence.

To pull off this behavior, the original H-P implementation stores several items in each iterator:

Listing 1 shows my version of this implementation. It shows the beginning of template class deque, including the definition of the nested class iterator. I preserve here the typedefs that precede it, so you have a better notion of what some of the types might mean within iterator.

As you can see, accessing an element with such an iterator is pretty cheap. Incrementing and decrementing is a bit harder. Subtracting two iterators is a nuisance, and adding an arbitrary integer to an iterator is a real mess.

But that's not the worst of it. This representation has several problems:

1) There's no way to tell whether incrementing or decrementing an iterator walks off the end of the active map.

2) The active map must be stored in contiguous elements of the map array.

3) An off-the-end iterator has two representations: off the end of the last active block or at the beginning of the next (usually nonexistent) block.

Problem (1) is more or less in keeping with the rest of STL, however annoying it may be during debugging. Problem (2) makes for much messier map administration. If you run out of space at either end, you have to move the active map up or down in the map array, or you have to grow the map. Problem (3) is a rich source of bugs in deque implementations.

Bugs and Betters

As it turned out, the original H-P implementation indeed suffered from more than one deque bug. So did mine, if only because I started out slavishly imitating an approach that I barely understood at the start. I believe SGI solved the ambiguity problem by setting aside an extra element, at all times, for an off-the-end iterator to point at.

Listing 2 shows how I addressed some of these problems. It is derived from code at my company's website:

http://www.dinkumware.com/vc_fixes

Here you will find a number of corrections to the files shipped with Microsoft Visual C++ V5.0 and V6.0, including a much improved <deque>, the source of Listing 2. It addresses problem (1) by putting null-pointer guards at either end of the active map. So at least increment and decrement operations know not to walk off either end. (Adding an arbitrary integer can still leap these guards, of course.) It addresses problem (2) by keeping off-the-end iterators in canonical form, to avoid the ambiguity. And it addresses the bugs caused by problem (3), at least to a large extent, by growing and shuffling the map much more carefully. (I don't show that code in Listing 2.)

I was pretty content with this versions, modulo a few small tweaks, until fairly recently. Then I started rewriting STL in Java. (Yes, it can be done, despite the absence of templates in Java.) Java doesn't have pointers, in the C or C++ sense. It also doesn't have value semantics for nonscalar objects, in the C or C++ sense. Everything is done with references (pointers, actually) to objects allocated on the heap. Moreover, those objects are never explicitly freed — Java relies on a "garbage collector" to round up orphaned storage from time to time.

For these and related reasons, I found myself extensively rethinking how to represent iterators in Java. I quickly gravitated to storing in a deque iterator just a pointer to the associated deque and an absolute offset akin to the N I began with above. The iterator accesses the current value of Map and Off stored in the deque object, so that it is actually far more robust than its C++ equivalent.

I soon realized that the STL implementation could also benefit from this representation. The rewrite showed a satisfying simplification of the code. I don't show it here because, within days, I hit upon another improvement. I winced at the thought of transliterating all that code for moving the active map about, particularly after a year or so of picking out bugs. To avoid ever moving the active map, I rethought the map array as a circular buffer. As the active map grows off either end, it simply wraps onto the other end. Only when the beginning and end elements threaten to share the same block is it necessary to grow the map.

Listing 3 shows the effect upon the deque iterator of this change in philosophy. operator*() is now messier, because the block number can wrap around within the map array, but everything else is much simpler. I think the tradeoff is well worth while. All sorts of messy map management software — the source of many bugs — goes out the window. In its place is a reasonably simple function for growing the map.

Rather than show the function _Growmap, however, I find it more revealing to show how it is used. Listing 4 shows the member functions that push and pop an element from the end of the controlled sequence. To me they have a comforting simplicity.

I end with my usual caution. The last of the code I show here is fresh off the drawing board. I have not tested it extensively enough to ship, so I make no guarantees. It may also suffer from the usual transcription errors in preparing it for presentation here. My goal is to convey some of the process of maintaining and enhancing a library as complex as STL, or the full Standard C++ library. Competition keeps us all a bit off balance. But it also forces us to keep improving the tools that we all use to develop working software.

P.J. Plauger is Senior Editor of C/C++ Users Journal and President of Dinkumware, Ltd. He is the author of the Standard C++ Library shipped with Microsoft's Visual C++, v5.0. For eight years, he served as convener of the ISO C standards committee, WG14. He remains active on the C++ committee, J16. 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.