C++ Tip #3: Creating an Index Table in STL, Take 2

In "Creating an Index Table in STL," ("C/C++ Tips #1," August 2000) Craig Hicks points out that an index table is a useful tool with no direct support in the Standard C++ library. However, there is a simple and flexible way to indirectly create one.

An index table is simply a specialized version of a common STL entity — a sequence of pointers. As everyone who has tried to sort a vector of pointers knows, by default, they will be sorted according to the order of the pointers — the ordering of the addresses in memory. Most of the time you'd rather sort them according to the ordering of the objects pointed to. The simplest way to do this is to define an operator< for the pointers:

bool operator < (Widget const *a, Widget const *b)
   { return *a < *b; }

This solution won't work for an index table, because you can't redefine operator< on built-in integer types, and you wouldn't want to if you could. Luckily, the STL authors anticipated the need to sort using other criteria. You are allowed to pass a comparison function or function object to the sort routines.

In this case, the comparison function needs to know the index value and the sequence that is being indexed. This solution requires a function object to store the information pertaining to what is being sorted. Though my solution uses only the begin iterator, I also store the end iterator. That feels more natural to me, and the end iterator could be used for error-checking, so it's a good idea to have it available. Note that the iterators must be random-access iterators for this to work.

#include <vector>
#include <algorithm>
#include <iostream>

template <class random_iterator>
class IndexedComparison
{
   public:
      IndexedComparison (random_iterator begin,
         random_iterator end)
         : p_begin (begin), p_end (end) {}
      bool operator () (unsigned int a, unsigned int b) const
         { return *(p_begin + a) < *(p_begin + b); }

   private:
      random_iterator const p_begin;
      random_iterator const p_end;
};

// Setup and reporting code below by Craig Hicks

int main()
{
   unsigned int i;
   int ai[10] = { 15,12,13,14,18,11,10,17,16,19 };

   std::cout << "#################" << std::endl;
   std::vector<int> vecai(ai, ai+10);

   std::vector<unsigned int> indices(vecai.size ());
   for (i = 0; i < indices.size (); i++)
      indices [i] = i;

   std::sort (indices.begin (), indices.end (),
      IndexedComparison<std::vector<int>::const_iterator>
         (vecai.begin (), vecai.end ()));

   for (i=0; i<10; i++)
      std::cout << "i=" << i
                << ", aidxtbl[i]=" << indices[i]
                << ", ai[aidxtbl[i]]=" << ai[indices[i]]
                << std::endl;
   std::cout << "#################" << std::endl;
   return 0;
}

The sort call becomes a bit long-winded, but it does the job admirably. It creates a temporary IndexedComparison object, keyed to the const_iterator of the sequence being indexed, and initialized with its begin and end iterators. That function object then ensures that the index sequence is sorted properly.

Any kind of STL sort can be used this way. The IndexedComparison object can also be extended to allow you to pass in a comparison function for the objects being indexed, which would make this solution every bit as flexible as the STL sorts themselves.

Herb Sutter pointed out a disadvantage of this approach: "it pushes logic out into the calling code, which now has to loop to build the array and then call sort with the correctly typed predicate — and this has to be repeated everywhere this is going to be used. The original was better encapsulated, with just a single function call that included the setup."

Herb adds, "However, exposing sort does give a benefit, to wit, the ability to replace the sorting function to be used, which was a question left for readers on the original."

Several other readers have contributed interesting solutions in response to Tip #1, which we may explore in future Tips. Some of those solutions, like Craig Hicks' solution, require creation of a temporary table of iterators — potentially costly in terms of space and performance. I like the solution above because it doesn't require creation of any intermediate tables. — mb

Thanks to Sol Foster for this tip. If you have a C/C++ programming tip and can write it up in 400 words or less, send it to [email protected]. If we print your tip, we'll send you a nice CUJ shirt and a copy of the CUJ CD-ROM.