1

问题

我有一个自定义类型A，它具有自然排序（有operator<）和多个替代排序（区分大小写、不区分大小写等）。现在我有一个std::pair（或std::tuple）由（一个或多个）组成A。以下是一些我想比较的类型示例：std::pair<A, int>, std::pair<int, A>, std::tuple<A, int, int>, std::tuple<int, A, int>. 我如何使用默认的逐元素比较实现来比较std::pair（或），插入我的比较函数？std::tupleA

编码

下面的代码无法编译：

#include <utility>      // std::pair
#include <tuple>        // std::tuple
#include <iostream>     // std::cout, std::endl

struct A
{
    A(char v) : value(v) {}
    char value;
};

// LOCATION-1 (explained in the text below)

int main()
{
    std::cout
        << "Testing std::pair of primitive types: "
        << (std::pair<char, int>('A', 1)
                <
            std::pair<char, int>('a', 0))
        << std::endl;

    std::cout
        << "Testing std::tuple of primitive types: "
        << (std::tuple<char, int, double>('A', 1, 1.0)
                <
            std::tuple<char, int, double>('a', 0, 0.0))
        << std::endl;

    // This doesn't compile:
    std::cout
        << "Testing std::pair of custom types: "
        << (std::pair<A, int>('A', 1)
                <
            std::pair<A, int>('a', 0))
        << std::endl;

    return 0;
}

这是因为operator<没有为struct A. 将其添加到LOCATION-1上面将解决问题：

bool operator<(A const& lhs, A const& rhs)
{
    return lhs.value < rhs.value;
}

现在，我们有另一种排序方式struct A：

bool case_insensitive_less_than(A const& lhs, A const& rhs)
{
    char const lhs_value_case_insensitive
        = ('a' <= lhs.value && lhs.value <= 'z'
            ? (lhs.value + 0x20)
            : lhs.value);
    char const rhs_value_case_insensitive
        = ('a' <= rhs.value && rhs.value <= 'z'
            ? (rhs.value + 0x20)
            : rhs.value);
    return lhs_value_case_insensitive < rhs_value_case_insensitive;
}

假设我们想保留原来operator<的 for struct A（区分大小写的），我们如何std::pair<A, int>与这种替代排序进行比较？

我知道添加operator<for的专用版本可以std::pair<A, int>解决问题：

bool operator<(std::pair<A, int> const& lhs, std::pair<A, int> const& rhs)
{
    return (case_insensitive_less_than(lhs.first, rhs.first)
        ? true
        : case_insensitive_less_than(rhs.first, lhs.first)
        ? false
        : (lhs.second < rhs.second));
}

但是，我认为这是一个次优的解决方案。

首先，对于std::pair，重新实现逐元素比较很容易，但std::tuple它可能很复杂（处理可变参数模板）并且容易出错。

其次，我几乎无法相信这是解决问题的最佳实践方法：想象我们必须为operator<以下每个类定义一个专门的版本：std::tuple<A, int, int>, std::tuple<int, A, int>, std::tuple<int, int, A>, std::tuple<A, A, int>, ... （这甚至不是一种实用的方法！）

重新使用编写良好的内置operator<forstd::tuple并插入我less-than的 forstruct A将是我想要的。可能吗？提前致谢！

4

1 回答 1

2

简单的方法是手动编写compare( tup, tup, f )用于f按字典顺序比较元组中的元素的方法。但这很无聊。

// This type wraps a reference of type X&&
// it then overrides == and < with L and E respectively
template<class X, class L, class E>
struct reorder_ref {
  using ref = reorder_ref;
  X&& x;
  friend bool operator<(ref lhs, ref rhs) {
    return L{}((X&&) lhs.x, (X&&) rhs.x);
  }
  friend bool operator==(ref lhs, ref rhs) {
    return E{}((X&&) lhs.x, (X&&) rhs.x);
  }
  // other comparison ops based off `==` and `<` go here
  friend bool operator!=(ref lhs, ref rhs){return !(lhs==rhs);}
  friend bool operator>(ref lhs, ref rhs){return rhs<lhs;}
  friend bool operator<=(ref lhs, ref rhs){return !(lhs>rhs);}
  friend bool operator>=(ref lhs, ref rhs){return !(lhs<rhs);}

  reorder_ref(X&& x_) : x((X&&) x_) {}
  reorder_ref(reorder_ref const&) = default;
};

