c++ - 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)
    }
};

score 1 · Accepted Answer

对于您的默认未排序案例，请使用对所有案例仅返回 false 的 Null 比较函子。
然后，您可以使用 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>
       {
           [...]
       };

score 1 · Accepted Answer

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

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

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

score 1 · Accepted Answer

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

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

score 0 · Accepted Answer

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 以某种方式检查 operator lessthan ... 看看我猜的 boost::type_traits 和 MPL 代码 - 他们做类似的事情。

c++ - C++ 模板化容器类：如何最好地支持有序和无序项类型？

4 回答 4

Related

Reference