Pronto aparecerá el estándar C ++ 20, que probablemente agregará el concepto de
rangos , pero pocas personas saben qué son y con qué comen. No pude encontrar acceso a una amplia audiencia de fuentes en ruso sobre esta bestia, por lo que en este artículo me gustaría hablar más sobre él, basado en una conferencia de Arno Schödl
"De los iteradores a los rangos: la evolución futura
de la STL" de Meeting C ++ 2015- del año Trataré de hacer este artículo lo más claro posible para aquellos que se encuentran por primera vez con este concepto, y al mismo tiempo hablaré sobre todo tipo de chips como adaptadores de intervalo para aquellos que ya están familiarizados con este concepto y desean saber más.
Bibliotecas con rangos
Al momento de escribir esto, hay tres bibliotecas principales que implementan intervalos:
La primera biblioteca, de hecho, es el progenitor de este concepto (lo cual no es sorprendente, porque no hay nada en la colección de la biblioteca
Boost :)). El segundo es la biblioteca de Eric Niebler, que se describirá más adelante. Y finalmente, la última biblioteca, como se puede adivinar, fue escrita por think-cell, que, podemos decir, desarrolló y mejoró Boost.Range.
¿Por qué los intervalos es nuestro futuro?
Para aquellos que no están familiarizados con el concepto de intervalo, definimos este concepto no trivial como algo que tiene un principio y un final (un
par de iteradores ).
Consideremos ahora la siguiente tarea: hay un vector, es necesario eliminar todos los elementos que se repiten. Bajo el estándar actual, lo resolveríamos así:
std::vector<T> vec=...; std::sort( vec.begin(), vec.end() ); vec.erase( std::unique( vec.begin(), vec.end() ), vec.end() );
¡En este caso, indicamos el nombre del vector hasta
6 veces! Sin embargo, usando el concepto de intervalos (combinando iteradores al principio y al final del vector en un objeto), podemos escribir muchas veces más fácilmente especificando el vector deseado solo
una vez :
tc::unique_inplace( tc::sort(vec) );
¿Cuáles de los intervalos están actualmente dentro del estándar actual?
En el estándar C ++ 11, se agregó un acceso universal y basado en el rango al principio / final de los contenedores, y en el último estándar C ++ 17, no se agregó nada nuevo relacionado con los intervalos.
for ( int& i : <range_expression> ) { ... }
std::begin/end(<range_expression>)
Intervalos futuros
Consideremos ahora la biblioteca Range V3 mencionada anteriormente. Eric Nibler, su creador, como su proyecto de origen creó la
especificación técnica del rango , modificando la biblioteca de
algoritmos para admitir intervalos. Se parece a esto:
namespace ranges { template< typename Rng, typename What > decltype(auto) find( Rng && rng, What const& what ) { return std::find( ranges::begin(rng), ranges::end(rng), what ); } }
En su sitio hay una vista previa de lo que quiere estandarizar, esto es
Range V3 .
¿Qué rango se puede considerar?
En primer lugar,
contenedores (vector, cadena, lista, etc.), porque tienen un principio y un final. Está claro que los contenedores tienen sus propios elementos, es decir, cuando nos referimos a los contenedores, nos referimos a todos sus elementos. Del mismo modo, al copiar y declarar una constante (copia profunda y coherencia). En segundo lugar, las
vistas también pueden considerarse intervalos. Las vistas son solo un par de iteradores que apuntan al principio y al final, respectivamente. Aquí está su implementación más simple:
template<typename It> struct iterator_range { It m_itBegin; It m_itEnd; It begin() const { return m_itBegin; } It end() const { return m_itEnd; } };
Las vistas, a su vez, solo se refieren a elementos, por lo que la copia y la coherencia son perezosas (esto no afecta a los elementos).
Adaptadores de intervalo
Los inventores de intervalos no se detuvieron en esto, porque de lo contrario este concepto sería bastante inútil. Por lo tanto, introdujeron un concepto como los adaptadores de rango.
Adaptador de transformación
Considere la siguiente tarea: dejar que se proporcione un vector
int , en el que necesitamos encontrar el primer elemento igual a 4:
std::vector<int> v; auto it = ranges::find(v, 4);
Ahora imaginemos que el tipo de vector no es int, sino algún tipo de estructura compleja autoescrita, pero en la que hay un int, y la tarea sigue siendo la misma:
struct A { int id; double data; }; std::vector<A> v={...}; auto it = ranges::find_if( v, [](A const& a) { return a.id == 4; } );
Está claro que estos dos códigos son similares en semántica, sin embargo, difieren significativamente en la sintaxis, porque en el último caso tuvimos que escribir manualmente una función que se ejecuta a través del campo
int . Pero si usa un adaptador de transformación (adaptador de
transformación ), entonces todo parece mucho más sucinto:
struct A { int id; double data; }; std::vector<A> v={...}; auto it = ranges::find( tc::transform(v, std::mem_fn(&A::id)), 4);
De hecho, el adaptador transformador "transforma" nuestra estructura al crear una clase de envoltura alrededor del campo int. Está claro que el puntero apunta al campo
id , pero si queremos que apunte a toda la estructura, debemos agregar al final de
.base () . Este comando encapsula el campo, por lo que el puntero puede correr por toda la estructura:
auto it = ranges::find( tc::transform(v, std::mem_fn(&A::id)), 4).base();
Aquí hay un ejemplo de implementación de un adaptador de transformación (consta de iteradores, cada uno de los cuales tiene su propio functor):
template<typename Base, typename Func> struct transform_range { struct iterator { private: Func m_func;
Adaptador de filtro
¿Y si en la última tarea necesitáramos encontrar no el primer elemento, sino "filtrar"
todo el campo de
int para la presencia de tales elementos? En este caso, usaríamos un adaptador de filtro:
tc::filter( v, [](A const& a) { return 4 == a.id; } );
Tenga en cuenta que el filtro se ejecuta perezosamente durante las iteraciones.
Y aquí está su implementación ingenua (algo así se implementa en Boost.Range):
template<typename Base, typename Func> struct filter_range { struct iterator { private: Func m_func;
Como podemos ver, aquí se requieren dos iteradores en lugar de uno, como estaba en el adaptador de transformación. El segundo iterador es necesario para no ir accidentalmente más allá de los límites del contenedor durante las iteraciones.
Algunas optimizaciones
Ok, pero ¿cómo se ve el iterador de
tc :: filter (tc :: filter (tc :: filter (...))) ?
Boost.range
Como parte de la implementación anterior, se ve así:
Los débiles de corazón no miran!m_func3
m_it3
m_func2
m_it2
m_func1
m_it1;
m_itEnd1;
m_itEnd2
m_func1
m_it1;
m_itEnd1;
m_itEnd3
m_func2
m_it2
m_func1
m_it1;
m_itEnd1;
m_itEnd2
m_func1
m_it1;
m_itEnd1;
Obviamente, esto es
terriblemente ineficiente.
Rango v3
Pensemos cómo optimizar este adaptador. La idea de Eric Nibler era poner información general (un functor y un puntero al final) en el objeto adaptador, y luego podemos almacenar un enlace a este objeto adaptador y el iterador deseado
*m_rng
m_it
Luego, en el marco de dicha implementación, un filtro triple se verá más o menos así:
Tykm_rng3
m_it3
m_rng2
m_it2
m_rng1
m_it1
Esto todavía no es perfecto, aunque a veces más rápido que la implementación anterior.
think-cell, concepto de índice
Ahora considere la solución think-cell. Introdujeron el llamado
concepto de índice para resolver este problema. Un índice es un iterador que realiza las mismas operaciones que un iterador normal, pero lo hace haciendo referencia a intervalos.
template<typename Base, typename Func> struct index_range { ... using Index = ...; Index begin_index() const; Index end_index() const; void increment_index( Index& idx ) const; void decrement_index( Index& idx ) const; reference dereference( Index& idx ) const; ... };
Mostramos cómo combinar un índice con un iterador regular.
Está claro que un iterador regular también puede considerarse un índice. En la dirección opuesta, la compatibilidad se puede implementar, por ejemplo, de la siguiente manera:
template<typename IndexRng> struct iterator_for_index { IndexRng* m_rng; typename IndexRng::Index m_idx; iterator& operator++() { m_rng.increment_index(m_idx); return *this; } ... };
Luego, el filtro triple se implementará de manera súper eficiente:
template<typename Base, typename Func> struct filter_range { Func m_func; Base& m_base; using Index = typename Base::Index; void increment_index( Index& idx ) const { do { m_base.increment_index(idx); } while ( idx != m_base.end_index() && !m_func(m_base.dereference_index(idx)) ); } };
template<typename IndexRng> struct iterator_for_index { IndexRng* m_rng; typename IndexRng::Index m_idx; ... };
En el marco de dicha implementación, el algoritmo funcionará rápidamente independientemente de la profundidad del filtro.
Intervalos con contenedores lvalue y rvalue
Ahora veamos cómo funcionan los intervalos con los contenedores lvalue y rvalue:
lvalue
Range V3 y think-cell se comportan igual con lvalue. Supongamos que tenemos un código como este:
auto rng = view::filter(vec, pred1); bool b = ranges::any_of(rng, pred2);
Aquí tenemos un vector previamente declarado que se encuentra en la memoria (lvalue), y necesitamos crear un intervalo y luego trabajar de alguna manera con él. Creamos una vista usando
view :: filter o
tc :: filter y nos alegramos, no hay errores, y luego podemos usar esta vista, por ejemplo, en any_of.
Rango V3 y valor r
Sin embargo, si nuestro vector aún no estuviera en la memoria (por ejemplo, si solo lo estuviéramos creando), y nos hubiéramos enfrentado a la misma tarea, entonces trataríamos de escribir y enfrentar un error:
auto rng = view::filter(create_vector(), pred1);
¿Por qué surgió? La vista será un enlace colgante a rvalue debido al hecho de que creamos un vector y lo colocamos directamente en un filtro, es decir, habrá un enlace rvalue en el filtro, que luego señalará algo desconocido cuando el compilador pasa a la siguiente línea y se produce un error. Para resolver este problema, Range V3 ideó una
acción :
auto rng = action::filter(create_vector(), pred1);
La acción hace todo a la vez, es decir, simplemente toma un vector, filtra por predicado y lo coloca en un intervalo. Sin embargo, el inconveniente es que ya no es perezoso, y think-cell intentó solucionar este inconveniente.
think-cell y rvalue
Think-cell lo hizo para que en lugar de ver se cree un contenedor:
auto rng = tc::filter(creates_vector(), pred1); bool b = ranges::any_of(rng, pred2);
Como resultado, no encontramos un error similar, porque en su implementación, el filtro recolecta el contenedor rvalue en lugar del enlace, por lo que esto sucede de manera perezosa. Range V3 no quería hacer esto porque temían que hubiera errores debido a que el filtro se comportara como una vista o como un contenedor, sin embargo, think-cell está convencido de que los programadores entienden cómo se comporta el filtro, y La mayoría de los errores surgen precisamente por esta "pereza".
Intervalos de generador
Generalizamos el concepto de intervalos. De hecho, hay intervalos sin iteradores. Se llaman
gamas generadoras . Supongamos que tenemos un widget GUI (un elemento de interfaz) y llamamos un widget de movimiento. Tenemos una ventana que solicita mover su widget, también tenemos un botón en el
cuadro de lista , y otra ventana también debe desplazarse a través de sus widgets, es decir, llamamos a
traverse_widgets , que conecta los elementos a un functor (
puede decir que hay una función de enumeración donde conecta el functor, y la función enumera todos los elementos que tiene en este functor ).
template<typename Func> void traverse_widgets( Func func ) { if (window1) { window1->traverse_widgets(std::ref(func)); } func(button1); func(listbox1); if (window2) { window2->traverse_widgets(std::ref(func)); } }
Esto recuerda un poco al espaciado de widgets, pero aquí no hay iteradores. Escribirlos directamente sería ineficiente y, sobre todo, muy difícil. En este caso, podemos decir que tales estructuras también se consideran intervalos. Luego, para tales casos, se utilizan métodos de intervalo útiles, como
any_of :
mouse_hit_any_widget=tc::any_of( [] (auto func) { traverse_widgets(func); }, [] (auto const& widget) { return widget.mouse_hit(); } );
think-cell intenta implementar métodos para que tengan la misma interfaz para todo tipo de intervalos:
namespace tc { template< typename Rng > bool any_of( Rng const& rng ) { bool bResult = false; tc::enumerate( rng, [&](bool_context b) { bResult = bResult || b; } ); return bResult; } }
Usando
tc :: enumerate , la diferencia entre los intervalos está oculta, ya que dicha implementación se adhiere al concepto de
iteración interna (lo que los conceptos de
iteración externa e
interna se describen con más detalle en la conferencia), sin embargo, esta implementación tiene sus inconvenientes, a saber,
std :: any_of se detiene tan pronto como se encuentra
verdadero . Intentan resolver este problema, por ejemplo, agregando excepciones (los llamados
intervalos de generador interrumpidos ).
Conclusión
Odio el bucle for basado en rango porque motiva a las personas a escribirlo donde sea necesario y donde no sea necesario, debido a que la concisión del código a menudo empeora, por ejemplo, la gente escribe esto:
bool b = false; for (int n : rng) { if ( is_prime(n) ) { b = true; break; } }
en cambio:
bool b = tc::any_of( rng, is_prime );