Polymorphic Comparisons

In this article, we discuss a class template utility called PolyLessThan that enables C++ programmers to rapidly develop and easily maintain a polymorphic comparator. PolyLessThan relies on the Visitor pattern.

Ordering polymorphic objects

Suppose that we wish to maintain a collection of teachers and students resident in a school. Teachers are ordered by their employee number, whereas students are ordered sorted by their name. The ordering within a type is defined trivially by overloading the < operator, but comparisons across types (i.e., between Residents) are not catered for. The classes that define these entities are outlined in Listing 1.

struct Resident
{
  ...
};

struct Teacher : Resident
{
  ...
  bool operator< (const Teacher& that) const
  {
    return that.ref < ref;
  }
  int ref;
};

struct Student : Resident
{
  ...
  bool operator< (const Student& that) const
  {
    return that.name < name;
  }
  string name;
};
			

Suppose next that we wish to maintain (i) a set of pointers to residents and (ii) a map of pointers to residents to their age in years. A standard solution that makes use of the Containers library is shown below:

  set<const Resident*> set_residents;
  map<const Resident*, int> map_resident_age;

Unless otherwise specified, a set or map will order these pointers according to their memory address, which may be unstable from one program execution to another and are obscure in relation to the object content, meaning that an iterator will traverse the objects in an unnatural and possibly unpredictable order. Consequently, one typically supplies a functor that provides a ‘less-than’ comparison operation via an additional template argument. This is straightforward in the case of a derived type. Listing 2 shows an ordered set of Teachers.

struct TeacherLessThan
{
  bool operator() (
  const Teacher* pTeacher1,
  const Teacher* pTeacher2) const
  {
    return *pTeacher1 < *pTeacher2;
  }
}

set<const Teacher*, 
  TeacherLessThan> set_teachers;
			

We now face the issue of how to compare Residents – or pointers to them – in a natural, robust and extensible fashion.

By natural, we mean that the order should be defined in a content-wise fashion, based on datatypes and values, rather than in relation to a memory address or a hashcode. For instance, we could insist that x < y for a teacher x and a student y.

By robust, we mean that reasoning about the types involved in the comparisons should work ‘with the grain’ of the C++ type system and not rely on support from type enums, type casts or similar indicators. This we accomplish via use of the well-known Visitor pattern, discussed below.

Finally, by extensible, we mean that it should be possible to derive new types from the base class and have them participate in comparisons (e.g., as set members or map keys) with minimal effort. For instance, we may wish to add an AdminStaff class, whose objects are sorted by start date.

Visitor pattern

The Visitor pattern is a form of dependency inversion, which permits the definition of an operation outside of the class definitions, whilst retaining polymorphism via virtual dispatch [Gamma95]. Listing 3 shows how the code in Listing 1 can be fleshed out such that the Resident inheritance structure supports visiting.

struct ResidentVisitor
{
  virtual ~ResidentVisitor() = default;
  virtual void Visit(const Teacher&) = 0;
  virtual void Visit(const Student&) = 0;
};

struct Resident
{
  virtual ~Resident() = default;
  virtual void Accept(ResidentVisitor& visitor)
    const = 0;
};

struct Teacher : Resident
{
  Teacher(int ref_) : ref(ref_) { }
  void Accept(ResidentVisitor& visitor) 
    const override final
  {
    visitor.Visit(*this);
  }

  bool operator< (const Teacher& that) const
  {
    return ref < that.ref;
  }
  int ref;
};

struct Student : Resident
{
  Student(string name_) : name(name_) { }
  void Accept(ResidentVisitor& visitor) const
    override final
  {
    visitor.Visit(*this);
  }

  bool operator< (const Student& that) const
  {
    return name < that.name;
  }
  string name;
};
			

To maintain a set of pointers to Resident ordered by content (as opposed to address or insertion order), we require a binary comparator functor, such as that shown in Listing 4. How such a comparator should be defined is not immediately obvious, owing to the polymorphism of Resident.

struct ResidentLessThan
{
  bool operator() (const Resident* pr1,
    const Resident* pr2) const
  {
    // Implementation...
  }
}

