Things to think about when designing your programs.
Prev	Chapter 4. Using the Standard Template Library	Next

Making function objects work with inheritance.

Sorting with STL

The sorting problem

A lot of STL classes and functions take a function class as a template argument. It's sort of hard to explain what this means, so I'll start with an example that comes up a lot. Suppose you want to sort an array of strings but you want to be able to decide at run time what order to use. For example, your program may take command line arguments that make it do plain alphabetical order or reverse alphabetical order. The super-slick OO way to do this is to use the Command design pattern:

Example 4-2. Sorting with the Command Design Pattern

template<class Type>
class Comparison
{
public:
    virtual ~Comparison() {};

    virtual int Compare( const Type & x, const Type & y ) = 0;
};

class AlphaCompare : public Comparison<string>
{
...
};

class ReverseAlphaCompare : public Comparison<string>
{
...
};

Each subclass of Comparsion<string> implements a different sort order. Then, we can do the sort as follows:

Example 4-3. Sorting with Commands

void DoSort( vector<string> & v, Comparison<string> * c )
{
  // use c->Compare(v[i], v[j]) to sort the vector
  ...
}

And depending on what command line flag we find:

Example 4-4. Using the command line

Comparison<string> * c;

if( alpha command line flag )
{
  c = new AlphaCompare();
}
else if( reverse alpha command line flag )
{
  c = new ReverseAlphaCompare();
}
...
DoSort( someVector, c );

The tricky part is using STL's sort function. Here's the signature for the two variations of sort:

Example 4-5. STL sort function

template<class RanIt>
    void sort(RanIt first, RanIt last);
template<class RanIt, class Pred>
    void sort(RanIt first, RanIt last, Pred pr);

Here, RanIt must be an iterator that supports random access. Vector iterators and such are fine for this. The first version of sort always uses the < operator. However, if we try to use that, then we can only sort strings according to the built-in, alphabetical order. So, it looks like we have to use the other version, which takes an additional template parameter. Pred is a predicate class, which must look something like this by STL convention:

Example 4-6. Predicate class

class SomePredicate
{
public:
   bool operator() ( const Type & a, const Type & b );
};

The code for sort actually looks something like this:

Example 4-7. How sort uses predicates

template<class RanIt, class Pred>
void sort(RanIt first, RanIt last, Pred pr)
{
  ...
  // do some efficient sort, and when we need to compare two items:
  if( pr( item1, item2 ) ) // calls operator() function
  {
    // put item1 first
  }
  else
  {
    // put item2 first
  }
  ...
}

The idea here is that we can presumably pass in different predicate objects and change the order at run-time. Something sort of like this:

Example 4-8. Changing sort order at run-time

Predicate pr;

if( alpha flag )
{
  pr = some instance of class Predicate that sorts in alphabetical
    order;
}
else if( reverse alpha flag )
{
  pr = some other instance of class Predicate that sorts in reverse 
    order;
}
...
sort( someVector.begin(), someVector.begin.end(), pr );

There are several things to note about this code.

We have to pass in the predicate object by value. This means that in the above example, pr is copied, and it is the copy that the sort function deals with.
The variable pr is declared to be of type Predicate, so we always end up calling this version of sort: sort( vector::iterator, vector::iterator, Predicate ).

A solution that doesn't work

One solution that many people came up with when they ran into this problem is the following:

Example 4-9. Wrong solution: virtual operator()

class FooComparison
{
public:
  virtual bool operator()( const string & a, const string & b ) = 0;
};

class AlphaFooComparison : class FooComparison
{
...
};

class ReverseAlphaFooComparison : class FooComparison
{
...
};

main()
{
  FooComparison * pr;

  if( alpha flag )
  {
    pr = new AlphaFooComparison();
  }
  else if( reverse alpha flag )
  {
    pr = new ReverseAlphaFooComparison();
  }
  ...
  sort( someVector.begin(), someVector.end(), *pr );
}

This is basically the same as the original code except that we got fancy and used STL's sort, so we had to use operator() to do the work instead of Compare. We expect the right version of operator() to be called since it is a virtual function. In other words, if we pass sort an instance of AlphaFooComparison, we expect it to call the AlphaFooComparison version of operator(), and if we pass in an instance of ReverseAlphaFooComparison, we expect it to call the ReverseAlphaFooComparison version of operator(). That's what virtual member functions are supposed to do, right?

Almost. If you fill in the details of the code and compile and run it, your program dies and says "Pure virtual function called."

The problem is this: The magic of virtual functions only works when you invoke them with a pointer or a reference:

Example 4-10. Virtual function magic

FooComparison * a;
FooComparison & b;

a->operator()( x, y ); // virtual function magic!
(*a)( x, y ); // different syntax, same magic!
b( x, y ); // magic!

FooComparsion c;
c( x, y ); // NO MAGIC!

