El modismo borrar-eliminar es una técnica común de C ++ para eliminar elementos que cumplen un cierto criterio de un contenedor de biblioteca estándar de C ++ . [1] [2] [3]
Motivación
Una tarea de programación común es eliminar todos los elementos que tienen un cierto valor o cumplen un cierto criterio de una colección . En C ++, esto se puede lograr mediante un bucle escrito a mano. Sin embargo, es preferible utilizar un algoritmo de la biblioteca estándar de C ++ para tales tareas. [1] [2] [3]
erase
se puede usar para eliminar un elemento de una colección, pero para los contenedores que se basan en una matriz, como, por ejemplo vector
, todos los elementos después del elemento eliminado deben moverse hacia adelante para evitar "huecos" en la colección. Llamar a borrar varias veces en el mismo contenedor genera mucha sobrecarga al mover los elementos.
La algorithm
biblioteca proporciona los algoritmos remove
y remove_if
para esto. Debido a que estos algoritmos operan en un rango de elementos denotados por dos iteradores hacia adelante, no tienen conocimiento del contenedor o colección subyacente. [1] [4]
Estos algoritmos no eliminan elementos del contenedor, sino que mueven todos los elementos que no se ajustan a los criterios de eliminación al frente del rango, manteniendo el orden relativo de los elementos. Esto se hace en una sola pasada a través del rango de datos.
Como en realidad no se eliminan elementos y el contenedor conserva el mismo tamaño, la cola de la matriz tiene una longitud igual al número de elementos "eliminados"; estos elementos permanecen en la memoria pero en un estado no especificado. remove
devuelve un iterador que apunta al primero de estos elementos de cola para que se puedan eliminar con una sola llamada a erase
.
Hacer lo mismo usando solo erase
da como resultado tantas pasadas como elementos haya para eliminar. Para cada una de estas pasadas, todos los elementos después del elemento borrado deben moverse, lo que requiere más tiempo que cambiar los elementos en una sola pasada.
Limitación
El modismo borrar-eliminar no se puede usar para contenedores que regresan const_iterator
(p. Ej., Set ) [5]
std::remove
y std::remove_if
no mantienen elementos que se eliminan (a diferencia de std::partition
, std::stable_partition
). Por lo tanto, erase-remove solo se puede usar con contenedores que contienen elementos con semántica de valor completo sin incurrir en pérdidas de recursos. [6]
Ejemplo
// Usa g ++ -std = c ++ 11 o clang ++ -std = c ++ 11 para compilar.#include // remove y remove_if#include #include // el contenedor de vectores de uso generalbool IsOdd ( int i ) { return i & 1 ; }Void Print ( const std :: vector < int > & vec ) { for ( const auto & i : vec ) { std :: cout << i << '' ; } std :: cout << '\ n' ; }int main () { // Inicializa un vector que contiene números del 0 al 9. std :: vector < int > v = { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 }; Imprimir ( v ); // Elimina todos los elementos con el valor 5. v . borrar ( std :: eliminar ( v . begin (), v . end (), 5 ), v . end ()); Imprimir ( v ); // Elimina todos los números impares. v . borrar ( std :: remove_if ( v . begin (), v . end (), IsOdd ), v . end ()); Imprimir ( v ); }/ * Salida: 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 6 7 8 9 0 2 4 6 8 * /
Referencias
- ↑ a b c Meyers, Scott (2001). STL eficaz: 50 formas específicas de mejorar el uso de la biblioteca de plantillas estándar . Addison-Wesley.
- ^ a b Sutter, Herb ; Alexandrescu, Andrei (2004). Estándares de codificación C ++: 101 reglas, pautas y mejores prácticas . Addison-Wesley.
- ^ a b Scott Meyers, "Algoritmos STL frente a bucles escritos a mano", Dr. Dobbs , 25 de octubre de 2001. [1]
- ^ Josuttis, Nicolai (1999). Biblioteca estándar de C ++: tutorial y referencia . Addison-Wesley.
- ^ "Erase – remove idiom with std :: set" . stackoverflow.com . Desbordamiento de pila. 25 de septiembre de 2010 . Consultado el 14 de abril de 2013 .
- ^ Meyers, Scott (2001). STL eficaz: 50 formas específicas de mejorar el uso de la biblioteca de plantillas estándar . Boston: Addison-Wesley. pp. 143 -145. ISBN 0201749629. OCLC 46713127 .