Range-v3: Una introducción a la biblioteca (Parte I)

Última actualización: 12 de agosto de 2020

Artículos de la serie:


Introducción


La biblioteca header-only Range-v3, desarrollada por Eric Niebler (Facebook), permite la programación con rangos en C++14/17/20 a través de un estilo esencialmente funcional, extensible y de fácil composición (puede consultarse su manual de usuario oficial en [1]). Su excelente acogida en la comunidad de desarrolladores en C++ ha conducido a que parte de la funcionalidad de esta biblioteca haya sido adoptada por el nuevo estándar del lenguaje ISO C++20 [2], a la espera de seguir ampliando su soporte en C++23.

En esta nueva serie de posts analizaremos algunos ejemplos concretos de uso de Range-v3, con el fin de ilustrar su alcance y utilidad. Para ello, emplearemos la versión 0.11.0 de la biblioteca (https://github.com/ericniebler/range-v3), así como el compilador GCC 10.2, que proporciona algunas características del estándar C++20 especialmente convenientes para nuestro estudio. Utilizaremos también la biblioteca {fmt}lib (https://fmt.dev) para facilitar el formato de strings. Para una correcta puesta a punto de este entorno de desarrollo, puede consultarse esta guía de instalación.

Como nota de interés, indicar que en esta serie de artículos haremos uso exclusivamente de las soluciones propias de Range-v3, aun cuando la parte estandarizada de la biblioteca para C++20 esté ya disponible en el compilador GCC (subespacio de nombres std::ranges::).

Con carácter general, un rango [first, last) es una abstracción que permite operar de forma uniforme sobre los elementos de una estructura de datos. Su método begin() devuelve un iterador input o output al primer elemento, mientras que su método end() retorna un centinela que referencia a un hipotético elemento posterior al último. Pensemos, por ejemplo, en un string, un vector o un mapa: todos ellos responden a dicho concepto.

Como primer punto a destacar, la biblioteca Range-v3 sobrecarga la mayoría de los algoritmos estándar de los ficheros de cabecera <algorithm> y <numeric> con el fin de habilitar su operación directa con rangos. Así, por ejemplo, podemos ordenar un vector completo de enteros con la siguiente instrucción simple:

   auto nums = std::vector{36, 2, 7, 5, 41};    ranges::sort(nums); // nums es ordenado a {1, 2, 3, 4, 5, 6, 7}

Por supuesto, el uso tradicional de iteradores sigue siendo también posible, lo que nos permitiría escribir ranges::sort(nums.begin(), nums.end()).

Como explicaremos a continuación, la biblioteca Range-v3 distingue tres tipos especiales de operaciones: algoritmos, vistas (views) y acciones (actions). Con el fin de emplear todas ellas con una sintaxis simplificada, procederemos a renombrar los siguientes espacios de nombres:

   namespace rn = ::ranges;    namespace ra = rn::actions;    namespace rv = rn::views;

Asimismo, asumiremos para una mejor legibilidad de los códigos:

   using namespace std;    using fmt::print;


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 leadersoldier 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).

Dado un vector de targets diversos que represente el estado de ataque al campamento en un instante dado, nos planteamos el problema de mostrar por la terminal el porcentaje de cada categoría ya completado. Por ejemplo, supongamos que el campamento cuenta con un total de quince objetivos, cuatro de los cuales son líderes, ocho soldados y tres tesoros. Si dos líderes y cuatro soldados hubiesen sido ya abatidos y uno de los tesoros adquirido, mostraríamos:

    leader --> 2/4
   soldier --> 4/8
  treasure --> 1/3

Para programar este ejemplo, incluiremos los siguientes ficheros de cabecera de la biblioteca Range-v3:

   #include <range/v3/iterator.hpp>    #include <range/v3/functional.hpp>    #include <range/v3/action/sort.hpp>    #include <range/v3/algorithm/count_if.hpp>    #include <range/v3/range/conversion.hpp>    #include <range/v3/view/generate_n.hpp>    #include <range/v3/view/group_by.hpp>

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 IIFE para inicializar localmente el vector a través de la invocación inmediata de una expresión lambda:

   auto targets = /*IIFE*/ []()-> 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.025.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 para generar categorías, coordenadas y booleanos achieved aleatorios con los que inicializar distintos objetivos enemigos, respectivamente. 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 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á bajo demanda dicho número de objetos mediante llamadas sucesivas a la función.
  • 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>, el cual reserva el espacio necesario en memoria para ubicar los objetos.
Deseamos que nuestro código no requiera conocer de antemano el número y/o categorías de objetivos, siendo capaz de deducir dicha información de forma automática mediante una adecuada inspección del vector de targets. 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 [3]. 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 adyacentes de idéntica categoría (H).


El bucle for itera entonces a lo largo de los subgrupos identificados por la vista group_by, nombrados por simplicidad como grp. En cada iteración, la línea de código (I) captura por referencia la categoría (string) del primer elemento del subgrupo (leader, soldier o treasure). El número total de objetivos de dicho tipo se corresponde con la longitud distance del subgrupo (J), mientras que el algoritmo count_if permite determinar (apoyándonos nuevamente en el uso de proyecciones) el número de objetivos ya completados en el subgrupo (K).


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. Sus procesos de copia, movimiento y asignación son de tiempo constante, es decir, son poco costosas de crear y copiar. Las vistas 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.  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 enviarlo a la acción envuelto 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.

¡Manos a la obra! Implementemos en primer lugar un functor predicado unario que permita determinar si un valor dado (cualquiera que sea su tipo T, siempre que cumpla el concepto std::totally_ordered) se encuentra dentro de un rango determinado:

   template<totally_ordered T>    struct In_range{       T const lower,               upper;       auto operator()(T const& v) const -> boolreturn !(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.012.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:

  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.


Puedes encontrar los siguientes ejemplos de empleo de Range-v3 en el segundo post de esta serie.


Referencias bibliográficas:
  1. Range-v3 User Manual - https://ericniebler.github.io/range-v3/
  2. Cppreference - Ranges library (C++20) - https://en.cppreference.com/w/cpp/ranges
  3. Range-based for statements with initializer (C++20) - http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0614r0.html
  4. Eric Niebler - Container algorithms - http://ericniebler.com/2014/11/23/container-algorithms/
  5. CppCon 2015 - Eric Niebler - 'Ranges for the Standard Library' - https://youtu.be/mFUXNMfaciE

No hay comentarios:

Publicar un comentario