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

Artículos de la serie:

1. Vistas y acciones, ejemplos 1 (generate_n, group_by, sort, to) y 2 (filter)
2. Ejemplos 3 (enumerate, shuffle, take, zip) y 4 (intersperse, tokenize)
3. Ejemplos 5 (getlines, transform) y 6 (iota, set_difference, split_when)
4. Ejemplo 7 (stable_partition, subrange)
5. Ejemplo 8 (concat, drop, generate, take_while)
6. Ejemplos 9 (cycle) y 10 (keys, values)
7. Ejemplo 11 (cartesian_product)

En este post proporcionaremos un nuevo ejemplo de programación con la biblioteca Range-v3, un subconjunto de la cual ha sido adoptada por el nuevo estándar del lenguaje C++20. Pueden consultarse los espacios de nombres utilizados por este artículo en el primer post de la serie.

---

Ejemplo 7: stable_partition, subrange

Creemos un vector con la siguiente lista de álbumes musicales (especificando sus autores y género):

   struct Album {       string title,              band,              genre;    };    auto albums = vector<Album>{          {.title = "the dark side of the moon", .band = "pink floyd",    .genre = "rock" },       { "tubular bells",              "mike oldfield", "new age" },       { "ok computer",                "radiohead",       "rock" },       { "the magnificent tree",       "hooverphonic",    "pop" },       { "favourite worst nightmare",  "arctic monkeys",  "rock" },       { "the four seasons",           "vivaldi",         "classical"},       { "parachutes",                 "coldplay",        "pop" },       { "the suburbs",                "arcade fire",     "rock" },       { "gran turismo",               "the cardigans",   "pop" }    };

Demos entonces la oportunidad al usuario de indicar por la terminal un título arbitrario, con el fin de realizar una búsqueda lineal de éste en el vector. De localizarse el título dentro de la discografía, acumularemos en torno a él todos los álbumes que pertenezcan a su mismo género musical. Realizaremos dicha reorganización de forma estable a ambos lados del álbum solicitado, con el fin de preservar el orden relativo original de los títulos. Por ejemplo, de realizar la búsqueda 'favourite worst nightmare', y partiendo del vector de títulos anterior, deberíamos visualizar el resultado siguiente:

  Title to search: favourite worst nightmare

              tubular bells [by] mike oldfield   | new age
       the magnificent tree [by] hooverphonic    | pop
  __________________________________________________________
  the dark side of the moon [by] pink floyd      | rock
                ok computer [by] radiohead       | rock
  favourite worst nightmare [by] arctic monkeys  | rock
                the suburbs [by] arcade fire     | rock
  __________________________________________________________
           the four seasons [by] vivaldi         | classical
                 parachutes [by] coldplay        | pop
               gran turismo [by] the cardigans   | pop

Observemos, en efecto, cómo todos los discos del mismo género que el solicitado (en este caso, rock) se agrupan en torno a él. Nuestro código de partición tomaría la forma siguiente (véase también la figura inferior como referencia auxiliar):

   auto const title_to_search = /* IILE */ []{       auto res = string{};       print("Title to search: ");       getline(cin, res);       return res;    }();    auto const iter = rn::find(albums, title_to_search, &Album::title);     // (A)    if (iter == albums.end())                                                    // (B)      /* interrumpir el proceso: el álbum solicitado no está en el vector */    auto const& found_genre = iter->genre;                           // (C)    auto same_genre = [&](string const& genre){ return genre == found_genre; };   // (D)    auto const ppt_1 = rn::stable_partition(albums.begin(), iter,                                            not_fn(same_genre), &Album::genre),  // (E)     ppt_2 = rn::stable_partition(iter + 1, albums.end(),  same_genre, &Album::genre);  // (F)

Solicitamos en primer lugar la introducción del título a buscar y, de encontrarse éste en la discografía [(A) y (B)], procedemos a completar los pasos siguientes:

• Obtenemos el género del álbum solicitado (C) y definimos una expresión lambda que averigüe si el género de un título cualquiera coincide con el del solicitado (D).

• Particionamos de forma estable el subrango del vector de álbumes comprendido desde el inicio del contenedor hasta el elemento encontrado (sin incluir este último) de forma que todos los álbumes de género idéntico al buscado se sitúen al fondo del subrango (E). Para ello, empleamos el fichero de cabecera <range/v3/algorithm/stable_partition.hpp>, así como la plantilla estándar std::not_fn para negar la lambda. De esta forma, obtenemos un primer punto de partición ppt_1 que referencia al primer título de igual género que el buscado.

• Particionamos de forma estable el subrango del vector de álbumes desde un elemento posterior al solicitado hasta el final del contenedor, de forma que todos los títulos de género idéntico al buscado se sitúen al frente del subrango (F). De esta forma, obtenemos un segundo punto de partición ppt_2 que referencia a un título posterior al último del género buscado (o al end() del vector).

Procedemos finalmente a mostrar en la terminal los álbumes ya reorganizados:

   auto show_albums = []<input_iterator I>(I first, I last) {               // (G)       for (auto const& [title, band, genre] : rn::subrange{first, last})       // (H)          print("{:>25} [by] {:<15} | {}\n", title, band, genre);    };    show_albums(albums.begin(), ppt_1);                                         // (I)    print("{:_<58}\n", "");    show_albums(ppt_1, ppt_2);                                                  // (J)    print("{:_<58}\n", "");    show_albums(ppt_2, albums.end());                                           // (K)

Para ello, definimos una expresión lambda genérica que tome un rango de álbumes especificado por dos iteradores de tipo input, first y last, e imprima en consola la información asociada a sus títulos (G). Observemos aquí que la operación ranges::subrange{first, last} (cabecera <range/v3/view/subrange.hpp> incluida en <range/v3/core.hpp>) define un rango [first, last) que poder iterar convenientemente a través de un bucle for (H). El concepto std::input_range, que restringe el parámetro de la plantilla, puede encontrarse en el fichero de cabecera <iterator>.

La función lambda definida en el punto anterior es invocada tres veces con el fin de mostrar, por este orden:

1. Los álbumes de género distinto al solicitado previos a éste (I).
2. El grupo de álbumes de género idéntico al solicitado agrupados en torno a éste (J).
3. Los álbumes de género distinto al solicitado posteriores a éste (K).

---

Puede encontrarse el siguiente ejemplo de empleo de Range-v3 en el quinto post de esta serie.

---