Columns

Standard C/C++

P. J. Plauger

Container Adapters

The long journey through the Standard Template Library finally ends, with a description of several handy container adapters.

Introduction

Way back in December 1995, I began a series of columns on the Standard Template Library, or STL for short. (See "Standard C/C++: The Standard Template Library," CUJ, December 1995, and all subsequent installments to date.) Depending on how you measure things, STL constitutes between a quarter and a third of the draft Standard C++ library today. And that library is no small critter. You can see why it has taken me so long to cover this topic, at least to the technical detail that I favor.

You may be happy to learn that I'm finally coming down to the wire. (At least one letter writer has said, "Enough on STL, already.") This installment presents the last of the code I intend to show from my implementation of STL. If I discuss the topic further, it will probably be to cover eleventh (or thirteenth) hour changes wrought by the C++ standards committees.

By way of quick review, STL involves three major concepts:

1) Iterators are a generalization of object pointers in C. You access or generate a sequence of elements, all of the same type, by stepping an iterator from element to element. Iterators are categorized by their flexibility: forward iterators, for example, can progress only forward through a sequence, while bidirectional iterators can step either forward or backward. Iterators come in half a dozen different categories.

2) Algorithms are template functions that perform common operations on sequences. A simple example is count, which merely counts the number of elements. Far more complex is sort, which orders a sequence by some ordering rule. All algorithms are written in terms of iterators of some clearly defined category, or categories.

3) Containers are template classes that control sequences, using different internal structures. Template class list, for example, maintains a bidirectional linked list, while template class set maintains a binary tree that is kept almost in balance. You trade off different levels of performance, and different degrees of complexity, in choosing among the containers. Template class vector, for example, supports fast random access, but requires considerable churning when you insert an element in the middle of its controlled sequence.

The power of STL lies in its unified structure. A container, for example, can supply iterators by which you can access elements of its controlled sequence. Hence, any of the algorithms that accept iterators of the appropriate categories manipulate the contents of containers as easily as any other sequence.

A consequence of this unified structure is extensibility. STL is as much a set of rules for writing additions as it is a set of ready-to-wear templates. If you define an iterator by the rules for a given STL iterator category, it can be used by any algorithms that accept that category of iterator. If you write a function by the rules for writing algorithms, it can be used like any STL algorithm. And if you write a container class by the rules for writing STL containers, all the relevant STL algorithms should work nicely with it.

An important goal of adding STL to the draft Standard C++ library is code reuse. Programmers reimplement lists over and over because the old versions don't generalize well to new applications. They avoid stock implementations of lists out of fear that the code will be inefficient, or even buggy. STL works hard at being at once very general, very efficient, and correct.

Good programmers have learned to avoid writing their own sort functions — they know that a library version is likely to be faster and more correct than custom code. STL endeavors to provide that same level of confidence for many other algorithms and common data structures. The evidence to date is that the sales effort is beginning to pay off. More and more articles submitted to CUJ describe how to use some STL facility to solve a problem, rather than reinvent the wheel yet again.

I've enjoyed writing this series of articles as part of the sales effort. Now that the draft C++ Standard seems to have settled down, I hope to finish a long-promised book on STL. My co-authors are the folks who developed STL:

• Alex Stepanov, formerly of Hewlett-Packard and now at Silicon Graphics
• Meng Lee, at Hewlett-Packard
• David R. Musser, at Rensselaer Polytechnic Institute

They get full credit for the ingenuity and balance that makes STL what it is.

That's the Standard Template Library in a nutshell. Now let's look at the last bits of it.

Stacks

My most recent columns on STL have covered the template container classes. It is only natural to conclude that concluding topic by describing an interesting companion to all those containers. These are template classes that do not themselves directly maintain controlled sequences. Rather, each contains within it as a member object a container object that does the job. The template classes I describe this month serve as container adapters. Of these, the simplest is template class stack.

So what's to adapt? Well, a typical template container class in STL has lots of member functions. The general idea is to provide all the operations on the controlled sequence that might possibly make sense. Remember, these critters are designed to be maximally reusable. It's generally easier to supply a member function that's not used in a given application than to require an application to extend a container in some nontrivial fashion. But flexibility of access is not always a virtue.

