CKTIS / C++
std::upper_bound — de grens na equivalente elementen
`std::upper_bound` vindt de partitiegrens voor de zoekwaarde: de functie geeft een iterator naar het eerste element waarvoor volgens de gebruikte vergelijking geldt dat `value` kleiner is dan dat element, of `last` als zo’n element ontbreekt. Met de standaardvergelijking voor oplopend gesorteerde getallen is dit het eerste getal dat groter is dan `value`.
Versie: C++23; repository compiler flag, production runtime not attested
Syntax
#include <algorithm>
std::upper_bound(first, last, value)
std::upper_bound(first, last, value, comp)std::upper_bound, gedeclareerd in <algorithm>, doorzoekt het halfopen bereik [first, last). Bij de standaardvergelijking en een oplopend bereik geeft de functie het eerste element terug dat groter is dan value; alle duplicaten van die waarde worden overgeslagen. Het resultaat is een iterator, geen index of aanwezigheidsaanduiding. Als er geen passend element is, ook in een leeg bereik, is het resultaat last. Dereferenceer de geretourneerde iterator alleen als die niet gelijk is aan last.
De overload met comp zoekt het eerste element e waarvoor comp(value, e) waar is. Als voorwaarde moet het bereik gepartitioneerd zijn: eerst moeten alle elementen staan waarvoor !comp(value, e) geldt, en daarna de overige elementen. Volledig sorteren volgens een compatibele ordening is voldoende, maar voor één zoekopdracht niet noodzakelijk. Doorzoek geen willekeurig ongeordende gegevens: schending van de voorwaarde leidt tot ongedefinieerd gedrag. Wat „groter” betekent, hangt af van de comparator en niet noodzakelijk van de numerieke operator >.
In een oplopend bereik vindt std::lower_bound het eerste element dat niet kleiner is dan value, terwijl std::upper_bound het eerste grotere element vindt. In een gesorteerd bereik begrenzen deze posities de elementen die volgens de vergelijking equivalent zijn. Let op de volgorde van de argumenten: std::upper_bound gebruikt comp(value, element), niet comp(element, value).
Er zijn minimaal forward-iterators nodig. Het aantal vergelijkingen is O(log N), maar zonder random access kan het aantal iteratorstappen O(N) zijn; met iterators van std::vector is het aantal stappen logaritmisch. Het voorbeeld gebruikt syntax die compatibel is met C++23. Het gekoppelde werkdocument blijft in ontwikkeling en kan nieuwere declaraties bevatten.
Voorbeelden
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
const std::vector<int> values{1, 2, 2, 2, 4, 7};
const auto it = std::upper_bound(values.begin(), values.end(), 2);
std::cout << "index=" << (it - values.begin()) << '\n';
if (it != values.end()) {
std::cout << "value=" << *it << '\n';
}
const auto end = std::upper_bound(values.begin(), values.end(), 7);
std::cout << "at_end=" << std::boolalpha << (end == values.end()) << '\n';
}
Resultaat
index=4 value=4 at_end=true
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.