Skip to content

Unintuitive (but correct) STL lower_bound algorithm

When I was looking for a C lower-bound algorithm — after I wound up writing it myself — I realized that there was an implementation in STL.

A Detour into STL

STL, in case your programming life is lived under a rock labeled “C#”, is an awesome set of template routines for C++, for having collections, iterating over them, applying functions, and generally making C++ achieve about a tenth of the power of a language like Lisp or perl.

I’m kidding. A little.

Anyway, the cool thing about STL is that it can achieve a lot of the power of a dynamic language by using templates in clever, innovative, and (critics say) scary and evil ways. For example, not taken at random, the concept of iterators exists in STL. An iterator is a sort of generalized pointer, where (at minimum) the operations ++ and * are defined on it. If the iterator is bidirectional, then the operation — is also defined. If the iterator is random-access, then the operations +(int) and -(int) are also defined. A bare pointer is an example of a random access iterator.

So fine, we’ve built up a formalism for describing pointers and things that act like pointers but are less useful. What’s the point? The point is, through the magic of templates, you can write code that takes advantage of the features of a random-access iterator but degrades gracefully to a weaker iterator (e.g., bidirectional or forward-only), and so you can write algorithms that work on both a vector and a doubly-linked list, but give you the best available scaling for free. Not only that, this selection operates at compile-time and incurs no runtime penalty.

Sounds like magic? It is! Here’s how the advance function is implemented in STL, using python-y pseudocode:

def advance( i, n )
  case i.class of ForwardIterator
    while( n-- ) i++
  case i.class of BidirectionalIterator
    if( n >= 0 )
      while( n-- ) i++
      while( n++ ) i--
  case i.class of RandomAccessIterator
    i += n

At a later date I’ll probably go into the gory details of how this selection is done in C++ at compile-time. Not because it’s not well explained at the SGI STL site and in many fine books. But because pushing the concepts out of my head into words makes them clearer in my mind. (Anyway, in brief, an ancillary type hierarchy of tag types is defined, and the compiler’s rule of selecting the most-derived matching template is exploited.)

Back to Lower Bound

For the moment let’s get back to lower bound, which is how we got here in the first place. The algorithm finds the furthest iterator in an ordered range that is still less than some test value. My naive guess as to the implementation was:

def lower_bound( l, u, v )
  case i.class of RandomAccessIterator
    # some variation of binary search
  case i.class of ForwardIterator
    lastgood = l
    while( *l < v )
      lastgood = l++
    return lastgood

So if we have a random-access capable iterator, where advancing the iterator any number of steps was O(1), we would use binary search, which gives us an overall running time of O(lg n). But if advancing the iterator n steps cost O(n), then we would use the naive linear search algorithm, for an overall average running time of O(n) and an expected cost of n/2 when the value is drawn from within the range [*l, *u).

But that’s not what the algorithm is at all. And to the strangeness (but correctness) of that, I will have to return another time, because right now I have to get to work.