Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

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.

Zdroje