Base de conocimientosCentro de exámenes
ESEspañol
Elegir idioma13

CKTIS / C++

std::equal_range: límites de elementos equivalentes a una clave

std::equal_range devuelve un par de iteradores que encierra todos los elementos equivalentes al valor buscado en un rango ordenado.

Versión: C++23

Sintaxis

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>, devuelve {lower_bound(...), upper_bound(...)}. El primer iterador marca el inicio de la clase de equivalencia y el segundo su final exclusivo; si no hay coincidencia, ambos son la posición de inserción.

El rango debe estar particionado respecto a comp(element, value) y !comp(value, element), y comp(element, value) debe implicar !comp(value, element) para cada elemento. Incumplir cualquiera de las particiones o esa implicación causa comportamiento indefinido. Ordenar por completo con el mismo orden débil estricto es una condición suficiente segura, no un requisito separado.

El algoritmo exige un iterador forward y realiza como máximo 2 * log2(N) + O(1) comparaciones. Los pasos son logarítmicos con random access, pero pueden ser lineales con otros iteradores. El comparador debe coincidir con el orden usado para preparar el rango.

Ejemplos

#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

Fuentes