CKTIS / C++
std::ranges::equal_range — plage d’éléments équivalents
std::ranges::equal_range trouve la plage semi-ouverte des éléments équivalents à une valeur recherchée selon un comparateur. Il prend en charge les plages, les paires itérateur-sentinelle et les projections ; les données doivent être partitionnées comme il convient, ce que garantit le tri.
Version : C++23; repository compiler flag, production runtime not attested
Syntaxe
std::ranges::equal_range(first, last, value)
std::ranges::equal_range(first, last, value, comp)
std::ranges::equal_range(first, last, value, comp, proj)
std::ranges::equal_range(range, value)
std::ranges::equal_range(range, value, comp)
std::ranges::equal_range(range, value, comp, proj)std::ranges::equal_range, déclaré dans <algorithm>, détermine la plage [lower_bound, upper_bound) sans modifier les données. L’équivalence signifie que les deux comparaisons comp(proj(element), value) et comp(value, proj(element)) sont fausses ; elle n’a pas besoin de correspondre à operator==. En l’absence de correspondance, le résultat est une plage vide à la position d’insertion de la valeur.
L’appel accepte une paire itérateur-sentinelle ou une plage entière. Il faut au moins des itérateurs forward, et comp doit respecter les exigences d’un ordre strict faible. Les valeurs par défaut sont std::ranges::less et std::identity. La projection transforme les éléments, pas la valeur recherchée. Les données doivent être partitionnées de sorte que les résultats booléens de chacune des expressions comp(proj(element), value) et !comp(value, proj(element)) forment un préfixe de valeurs vraies suivi d’un suffixe de valeurs fausses. Un tri avec le même comparateur et la même projection suffit ; violer les préconditions entraîne un comportement indéfini.
La surcharge prenant des itérateurs renvoie std::ranges::subrange<I>, tandis que celle prenant une plage renvoie std::ranges::borrowed_subrange_t<R>. Pour une plage temporaire qui ne modélise pas borrowed_range, ce dernier type est std::ranges::dangling, et non une sous-plage utilisable. Le résultat ne stocke pas de copies des éléments : les données doivent rester vivantes et leurs itérateurs valides.
Pour N éléments, il y a au plus 2 * log2(N) + O(1) comparaisons et projections ; sans itérateurs à accès aléatoire, les déplacements d’itérateurs peuvent être linéaires. L’exemple recherche des clés via &Item::key : trois correspondances occupent les indices [1, 4), tandis que la clé 3 donne un résultat vide. Cet exemple vise une configuration de compilation C++23 ; la compatibilité d’exécution en production n’est pas attestée.
Exemples
#include <algorithm>
#include <array>
#include <iostream>
struct Item {
int key;
};
int main() {
const std::array<Item, 5> items{{{1}, {2}, {2}, {2}, {4}}};
const auto matches = std::ranges::equal_range(items, 2, {}, &Item::key);
std::cout << "count=" << matches.size() << '\n';
std::cout << "begin=" << (matches.begin() - items.begin()) << '\n';
std::cout << "end=" << (matches.end() - items.begin()) << '\n';
const auto missing = std::ranges::equal_range(items, 3, {}, &Item::key);
std::cout << "missing=" << missing.empty() << '\n';
}
Résultat
count=3 begin=1 end=4 missing=1
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.