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