C ++ classe contêiner modelo: Como melhor suporte a pedidos e os tipos de itens un-ordenada?

Question

Eu estou escrevendo um templated C ++ classe contêiner genérico que pode, opcionalmente, manter o seu conteúdo em uma ordem bem definida. Anteriormente ele usou ponteiros de função para ordenar o seu conteúdo de uma maneira específica do tipo sensível, mas eu estou tentando alterá-lo para usar argumentos functor templated vez.

Uma vez que é frequentemente o caso que o usuário da classe pode querer manter os itens do mesmo tipo classificados de diferentes maneiras em diferentes recipientes, a classe recipiente recebe um argumento modelo opcional que permite que o usuário especifique opcionalmente o seu próprio comparar-functor:

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

Se o usuário classe não especificar um tipo de functor costume, ele usa a seguinte definição CompareFunctor por padrão:

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

Isso funciona muito bem para tipos built-in e também tipos definidos pelo usuário, onde um operador menor-que foi definido. No entanto, eu gostaria que o trabalho também automaticamente para tipos onde há pouca ou embutidos ou explicitamente definidas operador menor-que. Para os tipos, a ordenação dos itens dentro do recipiente não é importante.

A motivação é que eu uso este recipiente para armazenar uma grande quantidade de diferentes tipos, e na maioria das vezes, não se preocupam com a ordem dos tipos no recipiente, mas em alguns casos que eu faço ... e Eu não quero ter que ir e adicionar "dummy" menos do que os operadores de todos esses tipos diferentes apenas para que eu possa usá-los com esta classe recipiente ... e eu não quero ter que especificar explicitamente um personalizado "dummy" argumento CompareFunctor cada vez que usar a tabela para armazenar itens que não têm um operador menor-que.

Assim, há uma maneira eu posso usar especialização de modelo (ou algo) para que o CompareFunctor padrão (mostrado acima) é usado sempre que possível, mas nos casos em que CompareFunctor causaria um erro, C ++ seria automaticamente a um "dummy" FallbackCompareFunctor como a abaixo? Ou talvez alguma outra maneira inteligente de lidar com este dilema?

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

No caso alguém estiver interessado, eu era capaz de chegar a uma maneira de fazer o que eu queria, usando uma combinação das técnicas descritas acima. Meu código de prova de conceito (com teste de unidade) é mostrado abaixo.

#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

Para o seu caso não ordenada padrão, use um functor nulo Comparação que apenas retorna false para todos os casos.
Você pode então se especializar seu modelo para um recipiente ordenada usando o std :: menos () 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 3

Ao fazer algumas pesquisas do Google com base na resposta de Eugene, eu encontrei este artigo:

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

Talvez eu possa adaptar o código apresentado lá ...

Answer 4

boost :: enable_if pode virar modelo especializações dentro e fora com base em algum tipo de avaliação tempo de compilação.

Se você pode criar uma construção que avalia como false em tempo de compilação, se o tipo que você está verificando não tem lessthan operador, então você pode usar isso para permitir a especialização fallback para 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; 
}

Claro que você também precisa some_condition para verificar se há operador lessthan de alguma forma ... Olhe para boost :: type_traits e código MPL eu acho -. Eles fazem coisas semelhantes