KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

CKTIS / C++

Gepartitioneerd zoekbereik

`std::lower_bound` heeft geen volledig gesorteerd bereik nodig: voor de gegeven zoeksleutel moeten alle elementen die aan de test voldoen vóór de overige staan.

Versie: ISO C++23; implementation support may vary

Syntax

#include <algorithm>

std::lower_bound(first, last, key);
std::lower_bound(first, last, key, comp);
std::ranges::lower_bound(first, last, key, comp, proj);
std::ranges::lower_bound(range, key, comp, proj);

// For this key, the predicate must be true for a prefix and false for the rest.
// Classic: bool(comp(element, key))
// Ranges:  bool(std::invoke(comp, std::invoke(proj, element), key))

Een bereik [first, last) is voor een zoeksleutel gepartitioneerd als bool(comp(element, key)) eerst alleen true en daarna alleen false oplevert. Beide delen mogen leeg zijn en hoeven niet intern gesorteerd te zijn. De klassieke std::lower_bound uit <algorithm> geeft de eerste iterator waarvoor de test onwaar is, of last als die er niet is. Het gevonden element hoeft niet gelijk te zijn aan de sleutel. Als de partitioneringsvoorwaarde niet geldt, is het gedrag ongedefinieerd.

De klassieke overload met comparator vergelijkt alleen van element naar sleutel. Daardoor kan hij een lambda [](const Sale& row, int key) gebruiken die row.sales > key test; [] legt niets vast. std::ranges::lower_bound (sinds C++20) accepteert een iterator-sentinelpaar of een bereik. De comparator moet voor de geprojecteerde elementen en de sleutel voldoen aan indirect_strict_weak_order; met &Sale::sales worden gehele getallen vergeleken. Beide versies vereisen minstens forward iterators en doen een logaritmisch aantal vergelijkingen, maar zonder willekeurige toegang kan het aantal iteratorstappen lineair zijn. De bereikoverload retourneert std::ranges::dangling voor een tijdelijk bereik dat geen borrowed_range is. Derefereer geen einditerator of ongeldig geworden iterator.

std::nth_element en std::partial_sort vereisen random-access iterators en een strikte zwakke ordening: comp(x, x) moet onwaar zijn en zowel de vergelijking als de equivalentie op basis van twee onware vergelijkingen moet transitief zijn. Voor gehele verkoopcijfers voldoet a.sales > b.sales, maar >= niet. nth_element zet het element met de gekozen rang op zijn gesorteerde positie en scheidt de twee delen zonder te garanderen dat ze gesorteerd zijn. partial_sort sorteert het gevraagde voorste deel en laat de volgorde van de rest ongespecificeerd. Geen van beide garandeert partitionering van het hele bereik voor een willekeurige sleutel. Sorteer bij herhaalde zoekopdrachten met verschillende sleutels het hele bereik volgens dezelfde ordening.

Voorbeelden

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

struct Sale {
    int sales;
};

int main() {
    const std::vector<Sale> rows{{95}, {120}, {70}, {85}, {60}};
    const int key = 90;
    const auto before_key = [](const Sale& row, int key) {
        return row.sales > key;
    };

    const auto classic = std::lower_bound(rows.begin(), rows.end(), key, before_key);
    const auto ranged = std::ranges::lower_bound(rows, key, std::ranges::greater{}, &Sale::sales);

    if (classic != rows.end() && ranged != rows.end()) {
        std::cout << classic->sales << '\n' << ranged->sales << '\n';
    }
}

Resultaat

70
70

Voor `90` drukken beide aanroepen `70` af, de eerste waarde die de drempel niet overschrijdt, hoewel het bereik niet aflopend gesorteerd is. Voor `100` geeft `95` al `false` voordat `120` `true` geeft; geen van beide aanroepen is daarom geldig met `100` op dit bereik.

Gerelateerde lessen

  • C++ · Les 23 · Gevorderd · Versie: 3

Bronnen