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

Question

Какова логика порядка, в котором элементы передаются в функцию сравнения в 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 повторяется? И если так, разве не странно, что второй параметр передается в лямбду остается на первый элемент? Это зависит от компилятора? Спасибо!

1

c++sorting std stl strict-weak-ordering

Решение

Другие решения

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

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

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

1

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

1

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

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

0

Источник

Accepted Answer

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

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

return a > b;

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

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

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

1