C++ templated container class: How to best support both ordered and un-ordered item types?

Question

Hi all,

I'm writing a templated C++ generic container class that can optionally maintain its contents in a well-defined order. Previously it used function pointers to order its contents in a sensible type-specific way, but I am attempting to change it to use templated functor arguments instead.

Since it's often the case that the class's user might want to keep items of the same type sorted in different ways in different containers, the container class takes an optional template argument that lets the user optionally specify his own compare-functor:

template <class ItemType, class CompareFunctorType = CompareFunctor<ItemType> > class MyContainer
{
    [...]
};

If the class user doesn't specify a custom functor type, it uses the following CompareFunctor definition by default:

template <typename ItemType> class CompareFunctor
{
public:
    bool IsItemLessThan(const ItemType & a, const ItemType & b) const
    {
       return (a<b);   // will compile only for types with < operator
    }
};

This works great for built-in types and also user-defined types where a less-than operator has been defined. However, I'd like it to also automatically work for types where there is no built-in or explicitly defined less-than operator. For those types, the ordering of the items within the container is not important.

The motivation is that I use this container to hold a lot of different types, and most of the time, I don't care about the order of the types in the container, but in some cases I do... and I don't want to have to go in and add "dummy" less-than operators to all of these different types just so I can use them with this container class... and I don't want to have to explicitly specify a custom "dummy" CompareFunctor argument every time I use the table to store items that don't have a less-than operator.

So, is there a way I can use template specialization (or something) so that the default CompareFunctor (shown above) is used whenever possible, but in cases where that CompareFunctor would cause an error, C++ would automatically fall back to a "dummy" FallbackCompareFunctor like the one below? Or perhaps some other clever way to handle this dilemna?

template <typename ItemType> class FallbackCompareFunctor
{
public:
    bool IsItemLessThan(const ItemType & a, const ItemType & b) const
    {
       return ((&a)<(&b));   // will compile for all types (useful for types where the ordering is not important)
    }
};

Answer 1

For your default unsorted case, use a Null Comparison functor that just returns false for all cases.
You can then specialise your template to a sorted container using the std::less() functor.

       template<class T>
       struct NullCompare: public binary_function <T, T, bool> 
       {
          bool operator()(const T &l, const T &r) const
          {
              // edit: previously had "return true;" which is wrong.
              return false;
          }
       };

       template <class T, class Compare=NullCompare<T> > 
       class MyContainer
       {
           [...]
       };

       template <class T, class Compare=std::less<T> > 
       class MySortedContainer : public MyContainer<T, Compare>
       {
           [...]
       };

Answer 2

boost::enable_if can turn template specializations on and off based on some compile time evaluation.

If you can create a construct that would evaluate to false at compile time if the type you are checking doesn't have lessthan operator, then you can use that to enable fallback specialization for CompareFunctor::IsItemLessThan.

template <typename ItemType> class CompareFunctor
{
public:
    bool IsItemLessThan(const ItemType & a, const ItemType & b) const
    {
       return OptionalLessThan<ItemType>(a, b); 
    }
};

template<class T> 
typename boost::enable_if<some_condition<T>, bool>::type 
OptionalLessThan(const T& a, const T& b)
{
    return ((&a)<(&b)); 
}

template<class T> 
typename boost::disable_if<some_condition<T>, bool>::type 
OptionalLessThan(const T& a, const T& b)
{
    return a < b; 
}

Of course you also need some_condition to check for operator lessthan somehow... Look at boost::type_traits and MPL code I guess -- they do similar stuff.

Answer 3

While doing some Google searches based on Eugene's answer, I found this article:

http://www.martinecker.com/wiki/index.php?title=Detecting_the_Existence_of_Operators_at_Compile-Time

Perhaps I can adapt the code presented there...

Answer 4

In case anyone is interested, I was able to come up with a way to do what I wanted, using a combination of the techniques described above. My proof-of-concept code (with unit test) is shown below.

#include <stdio.h>