Let's say, for example, that what you really need is a stack. Also known as a last-in first-out (LIFO) queue, a stack maintains a rigorous access discipline. All you can see within the controlled sequence is the top of the stack — last element you insert, or push, on the stack. And the only element you can erase, or pop, from the stack is that top element. All other elements remain buried, like the middle members of a stack of cafeterial trays in one of those spring-loaded dispensers.

You might choose to implement a stack as, say, template class vector. If you do, you can then get to all those buried elements a lot quicker and easier than you can in any silly old stack. But that doesn't mean you should do so. Object-oriented design stresses the importance of information hiding. You declare the member objects of a class private, for example, to prevent programmers from writing code that depends on a particular implementation of the class. That way, you have more flexibility in altering (and presumably improving) the implementation at a later date with no fear of breaking code that uses the class and (improperly) accesses its members directly.

Similarly, you might well want to hide all that extra power of template class vector. Like those private member objects, the member functions of vector say too much and do too much to be exposed in the implementation of a stack. For this reason, you want to avoid the "is a" relationship that comes when you derive a stack from a template, as in:

template<class T>
 class stack : public vector<T>;

Such derivation lets you add member functions, such as push, pop, and top; but it doesn't help you hide the member functions you'd like to keep hidden. Yes, you can make the base protected or private, but the stack still "is a" vector for many purposes, and that relationship is simply inappropriate.

STL thus provides a template class stack that "has a" container as a member object. The container object stores the actual controlled sequence that implements the stack. Whatever operations the container may support, however, the stack only lets you push and pop elements. The template class is declared as:

template<class Ty, class C = deque<Ty> >
 class stack;

Template parameter Ty specifies the type of elements stored in the stack. Template parameter C specifies the type of container used to control the sequence of elements.

If an implementation supports default template arguments, you can write stack<int> and the translator will automatically supply the container type deque<int>. A deque makes a pretty good stack. (See "Standard C/C++: The Header <deque>," CUJ, March 1997.) Otherwise, you must specify the container type yourself. It is then up to you to ensure that your container C can store elements of type Ty properly.

Listing 1 shows one way to implement template class stack. It is defined in the header <stack>. As promised, the only ways you can change a stack are to push and pop the top element. The template class does, however, provide a handful of additional capabilities:

• You can construct a stack whose initial contents are copied from an existing container object.
• You can inspect the top element of the stack, by calling top.
• You can test whether a stack is empty, by calling empty, or determine how many elements it contains, by calling size.
• You can even compare two stacks in their entirety, by using the six comparison operators.

A stack performs all these operations by calling upon its member container object, in turn, to do the actual work. That imposes a number of implicit requirements on any container type you specify for a stack. Specifically, the container C must have at least the following external interface:

class C {
public:
 typedef Ty value_type;
 typedef T0 size_type;
 Cont();
 bool empty() const;
 size_type size() const;
 value_type& back();
 const value_type& back() const;
 void push_back(const value_type& x);
 void pop_back();
 bool operator==(const C& X) const;
 bool operator!=(const C& X) const;
 bool operator<(const C& X) const;
 bool operator>(const C& X) const;
 bool operator<=(const C& X) const;
 bool operator>=(const C& X) const;
 };

Here, T0 is an unspecified type that meets the requirements of a "size" type. (Typically, it is size_t.) The behavior of each of these member functions must be essentially the same as for template class deque<Ty>. It is worth noting that the STL containers list and vector both meet these requirements. (See "Standard C/C++: The Header <vector>," CUJ, January 1997, and "Standard C/C++: The Header <list>," CUJ, February 1997.) For a given application, you thus have three easy options to choose among when implementing a stack. When in doubt, stick with deque — it has a good combination of tradeoffs.

Queues

Another container adapter is template class queue. Where a stack imposes a last-in first-out, or LIFO, discipline, a queue is first-in first-out, or FIFO. I don't have to tell you how often queues occur in programming. They are at least as prevalent as stacks. They are also highly similar in structure.

Template class queue is declared as:

template<class Ty, class C = deque<Ty> >
 class queue;

The template parameters have the same meaning as for template class stack.

Listing 2 shows one way to implement template class queue. It is defined in the header <queue>. The only ways you can change a queue are to push elements on the back and pop them from the front. The template class also provides a handful of additional capabilities:

