CKTIS / C++
std::equal_range : bornes des éléments équivalents à une clé
std::equal_range renvoie une paire d’itérateurs encadrant tous les éléments équivalents à la valeur cherchée dans une plage ordonnée.
Version : C++23
Syntaxe
template<class ForwardIterator, class T, class Compare>
constexpr std::pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);std::equal_range(first, last, value, comp) de <algorithm> renvoie {lower_bound(...), upper_bound(...)}. Le premier itérateur marque le début de la classe d’équivalence et le second sa fin exclue ; sans correspondance, tous deux valent la position d’insertion.
La plage doit être partitionnée pour comp(element, value) et !comp(value, element), et comp(element, value) doit impliquer !comp(value, element) pour chaque élément. Violer une condition de partition ou cette implication produit un comportement indéfini. Un tri complet selon le même ordre faible strict est une condition suffisante sûre, non une exigence distincte.
L’algorithme exige un itérateur forward et effectue au plus 2 * log2(N) + O(1) comparaisons. Les pas sont logarithmiques avec random access, mais peuvent être linéaires pour les autres itérateurs. Le comparateur doit correspondre à l’ordre ayant préparé la plage.
Exemples
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
const std::vector<int> values{1, 2, 2, 2, 4};
const auto [first, last] = std::equal_range(values.begin(), values.end(), 2);
std::cout << (first - values.begin()) << ' ' << (last - first) << '\n';
}
Résultat
1 3
std::equal_range → 1 3