CKTIS / C++
std::equal_range: limites dos elementos equivalentes a uma chave
std::equal_range devolve um par de iteradores que encerra todos os elementos equivalentes ao valor procurado num intervalo ordenado.
Versão: C++23
Sintaxe
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>, devolve {lower_bound(...), upper_bound(...)}. O primeiro iterador marca o início da classe de equivalência e o segundo a posição seguinte; sem correspondência, ambos são a posição de inserção.
O intervalo tem de estar particionado para comp(element, value) e !comp(value, element), e comp(element, value) tem de implicar !comp(value, element) para cada elemento. Violar qualquer partição ou essa implicação causa comportamento indefinido. A ordenação completa pelo mesmo ordenamento fraco estrito é uma condição suficiente segura, não um requisito separado.
O algoritmo exige um iterador forward e realiza no máximo 2 * log2(N) + O(1) comparações. Os passos são logarítmicos com random access, mas podem ser lineares com outros iteradores. O comparador deve coincidir com a ordem usada para preparar o intervalo.
Exemplos
#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';
}
Resultado
1 3
std::equal_range → 1 3