std::ranges::equal_range
De cppreference.com
<tbody>
</tbody>
<tbody class="t-dcl-rev t-dcl-rev-num ">
</tbody><tbody>
</tbody>
<tbody class="t-dcl-rev t-dcl-rev-num ">
</tbody><tbody>
</tbody>
| Definido en el archivo de encabezado <algorithm>
|
||
| Signatura de la llamada |
||
| (1) | ||
template< std::forward_iterator I, std::sentinel_for<I> S, class T, class Proj = std::identity, std::indirect_strict_weak_order <const T*, std::projected<I, Proj>> Comp = ranges::less > constexpr ranges::subrange<I> equal_range( I first, S last, const T& value, Comp comp = {}, Proj proj = {} ); |
(desde C++20) (hasta C++26) |
|
template< std::forward_iterator I, std::sentinel_for<I> S, class Proj = std::identity, class T = std::projected_value_t<I, Proj>, std::indirect_strict_weak_order <const T*, std::projected<I, Proj>> Comp = ranges::less > constexpr ranges::subrange<I> equal_range( I first, S last, const T& value, Comp comp = {}, Proj proj = {} ); |
(desde C++26) | |
| (2) | ||
template< ranges::forward_range R, class T, class Proj = std::identity, std::indirect_strict_weak_order <const T*, std::projected<ranges::iterator_t<R>, Proj>> Comp = ranges::less > constexpr ranges::borrowed_subrange_t<R> equal_range( R&& r, const T& value, Comp comp = {}, Proj proj = {} ); |
(desde C++20) (hasta C++26) |
|
template< ranges::forward_range R, class Proj = std::identity, class T = std::projected_value_t<ranges::iterator_t<R>, Proj>, std::indirect_strict_weak_order <const T*, std::projected<ranges::iterator_t<R>, Proj>> Comp = ranges::less > constexpr ranges::borrowed_subrange_t<R> equal_range( R&& r, const T& value, Comp comp = {}, Proj proj = {} ); |
(desde C++26) | |
El rango [first, last) debe estar al menos parcialmente ordenado con respecto a value, es decir, debe satisfacer todos los siguientes requisitos:
- particionado con respecto a
element < valueocomp(element, value)(es decir, todos los elementos para los que la expresión estruepreceden a todos los elementos para los que la expresión esfalse). - particionado con respecto a
!(value < element)o!comp(value, element). - para todos los elementos, si
element < valueocomp(element, value)estrueentonces!(value < element)o!comp(value, element)también estrue.
Un rango completamente ordenado cumple con estos criterios.
La vista devuelta se construye a partir de dos iteradores, uno que apunta al primer elemento que es no menor que value y otro que apunta al primer elemento mayor que value. El primer iterador se puede obtener alternativamente con std::ranges::lower_bound(), el segundo con std::ranges::upper_bound().
2) Igual que (1), pero utiliza
r como rango de origen, como si usara el rango ranges::begin(r) como first y ranges::end(r) como last.Las entidades similares a funciones descritas en esta página son niebloids, es decir:
- Las listas de argumentos de plantilla explícitas no se pueden especificar al llamar a cualquiera de ellas.
- Ninguna de ellas es visible para la búsqueda dependiente de argumentos.
- Cuando alguna de ellas se encuentra mediante la búsqueda normal no calificada como el nombre a la izquierda del operador de llamada a función, se inhibe la búsqueda dependiente de argumentos.
En la práctica, pueden implementarse como objetos función o con extensiones de compilador especiales.
Parámetros
| first, last | - | El rango de los elementos a examinar. |
| r | - | El rango de los elementos a examinar. |
| value | - | El valor con el que comparar los elementos. |
| comp | - | Si el primer argumento es menor que (es decir, está ordenado antes) el segundo. |
| proj | - | La proyección que se aplicará a los elementos. |
Valor de retorno
std::ranges::subrange contiene un par de iteradores que definen el rango deseado, el primero apunta al primer elemento que no es menor que value y el segundo apunta al primer elemento que es mayor que value.
Si no hay elementos que sean menores que value, el último iterador (iterador que sea igual a last o ranges::end(r)) se devuelve como el primer elemento. De manera similar, si no hay elementos que sean mayores que value, el último iterador se devuelve como el segundo elemento.
Complejidad
La cantidad de comparaciones realizadas es logarítmica en la distancia entre first y last (como máximo 2 * log
2(last - first) + O(1) comparaciones). Sin embargo, para un iterador que no modela random_access_iterator, la cantidad de incrementos del iterador es lineal.
Posible implementación
struct equal_range_fn
{
template<std::forward_iterator I, std::sentinel_for<I> S,
class Proj = std::identity, class T = std::projected_value_t<I, Proj>,
std::indirect_strict_weak_order
<const T*, std::projected<I, Proj>> Comp = ranges::less>
constexpr ranges::subrange<I>
operator()(I first, S last, const T& value, Comp comp = {}, Proj proj = {}) const
{
return ranges::subrange
(
ranges::lower_bound(first, last, value, std::ref(comp), std::ref(proj)),
ranges::upper_bound(first, last, value, std::ref(comp), std::ref(proj))
);
}
template<ranges::forward_range R, class Proj = std::identity,
class T = std::projected_value_t<ranges::iterator_t<R>, Proj>,
std::indirect_strict_weak_order
<const T*, std::projected<ranges::iterator_t<R>,
Proj>> Comp = ranges::less>
constexpr ranges::borrowed_subrange_t<R>
operator()(R&& r, const T& value, Comp comp = {}, Proj proj = {}) const
{
return (*this)(ranges::begin(r), ranges::end(r), value,
std::ref(comp), std::ref(proj));
}
};
inline constexpr equal_range_fn equal_range;
|
Notas
| Macro de Prueba de característica | Valor | Estándar | Comentario |
|---|---|---|---|
__cpp_lib_algorithm_default_value_type |
202403 |
(C++26) | Inicialización de lista para algoritmos (1,2) |
Ejemplo
Ejecuta este código
#include <algorithm>
#include <compare>
#include <complex>
#include <iostream>
#include <vector>
struct S
{
int num {};
char nombre {};
// nota: nombre se ignora por estos operadores de comparación
friend bool operator== (const S s1, const S s2) { return s1.num == s2.num; }
friend auto operator<=>(const S s1, const S s2) { return s1.num <=> s2.num; }
friend std::ostream& operator<<(std::ostream& os, S o)
{
return os << '{' << o.num << ", '" << o.nombre << "'}";
}
};
void println(auto comentario, const auto& v)
{
for (std::cout << comentario; const auto& e : v)
std::cout << e << ' ';
std::cout << '\n';
}
int main()
{
// nota: no ordenado, solo particionado con respecto a S abajo
std::vector<S> vec
{
{1,'A'}, {2,'B'}, {2,'C'}, {2,'D'}, {4, 'D'}, {4,'G'}, {3,'F'}
};
const S valor{2, '?'};
namespace ranges = std::ranges;
auto a = ranges::equal_range(vec, valor);
println("1. ", a);
auto b = ranges::equal_range(vec.begin(), vec.end(), valor);
println("2. ", b);
auto c = ranges::equal_range(vec, 'D', ranges::less {}, &S::nombre);
println("3. ", c);
auto d = ranges::equal_range(vec.begin(), vec.end(), 'D', ranges::less {}, &S::nombre);
println("4. ", d);
using CD = std::complex<double>;
std::vector<CD> nums{{1, 0}, {2, 2}, {2, 1}, {3, 0}, {3, 1}};
auto cmpz = [](CD x, CD y) { return x.real() < y.real(); };
#ifdef __cpp_lib_algorithm_default_value_type
auto p3 = ranges::equal_range(nums, {2, 0}, cmpz);
#else
auto p3 = ranges::equal_range(nums, CD{2, 0}, cmpz);
#endif
println("5. ", p3);
}
Salida:
1. {2, 'B'} {2, 'C'} {2, 'D'}
2. {2, 'B'} {2, 'C'} {2, 'D'}
3. {2, 'D'} {4, 'D'}
4. {2, 'D'} {4, 'D'}
5. (2,2) (2,1)
Véase también
(C++20) |
Devuelve un iterador al primer elemento no menor que el valor dado. (niebloid) |
(C++20) |
Devuelve un iterador al primer elemento mayor que un cierto valor. (niebloid) |
(C++20) |
Determina si un elemento existe en un cierto rango. (niebloid) |
(C++20) |
Divide un rango de elementos en dos grupos (niebloid) |
(C++20) |
Determina si dos conjuntos de elementos son iguales. (niebloid) |
| Devuelve el rango de los elementos que coinciden con una clave específica. (plantilla de función) |