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.