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

Question

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

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

Answer 1

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

Следовательно, для вашего предиката:

return a > b;

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

---

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

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

Answer 2

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

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

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

Answer 3

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

Answer 4

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

Тот факт, что a или b являются первым или последним элементомМассив или фиксированный, зависит от алгоритма сортировки и, конечно, от ваших данных!