You can't beat a balanced binary tree for fast access, provided someone else supplies the tricky code.
Introduction
For the past several months, I have been describing the template container classes defined by the Standard Template Library (STL). These include the template classes vector, list, and deque. (See "Standard C/C++: Containers," CUJ, December 1996, "Standard C/C++: The Header <vector>," CUJ, January 1997, "Standard C/C++: The Header <list>," CUJ, February 1997, and "Standard C/C++: The Header <deque>," CUJ, March 1997.) This month, I introduce a more sophisticated group of template container classes.
All members of this group support rapid lookup of elements. Say you have some value val and you want to determine whether a container object contains an element with this value. Typically, you have to inspect every element of the container to locate all with matching values. To find just one matching element, you must on average inspect half the elements. In either case, the time complexity is linear, or order N for a container with N elements.
You can speed up searches if you can impose some order on the values you're comparing, and if you can take advantage of that order to skip comparisons. For example, let's say that operator< is defined on pairs of values X and Y. You can then use X < Y comparisons to order the elements in a container. If you want the smallest values at the beginning of the controlled sequence, that means !(Y < X) is true for any X that precedes Y in the sequence. (This is a finicky way of allowing elements with equivalent value next to each other in the ordered sequence, without having to define operator<= as well.)
Having a neatly ordered list doesn't do much good, however. You still have to chain from one element to the next in the linked list to visit all the elements. Put more formally, template class list supports access only via bidirectional iterators. You're rather better off with a vector or a deque. They support access via random-access iterators, so you can perform a binary chop to locate a particular value (or its absence) in an ordered sequence. The function bsearch, declared in <stdlib.h> traditionally searches by this method.
The search time for binary chop increases as the logarithm of N. That's a dramatic improvement over a linear search. Consider the payoff for searching a sequence of 1,000 elements. On average, a linear search must make 500 comparisons, while a binary chop must make only 9. And the difference only gets more striking with increasing N. For 1,000,000 elements, the relative number of comparisons becomes 500,000 and 19. No contest.
We could thus define the template classes ordered_vector and ordered_deque. Each could be implemented in terms of the existing template containers. We might want to add a template parameter Pr to specify the ordering rule. An object pred, of class Pr, can then provide the predicate pred(X, Y) as a generalization of the ordering rule X < Y.
The payoff for this added machinery is the member function find. Give it a key value for an argument and it locates a matching element jiffy quick. Of course, we need to be a bit more precise about what we mean by "matching." Given just an ordering rule such as X < Y, we say the two operands match if !(X < Y) && !(Y < X). (Neither operand is less than the other.)
Readers with long memories will recall that this definition of "matching" is what I called "equivalent ordering" nearly a year ago. (See "Standard C/C++: Algorithms," CUJ, August 1996.) And the ordering rule, based on operator< or an equivalent predicate, is what I called "strict weak ordering" in that same installment. It should come as no surprise that the technology captured in STL algorithms applies nicely to ordering sequences in containers as well.
Binary Trees
STL does rather more than just supply ordered vectors and deques, however. There are other ways to maintain an ordered sequence, ways that have additional desirable properties. Consider, for example, a binary tree. Each node stores a value and has at most two subtrees. The left subtree for the node with value B contains only elements with values A such that !(B < A). The right subtree contains only elements with values C such that B < C. You can then perform a binary chop just by climbing down subtrees, making judicious choices at each node.
Well, almost. A perverse binary tree can be long and skinny. Let's say that insertions never add elements to a right subtree. Then the tree effectively becomes a linked list. The "binary" chop doesn't exclude half the remaining elements with each comparison, but just one. Logarithmic search times become linear search times. The advantage of the tree structure is lost.
What we really want to maintain is a balanced binary tree. Every left subtree for a node should have just as many nodes as the right subtree, plus or minus one, of course. Then the tree structure really does capture the full benefit of a binary chop. All searches remain nicely logarithmic.
A binary tree also speeds insertions and erasures (deletions). Recall that a vector and a deque require linear time to insert or erase an element at an arbitrary location in the middle — you basically have to copy the controlled sequence over to new storage. But a binary tree consists of independent nodes linked together much like a list. It takes logarithmic time to find where to insert or erase the element, but only constant time to do the subsequent operation.
Well, almost, again. Inserting or erasing an element can easily upset a balanced tree. To rebalance the tree may require shuffling elements between left and right subtrees at a given node. And you may have to do so for nodes everywhere from the top to the bottom of the tree, a depth proportional to the logarithm of N. Insertions and erasures still take logarithmic time, but they take more time nonetheless if you want to keep the tree in balance. And you do.
STL implements a template container class that represents an ordered sequence as a balanced binary tree. (Well, almost, yet again. But that's the topic of next month's installment.) It doesn't expose these trees directly to the programmer. Rather, it uses them to implement four different template container classes. They come in two pairs.
The simpler of the two pairs includes the template classes set and multiset:
template<class K, class Pr = less<K>, class A = allocator<K> > class set; template<class K, class Pr = less<K>, class A = allocator<K> > class multiset;Both store elements with values of type K. Both are ordered by function objects of type Pr, as described above for the fictitious ordered vector and deque classes. And both have the allocator parameter, common to all STL containers. An object of class A allocates and frees storage for the container, as I have described in earlier installments.
Listing 1 shows the template class set. I omit multiset because it is so similar to set. As you might guess, both template classes lean heavily on template class Tree to do all the serious work. I'll discuss Tree next month.
The two template classes differ in one important regard. An object of template class set will not store two elements that have equivalent ordering. An object of template class multiset will do so. The difference has a small effect on one member function. One version of insert returns a range of values with equivalent ordering for multiset. Obviously, only one such value can exist for set.
A set is ordered on the values it stores. That can be a handy way to represent many collections — a set in the usual mathematical sense, for example. But sometimes it can be overly restrictive. Sometimes, you'd like to order a sequence on just part of the information stored in each element. Other information should just go along for the ride. Consider, for example, a symbol table. You want it ordered on the names of the symbols, for quick lookup. But you'd rather the order not be sensitive to the value of the symbol, or any attribute flags.
No problem. You can simply define the predicate class as you see fit. It can compare the name components of stored values and ignore the rest. While this is not a big problem, it is a common enough occurrence to be a nuisance. You'd rather not have to write a special predicate class for every container that holds both a key and a separate value component.
Thus, the second pair of template classes implemented in terms of binary trees. The pair includes the template classes map and multimap:
template<class K, class Ty, class Pr = less<K>, class A = allocator<Ty> > class map; template<class K, class Ty, class Pr = less<K>, class A = allocator<Ty> > class multimap;Both store elements with a pair of values. One element of the pair is the ordering key, of type K. The other element has type Ty. The remaining parameters are the same as for set and multiset.
Listing 2 shows the template class map. Once again, I omit multimap because it is so similar to map. As you can see, map is implemented much like set in Listing 1. It just makes a tree of {key, value} pairs, defining a predicate on the key part alone.
As you might expect, an object of template class map will not store two elements that have equivalent ordering. An object of template class multimap will do so. The two template classes differ rather more than set and multiset, but I won't discuss all the differences here. Suffice it to say that operator[] makes eminent sense for map — it is a cute notation for locating the element uniquely determined by a given key value, or adding such an element if it is not present. But it makes rather less sense for multimap to define such an operator. So it doesn't.
The Power of Association
The template classes set, multiset, map, and multimap are all called associative containers. They all associate a key value with each element, and can use the key to speed lookup, insertion, and erasure of elements.
Table 1, reproduced yet again from earlier installments, shows the payoff for the added complexity in the associative containers (labeled "set/map" in the table). They are clearly superior to all other STL containers when you need to lookup an element by key value. While an ordered vector or deque can match this behavior, neither can do better than linear time for inserts and erases. The underlying tree representation can perform these operations in logarithmic time as well.
A vector or deque can win if you also need to perform indexed lookups as well as associative ones, but this is a rare occurrence. They can also win if you begrudge the extra storage consumed by all those extra pointers per element. Once again, however, this is rarely a major consideration.
So if you need to maintain an ordered sequence to speed associative lookups, insertions, and/or erasures, you can't do better than to use one of the associative containers. But if you don't need the extra performance in these areas, you should probably avoid the considerable extra code complexity required to deliver the better time complexity. 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.