CKTIS / C++
std::equal_range: hranice prvků ekvivalentních klíči
std::equal_range vrátí dvojici iterátorů ohraničující všechny prvky ekvivalentní hledané hodnotě v uspořádaném rozsahu.
Verze: 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) z <algorithm> vrací {lower_bound(...), upper_bound(...)}. První iterátor označuje začátek třídy ekvivalence a druhý pozici za ní; není-li shoda, oba ukazují na pozici vložení.
Rozsah musí být rozdělen podle comp(element, value) i !comp(value, element) a pro každý prvek musí comp(element, value) implikovat !comp(value, element). Porušení kteréhokoli rozdělení nebo této implikace vede k nedefinovanému chování. Úplné seřazení stejným striktním slabým uspořádáním je bezpečná postačující podmínka, nikoli samostatný požadavek.
Algoritmus vyžaduje dopředný iterátor a provede nejvýše 2 * log2(N) + O(1) porovnání. S random access jsou kroky logaritmické, s jinými iterátory mohou být lineární. Komparátor musí odpovídat uspořádání použitému k přípravě rozsahu.
Příklady
#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';
}
Výsledek
1 3
std::equal_range → 1 3