Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C++

Sortowanie, porównania i zakresy do wyszukiwania

Poprawne sortowanie wymaga komparatora definiującego ścisły słaby porządek. Wyszukiwanie binarne wymaga zakresu podzielonego względem właściwego warunku; pełne posortowanie jest warunkiem wystarczającym, lecz nie zawsze koniecznym.

Wersja: C++23; repository compiler flag, production runtime not attested

Składnia

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

std::sort z <algorithm> porządkuje półotwarty zakres [first, last) według comp: żaden późniejszy element nie poprzedza wcześniejszego. Wymaga iteratorów dostępu swobodnego oraz elementów spełniających wymagania przenoszenia i zamiany. Wykonuje O(N log N) porównań. Nie gwarantuje zachowania kolejności elementów równoważnych; do tego służy std::stable_sort.

Komparator musi definiować ścisły słaby porządek. comp(a, b) oznacza, że a poprzedza b, a comp(a, a) musi być fałszem. Relacja musi być przechodnia. Równoważność !comp(a, b) && !comp(b, a) także musi być przechodnia i nie musi odpowiadać operator==. Nie używaj <=: narusza warunek dla identycznych argumentów. Niespełnienie wymagań komparatora unieważnia gwarancje algorytmu.

Zakres podzielony względem predykatu zawiera najpierw wszystkie elementy dające true, a następnie wszystkie dające false; dowolna część może być pusta. Dla std::lower_bound(first, last, value, comp) predykatem jest comp(e, value). Funkcja zwraca granicę: pierwszy element, dla którego wynik jest fałszywy, albo last. Nie sprawdza tym samym obecności szukanej wartości; nie dereferencjonuj last.

Posortowanie według tego samego porządku zapewnia taki podział dla każdego klucza. Dla pojedynczego klucza wystarczy sam podział: [2, 1, 4, 3] spełnia warunek std::lower_bound dla value = 3 i porównania <, choć nie jest posortowane. Inne funkcje wyszukiwania binarnego mają własne warunki podziału. std::lower_bound wykonuje O(log N) porównań, lecz bez iteratorów dostępu swobodnego może wykonać liniowo wiele kroków iteratora.

Przykład sortuje liczby, a następnie używa tego samego comp, uzyskując indeks 3. Zakres treści to C++23; podany odnośnik prowadzi do rozwijanego szkicu, nie do zamrożonej publikacji C++23. Obsługa przez kompilator i środowisko produkcyjne nie została potwierdzona.

Przykłady

#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';
}

Wynik

1 1 2 3 4
index=3

Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.

Źródła