Última actualización: 31 de octubre de 2021
Artículos de la serie:
- Vistas y acciones, ejemplos 1 (generate_n, group_by, sort, to) y 2 (filter)
- Ejemplos 3 (enumerate, shuffle, take, zip) y 4 (intersperse, tokenize)
- Ejemplos 5 (getlines, transform) y 6 (iota, set_difference, split_when)
- Ejemplo 7 (stable_partition, subrange)
- Ejemplo 8 (concat, drop, generate, take_while)
- Ejemplos 9 (cycle) y 10 (keys, values)
- Ejemplo 11 (cartesian_product)
Introducción
C++20 define un rango R = [first,last) como una abstracción que permite operar uniformemente sobre los elementos de una estructura de datos, siendo first = std::ranges::begin(R) un iterador input y/o output al inicio del rango y last = std::ranges::end(R) un centinela que señaliza su final. Cadenas std::string y contenedores como std::vector o std::map --iterables mediante llamadas a begin/end-- responden claramente a este concepto, si bien de una forma muy particular: son propietarios de los datos referenciados. En contraste, std::string_view proporciona un ejemplo de rango no propietario que referencia una secuencia contigua inmutable de caracteres almacenada en otra parte.
Aun cuando el subconjunto de la biblioteca estandarizado para C++20 esté ya disponible en el compilador GCC 10.2 y superiores, en esta serie de artículos haremos uso exclusivamente de las soluciones propias de Range-v3, proporcionando múltiples ejemplos que ilustren su alcance y utilidad. Para ello, emplearemos su última versión 0.11.0 [5]. Utilizaremos también la biblioteca {fmt}lib [6] para facilitar el formato de texto. Para una correcta puesta a punto de un entorno de desarrollo en MS Windows, puede consultarse esta guía de instalación.
La biblioteca Range-v3 distingue tres tipos principales de operaciones: algoritmos, vistas (views) y acciones (actions). Tal y como se explica en el punto 6 de [4] y analizaremos en más detalle en los ejemplos:
- Los algoritmos son operaciones que (i) mutan ansiosamente (eagerly) un rango de entrada (e.g., sort), (ii) producen un valor (e.g., max_element), (iii) ambas cosas a la vez (e.g., partition) o (iv) producen un nuevo rango mediante un iterador de salida o un rango de salida (e.g., copy).
- Las vistas son operaciones que producen de forma perezosa (lazily) un nuevo rango.
- Las acciones son operaciones que producen ansiosamente un nuevo rango.
Con el fin de emplear todas estas operaciones con una sintaxis simplificada, procederemos a renombrar los siguientes espacios de nombres:
namespace rn = ::ranges;
namespace ra = rn::actions;
namespace rv = rn::views;
Asumiremos también, para garantizar una mejor legibilidad de los códigos:
using namespace std;
using fmt::print;
Las herramientas elementales de la biblioteca se encuentran recogidas en la cabecera <range/v3/core.hpp>, a la que añadiremos cabeceras adicionales correspondientes a algoritmos, vistas y/o acciones individuales según sea necesario. Conviene indicar, sin embargo, que si el lector estuviese dispuesto a asumir tiempos de compilación mayores, la totalidad de los ejemplos de esta serie de artículos podría ser compilada con la inclusión de las siguientes cabeceras (o un subconjunto de las mismas), que incluyen la totalidad de algoritmos, acciones y/o vistas de la biblioteca:
#include <range/v3/core.hpp>
#include <range/v3/algorithm.hpp>
#include <range/v3/action.hpp>
#include <range/v3/view.hpp>
Como primer punto a destacar, señalemos que la biblioteca Range-v3 sobrecarga la mayoría de los algoritmos estándar de las cabeceras <algorithm> y <numeric> con el fin de habilitar su operación directa con rangos. Así, por ejemplo, podemos ordenar un array completo de enteros con la siguiente instrucción simple:
auto nums = array{3, 6, 2, 7, 5, 4, 1};
rn::sort(nums); // nums es ordenado a {1, 2, 3, 4, 5, 6, 7}
Por supuesto, el uso tradicional de parejas de iteradores sigue siendo también posible, lo que nos permitiría escribir rn::sort(nums.begin(), nums.end()) de forma equivalente a la ordenación anterior. Los algoritmos de Range-v3 se ven enriquecidos, asimismo, por la posibilidad de especificar proyecciones que aplicar sobre los elementos antes de operar sobre ellos. Analizaremos este punto en más detalle a través de casos de uso diversos.
Ejemplo 1: generate_n, group_by, sort, to
Consideremos, en el contexto de un videojuego, el ataque a un campamento militar 2-dimensional de dimensiones 50x50 (medidas en unidades apropiadas). Cada objetivo enemigo quedará caracterizado por un objeto de tipo Target en el que se registrarán su categoría (type, distinguiéndose leader, soldier o treasure), localización (location) y estado de logro actual (achieved):
struct Location {
double x, y;
};
struct Target {
string type;
Location location;
bool achieved;
};
El booleano achieved, en particular, indica si el target ha sido ya abatido (en el caso de un líder o soldado) u obtenido (en el caso de un tesoro).
leader --> 2/4
soldier --> 4/8
treasure --> 1/3
Para programar este ejemplo, incluiremos los siguientes ficheros de cabecera de la biblioteca Range-v3:
Con el fin de caracterizar un posible estado de progreso en la misión, generaremos quince objetivos de forma aleatoria y los almacenaremos en un vector de nombre targets. Haremos uso de la técnica IILE para inicializar localmente el vector a través de la invocación inmediata de una expresión lambda:
#include <range/v3/core.hpp>
#include <range/v3/action/sort.hpp>
#include <range/v3/algorithm/count_if.hpp>
#include <range/v3/view/generate_n.hpp>
#include <range/v3/view/group_by.hpp>
auto targets = /* IILE */ []()-> vector<Target> {
auto const target_types = array{"leader", "soldier", "treasure"};
using sz_t = decltype(target_types)::size_type;
auto gen = mt19937{random_device{}()}; // (A)
auto idx_distr = uniform_int_distribution<sz_t>{0, target_types.size()-1}; // (B) [a,b]
auto xy_distr = uniform_real_distribution{-25.0, 25.0}; // (C) [a,b)
auto done_distr = bernoulli_distribution{1.0/3.0}; // (D)
auto random_target = [&]{
return Target{
.type = target_types[idx_distr(gen)],
.location = {.x = xy_distr(gen), .y = xy_distr(gen)},
.achieved = done_distr(gen)
};
};
auto const num_targets = 15;
return rv::generate_n(random_target, num_targets) | rn::to<vector>; // (E)
}();
Empleamos aquí un generador de números aleatorios basado en el algoritmo Mersenne-Twister, disponible en el fichero de cabecera estándar <random> (A). El objeto random_device proporcionará una semilla no-determinista con la que alimentar a dicho algoritmo. Las distribuciones (B), (C) y (D) serán utilizadas, respectivamente, para generar categorías, coordenadas y booleanos achieved aleatorios con los que inicializar distintos objetivos enemigos. Aproximadamente un tercio de los objetivos estarán ya completados (D). Tanto el generador como las distribuciones y el array target_types serán destruidos automáticamente al finalizar la invocación de la expresión lambda, permaneciendo únicamente el vector targets recién generado.
La línea de código de retorno (E) presenta una primera concatenación (pipeline) de operaciones propias de la biblioteca Range-v3:
- La vista generate_n toma como argumentos la función nularia random_target --la cual genera un objeto Target aleatorio-- y el número total num_targets de objetivos a producir, retornando un rango que generará dicho número de objetos mediante llamadas sucesivas a la función nularia.
- Una vez conseguida dicha vista, procedemos a materializarla en el vector de objetos Target deseado. Para ello, hacemos uso del conversor to<> proporcionado en el fichero de cabecera <range/v3/range/conversion.hpp> (incluido en <range/v3/core.hpp>), el cual reserva el espacio necesario en memoria para ubicar los objetos.
Deseamos que el código encargado de generar el HUD a partir del vector de targets no requiera conocer de antemano el número y/o categorías de objetivos en él contenidos. Antes bien, debería ser capaz de deducir dicha información de forma automática mediante una adecuada inspección del vector. Así, nuestra implementación será capaz de generar una tabla de porcentajes para escenarios del videojuego radicalmente diferentes. Esto puede lograrse con un bucle de fácil comprensión:
for (
auto same_type = [](Target const& t1, Target const& t2){
return t1.type == t2.type;
}; // (F)
auto grp : (targets |= ra::sort(rn::less{}, &Target::type)) // (G)
| rv::group_by(same_type) // (H)
) {
auto const& type = grp.begin()->type; // (I)
auto const total = rn::distance(grp); // (J)
auto const achieved = rn::count_if(grp, &Target::achieved); // (K)
print("{:>10} --> {}/{}\n", type, achieved, total);
}
En primer lugar, observemos que C++20 permite realizar una inicialización antes de la propia declaración de iteración [7]. En nuestro caso, creamos un predicado binario de nombre same_type que nos permitirá discernir si dos objetivos pertenecen o no a la misma categoría (F). Su uso queda ligado al ámbito del bucle. A continuación, el vector targets es sometido a dos operaciones consecutivas:
- En primer lugar, el vector es ordenado in situ lexicográficamente según la categoría de los objetivos a través de una acción sort (G). En particular, dicha acción emplea la proyección &Target::type para especificar el dato miembro del agregado Target en base al cual deseamos realizar la ordenación.
- Una vez ordenado el vector, tenemos garantizado que los objetivos de una misma categoría ocuparán posiciones adyacentes de la estructura. Sometemos entonces al contenedor a una vista de agrupamiento group_by(same_type) que identifica sencillamente los subrangos del vector formados por elementos consecutivos de idéntica categoría (H).
Indicar, por último, que el predicado same_type podría ser definido de forma alternativa como una proyección de la forma boost::hof::proj(&Target::type, rn::equal_to{}) tal y como se explica en este post.
Un paréntesis antes de continuar
Como podemos observar, tanto las acciones como las vistas pueden componerse con facilidad, creándose pipelines de operaciones a conveniencia a través del operador operator|.
Con carácter general, las vistas (views) no provocan la copia o mutación de los datos subyacentes, adoptando una semántica de referencia no-propietaria. Como su propio nombre indica, presentan vistas personalizadas de datos almacenados en otro lugar. Operan de forma perezosa (lazy evaluation) sobre rangos, retornando nuevos rangos que seguir adaptando. Las vistas son ellas mismas rangos para los que los procesos de copia, movimiento y asignación son de tiempo constante, es decir, son poco costosas de crear y copiar. Suelen operar sobre contenedores lvalue (más información acerca de las categorías de valor en este post), si bien aceptan también rangos rvalue con el fin de poder crear pipelines de las mismas, como en lvalue_container | rv::some_view_1 | rv::some_view_2, donde lvalue_container | rv::some_view_1 es un rango rvalue admitido por la segunda vista no-propietaria rv::some_view_2.
Las acciones (actions), por el contrario, operan de forma ansiosa (eager evaluation) y provocan, generalmente, una mutación de los datos subyacentes [8]. Actúan típicamente sobre contenedores rvalue y pueden componerse, como en get_container() | ra::some_action_1 | ra::some_action_2. Aquí, el contenedor temporal obtenido a partir de get_container() es mutado y movido de una acción a otra. Con el fin de modificar in situ un contenedor ya existente (lvalue), será necesario envolverlo en un reference_wrapper, como en ref(container) | ra::some_action. Una sintaxis equivalente pero simplificada para la operación anterior viene dada por container |= ra::some_action (véase nuestro código más arriba).
Ejemplo 2: filter
En nuestro siguiente ejemplo consideraremos la gestión de una base de datos bibliográfica, en la que cada libro dispone, entre otra información relevante, de un título y un precio de venta:
struct Book {
string title;
double price;
};
auto const books = vector<Book>{
{.title = "Romeo and Juliet", .price = 8.95},
{ "The Count of Monte Cristo", 12.89},
{ "Chronicle of a Death Foretold", 10.59},
{ "A Study in Scarlet", 9.89},
{ "War and Peace", 7.59}
};
Analicemos, a efectos ilustrativos, el problema de filtrar los libros del vector books del código anterior según un rango específico de precios (por ejemplo, entre 8.00 y 11.99), para después mostrar dicha selección por la terminal ordenada de mayor a menor precio. Para hacer más interesante el ejercicio, observemos que el vector ha sido declarado constante (const), por lo que deberemos realizar las operaciones descritas sin modificarlo.
Implementemos en primer lugar un functor predicado unario que permita determinar si un valor dado se encuentra dentro de un rango determinado:
template<typename T>
struct In_range{
T const lower,
upper;
auto operator()(T const& v) const -> bool { return !(v < lower) and (v < upper); }
};
Nuevamente, un simple bucle for resulta suficiente para la consecución de nuestros objetivos:
for (Book const& b : books | rv::filter(In_range{8.0, 12.0}, &Book::price) // (A)
| rn::to<vector<reference_wrapper<Book const>>> // (B)
| ra::sort(rn::greater{}, &Book::price) // (C)
) {
print("title: {:<30} | price: {}\n", b.title, b.price);
}
La secuencia de operaciones es auto-explicativa. En primer lugar, el vector de libros books es sometido a un filtrado para precios comprendidos en [8.0, 12.0) (A). El fichero de cabecera a incluir para esta operación es <range/v3/view/filter.hpp>. Una vez conseguida dicha vista reducida de nuestra base de datos, procedemos a materializarla y generar un nuevo vector temporal que contenga referencias reference_wrapper únicamente a los libros recién filtrados. Para ello, hacemos uso del conversor to<> (B). Este nuevo contenedor es entonces ordenado de mayor a menor precio a través de una acción sort (C) y sometido finalmente a iteración en el bucle (nos servimos en ambos casos de la conversión implícita de reference_wrapper<T> a T&).
Sin haber llegado a modificar en ningún punto el vector books original, los mensajes mostrados por la terminal serán entonces:
Sin haber llegado a modificar en ningún punto el vector books original, los mensajes mostrados por la terminal serán entonces:
title: Chronicle of a Death Foretold | price: 10.59
title: A Study in Scarlet | price: 9.89
title: Romeo and Juliet | price: 8.95
Por supuesto, si los precios límite establecidos para el filtrado fuesen tales que el subrango de libros resultante estuviese vacío, no recibiríamos ningún listado en pantalla. Es importante resaltar, asimismo, el hecho de que el vector obtenido a través de la secuencia de operaciones anterior sea un prvalue y que, por tanto, su tiempo de vida sea extendido hasta el final del bucle.
Pueden encontrarse los siguientes ejemplos de empleo de Range-v3 en el segundo post de esta serie.
Referencias bibliográficas:
- Range-v3 User Manual - https://ericniebler.github.io/range-v3/
- CppCon 2015 - Eric Niebler - 'Ranges for the Standard Library' - https://youtu.be/mFUXNMfaciE
- Cppreference - Ranges library (C++20) - https://en.cppreference.com/w/cpp/ranges
- A Plan for C++23 Ranges - http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p2214r1.html
- Range-v3 - github - https://github.com/ericniebler/range-v3
- {fmt}lib - github - https://github.com/fmtlib/fmt
- Range-based for statements with initializer (C++20) - http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0614r0.html
- Eric Niebler - Container algorithms - http://ericniebler.com/2014/11/23/container-algorithms/
No hay comentarios:
Publicar un comentario