Extending the STL

John Dibling is a software engineer in Chicago, Illinois and can be contacted at [email protected].

When first learning STL, I was awestruck by it—not by how cool or revolutionary it was, but instead by how huge and confusing it was. I couldn't tell you why a list is better than a vector in such-and-such a situation, or what the differences were between input iterators and forward iterators. But something told me I should keep at it, and eventually my understanding grew. In learning the STL, one thing that struck me was Matt Austern's statement in Generic Programming and the STL that "to use the STL is to extend it" [1].

During this time, my programming style was evolving from a somewhat naive application of object-oriented methods to brief diversions toward functional and generic styles, and finally ending up as a weird hybrid of functional and object-oriented styles that I call "Algorithmic Programming" (AP). A core philosophy of my AP style is borrowed from UNIX: Use many small, sharp tools together to get big jobs done. The STL is itself a great implementation of this principle, and with its tools I could accomplish many tasks simply and cleanly. Nevertheless, I discovered that the STL is incomplete. In fact, there is a great deal of functionality that does not exist in the STL as defined by the C++ Standard. To make matters worse, many STL features defined by the Standard were not implemented in the compiler I used at work. So while the foundation of my programming style was the small, sharp tools, it seemed like half of the wrenches were missing. Consequently, I developed a methodology for extending the STL, and built a library of STL extensions (available at http://www.cuj.com/code/) that filled in some of the gaps.

Identifying Missing Algorithms

In the STL, algorithms are "the thing." Some programmers may argue that the STL's biggest benefit is the collections it provides, but that only scratches the surface. After all, you aren't just going to plunk a bunch of things into a collection and leave them there forever. Instead, you want to do something with them—sort, print, sum, or generate every possible permutation of them, but you won't just ignore them. Using the STL's collections without using its algorithms is not really using the STL.

The most profound and most interesting relation between containers and algorithms are iterators—the glue that holds the STL together and gives it form. There are also functions of various kinds, such as predicates and binary operations, which refine the relationship between container and algorithm. There are simple utility objects (such as auto_ptr) that can be used alone, and other utility objects (such as unary_function, used to build functors) that are like rivets in a bridge. Considering the containers and the algorithms and all the pieces that relate them, the STL has a fairly complete, well-designed foundation. Still, even though the STL is fairly complete, that doesn't mean that nothing is missing. It's complete because you can accomplish just about any task using just the tools the STL gives you. But things are missing because, in many cases, it's just too hard to use the tools the STL gives you. As an illustration, you could design a Turing-complete programming language that has only eight instructions. But would you want to actually use that language? The STL needs more wrenches.

The STL algorithms provided by the Standard can be divided into two types: Those that act on all the elements in a sequence and those that act on only certain elements in a sequence.

For those that act on only some elements, there are two ways to specify which ones the algorithm effects—by either specifying a value that is convertible to the element's type and comparable using operator==(), or by specifying a predicate comparator. The predicated version of the algorithm has the same name as the non-predicated version, but with _if appended. This pattern is applied to STL algorithms with nearly unbroken regularity—except for find() and find_if(). All the find()-type algorithms seem to be exceptions to this rule.

One of the best things about the STL is how the usefulness of the predicated algorithms is practically unlimited. Anything you can't find with find(), for instance, you can probably find by writing your own comparator using find_if(). One of the worst things about the STL is that this unlimited usefulness doesn't extend to the algorithms that operate on all the elements of a sequence. For instance, if you have a collection of, say, stock trades in a vector and you are looking for the first one that was executed on "SDS" with a price greater than $30.00, you could construct a comparator functors and use find_if() to find it (see Listing 1). To copy just some elements from a source sequence to a destination sequence, you have to fall back on writing another loop:

std::vector<StockTrade> result;
for( vector<StockTrade>::iterator itF = 
     find_if(trades.begin(),trades.end(),
        stock_traded_at("SDS",30.0)); 
   itF != trades.end(); 
   itF = find_if(++itF,trades.end(),
          stock_traded_at("SDS",30.0)) )
{
   result.push_back(*itF);
}

Writing that loop is troublesome, and the resulting code is probably prone to defects. It would make more sense and cleaner code if there were a version of the copy() algorithm that copied certain elements. Writing a copy_if() algorithm is not a difficult matter, and is discussed in detail in Effective STL [2]. The version that is included in the cstdlibext library (http://www.cuj.com/code/) looks like this:

template<class InputIterator, class 
  OutputIterator, 
  class Predicate>OutputIterator copy_if(InputIterator first, 
     InputIterator last, OutputIterator result, Predicate pred)
{
   for (; first != last; ++first)
   {
      if( pred(*first) )
      *result++ = *first;
   }
   return result;
}

Now the troublesome copying code is reduced to a simple piece of code:

typedef std::vector<StockTrade> StockTrades;
StockTrades result;
std::copy_if(trades.begin(), trades.end(), 
   back_insert_iterator<StockTrades>(result), 
   stock_traded_at("SDS",30.0));

In many cases, it doesn't seem likely that an existing STL algorithm should be extended to work on only certain elements in a sequence. But in many of these cases, the extension is useful. For example, before realizing that for_each_if() was a missing algorithm, it was difficult for me to grasp that I should be able to apply a function to only some of the elements in a collection. But when I did realize this, it was plain as day. The question became not "Should I be able to do a for_each_if()?" but "Why shouldn't I be able to do a for_each_if()?" It seemed obvious that I should, and once I wrote for_each_if() it became the most-used algorithm in my library. In fact, it became clear that with my AP programming style depending on the small, sharp tools being used together to do big jobs, I would never realize the true potential of AP programming until I had this particular tool.

transform_if() is another example of an enabling idiom without which the toolbox is missing key tools. transform() builds a new collection based on the contents of an original collection. It is different from copy() in that the values aren't just copied; they are passed to some function that creates some other value based on the original, and the new value is what is added to the new collection. So transform() can be used to copy the contents of one collection to a collection of different types. But in the same way that you might want to copy only certain values from one collection to another, you also might want to transform only certain elements in a source collection; hence transform_if().

Designing an Algorithm Extension

On pages 2-3 of the August 2004 edition of Dr. Dobb's Journal, an advertisement for Google Labs solicits résumés of high-level programmers. This ad caught my eye because it is a logic puzzle and I love logic puzzles. In this puzzle, there is a vending machine, with rows and columns of snacks and goodies. Vending machines typically have a grid of keys to select a snack; some keys have letters, others have numbers. Each cell where a snack is located has a sticker with a letter and number, uniquely identifying each snack. You push one letter and one number key, and out comes the snack with the same identifying code—E5 for the chips, G11 for the pack of year-old gum, and so on. In the Google ad, the keys aren't letters and numbers, just numbers with some duplicates; see Figure 1. The identifying plaque on each snack is also just a number, without duplicates. To get your snack, you push five buttons instead of the usual two and pass their values in to a formula provided in the ad: A*B+C-D+E. The value that comes out of the formula matches one of the snack's plaque numbers, and identifies the snack you get. The puzzle is to identify the single snack that can't be obtained by pushing any possible combination of five buttons.

Right off I saw one possible way to solve this problem—just "push" every possible combination of keys and keep track of which snacks came out as a result. The concept is simple, but since I had never written such a piece of code before, I needed to think about how to efficiently generate every permutation of keys. My first attempt identified the missing snack, but was hopelessly inefficient. It pushed the same combinations of keys more than once, and fast is better than slow. I recalled reading about permutation-generating algorithms in Donald Knuth's seminal The Art of Computer Programming [3], which has not one, but two algorithms that apply to this situation. Listing 2 is my implementation of Knuth's algorithm.

permute() is a recursive function that rotates every possible value into every possible slot once. Every time a new permutation is generated, permute() calls the specified callback function pointed to in pfn. My algorithm differs from Knuth's in that Knuth assumed that the number of slots was equal to the number of elements, whereas my algorithm permits an arbitrary number of slots. Although the callback function is a black box, in this case I computed the snack value and searched for that value in a populated vector of all the snacks in the vending machine. If it found the value in the vector, the snack was removed from the vector (not every combination of button-presses results in a value of a snack that exists in the machine). When all was said and done, there should be only one snack left in the vector—the one I can't get.

Knuth's algorithm is simple in concept, and my code is about as simple as any recursive function can be in implementation. Still, it took time to get the code right, and it seemed like a waste to simply solve the problem and toss the code. I'm not the first (and certainly not the last) person to write a recursive permutation-generating algorithm, so somebody might find this code useful someday. While writing the code—passing in a pointer to a callback function as a parameter to permute()—it occurred to me that I was really applying some function to each permutation of some set of values. That those values just happened to be ints—or that the callback did some specific task—seemed beside the point. After all, I could change both permute() and the callback function to take strings or anything else, and there would be no architectural implications for permute—only the implementation details would change. What's more, my AP style abhors writing loops, and isn't a recursion really just a fancy loop? Of course, you can't write interesting code without writing loops. But if I need two loops that do more or less the same thing, or if one loop is particularly hard to write, AP says that a loop should be a well-written, sharp tool that can be included in the toolbox. It seemed like permute() was begging to be crafted and for_each_permutation() was conceived.

Implementing for_each_permutation()

The first question that needs to be answered when writing for_each_permutation() is, "How do we get the array of elements to for_each_permutation()?" In my first implementation of Knuth, I just sent a pointer to the first element in the array along with the number of elements in the array. This is a simple and effective approach, but it has problems. First, to traverse the array, you need to know the size of one element. This can be specified either by making it an array of a prescribed type and, therefore, known size (as I did in my first implementation of Knuth) or by making it an array of arbitrary type and specifying the size as another function parameter.

Neither of these solutions is great. In the first one, you can only use permute on ints and never strings without another implementation. In the second one, you would have to defeat the C++ type system by sending the pointer to the first element as a void pointer. The C++ type system is your friend, and defeating it is fraught with peril. Another problem with sending a pointer to the first element in the array is less obvious, but even worse. It requires that the array is contiguous, because that's how pointers work. The interface of what is essentially a third-party utility function should not have any implications on the application that uses it, but this simple approach does have such implications. This is Pure Evil, and must be avoided. The STL's approach to solving this problem is free of any such implications; use iterators as abstractions of pointers, and use one to indicate the beginning and one to indicate the end of the sequence. Iterators can iterate anything; what is in the sequence is irrelevant. If you need to know the number of elements in the array, you can find out by using distance(). In most cases, the number of elements doesn't even matter. So the first question is answered. for_each_permutaion() would take iterators pointing to the beginning and end of the sequence.

The second question that needs to be answered is, "How do you tell for_each_permutation() what to do with each permutation?" In my first implementation of Knuth, I passed a pointer to a callback function. This is fundamentally sound, but the problem is similar to those in the first question—it requires that the callback function have a specific signature. That is, it must have a prescribed return type, and take a prescribed number and types of parameters. Again, this is Evil. The STL approach is to use functors, which are objects with an overridden operator(). Since it has an operator(), the functor can be used by for_each_permutation() just like a function. But since it is an object, it can also be stateful, which is useful for accumulation, initialization, and termination. Interestingly, for_each_permutation() must have somewhere in its implementation a line of code that calls the functor's operator(), for instance:

Template<class Function>
for_each_permutation( ..., Function fn)
{
   :   :
   fn(current_permutation);
   :   :
}

So this approach still has the same problem that the callback-pointer approach had—the signature of fn() must be known to for_each_permutation(). This is true, but it isn't a problem because for_each_permutation() doesn't prescribe the signature of fn—it just knows what the signature looks like because fn is a template parameter.

The third question that you have to address is, "What should for_each_permutation() return?" My first implementation of Knuth simply returned nothing. But the function had an out parameter that contained the number of permutations generated. Shouldn't this out parameter just be the return value from the function? It's possible that the permutation count won't be needed by the caller in most cases, but in this case, it shouldn't even be a required parameter in the first place, should it? The STL approach to this is to use the functor again. Since the functor can be stateful, any accumulated data needed by a particular application can be kept track of by the functor itself. STL algorithms that perform accumulation return the functor as the return value, and the accumulated data can be received from it.

Now all you have to address is how to specify the number of slots in each permutation. There's no reason not to specify this as a parameter to for_each_permutation:

template<class Iterator, class Function, class Size>
Function for_each_permutation(Iterator first, 
   Iterator last, Size slots, Function fn);

This algorithm signature is generic, but it is not so completely generic as to be useless. Enough is specified so that the algorithm is semantically clear and easy to use correctly. It follows the same pattern as the STL, which is a well-known pattern. So for instance, you know that last actually points to one past the end of the sequence because that's the STL way. But not so much is specified to confine for_each_permutation()'s users to overly restrictive requirements. For instance, first and last might point to a C-style array, or a vector, or a tree, or any other data structure. for_each_permutation() can work with ints, strings, stock trades, or whatever. Using this algorithm is easy. In the case of the Google puzzle, all you have to do is write a functor that implements the formula specified in the ad, and keep track of which snacks you get; see Listing 3.

Aside from the differences between the signatures for my first Knuth implementation and for_each_permutation(), little changes. In most cases, when calling a recursive function, you need to pass in some values that give the function a clue when to quit the recursion. But the fact that for_each_permutation() is recursive is actually an implementation detail that the caller shouldn't care about. So to avoid requiring the caller to specify the special seed values, for_each_permutation() actually becomes a thin wrapper around the function that actually does the recursion work, and for_each_permutation() sends the seed values to that function; see Listing 4.

Limitations in Extending the STL

I'm a big advocate of using the STL as a first choice to get a given job done, no doubt annoying my coworkers who've said, "If the STL is so great, why is it so hard to format a string?" This is a valid complaint, and I share it. True, the "new way" of doing string formatting is to use the stream classes, but lots of programmers—myself included—hate the stream classes. They are big and clunky, the insertion/extraction operators are not what we are used to, and it usually takes a lot more typing to get a finely crafted string from stringstream than from sprintf(). I am all for advancing the state of the art, but in this case, the old-schoolers had it right the first time. I like sprintf(), and I'm proud of it [4].

But the problem is that there's no easy and Standard-compliant way to use sprintf() to format an std::string object. You could try to use the c_str() or data() functions to get at the actual char buffer, but this is a slippery path. These functions return const char pointers, and are not guaranteed to return a pointer to the actual data. You could use printf on a raw char buffer or an appropriately sized vector<char> and simply copy that in to your std::string, but isn't that a big mess? This problem would be solved if only there were a function designed to format a std::string directly in a sprintf()-type way.

It turns out that implementing a general-purpose std::string-capable version of sprintf() is far from trivial. It's almost as if the code resists being written. The biggest problem was parsing the format string and processing the variable argument list. It would seem to be nothing more than a big switch statement. But when you factor in locales, different variations on basic_string<X> and platform independence, the code becomes a leviathan of machinery and complexity. Instead, I wrote a simple wrapper function that calls existing Microsoft Visual C Runtime Library code to work with basic_string<char> strings. Frankly, I hate this code for lots of reasons. It's ugly, it relies on questionable MSVC-specific details, and it only works with basic_string<char> strings. But in the narrow domain where it does apply, it is extremely useful. In MSVC under Windows, I now have a way to sprintf() strings. It's not technically part of the cstdlibext library, but Listing 5 presents it for you to use if you like.

Conclusion

The STL is a great collection of great tools, but it isn't a complete toolbox all by itself. Often times, it can be frustrating to try to use the STL to do things that aren't directly supported, such as using for_each() to apply a function to only some elements in a sequence. In these cases, using the STL really does mean extending the STL. Writing STL extensions turns out to not be as challenging as it may first seem. Once you get the hang of it, you may find yourself churning out whole libraries of extensions yourself.

References

[1] Austern, Matthew. Generic Programming and the STL: Using and Extending the C++ Standard Template Library, Addison-Wesley, 1998.

[2] Meyers, Scott. Effective STL, Addison-Wesley, 2001.

[3] Knuth, Donald. The Art of Computer Programming, Addison-Wesley, 1998.

[4] This is a mostly religious debate. I'm not trying to convince you that sprintf() is Good and the streams are Evil. Just that some programmers have this opinion. Good luck trying to get a programmer to use a tool (streams, for instance) that they don't like.