CKTIS / C++
std::ranges::equal_range — rango de elementos equivalentes
std::ranges::equal_range encuentra el rango semiabierto de elementos equivalentes a un valor buscado según un comparador. Admite rangos, pares iterador-sentinela y proyecciones; los datos deben estar particionados adecuadamente, condición que garantiza la ordenación.
Versión: C++23; repository compiler flag, production runtime not attested
Sintaxis
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, declarado en <algorithm>, determina el rango [lower_bound, upper_bound) sin modificar los datos. Equivalencia significa que ambas comparaciones comp(proj(element), value) y comp(value, proj(element)) son falsas; no tiene por qué coincidir con operator==. Si no hay coincidencias, el resultado es un rango vacío en la posición de inserción del valor.
La llamada acepta un par iterador-sentinela o un rango completo. Se requieren al menos iteradores forward, y comp debe cumplir los requisitos de orden débil estricto. Los valores predeterminados son std::ranges::less y std::identity. La proyección transforma los elementos, no el valor buscado. Los datos deben estar particionados de modo que los resultados booleanos de cada expresión comp(proj(element), value) y !comp(value, proj(element)) formen primero un prefijo verdadero y después un sufijo falso. Ordenar con el mismo comparador y la misma proyección es suficiente; incumplir las precondiciones provoca comportamiento indefinido.
La sobrecarga de iteradores devuelve std::ranges::subrange<I>, mientras que la sobrecarga de rango devuelve std::ranges::borrowed_subrange_t<R>. Para un rango temporal que no modela borrowed_range, el último tipo es std::ranges::dangling, no un subrango utilizable. El resultado no almacena copias de los elementos: los datos deben seguir existiendo y sus iteradores deben seguir siendo válidos.
Para N elementos, hay como máximo 2 * log2(N) + O(1) comparaciones y proyecciones; sin iteradores de acceso aleatorio, los movimientos de iterador pueden ser lineales. El ejemplo busca claves mediante &Item::key: tres coincidencias ocupan los índices [1, 4), mientras que la clave 3 produce un resultado vacío. El ejemplo está pensado para una configuración de compilación C++23; no se certifica la compatibilidad de ejecución en producción.
Ejemplos
#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';
}
Resultado
count=3 begin=1 end=4 missing=1
El código mostrado y el resultado declarado se verificaron en un entorno aislado mediante el método registrado en la evidencia de verificación de esta versión exacta.