CKTIS / C++
std::upper_bound — la limite après les éléments équivalents
`std::upper_bound` trouve la limite de partition pour la valeur recherchée : la fonction renvoie un itérateur vers le premier élément auquel `value` est inférieur selon la comparaison utilisée, ou `last` si aucun élément ne répond à ce critère. Avec la comparaison par défaut et des nombres triés par ordre croissant, il s’agit du premier nombre supérieur à `value`.
Version : C++23; repository compiler flag, production runtime not attested
Syntaxe
#include <algorithm>
std::upper_bound(first, last, value)
std::upper_bound(first, last, value, comp)std::upper_bound, déclaré dans <algorithm>, recherche dans la plage semi-ouverte [first, last). Avec la comparaison par défaut et une plage croissante, la fonction renvoie le premier élément supérieur à value, en ignorant tous les doublons de cette valeur. Le résultat est un itérateur, et non un indice ni une indication de présence. S’il n’existe aucun élément correspondant, y compris dans une plage vide, le résultat est last. Vérifiez que le résultat est différent de last avant de le déréférencer.
La surcharge avec comp recherche le premier élément e pour lequel comp(value, e) est vrai. Elle exige que la plage soit partitionnée : tous les éléments vérifiant !comp(value, e) doivent précéder les autres. Un tri complet selon un ordre compatible suffit, mais n’est pas nécessaire pour une seule recherche. Ne recherchez pas dans des données arbitrairement non ordonnées : le non-respect de cette condition préalable entraîne un comportement indéfini. La notion de « supérieur » dépend du comparateur, et pas nécessairement de l’opérateur numérique >.
Dans une plage croissante, std::lower_bound trouve le premier élément qui n’est pas inférieur à value, tandis que std::upper_bound trouve le premier élément supérieur. Dans une plage triée, ces limites encadrent les éléments équivalents selon la comparaison. Faites attention à l’ordre des arguments : std::upper_bound utilise comp(value, element), et non comp(element, value).
Au moins des itérateurs forward sont requis. Le nombre de comparaisons est O(log N), mais le nombre de pas peut être O(N) sans accès aléatoire ; avec les itérateurs de std::vector, le nombre de pas est logarithmique. L’exemple utilise une syntaxe compatible avec C++23. Le projet de norme lié évolue et peut contenir des déclarations plus récentes.
Exemples
#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';
}
Résultat
index=4 value=4 at_end=true
Le code affiché et le résultat déclaré ont été vérifiés dans un environnement isolé selon la méthode consignée dans la preuve de vérification de cette version exacte.