• You can construct a queue whose initial contents are copied from an existing container object.
• You can inspect the front element of the queue, by calling front, and the back element, by calling back.
• You can test whether a queue is empty, by calling empty, or determine how many elements it contains, by calling size.
• You can even compare two queues in their entirety, by using the six comparison operators.

A queue thus imposes slightly different requirements, compared to a stack, on any container type you specify for a it. Specifically, the container C must have at least the following external interface:

class C {
public:
 typedef Ty value_type;
 typedef T0 size_type;
 Cont();
 bool empty() const;
 size_type size() const;
 value_type& front();
 const value_type& front() const;
 value_type& back();
 const value_type& back() const;
 void push_back(const value_type& x);
 void pop_front();
 bool operator==(const C& X) const;
 bool operator!=(const C& X) const;
 bool operator<(const C& X) const;
 bool operator>(const C& X) const;
 bool operator<=(const C& X) const;
 bool operator>=(const C& X) const;
 };

The behavior of each of these member functions must be essentially the same as for template class deque<Ty>. It is worth noting that the STL container list (but not vector) meets these requirements. For a given application, you thus have two easy options to choose among when implementing a queue. Once again, when in doubt, stick with deque.

Priority Queues

The last of the container adapters is also the most ornate. Template class priority_queue, like the simpler queue imposes a first-in first-out, or FIFO, discipline, but with an added wrinkle. You specify an ordering rule, or predicate, that determines which element has the highest priority. The template class ensures that each element you extract from the controlled sequence, by calling pop, is the remaining element with highest priority. It does so by reordering the sequence, as needed, each time you add an element, by calling push.

Template class priority_queue is declared as:

template<class Ty, class C = vector<Ty>,
 class Pr = less<C::value_type> >
 class priority_queue;

The first two template parameters have the same meaning as for the template classes stack and queue. Template parameter Pr is the ordering rule. As with many of the STL algorithms we considered earlier, this rule take the form of a function object. (See "Standard C/C++: Algorithms," CUJ, August 1996.) The default argument effectively invokes operator< as needed.

Listing 3 shows one way to implement template class priority_queue. It is also defined in the header <queue>. The only ways you can change a priority queue are to push an element and pop the one with highest priority. The template class also provides a handful of additional capabilities:

• You can construct a priority queue whose initial contents are copied from an existing container object or from a sequence of elements delimited by iterators (and then ordered, of course).
• You can inspect the highest-priority element of the priority queue, by calling top.
• You can test whether a queue is empty, by calling empty, or determine how many elements it contains, by calling size.
• Note that you cannot compare two priority queues in their entirity, as you can queues and stacks.

A priority queue thus imposes still different requirements, compared to a stack or a queue, on any container type you specify for a it. Specifically, the container C must have at least the following external interface:

class C {
public:
 typedef Ty value_type;
 typedef T0 size_type;
 typedef T1 iterator;
  Cont();
  template<class InIt>
   Cont(InIt first, InIt last);
  template<class InIt>
   void insert(iterator it, InIt first, InIt last);
  iterator begin();
  iterator end();
 bool empty() const;
 size_type size() const;
 value_type& front();
 const value_type& front() const;
 value_type& back();
 const value_type& back() const;
 void push_back(const value_type& x);
 void pop_back();
 };

(This interface is regrettably ornate. Most of the extra requirements, over queue and stack, result from additions made to priority_queue with no consideration for their effect on underlying container requirements.)

The behavior of each of these member functions must be essentially the same as for template class vector<Ty>. It is worth noting that the STL container deque (but not list) meets these requirements. For a given application, you thus have two easy options to choose among when implementing a priority queue. Once again, when in doubt, stick with the default choice of vector.

On-Line References

My company, Dinkumware, Ltd., maintains a complete on-line reference to the Standard Template Library, as a public service. We also maintain complete references to the Standard C library and the draft Standard C++ library in its entirety. See our Web site, at http://www.dinkumware.com. Chase the links through the propaganda pages for our on-line reference products.

The versions at our Web site do not reflect changes made since the November 1996 C++ standards meeting. Instead, we provide a summary of changes on the site. (We save the latest and greatest versions for our paying customers.) But you will still find the material to be pretty complete and accurate. 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.