Сравнение std::tuple (или std::pair) пользовательских типов, которые имеют альтернативные порядки. Можно ли подключить пользовательскую функцию "меньше / меньше"?
Эта проблема
У меня есть пользовательский тип 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::tuple) используя стандартную реализацию поэлементного сравнения, подключив мою функцию сравнения для A?
Код
Код ниже не компилируется:
#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< за struct A (с учетом регистра), как мы можем сравнить std::pair<A, int> с этим альтернативным заказом?
Я знаю, что добавление специализированной версии operator< за 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< за std::tuple и подключить мой less-than за struct A было бы то, что я хочу. Является ли это возможным? Заранее спасибо!
1 ответ
Самый простой способ - написать вручную 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 такой, что Z<T> это заказ на Ts, выше дает вам универсальный порядок на что угодно.
Этот следующий мой любимый. Он принимает тип 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::map или же std::set, и он будет заказывать любые кортежи или пары, встречающиеся с my_less замена порядка элементов по умолчанию.