KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

CKTIS / C++

std::lower_bound — eerste positie die niet kleiner is dan een sleutel

std::lower_bound zoekt de grens in een passend gepartitioneerd bereik: het eerste element dat niet kleiner is dan de sleutel, of het einde van het bereik. De functie retourneert een iterator en bevestigt niet dat er een gelijke waarde bestaat.

Versie: C++23; repository compiler flag, production runtime not attested

Syntax

#include <algorithm>
std::lower_bound(first, last, value)
std::lower_bound(first, last, value, comp)

std::lower_bound, gedeclareerd in <algorithm>, doorzoekt [first, last) en retourneert de eerste iterator waarvoor comp(*it, value) onwaar is, of last als zo’n element niet bestaat. Zonder comp gebruikt de functie de standaardvergelijking voor kleiner-dan. In een oplopend numeriek bereik wijst het resultaat naar het eerste element >= value, ook als dat een duplicaat is.

Voorwaarde is dat het bereik voor de betreffende sleutel is gepartitioneerd: alle elementen waarvoor comp(element, value) geldt, moeten vóór de overige elementen staan. Volledig sorteren volgens dezelfde vergelijking is voldoende, maar niet noodzakelijk. Schending van deze voorwaarde leidt tot ongedefinieerd gedrag; de functie sorteert de gegevens niet.

Het resultaat bevestigt niet dat de sleutel bestaat. Controleer it != last voordat je *it gebruikt. In het voorbeeld met gehele getallen controleert de code alleen it != values.end() voordat de kandidaatwaarde wordt afgedrukt; de waarde wordt niet met de sleutel vergeleken. Als de iterator niet aan het einde van het bereik staat, kun je de gelijkheid apart testen met *it == key. Bij een aangepaste ordening betekent equivalentie !comp(a, b) && !comp(b, a), en niet noodzakelijk a == b.

Er zijn minstens forward-iterators vereist. Voor N elementen is het aantal vergelijkingen O(log N), maar zonder random-access-iterators kan het aantal iteratorstappen lineair zijn. Het voorbeeld is bedoeld voor C++23; het gekoppelde document is een evoluerend werkdocument, geen vastgelegde C++23-editie.

Voorbeelden

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

int main() {
    const std::vector<int> values{1, 3, 3, 7};
    for (int key : {3, 4, 9}) {
        const auto it = std::lower_bound(values.begin(), values.end(), key);
        std::cout << key << ": index=" << (it - values.begin());
        if (it != values.end()) {
            std::cout << ", value=" << *it;
        } else {
            std::cout << ", end";
        }
        std::cout << '\n';
    }
}

Resultaat

3: index=1, value=3
4: index=3, value=7
9: index=4, end

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.

Bronnen