C++ -> Fundamentos de Programación: Programando con C++20 (Parte III): Funciones std::erase y std::erase

Artículos de la serie:

Introducción

Consideremos el problema de eliminar de un contenedor estándar todos aquellos elementos que cumplan un criterio específico, bien porque éstos se comparen igual a un cierto valor dado o porque cumplan un determinado predicado unario. De emplear estándares previos a C++20, la consecución de una acción de este tipo en contenedores como std::vector, std::string o std::deque requeriría el uso de la solución idiomática conocida bajo el nombre de erase-remove [1]. En contraste, listas como std::list o std::forward_list permitirían usar funciones miembro públicas de eliminación específicas.

Así, por ejemplo, tomemos un vector de números enteros en el que queramos deshacernos de todas aquellas entradas que sean impares. La solución erase-remove requeriría:

Aplicar el algoritmo no-miembro std::remove_if proporcionado en <algorithm> para trasladar al frente del vector todos aquellos elementos que no cumplan la condición de eliminación, expresada mediante un predicado unario [2]. Esta acción se lleva a cabo a través de operaciones de movimiento std::move, manteniendo el orden relativo original de los elementos supervivientes. El algoritmo retorna un iterador representando el nuevo end() lógico del vector. Sin embargo, todos los elementos comprendidos entre dicho iterador y el end() físico original del vector siguen estando ocupados y contribuyen aún al tamaño físico del contenedor, que no se ha visto modificado (ver figura inferior). Dichos elementos remanentes poseen, en general, valores inespecíficos.
Tan sólo resta realizar una llamada a la función miembro pública erase() del vector con el fin de eliminar dichas entradas de valor inespecífico localizadas entre el nuevo end() lógico y el end() físico original, reduciendo de forma efectiva el tamaño del vector a su nueva longitud lógica.

Nuestro código tomaría, así, la forma siguiente (véase más abajo la representación gráfica de la secuencia de operaciones):

   auto nums = std::vector{1, 2, 3, 4, 5, 6, 7, 8, 9};
   auto is_odd = [](int i){ return i%2 != 0; };
   auto const new_end = std::remove_if(nums.begin(), nums.end(), is_odd);
   nums.erase(new_end, nums.end());
   for (int const i : nums)
      fmt::print("{} ", i); // output: 2 4 6 8

El código anterior contrasta con el que programaríamos con el fin de eliminar números impares en una lista std::list de enteros. En efecto, este contenedor cuenta con su propia función miembro pública de eliminación remove_if(), de forma que el código siguiente resultaría más eficiente que el proporcionado por un esquema erase-remove como el anterior:

   auto nums = std::list{1, 2, 3, 4, 5, 6, 7, 8, 9};
   nums.remove_if([](int i){ return i%2 != 0; });
   for (int const i : nums)
      fmt::print("{} ", i); // output: 2 4 6 8

La situación es más compleja para contenedores asociativos como std::set, std::map y sus versiones desordenadas, para los que el algoritmo no-miembro std::remove_if no es aplicable. El siguiente código de ejemplo muestra cómo eliminar obras literarias en un mapa título->año cuyas publicaciones tuviesen lugar con anterioridad al siglo XIX:

   auto books = std::map<std::string, int>{
      {"Hamlet", 1609},
      {"Don Quijote de La Mancha", 1605},
      {"Les Trois Mousquetaires", 1844},
      {"Les Miserables", 1862}
   };
 
   auto before_xix = [](auto const& p){ return p.second < 1800; };
   for (auto it = books.begin(); it != books.end(); /* no-op */) {
      if (before_xix(*it))
         it = books.erase(it);
      else
         ++it;
   }
 
   for (auto const& [title, year] : books)
      fmt::print("{:<23} -> {}\n", title, year);
   
   /*
      output:
         Les Miserables          -> 1862
         Les Trois Mousquetaires -> 1844
   */

Solución unificada