The problem with the sorting code is that it passes the predicate object in by value. When you call a method on an actual object, not a reference or a pointer, you always get the version that corresponds to the type of the variable. In other words, the sort function ends up doing this:

Example 4-11. Where sorting goes wrong

sort( vector<string>::iterator first,
      vector<string>::iterator last,
      FooComparsion pr )
{
  ...
  // sorting right along...
  if( pr( item1, item2 ) ) // OOPS!
  {
  ...
  }
  ...
}

In the OOPS! line, it sees that it has an actual FooComparsion object and not a pointer or reference, so it calls FooComparsion::operator() which, as you can see by the definition, is a pure virtual function, which you aren't allowed to call, hence our catastrophe.

Another solution that doesn't work

So, what do we do? Well, things would be okay if we could pass in that predicate by reference. So, we make another brave attempt and explicitly give sort its template arguments:

Example 4-12. Trying to be more explicit (and failing)

sort<vector<string>::iterator,FooComparsion&>( someVector.begin(),
    someVector.end(), pr );

And we are disappointed to see that for whatever reason, this doesn't work either. We compile and run and it tells us once again, "pure virtual function called". So, despite our best efforts, that predicate is still being passed around by value. I'm not sure if it's supposed to according to the C++ standard. At any rate, if it doesn't work now, it doesn't matter if they're going fix it in the next release of gcc a year from now; our program is due by midnight! So what do we do?

A working solution using an Adapter class

How about using an Adapter class: The idea here is that we must pass in something that you can call operator() on, that you can pass around by value (by copy), and that will do virtual function magic. The operator() part means it must be an instance of class, but how do we do the rest of it? It sounds like we need to put a wrapper around a pointer somehow:

Example 4-13. STLTestAdapter class

template<class Type>
class Comparison
{
public:
    virtual ~Comparison() {};
    virtual bool operator()( const Type & x, const Type & y ) = 0;

};

template<class Type>
class STLTestAdapter
{
public:
    STLTestAdapter( Comparison<Type> * c ) 
	: myCompare(c) 
	{}

    bool operator()( const Type & left, const Type & right )
	{
	    return (*myCompare)( left, right );
	}

private:
    Comparison<Type> * myCompare;
};

...

main()
{

  Comparison * pr;
  ...

  // our sorting call becomes:
  STLTestAdapter<string> adapter( pr ); 
  sort( someVector.begin(), someVector.end(), adapter );

  ...
}

If you think for a minute, you'll see what's different about this case. Now watch what happens when sort needs to compare something:

Example 4-14. How sort uses predicates

sort( vector<string>::iterator first,
      vector<string>::iterator last,
      STLTestAdapter<string> pr )
{
...
   if( pr( item1, item2 ) )
   {
   ...
   }
...
}

Since it has an acutal STLTestAdapter object, it calls STLTestAdapter::operator() as we expect from our previous woes. But, that method turns around and invokes operator() on the myCompare member of the STLTestAdapter object, but it's a pointer! The call pr(item1, item2) is really doing this:

Example 4-15. What the parentheses do

(pr.myCompare)->operator()( item1, item2 )

That call does do virtual function magic, the right version of operator() is called, and finally our sorting program works. The virtual function call has been wrapped in a non-virtual function call that happens to fit the syntax required by the templated sort function.

Here's a full source listing that demonstrates sorting that works like we want, just for reference:

Example 4-16. Full source of sorting program

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

template<class Type>
class Comparison
{
public:
    virtual ~Comparison() {};

    virtual bool operator()( const Type & x, const Type & y ) = 0;

};


template<class Type>
class STLTestAdapter
{
public:
    STLTestAdapter( Comparison<Type> * c ) 
	: myCompare(c) 
	{}

    bool operator()( const Type & left, const Type & right )
	{
	    return (*myCompare)( left, right );
	}

private:
    Comparison<Type> * myCompare;
};

class AlphaOrder : public Comparison<string>
{
public:
    bool operator()( const string & left, const string & right )
	{
	    return left < right;
	}
};

class ReverseAlphaOrder : public Comparison<string>
{
public:
    bool operator()( const string & left, const string & right )
	{
	    return right < left;
	}
};

void
Print( vector<string> & v )
{
    vector<string>::iterator iter;
    for( iter = v.begin(); iter != v.end(); iter++ )
    {
	cout << *iter << endl;
    }
    cout << "-----" << endl;
}

void
DoSort( vector<string> & v, Comparison<string> * compare )
{

    STLTestAdapter<string> adapter(compare);
    sort( v.begin(), v.end(), adapter );
}

main()
{
    vector<string> words;
    words.push_back( "banana" );
    words.push_back( "apple" );
    words.push_back( "spoon" );
    words.push_back( "pancake" );
    words.push_back( "ant" );

    Print( words );

    DoSort( words, new AlphaOrder() );
    Print( words );

    DoSort( words, new ReverseAlphaOrder() );
    Print( words );

}

Prev	Home	Next
Using the Standard Template Library	Up	Hints on a few assignments