CKTIS / C++
Řazení, porovnávání a vyhledávací rozsahy
Správné řazení vyžaduje komparátor definující striktní slabé uspořádání. Binární vyhledávání vyžaduje rozsah rozdělený podle příslušné podmínky; seřazení celého rozsahu stačí, ale není vždy nutné.
Verze: C++23; repository compiler flag, production runtime not attested
Syntaxe
std::sort(first, last, comp);
std::lower_bound(first, last, value, comp);std::sort z <algorithm> uspořádá polouzavřený rozsah [first, last) podle comp: žádný pozdější prvek nepředchází dřívějšímu. Vyžaduje iterátory s náhodným přístupem a prvky splňující požadavky na přesouvání a výměnu. Provede O(N log N) porovnání. Nezaručuje zachování pořadí ekvivalentních prvků; k tomu slouží std::stable_sort.
Komparátor musí definovat striktní slabé uspořádání. comp(a, b) znamená, že a předchází b, a comp(a, a) musí být nepravdivé. Relace musí být tranzitivní. Také ekvivalence definovaná jako !comp(a, b) && !comp(b, a) musí být tranzitivní a nemusí odpovídat operator==. Nepoužívejte <=: pro totožné argumenty porušuje požadavek. Pokud nejsou požadavky na komparátor splněny, záruky algoritmu neplatí.
Striktní slabé uspořádání a rozdělení vyhledávacích rozsahů jsou související, ale odlišné požadavky. V rozsahu rozděleném podle predikátu jsou nejprve všechny prvky s výsledkem true a pak všechny s výsledkem false; kterákoli část může být prázdná. Pro std::lower_bound(first, last, value, comp) je predikátem comp(e, value). Funkce vrací hranici: první prvek s výsledkem false, nebo last. Tím se nepotvrzuje přítomnost hledané hodnoty; nedereferencujte last.
Řazení podle stejného uspořádání zaručuje toto rozdělení pro každý klíč. Pro jediný klíč stačí samotné rozdělení: [2, 1, 4, 3] splňuje podmínku std::lower_bound pro value = 3 a porovnání <, přestože není seřazený. Jiné funkce binárního vyhledávání mají vlastní požadavky na rozdělení. std::lower_bound provede O(log N) porovnání, ale bez iterátorů s náhodným přístupem může vyžadovat lineární počet kroků iterátoru.
Příklad seřadí celá čísla a potom použije stejný comp k získání indexu 3. Obsah cílí na C++23; uvedený odkaz vede na průběžně upravovaný pracovní návrh, nikoli na neměnné vydání C++23. Podpora kompilátorem a produkčním běhovým prostředím není potvrzena.
Příklady
#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';
}
Výsledek
1 1 2 3 4 index=3
Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.