База знанияИзпитен център
BGБългарски
Избери език13

CKTIS / C++

Сортиране, сравнения и диапазони за търсене

Правилното сортиране изисква компаратор, който дефинира строг слаб ред. Двоичното търсене изисква диапазон, разделен според съответното условие; сортирането на целия диапазон е достатъчно, но не винаги необходимо.

Версия: C++23; repository compiler flag, production runtime not attested

Синтаксис

std::sort(first, last, comp);
std::lower_bound(first, last, value, comp);

std::sort от <algorithm> подрежда полуотворения диапазон [first, last) според comp: никой по-късен елемент не предхожда по-ранен. Изисква итератори с произволен достъп и елементи, отговарящи на изискванията за преместване и размяна. Извършва O(N log N) сравнения. Не гарантира запазване на реда на еквивалентните елементи; за това използвайте std::stable_sort.

Компараторът трябва да дефинира строг слаб ред. comp(a, b) означава, че a предхожда b, а comp(a, a) трябва да е false. Релацията трябва да е транзитивна. Еквивалентността, дефинирана като !comp(a, b) && !comp(b, a), също трябва да е транзитивна и не е задължително да съвпада с operator==. Не използвайте <=: той нарушава изискването при еднакви аргументи. Ако изискванията към компаратора не са изпълнени, гаранциите на алгоритъма не важат.

Строгият слаб ред и разделянето на диапазоните за търсене са свързани, но различни изисквания. В диапазон, разделен според предикат, първо са всички елементи с резултат true, а след тях — тези с резултат false; която и да е част може да е празна. За std::lower_bound(first, last, value, comp) предикатът е comp(e, value). Функцията връща границата: първия елемент с резултат false или last. Това не доказва, че търсената стойност присъства; не дереферирайте last.

Сортирането по същия ред гарантира това разделяне за всеки ключ. За един ключ е достатъчно само разделянето: [2, 1, 4, 3] удовлетворява предусловието на std::lower_bound за value = 3 и сравнението <, въпреки че не е сортиран. Другите функции за двоично търсене имат собствени изисквания за разделяне. std::lower_bound извършва O(log N) сравнения, но без итератори с произволен достъп може да изисква линеен брой стъпки на итератора.

Примерът сортира цели числа, след което използва същия comp, за да получи индекс 3. Съдържанието е предназначено за C++23; посочената препратка води до развиващ се работен проект, а не до окончателно издание на C++23. Поддръжката от компилатора и производствената среда за изпълнение не е потвърдена.

Примери

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{4, 1, 3, 1, 2};
    const auto comp = [](int a, int b) { return a < b; };

    std::sort(values.begin(), values.end(), comp);
    for (std::size_t i = 0; i < values.size(); ++i) {
        if (i != 0) std::cout << ' ';
        std::cout << values[i];
    }
    std::cout << '\n';

    const auto it = std::lower_bound(values.begin(), values.end(), 3, comp);
    std::cout << "index=" << (it - values.begin()) << '\n';
}

Резултат

1 1 2 3 4
index=3

Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.

Източници