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

这对于内置类型以及定义了小于运算符的用户定义类型非常有用。 但是，我希望它也能自动适用于没有内置或显式定义的小于运算符的类型。 对于这些类型，容器内物品的顺序并不重要。

动机是我使用这个容器来容纳很多不同的类型，大多数时候，我不关心容器中类型的顺序，但在某些情况下我会关心......而且我不关心不想必须进去并向所有这些不同类型添加“虚拟”小于运算符，这样我就可以将它们与这个容器类一起使用......并且我不想必须显式指定自定义“虚拟”每次我使用表来存储没有小于运算符的项目时，都会使用 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

对于默认的未排序情况，请使用 Null Comparison 函子，该函子对所有情况都返回 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 2

在根据尤金的回答进行一些谷歌搜索时，我发现了这篇文章：

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

也许我可以调整那里提供的代码......

Answer 3

如果有人感兴趣，我可以结合使用上述技术想出一种方法来做我想做的事情。 我的概念验证代码（带有单元测试）如下所示。

#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 4

boost::enable_if 可以打开模板特化并基于一些编译时评估。

如果您可以创建一个在您检查的类型没有小于运算符的情况下在编译时计算结果为 false 的构造，那么您可以使用它来启用 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 代码——它们做了类似的事情。