Ярлык для создания компаратора на основе поля члена или функции

Question

Мне часто хочется создать объекты-компараторы для struct или class, который просто извлекает одного члена класса и выполняет обычное < сравнение с этим.

Например:

struct student {
   int id;
   std::string name;
};

// sort by ID
std::sort(students.begin(), students.end(), [](const student& l, const student& r){ return l.id < r.id; });

Там много шаблонов, в частности, потому что мы должны повторить декларацию для l и r. Есть ли способ в стандартной библиотеке создать компаратор на основе функции «экстрактора», которая возвращает объект для сравнения?

Что-то вроде:

std::sort(students.begin(), students.end(), compare_on([](const student& s){ return s.id; });

Я использую C ++ 11, но мне также интересно, есть ли решения в более поздних стандартах, которые не применяются в C ++ 11 (поэтому я могу добавить что-то в свой список «причин для обновления»).

Я спрашиваю здесь об использовании одного члена в качестве компранда, а также сравнение по умолчанию «меньше чем», но бонусные баллы за методы, которые легко сочиняются, например, которые позволяют использовать два поля в лексикографическом порядке или изменить оператор сравнения.

Answer 1

range-v3 реализует проекция :

// sort by ID
ranges::sort(students, std::less<>{}, &student::id);

Answer 2

По Вашему предложению я предлагаю такие compare_on:

template<class T>
auto compare_on(T &&t){
    return [t](const auto &l, const auto &r){
        return l.*t < r.*t; 
    };
}
... 
std::sort(students.begin(), students.end(), compare_on(&student::id));

Требуется C ++ 14. Он использует указатель на член, чтобы получить именно то поведение, о котором вы просили.

В C ++ 11, используя аналогичную идею, это выглядело бы так:

template<class U>
class comparison{
public:
    comparison(const U &ptr) : memberPtr(ptr){}

    template<class T>
    int operator()(const T &l, const T &r){
        return l.*memberPtr < r.*memberPtr;
    }

private:
    U memberPtr;
};

template<class T>
comparison<T> compare_on(T &&t){
    return comparison<T>(std::forward<T>(t));
}

Как подсказывает @Barry, вы должны заменить все l.*t на std::invoke(t, l), чтобы сделать его более обобщенным в C ++ 17.

Answer 3

То, что вы действительно ищете, - это возможность передачи проекций в алгоритмы. N4128 предложил это для стандартной библиотеки, и C ++ 20 будет иметь их для многих алгоритмов.

Но до тех пор мы можем сделать это сами. Напишите новую перегрузку sort:

struct identity {
    template <typename T>
    T&& operator()(T&& t) const noexcept { return std::forward<T>(t); }
};

// because no std::less<> in C++11 yet
struct less {
    template <typename T, typename U>
    constexpr bool operator()(T const& lhs, U const& rhs) const {
        return lhs < rhs;
    }
};

template <typename Range, typename Comp=less, typename Proj=identity>
void sort_proj(Range& range, Comp comp={}, Proj proj={}) {
    using std::begin;
    using std::end;
    auto first = begin(range), last = end(range);
    using reference = typename std::iterator_traits<decltype(first)>::reference;

    std::sort(first, last,
        [&](reference lhs, reference rhs) {
            return comp(std::ref(proj)(lhs), std::ref(proj)(rhs));
        });
}

std::ref(f)(x) - это хитрость для получения функциональности INVOKE в C ++ 11. Это в основном позволяет передавать указатели членам в качестве проекции. Эта реализация позволит вам написать:

sort_proj(students, less{}, &student::id);

Обратите внимание, что проекция не зависит от порядка. Так что я могу довольно легко делать разные вещи:

sort_proj(students);                            // sort on students, if they're ordered
sort_proj(students, greater{}, &student::name); // decreasing, by name
sort_proj(students, less{},                     // by name, then id
    [](student const& s) {
        return std::tie(s.name, s.id);
    });

<час />

Такой подход super полезен для исключения большого количества шаблонов из алгоритмов в целом. У меня есть заголовок, который просто полон проекционных перегрузок многих обычно используемых стандартных алгоритмов.

Answer 4

Вы можете определить служебный класс

template <class Fct> class compare_on {
  public:
    compare_on(Fct&& get) : get(std::forward<Fct>(get)) {}

    template <class T> bool operator()(const T& lhs, const T& rhs)
    {
       return get(lhs) < get(rhs);
    }

  private:
    Fct get;
};

и затем передайте его std::sort, как вы его изобразили (используя вычет аргумента шаблона класса C ++ 17)

std::sort(students.begin(), students.end(),
    compare_on([](const student& s){ return s.id; }));

Начиная с C ++ 17, @Justin указал в комментариях, что фактическое сравнение может быть улучшено (с #include <functional>) таким образом, что

return std::invoke(get, lhs) < std::invoke(get, rhs);

, которая позволяет создавать экземпляры со ссылками на элементы данных:

std::sort(students.begin(), students.end(), compare_on(&student::id));

При связывании с C ++ 11 забудьте о std::invoke и перейдите к явной реализации compare_on. Последний не подходит для лямбд, поэтому обычный вывод аргументов make_* helper:

template <class Fct> auto make_compare_on(Fct&& get)
    -> decltype(compare_on<Fct>(std::forward<Fct>(get)))
{
    return compare_on<Fct>(std::forward<Fct>(get));
}

Обратите внимание, что вы можете удалить конечный тип возврата в C ++ 14.

Как последнее замечание, здесь следует улучшить наименование: compare_on вводит в заблуждение, поскольку оно скрывает, что на самом деле делает объект функции - сравнение с помощью operator <. Может быть, compare_less_then или что-то подобное будет лучше, или добавление другого параметра шаблона, который может быть указан в качестве одного из стандартных предикатов (std::less и т. Д.).