CKTIS / C++
Sorteren, vergelijkingen en zoekbereiken
Correct sorteren vereist een comparator die een strikte zwakke ordening definieert. Binair zoeken vereist een bereik dat voor de relevante voorwaarde is gepartitioneerd; het hele bereik sorteren is voldoende, maar niet altijd noodzakelijk.
Versie: C++23; repository compiler flag, production runtime not attested
Syntax
std::sort(first, last, comp);
std::lower_bound(first, last, value, comp);std::sort uit <algorithm> ordent het halfopen bereik [first, last) volgens comp: geen later element gaat vooraf aan een eerder element. De functie vereist iterators met willekeurige toegang en elementen die aan de eisen voor verplaatsen en verwisselen voldoen. Er worden O(N log N) vergelijkingen uitgevoerd. Het behoud van de volgorde van equivalente elementen is niet gegarandeerd; gebruik daarvoor std::stable_sort.
De comparator moet een strikte zwakke ordening definiëren. comp(a, b) betekent dat a voorafgaat aan b, en comp(a, a) moet false zijn. De relatie moet transitief zijn. Ook equivalentie, gedefinieerd als !comp(a, b) && !comp(b, a), moet transitief zijn en hoeft niet overeen te komen met operator==. Gebruik geen <=: dat schendt de eis voor identieke argumenten. Als niet aan de comparatorvereisten wordt voldaan, gelden de garanties van het algoritme niet.
Een strikte zwakke ordening en gepartitioneerde zoekbereiken zijn verwante, maar verschillende vereisten. In een bereik dat volgens een predicaat is gepartitioneerd, staan alle elementen met resultaat true vóór alle elementen met resultaat false; een van beide delen mag leeg zijn. Voor std::lower_bound(first, last, value, comp) is het predicaat comp(e, value). De functie geeft de grens terug: het eerste element met resultaat false, of last. Dit stelt niet vast dat de gezochte waarde aanwezig is; dereferenceer last niet.
Sorteren volgens dezelfde ordening garandeert deze partitionering voor elke sleutel. Voor één sleutel volstaat partitionering: [2, 1, 4, 3] voldoet aan de voorwaarde van std::lower_bound voor value = 3 en vergelijking <, hoewel het bereik niet gesorteerd is. Andere functies voor binair zoeken hebben hun eigen partitioneringseisen. std::lower_bound voert O(log N) vergelijkingen uit, maar kan zonder iterators met willekeurige toegang een lineair aantal iteratorstappen vereisen.
Het voorbeeld sorteert gehele getallen en gebruikt daarna dezelfde comp om index 3 te krijgen. De inhoud is gericht op C++23; de opgegeven verwijzing leidt naar een veranderlijk werkdocument, niet naar een vastgelegde C++23-publicatie. Ondersteuning door compiler en productie-runtime is niet bevestigd.
Voorbeelden
#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';
}
Resultaat
1 1 2 3 4 index=3
De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.