// Real functor, should be used by default when ItemType has a < operator
template <typename ItemType> class RealCompareFunctor
{
public:
   bool IsLessThan(const ItemType & item1, const ItemType & item2)
   {
      printf(" --> RealCompareFunctor called!\n");
      return item1 < item2;
   }

   typedef ItemType TheItemType;
};

// Dummy functor, should be used by default when ItemType has no < operator
template <typename ItemType> class DummyCompareFunctor
{
public:
   bool IsLessThan(const ItemType & item1, const ItemType & item2)
   {
      printf(" --> DummyCompareFunctor called!\n");
      return (&item1) < (&item2);
   }
};

namespace implementation_details
{
    // A tag type returned by operator < for the any struct in this namespace when T does not support (operator <)
    struct tag {};

    // This type soaks up any implicit conversions and makes the following (operator <)
    // less preferred than any other such operator found via ADL.
    struct any
    {
        // Conversion constructor for any type.
        template <class T> any(T const&);
    };

    // Fallback (operator <) for types T that don't support (operator <)
    tag operator < (any const&, any const&);

    // Two overloads to distinguish whether T supports a certain operator expression.
    // The first overload returns a reference to a two-element character array and is chosen if
    // T does not support the expression, such as < whereas the second overload returns a char
    // directly and is chosen if T supports the expression. So using sizeof(check(<expression>))
    // returns 2 for the first overload and 1 for the second overload.
    typedef char yes;
    typedef char (&no)[2];

    no check(tag);

    template <class T> yes check(T const&);

    // Implementation for our has_less_than_operator template metafunction.
    template <class T> struct has_less_than_operator_impl
    {
        static const T & x;
        static const bool value = sizeof(check(x < x)) == sizeof(yes);
    };

   template <class T> struct has_less_than_operator : implementation_details::has_less_than_operator_impl<T> {};

   template <bool Condition, typename TrueResult, typename FalseResult>
   class if_;

   template <typename TrueResult, typename FalseResult>
   struct if_<true, TrueResult, FalseResult>
   {
     typedef TrueResult result;
   };

   template <typename TrueResult, typename FalseResult>
   struct if_<false, TrueResult, FalseResult>
   {
      typedef FalseResult result;
   };
}

template<typename ItemType> struct AutoChooseFunctorStruct
{
   typedef struct implementation_details::if_<implementation_details::has_less_than_operator<ItemType>::value, RealCompareFunctor<ItemType>, DummyCompareFunctor<ItemType> >::result Type;
};

/** The default FunctorType to use with this class is chosen based on whether or not ItemType has a less-than operator */
template <class ItemType, class FunctorType = struct AutoChooseFunctorStruct<ItemType>::Type > class Container
{
public:
   Container()
   {
      ItemType itemA;
      ItemType itemB;
      FunctorType functor;
      bool isLess = functor.IsLessThan(itemA, itemB);
      //printf(" --> functor says isLess=%i\n", isLess);
   }
};

// UNIT TEST CODE BELOW

struct NonComparableStruct {};

struct ComparableStructOne
{
   bool operator < (ComparableStructOne const&) const { return true; }
};

struct ComparableStructTwo {};
bool operator < (ComparableStructTwo const&, ComparableStructTwo const&) { return true; }

class NonComparableClass
{
public:
   NonComparableClass() {/* empty */}
};

class ComparableClass
{
public:
   ComparableClass() {/* empty */}

   bool operator < (const ComparableClass & rhs) const {return (this < &rhs);}
};

int main(int argc, char * argv[])
{
   printf("\nContainer<int>\n");
   Container<int> c1;

   printf("\nContainer<ComparableStructOne>\n");
   Container<ComparableStructOne> c2;

   printf("\nContainer<ComparableStructTwo>\n");
   Container<ComparableStructTwo> c3;

   printf("\nContainer<NonComparableStruct>\n");
   Container<NonComparableStruct> c4;

   printf("\nContainer<NonComparableClass>\n");
   Container<NonComparableClass> c5;

   printf("\nContainer<ComparableClass>\n");
   Container<ComparableClass> c6;

   return 0;
}