Различные типы для компаратора 'std :: sort' в С++

Когда мы предоставляем функцию сравнения для std::sort, мы используем следующую перегрузку:

template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );

в котором функция сравнения для std::sort должна иметь следующий синтаксис:

bool cmp(const Type1 &a, const Type2 &b);

Но, как вы можете видеть, a и b могут иметь разные типы. cppreference говорит:

Типы Type1 и Type2 должны быть такими, чтобы объект типа RandomIt мог быть разыменован, а затем неявно преобразован в оба из них.

Но я до сих пор не могу точно понять, как мы можем иметь 2 разных типа в одном массиве, когда мы пытаемся отсортировать его.

Может ли кто-нибудь предоставить небольшой пример с разными типами для функции сравнения std::sort?

Ответы

Ответ 1

Речь идет не о том, что хранится в массиве, может быть сохранен только один тип. Речь идет о функции компаратора. Возьмем для примера это:

struct Animal {};
struct Cat : Animal {};
struct Dog : Animal {};
struct Hound : Dog {};

bool cmp(const Animal &a, const Animal &b);

Даже если у вас есть список Dog, Cat или Hound вы все равно можете отсортировать их с помощью функции cmp потому что все они неявно конвертируемы. то есть.

std::vector<Hound> hounds;
... // fill hounds
std::sort(hounds.begin(), hounds.end(), cmp);

И вы даже можете представить себе случаи, когда Type1 и Type2 не совпадают, например:

bool cmp(const Animal &a, const Dog &b);
etc ...

Хотя это было бы крайне редко.

Типы Type1 (Animal) и Type2 (Dog) должны быть такими, чтобы объект типа RandomIt (Hound) мог быть разыменован, а затем неявно преобразован в них обоих. Что является правдой.

Дело в том, что ограничение типов, которое функция cmp может использовать для одного и того же, исключает общность. В некоторых случаях это хорошая идея, но в этом случае она будет неоправданно строгой и может вызвать проблемы для реализаций пограничного случая. Кроме того, функция cmp используемая в std::sort, связана с требованиями, установленными для Compare (возможно, для простоты). Требования сравнения используются для всех видов вещей, таких как std::max.

Ответ 2

Но я все еще не могу точно понять, как мы можем иметь 2 разных типа в одном массиве, когда мы пытаемся отсортировать его.

Вы не можете иметь два разных типа в массиве. Компаратор не предлагает это возможно. Это указано так просто потому что:

  1. Код может быть правильно сформирован, когда типы не совпадают.
  2. Требование одного и того же типа является ограничением, которое мало что дает.

Таким образом, спецификация предлагает более свободный контракт, чем "очевидный", чтобы помочь нашему коду быть более гибким в случае необходимости. В качестве игрушечного примера, скажем, у нас есть этот компаратор:

auto cmp(int a, long b) -> bool { return a < b; }

Почему мы не можем использовать эту совершенно легальную (хотя и глупую) функцию для сортировки массива целых чисел?

Ответ 3

Но я все еще не могу точно понять, как мы можем иметь 2 разных типа в одном массиве, когда мы пытаемся отсортировать его.

Ты не можешь.

Но требования Compare не только для сортировки массивов или просто для сортировки вообще!

Они на любое время хотят сравнить одно с другим.

minutes(42) меньше чем hours(1)? Да! Вы можете найти полезный компаратор для таких случаев.

Сравнение - это более общая концепция, которая находит применение во всем языке.

Возможно ли, что кто-то предоставит небольшой пример с разными типами для функции сравнения std :: sort

Другие показали примеры, которые показывают, насколько глупым должен быть поиск "полезного" примера для использования против std::sort специально.

Но это не "функция сравнения std :: sort". Это функция компаратора, которую вы используете для std::sort.

Это правда, что при этом вы, вероятно, хотите, чтобы конкретный компаратор, который вы выбираете, принимал операнды одного типа.

Ответ 4

Но я до сих пор не могу точно понять, как мы можем иметь 2 разных типа в одном массиве

Вы не можете иметь два разных типа в одном массиве.

Массив может иметь объекты только одного типа. Но этот единственный тип должен быть неявно конвертируемым в оба типа аргумента cmp.

Возможно ли, чтобы кто-то предоставил небольшой пример с разными типами для функции сравнения std :: sort?

Ну вот:

int arr[] = {1, 2, 3, 0};
auto cmp = [](const int &a, const long &b) {
    return a < b;
};
std::sort(std::begin(arr), std::end(arr), cmp);

Обратите внимание на два разных аргумента cmp. Это лишь минимальный пример, который технически правильный, но, по общему признанию, бессмысленный. Честно говоря, я никогда не сталкивался со случаем, когда было бы полезно иметь разные типы для аргументов функции сравнения.

Ответ 5

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

  1. Он должен принять двух разыменованных итераторов в последовательности в качестве аргументов.
    Использование неявной последовательности преобразования - это нормально.
  2. Возвращаемое значение должно быть контекстно-конвертируемым в bool.
    Явный оператор преобразования работает просто отлично.
  3. Это должен быть копируемый и неразрушаемый полный тип.
  4. Он не должен изменять аргументы, поэтому он не мешает вызывающему алгоритму.
    Это никоим образом не подразумевает использование константных ссылок, если ссылки используются вообще.
  5. Он должен вызывать полный слабый порядок (cmp (a, b) подразумевает! Cmp (b, a), cmp (a, b) && cmp (b, c) подразумевает cmp (a, c)).

Итак, действительный, но довольно бесполезный компаратор будет:

template <class... X>
auto useless(X&&...) { return nullptr; }

Ответ 6

Требования к типу в Compare не говорят много об элементах последовательности, которую вы сортируете, но вместо этого они разрешают все comp для которых

if (comp(*first, *other))

является действительным.

Большую часть времени Type1 будет равен Type2, но они не обязательно должны быть равными.