CKTIS / C++
Triedenie, porovnávanie a vyhľadávacie rozsahy
Správne triedenie vyžaduje komparátor definujúci striktné slabé usporiadanie. Binárne vyhľadávanie vyžaduje rozsah rozdelený podľa príslušnej podmienky; usporiadanie celého rozsahu stačí, ale nie je vždy nevyhnutné.
Verzia: C++23; repository compiler flag, production runtime not attested
Syntax
std::sort(first, last, comp);
std::lower_bound(first, last, value, comp);std::sort z <algorithm> usporiada polootvorený rozsah [first, last) podľa comp: žiadny neskorší prvok nepredchádza skoršiemu. Vyžaduje iterátory s náhodným prístupom a prvky spĺňajúce požiadavky na presúvanie a výmenu. Vykoná O(N log N) porovnaní. Nezaručuje zachovanie poradia ekvivalentných prvkov; na to slúži std::stable_sort.
Komparátor musí definovať striktné slabé usporiadanie. comp(a, b) znamená, že a predchádza b, a comp(a, a) musí byť nepravdivé. Relácia musí byť tranzitívna. Aj ekvivalencia definovaná ako !comp(a, b) && !comp(b, a) musí byť tranzitívna a nemusí zodpovedať operator==. Nepoužívajte <=: pri totožných argumentoch porušuje požiadavku. Ak požiadavky na komparátor nie sú splnené, záruky algoritmu neplatia.
Striktné slabé usporiadanie a rozdelenie vyhľadávacích rozsahov sú súvisiace, ale odlišné požiadavky. V rozsahu rozdelenom podľa predikátu sú najprv všetky prvky s výsledkom true a potom všetky s výsledkom false; ktorákoľvek časť môže byť prázdna. Pre std::lower_bound(first, last, value, comp) je predikátom comp(e, value). Funkcia vráti hranicu: prvý prvok s výsledkom false alebo last. Tým sa nepotvrdzuje, že hľadaná hodnota je prítomná; nedereferencujte last.
Triedenie podľa toho istého usporiadania zaručuje toto rozdelenie pre každý kľúč. Pre jeden kľúč stačí samotné rozdelenie: [2, 1, 4, 3] spĺňa podmienku std::lower_bound pre value = 3 a porovnanie <, hoci nie je usporiadaný. Ostatné funkcie binárneho vyhľadávania majú vlastné požiadavky na rozdelenie. std::lower_bound vykoná O(log N) porovnaní, ale bez iterátorov s náhodným prístupom môže vyžadovať lineárny počet krokov iterátora.
Príklad usporiada celé čísla a potom použije ten istý comp na získanie indexu 3. Obsah je určený pre C++23; uvedený odkaz smeruje na priebežne upravovaný pracovný návrh, nie na nemenné vydanie C++23. Podpora kompilátorom a produkčným behovým prostredím nie je potvrdená.
Prí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ýsledok
1 1 2 3 4 index=3
Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.