How to implement a “virtual” operator<

In order to support a collection of heterogenous objects, I implemented a std::set<std::shared_ptr<Base>> then inherited the derived classes from Base.  That works fine, except that the ordering and uniqueness is controlled by the object addresses, not the values of the derived objects.  Ideally, one would make operator< virtual on Base, but that won’t work here because the signature of operator< for each of the derived classes is different:

bool Base::operator<( const Base& rhs ) const
{  /* implementation */ }

bool A::operator<(const A& rhs ) const
{ /* implementation */  }

bool B::operator<(const B& rhs ) const
{ /* implementation */  }

Instead, this solution follows the “Non-Virtual Interface” idiom and leaves operator< non-virtual. Instead, operator< delegates to a separate virtual method, compares_less. In order to provide a strict-weak-ordering, the objects of distinct types need to be handled too – it’s not enough to fall back to comparing pointer addresses (the addresses could provide an inconsistent ordering).  Here, inter-type comparisons are handled by ordering on the type name (supplied by another virtual method).

// LessThan.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <iostream>
#include <set>
#include <string>

template<typename Container>
void dump( const Container& elements )
{
  for ( auto it = elements.begin(); it != elements.end(); ++it )
  {
    if ( it != elements.begin() )
    {
      std::cout << ", ";
    }
    std::cout << (*it);
  }
  std::cout << std::endl;
}

class Base
{
public:
  bool operator<( const Base& rhs ) const
  {
    return this->compares_less( rhs );
  }

  virtual std::ostream& dump( std::ostream& os ) const = 0;

  virtual bool compares_less( const Base& rhs ) const = 0;
  virtual std::string type_name() const = 0;
};

class A : public Base
{
  int a_;
public:
  A(int a) : a_(a)
  {}

  int a() const { return a_; }

  virtual std::ostream& dump( std::ostream& os ) const
  {
    os << a_;
    return os;
  }

  virtual bool compares_less( const Base& rhs ) const
  {
    if ( auto pA = dynamic_cast<const A*>( &rhs ) )
    {
      return a_ < pA->a_;
    }
    return this->type_name() < rhs.type_name();
  }

  virtual std::string type_name() const
  {
    return "A";
  }
};

class B : public Base
{
  std::string b_;
public:
  B( std::string b ) : b_(b)
  {}

  std::string b() const { return b_; }

  virtual bool compares_less( const Base& rhs ) const
  {
    if ( auto pB = dynamic_cast<const B*>( &rhs ) )
    {
      return b_ < pB->b_;
    }
    return this->type_name() < rhs.type_name();
  }

  virtual std::string type_name() const
  {
    return "B";
  }

  virtual std::ostream& dump( std::ostream& os ) const
  {
    os << b_;
    return os;
  }
};

std::ostream& operator<<( std::ostream& os, const std::shared_ptr<Base>& b )
{
  b->dump( os );
  return os;
}

struct LessThan
{
  bool operator()( const std::shared_ptr<Base>& lhs, const std::shared_ptr<Base>& rhs ) const
  {
    return *lhs < *rhs;
  }
};

int _tmain(int argc, _TCHAR* argv[])
{
  std::set<std::shared_ptr<Base>, LessThan> elements;

  elements.insert( std::make_shared<A>( 1 ) );
  elements.insert( std::make_shared<A>( 10 ) );
  elements.insert( std::make_shared<B>( "World" ) );
  elements.insert( std::make_shared<A>( 7 ) );
  elements.insert( std::make_shared<B>( "C++ says" ) );
  elements.insert( std::make_shared<A>( 3 ) );
  elements.insert( std::make_shared<B>( "Hello" ) );
  elements.insert( std::make_shared<A>( 5 ) );

  dump( elements );

  return 0;
}

Here’s the output, showing that the A’s and B’s are ordered as expected:
VirtualLessThanOutput

Leave a comment

Filed under C++, C++ Code, Programming

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s