Вопросы Теги

режим защиты от улей

Сортировка такого vector или любого другого применимого (изменяемого входного итератора) диапазона пользовательских объектов типа X может быть достигнута с использованием различных методов, особенно включая использование стандартных библиотечных алгоритмов, таких как

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

«Лучший» подход будет зависеть от разных факторов:

  1. диапазон сортировки объектов X - обычная или редкая задача (будут ли эти диапазоны отсортированы в разных местах в программе или пользователями библиотеки)?
  2. Требуется ли сортировка «естественная» (ожидаемая) или Есть ли несколько способов сравнить тип с самим собой?
  3. Является ли производительность проблемой или должны ли диапазоны сортировки объектов X быть безупречными?

Если sor диапазоны ting X являются общей задачей, и ожидаемая сортировка должна ожидаться (т. X просто обертывает одно фундаментальное значение), тогда он, вероятно, перейдет на перегрузку operator<, поскольку он позволяет сортировать без каких-либо fuzz (например, правильно передавать соответствующие компараторы) и многократно дает ожидаемые результаты.

Если сортировка общая задача или может потребоваться в разных контекстах, но есть несколько критериев, которые можно использовать для сортировки объектов X, я бы пошел на функторы (перегруженные функции operator() пользовательских классов) или указатели на функции (то есть один функтор / функция для лексического упорядочения и еще один для естественного упорядочения).

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

Это особенно верно, если сортировка не является «понятной» или «естественной». Вы можете легко получить логику заказа, глядя на лямбду, которая применяется на месте, тогда как operator< - это противостояние с первого взгляда, и вам нужно будет найти определение, чтобы знать, какая логика упорядочения будет применена.

Обратите внимание, однако, что одно определение operator< является единственной точкой отказа, тогда как несколько lambas являются множественными точками отказа и требуют большей осторожности.

Если определение operator< isn 't, если сортировка выполнена / шаблон сортировки скомпилирован, компилятору может быть предложено вызвать вызов функции при сравнении объектов, вместо того, чтобы встраивать логику упорядочения, которая может быть серьезным недостатком (по крайней мере, когда оптимизация / код времени ссылки генерация не применяется).

Способы достижения сопоставимости class X для использования стандартных алгоритмов сортировки библиотек

Пусть std::vector vec_X; и std::vector vec_Y;

] 1. Перегрузка T::operator<(T) или operator<(T, T) и использование стандартных шаблонов библиотек, которые не ожидают функции сравнения.

Любой элемент перегрузки operator<: 

struct X {
  int i{}; 
  bool operator<(X const &r) const { return i < r.i; } 
};
// ...
std::sort(vec_X.begin(), vec_X.end());

или free operator< : 

struct Y {
  int j{}; 
};
bool operator<(Y const &l, Y const &r) { return l.j < r.j; }
// ...
std::sort(vec_Y.begin(), vec_Y.end());

2. Использовать указатель функции с пользовательской функцией сравнения в качестве параметра функции сортировки. 

struct X {
  int i{};  
};
bool X_less(X const &l, X const &r) { return l.i < r.i; }
// ...
std::sort(vec_X.begin(), vec_X.end(), &X_less);

3. Создайте перегрузку bool operator()(T, T) для настраиваемого типа, который может быть передан как функтор сравнения. 

struct X {
  int i{};  
  int j{};
};
struct less_X_i
{
    bool operator()(X const &l, X const &r) const { return l.i < r.i; }
};
struct less_X_j
{
    bool operator()(X const &l, X const &r) const { return l.j < r.j; }
};
// sort by i
std::sort(vec_X.begin(), vec_X.end(), less_X_i{});
// or sort by j
std::sort(vec_X.begin(), vec_X.end(), less_X_j{});

Эти определения объектов функций могут быть написаны немного более общие с использованием C ++ 11 и шаблонов: 

struct less_i
{ 
    template
    bool operator()(T&& l, U&& r) const { return std::forward(l).i < std::forward(r).i; }
};

, который можно использовать для сортировки любого типа с элементом i, поддерживающим <.

4. Передайте закрытие анонима (лямбда) в качестве параметра сравнения к функциям сортировки. 

struct X {
  int i{}, j{};
};
std::sort(vec_X.begin(), vec_X.end(), [](X const &l, X const &r) { return l.i < r.i; });

В тех случаях, когда C ++ 14 допускает еще более общее лямбда-выражение: 

std::sort(a.begin(), a.end(), [](auto && l, auto && r) { return l.i < r.i; });

, которое может быть обернуто в макрос 

#define COMPARATOR(code) [](auto && l, auto && r) -> bool { return code ; }

, что делает обычное создание компаратора совершенно гладким: 

// sort by i
std::sort(v.begin(), v.end(), COMPARATOR(l.i < r.i));
// sort by j
std::sort(v.begin(), v.end(), COMPARATOR(l.j < r.j));

0
задан Raheem Mohammad 13 July 2018 в 09:26
поделиться