c++ - 代替順序を持つカスタム型の std::tuple (または std::pair) を比較します。カスタムより小さい/比較関数をプラグインすることは可能ですか?

Question

問題

A自然な順序付け ( を持つoperator<) と複数の代替順序付け (大文字と小文字を区別する、大文字と小文字を区別しないなど)を持つカスタム型があります。これで、std::pair(またはstd::tuple) からなる (1 つまたは複数の) ができAました。std::pair<A, int>比較したいタイプの例を次に示しstd::pair<int, A>ます。の比較関数をプラグインして、デフォルトの要素ごとの比較実装を使用して(または) を比較するにはどうすればよいですか?std::tuple<A, int, int>std::tuple<int, A, int>std::pairstd::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複雑で (可変個引数テンプレートの処理)、エラーが発生しやすい可能性があります。

第 2 に、これが問題を解決するためのベストプラクティスの方法であるとはほとんど信じられません。operator<次のクラスのそれぞれに対しての特殊なバージョンを定義する必要があると想像してください: std::tuple<A, int, int>、std::tuple<int, A, int>、std::tuple<int, int, A>、std::tuple<A, A, int>... (これは実際的な方法でさえありません) !)

operator<よく書かれた組み込みのforを再利用し、私の forstd::tupleをプラグインすることは、私が望むものです。出来ますか？前もって感謝します！less-thanstruct A

score 2 · Accepted Answer

簡単な方法は、タプル内の要素を辞書的に比較するため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);
  }
};

したがって、 s の順序付けである such があるtemplate<class T>class Z場合、上記により、あらゆるものに対する普遍的な順序付けが得られます。Z<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 >;

bob はあなたのおじです (実例)。

special_orderstd::mapまたはに渡すことができ、要素のデフォルトの順序を置き換えることでstd::set遭遇したタプルまたはペアを順序付けます。my_less

c++ - 代替順序を持つカスタム型の std::tuple (または std::pair) を比較します。カスタムより小さい/比較関数をプラグインすることは可能ですか?

問題

コード

1 に答える 1

Related

Reference