set<Resident*, ResidentLessThan> set_residents;
map<Resident*, Contact, 
  ResidentLessThan> map_resident_contact;
			

Any visitor-based comparator must visit both *pr1 and *pr2 in order to establish their type. Within- or across-type comparisons can proceed once this information is available. However, writing this code every time a new visitable inheritance hierarchy is defined is laborious.

Comparator Visitor

We propose the labour-saving class template PolyLessThan to facilitate sorting of visitable objects, defined in Listing 5.

template <class TVisitorBase, class ...TArgs>
class PolyLessThan
{

public:
  template <class T1, class T2>
  bool operator()(const T1* pt1,
    const T2* pt2) const
  {
    auto polyCompare = Impl<1, TArgs...>();
    pt1->Accept(polyCompare);
    pt2->Accept(polyCompare);
    return polyCompare.result;
  }

private:
  template <int N, class ...TInnerArgs>
  struct Impl : TVisitorBase
  {
    bool result = false;
  protected:
    int n = 0;
    const void* pt = nullptr;
  };
  template <int N, class TItem,
    class ...TInnerArgs>
  struct Impl<N, TItem, TInnerArgs...> 
    : Impl<N+1, TInnerArgs...>
  {
    void Visit(const TItem &t) override final
    {
      if (this->n == 0)
      {
        this->n = N;
        this->pt = static_cast<const void *>(&t);
      }
      else if (this->n < N)
      {
        this->result = true;
      }
      else if (N < this->n)
      {
        this->result = false;
      }
      else
      {
        this->result = *static_cast<const TItem 
          *>(this->pt) < t;
      }
    }
  };
  static_assert(
    !std::is_abstract<Impl<1, TArgs...>>::value,
    "Cannot compile polymorphic comparator: "
    "no concrete implementation for one or more "
    "Visit functions");
};
			

The class template takes a pure virtual visitor base class as its first argument, followed by a complete variadic list of visitable types for the remainder of its arguments, such that types specified earlier in the list are less than those that come later. Listing 6 shows a Resident comparator that sorts Teachers before Students, along with an example of its deployment.

using ResidentLessThan =
  PolyLessThan<ResidentVisitor,
  Teacher,
  Student>;

  auto student1 = Student("Jarvis");
  auto student2 = Student("Deborah");
  auto teacher1 = Teacher(1701);
  auto teacher2 = Teacher(24601);
  auto residents =
    set<const Resident*, ResidentLessThan>({
      &student1,
      &student2,
      &teacher1,
      &teacher2 });
			

From the programmer’s perspective, the task of defining a polymorphic comparator is accomplished entirely by this alias. If a new Visit clause is added to ResidentVisitor, then the using statement will not compile until the ordering over types is updated.

The implementation of the class template itself proceeds along similar lines to the inline visitor [Mill14, Coe15]. The private class Impl is templated on a particular item type and an ordering integer N. As each variadic argument is stripped off the list TArgs, N is incremented, and a new base class is defined; and this pattern recurses until all the arguments are consumed. The Visit functions are designed to be called up to twice.

• First, *pt1 accepts Impl as a visitor. The invoked Visit member retains the pointer pt1, along with the template argument N, established at compile-time, which serves to enumerate the type. These are stored in protected members of the innermost Impl base class, pt and n, respectively. The Impl class is aware of the first invocation because a value of 0 for n serves as a sentinel.
• Second, *pt2 accepts Impl as a visitor. When the control path enters the base class containing the Visit member, if the value for N matches that stored from the previous iteration, the types match, and the values are compared using the <operator particular to that sub-type. Otherwise, the values of N are themselves compared, which effects an ordering over types.

Although the logic underlying the template is recursive, this does not translate into recursive logic at runtime; the outermost (i.e. the most derived) Impl class is simply an automated implementation of the visitor class that the consumer would need to write themselves without PolyLessThan.

References

[Coe15] Jonathan Coe, ‘An Inline-variant-visitor with C++ Concepts’, Overload 129, October 2015.

[Gamma95] E. Gamma et al., Design Patterns, Addison-Wesley, Longman, 1995.

[Mill14] Robert Mill and Jonathan Coe, ‘Defining Visitors Inline in Modern C++’ Overload 123, October 2014.