El estándar C++20 proporciona sobrecargas de un nuevo algoritmo no-miembro de nombre std::erase_if() en las cabeceras <string>, <deque>, <forward_list>, <list>, <vector>, <map>, <set>, <unordered_map> y <unordered_set>. Dicho algoritmo permite adoptar una sintaxis común en los casos contemplados anteriormente, convirtiendo en obsoleta la solución idomática erase-remove en contenedores como el vector.

Así, en el ejemplo de eliminación de números impares en un vector de enteros, podríamos ahora escribir simplemente:

   auto nums = std::vector{1, 2, 3, 4, 5, 6, 7, 8, 9};
   std::erase_if(nums, [](int i){ return i%2 != 0; });
   for (int const i : nums)
      fmt::print("{} ", i); // output: 2 4 6 8

Este código resulta equivalente a la aplicación de la solución erase-remove analizada en la sección anterior.

Por consistencia, un esquema análogo podría ser también aplicado a la lista std::list:

   auto nums = std::list{1, 2, 3, 4, 5, 6, 7, 8, 9};
   std::erase_if(nums, [](int i){ return i%2 != 0; });
   for (int const i : nums)
      fmt::print("{} ", i); // output: 2 4 6 8

Este código resulta equivalente a realizar una llamada a la función miembro pública remove_if() de la lista, por lo que no conlleva pérdida alguna de eficiencia.

Aun cuando no haya sido empleado en los ejemplos anteriores, conviene indicar que el algoritmo std::erase_if() devuelve un entero sin signo que contabiliza el número total de elementos eliminados. En efecto, en el caso del vector, la signatura de la función toma la forma [3]:

   namespace std {
      template<typename T, typename Alloc, typename Pred>
      constexpr auto erase_if(std::vector<T, Alloc>& c, Pred pred) 
         -> typename std::vector<T, Alloc>::size_type;
   }

La signatura es similar para el resto de contenedores. Así, en el ejemplo del mapa que liga títulos de libros y años de publicación, podríamos codificar:

   auto books = std::map<std::string, int>{
      {"Hamlet", 1609},
      {"Don Quijote de La Mancha", 1605},
      {"Les Trois Mousquetaires", 1844},
      {"Les Miserables", 1862}
   };
   
   auto before_xix = [](auto const& p){ return p.second < 1800; };
   auto const erased_sz = std::erase_if(books, before_xix);
   
   fmt::print("Number of erased elements: {}\n", erased_sz);
   for (auto const& [title, year] : books)
      fmt::print("{:<23} -> {}\n", title, year);
   
   /*
      output:
         Number of erased elements: 2
         Les Miserables          -> 1862
         Les Trois Mousquetaires -> 1844
   */

Los contenedores secuenciales <deque>, <forward_list>, <list>, <string> y <vector> vienen acompañados, adicionalmente, por un algoritmo no-miembro std::erase() para eliminar elementos que se comparen iguales a un cierto valor proporcionado. A modo de ejemplo, el código siguiente elimina todas las entradas de un vector de números enteros que sean iguales a 2:

   auto nums = std::vector{1, 2, 3, 2, 7, 2};
   auto const erased_sz = std::erase(nums, 2);
   fmt::print("Number of erased elements: {}\n", erased_sz);
   for (int const i : nums)
      fmt::print("{} ", i);

   /*
      output:
         Number of erased elements: 3
         1 3 7
   */

Donde la llamada a std::erase() anterior resulta lógicamente equivalente a:

   auto const erased_sz = std::erase_if(nums, [](int i){ return i == 2; });

Referencias bibliográficas

Scott Meyers, Effective STL. Addison-Wesley, 2001.
Cppreference - std::remove, std::remove_if - https://en.cppreference.com/w/cpp/algorithm/remove
Cppreference - std::erase, std::erase_if (std::vector) - https://en.cppreference.com/w/cpp/container/vector/erase2

C++ -> Fundamentos de Programación

Programando con C++20 (Parte III): Funciones std::erase y std::erase_if

Introducción

Solución unificada

No hay comentarios:

Publicar un comentario