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

Я практикую лямбды:

 int main()
 {
    std::vector<int> v {1,2,3,4};
    int count = 0;
    sort(v.begin(), v.end(), [](const int& a, const int& b) -> bool
        {
        return a > b;
        });
  }

Это просто код от GeeksForGeeks для сортировки в порядке убывания, ничего особенного. Я добавил несколько заявлений для печати (но вынул их для этого поста), чтобы посмотреть, что происходит внутри лямбды. Они печатают весь вектор, а a а также b ценности:

1 2 3 4  
a=2 b=1

2 1 3 4  
a=3 b=2

3 2 1 4  
a=4 b=3

4 3 2 1 <- final

Итак, мой более подробный вопрос: какова логика порядка, в котором векторные элементы передаются в a а также b параметры?

Является b постоянно в индексе 0 в то время как a повторяется? И если так, не странно ли, что второй параметр, передаваемый лямбде, остается в первом элементе? Это зависит от компилятора? Спасибо!

Источник

4 ответа

Решение

Передавая предикат std::sort(), вы указываете свой критерий сортировки. Предикат должен возвращаться true если первый параметр (т.е. a) предшествует второму (т.е. b), для указанного вами критерия сортировки.

Поэтому для вашего предиката:

return a > b;

Если a больше чем b, затем a будет предшествовать b,

Итак, мой более подробный вопрос: какова логика порядка, в котором векторные элементы передаются в a а также b параметры?

a а также b это просто пары элементов элементов, которые вы передаете std::sort(), "Логика" будет зависеть от основного алгоритма, который std::sort() реализует. Пары могут также отличаться для вызовов с одинаковым входом из-за рандомизации.

Источник

Постоянно ли находится индекс "b" в индексе 0, а "a" выполняет итерацию? И если так, не странно ли, что второй параметр, передаваемый лямбде, остается в первом элементе?

Нет, потому что первый элемент выше.

Кажется, что с помощью этого алгоритма все элементы проверяются (и, возможно, переключаются) с более высоким (в первом раунде), а более высокий помещается в первую позицию; так b когда-либо указывает на более высокий.

Источник

Для Visual Studio std::sort использует сортировку вставкой, если размер вложенного массива <= 32 элемента. Для большего подмассива он использует интросортировку, которая является быстрой сортировкой, если глубина "рекурсии" не становится слишком большой, и в этом случае он переключается на сортировку кучи. Вывод, который вы программируете, кажется, соответствует некоторой вариации типа вставки. Так как функция сравнения "меньше чем", и поскольку сортировка вставкой ищет не в порядке из-за левых значений "больше, чем" правых значений, входные параметры меняются местами.

Источник

Вы просто сравниваете два элемента с заданным порядком. Это означает, что если заказ a а потом bтогда лямбда должна вернуться true,

Дело в том, что a или же b Первый или последний элемент массива, или фиксированный, зависит от алгоритма сортировки и конечно от ваших данных!

Источник
Другие вопросы по тегам