以上是改变我们订购方式的参考。

// a type tag, to pass a type to a function:
template<class X>class tag{using type=X;};

// This type takes a less than and equals stateless functors
// and takes as input a tuple, and builds a tuple of reorder_refs
// basically it uses L and E to compare the elements, but otherwise
// uses std::tuple's lexographic comparison code.
template<class L, class E>
struct reorder_tuple {
  // indexes trick:
  template<class Tuple, class R, size_t... Is>
  R operator()(tag<R>, std::index_sequence<Is...>, Tuple const& in) const {
    // use indexes trick to do conversion
    return R( std::get<Is>(in)... );
  }

  // forward to the indexes trick above:
  template<class... Ts, class R=std::tuple<reorder_ref<Ts const&, L, E>...>>
  R operator()(std::tuple<Ts...> const& in) const {
    return (*this)(tag<R>{}, std::index_sequence_for<Ts...>{}, in);
  }
  // pair filter:
  template<class... Ts, class R=std::pair<reorder_ref<Ts const&, L, E>...>>
  R operator()(std::pair<Ts...> const& in) const {
    return (*this)(tag<R>{}, std::index_sequence_for<Ts...>{}, in);
  }
};

上面的无状态函数对象接受了一些新的 less 和 equals 操作，并将任何元组映射到 的元组reorder_ref<const T, ...>，这将分别更改顺序为L和E。

下一个类型做了一些事情std::less<void>——std::less<T>它接受一个特定于类型的无状态排序函数模板对象，并使其成为一个类型通用的无状态排序函数对象：

// This takes a type-specific ordering stateless function type, and turns
// it into a generic ordering function type
template<template<class...> class order>
struct generic_order {
  template<class T>
  bool operator()(T const& lhs, T const& rhs) const {
    return order<T>{}(lhs, rhs);
  }
};

所以如果我们有一个template<class T>class Z这样的 sZ<T>上的排序T，上面给你一个对任何东西的通用排序。

下一个是我的最爱。它接受类型 T，并根据到类型 U 的映射对其进行排序。这非常有用：

// Suppose there is a type X for which we have an ordering L
// and we have a map O from Y->X.  This builds an ordering on
// (Y lhs, Y rhs) -> L( O(lhs), O(rhs) ).  We "order" our type
// "by" the projection of our type into another type.  For
// a concrete example, imagine we have an "id" structure with a name
// and age field.  We can write a function "return s.age;" to
// map our id type into ints (age).  If we order by that map,
// then we order the "id" by age.
template<class O, class L = std::less<>>
struct order_by {
  template<class T, class U>
  bool operator()(T&& t, U&& u) const {
    return L{}( O{}((T&&) t), O{}((U&&) u) );
  }
};

现在我们将它们粘合在一起：

// Here is where we build a special order.  Suppose we have a template Z<X> that returns
// a stateless order on type X.  This takes that ordering, and builds an ordering on
// tuples based on it, using the above code as glue:
template<template<class...>class Less, template<class...>class Equals=std::equal_to>
using tuple_order = order_by< reorder_tuple< generic_order<Less>, generic_order<Equals> > >;

tuple_order为我们完成大部分工作。我们只需要为它提供一个按元素排序的template无状态函数对象。 tuple_order然后将基于它生成一个元组排序仿函数。

// Here is a concrete use of the above
// my_less is a sorting functiont that sorts everything else the usual way
// but it sorts Foo's backwards
// Here is a toy type.  It wraps an int.  By default, it sorts in the usual way
struct Foo {
  int value = 0;
  // usual sort:
  friend bool operator<( Foo lhs, Foo rhs ) {
    return lhs.value<rhs.value;
  }
  friend bool operator==( Foo lhs, Foo rhs ) {
    return lhs.value==rhs.value;
  }
};

template<class T>
struct my_less : std::less<T> {};

// backwards sort:
template<>
struct my_less<Foo> {
  bool operator()(Foo const& lhs, Foo const& rhs) const {
    return rhs.value < lhs.value;
  }
};

using special_order = tuple_order< my_less >;

鲍勃是你的叔叔（活生生的例子）。

special_order可以传递给std::mapor std::set，它将对my_less替换元素的默认顺序时遇到的任何元组或对进行排序。

于 2015-02-22T15:52:07.577 回答