Классифицированный контейнерный класс C++: как лучше поддерживать как упорядоченные, так и неупорядоченные типы элементов?

Question

Я пишу шаблонный контейнерный класс C++, который может поддерживать свое содержимое в четко определенном порядке. Ранее он использовал указатели на функции для упорядочивания своего содержимого разумным образом, зависящим от типа, но я пытаюсь изменить его, чтобы использовать вместо него аргументы шаблонного функтора.

Поскольку часто бывает так, что пользователь класса может захотеть хранить элементы одного и того же типа отсортированными по-разному в разных контейнерах, класс контейнера принимает необязательный аргумент шаблона, который позволяет пользователю по желанию указать свой собственный функцию сравнения:

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

Если пользователь класса не указывает пользовательский тип функтора, он по умолчанию использует следующее определение CompareFunctor:

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
    }
};

Это прекрасно работает для встроенных типов, а также для пользовательских типов, где был определен оператор "меньше". Однако мне бы хотелось, чтобы он также автоматически работал для типов, в которых нет встроенного или явно определенного оператора меньше чем. Для этих типов порядок элементов в контейнере не важен.

Мотивация заключается в том, что я использую этот контейнер для хранения множества различных типов, и большую часть времени меня не волнует порядок типов в контейнере, но в некоторых случаях я делаю... и я не Я не хочу входить и добавлять "фиктивные" операторы "меньше" ко всем этим различным типам, просто чтобы я мог использовать их с этим классом контейнера... и я не хочу явно указывать собственный "фиктивный" Msgstr "Аргумент CompareFunctor каждый раз, когда я использую таблицу для хранения элементов, у которых нет оператора меньше чем.

Итак, есть ли способ, которым я могу использовать специализацию шаблона (или что-то в этом роде), чтобы по умолчанию использовался CompareFunctor (показанный выше), когда это возможно, но в тех случаях, когда этот CompareFunctor приводил к ошибке, C++ автоматически возвращался к "фиктивному" FallbackCompareFunctor, как показано ниже? Или, может быть, какой-то другой умный способ справиться с этой дилеммой?

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

В случае, если кому-то интересно, я смог придумать способ сделать то, что хотел, используя комбинацию методов, описанных выше. Мой код подтверждения концепции (с модульным тестом) показан ниже.

#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;
}

Answer 2

Для вашего несортированного случая по умолчанию используйте функтор сравнения Null, который просто возвращает false для всех случаев.
Затем вы можете специализировать свой шаблон для отсортированного контейнера с помощью функтора std::less().

       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 3

Выполняя поиск в Google на основе ответа Юджина, я нашел эту статью:

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

Возможно, я смогу адаптировать код, представленный там...

Answer 4

boost::enable_if может включать и выключать специализации шаблонов на основе некоторой оценки времени компиляции.

Если вы можете создать конструкцию, которая будет иметь значение false во время компиляции, если проверяемый вами тип не имеет оператора lessthan, то вы можете использовать его для включения резервной специализации для 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; 
}

Конечно, вам также нужно some_condition для проверки оператора lessthan каким-то образом... Посмотрите на boost::type_traits и код MPL, я думаю - они делают схожие вещи.