Cómo eliminar elementos de un contenedor en C ++

Cómo eliminar elementos del contenedor es una pregunta común en las entrevistas de C ++, por lo que puede ganar algunos puntos brownie si lee esta página con atención.

El modismo borrar-eliminar es una técnica de C ++ para eliminar elementos que cumplen un cierto criterio de un contenedor. Sin embargo, es posible eliminar elementos con el bucle tradicional escrito a mano, pero el lenguaje borrar-eliminar tiene varias ventajas.

Comparación

// Using a hand-written loop std::vector v = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; for (auto iter = v.cbegin(); iter < v.cend(); /*iter++*/) { if (is_odd(*iter)) { iter = v.erase(iter); } else { ++iter; } } // Using the erase–remove idiom std::vector v = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; v.erase(std::remove_if(v.begin(), v.end(), is_odd), v.end());

Como puede ver, el código con un bucle escrito a mano requiere un poco más de escritura, pero también tiene un problema de rendimiento. Cada erasellamada tiene que avanzar todos los elementos después del eliminado, para evitar “huecos” en la colección. Llamar erasevarias veces en el mismo contenedor genera una gran sobrecarga para mover los elementos.

Por otro lado, el código con el modismo borrar-eliminar no solo es más expresivo, sino que también es más eficiente. Primero, usa remove_if/removepara mover todos los elementos que no se ajustan a los criterios de eliminación al frente del rango, manteniendo el orden relativo de los elementos. Entonces, después de llamar remove_if/remove, una sola llamada de eraseelimina todos los elementos restantes al final del rango.

Ejemplo

#include  // the general-purpose vector container #include  // cout #include  // remove and remove_if bool is_odd(int i) { return (i % 2) != 0; } void print(const std::vector &vec) { for (const auto& i : vec) std::cout << i << ' '; std::cout << std::endl; } int main() { // initializes a vector that holds the numbers from 1-10. std::vector v = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; print(v); // removes all elements with the value 5 v.erase(std::remove(v.begin(), v.end(), 5), v.end()); print(v); // removes all odd numbers v.erase(std::remove_if(v.begin(), v.end(), is_odd), v.end()); print(v); // removes multiples of 4 using lambda v.erase(std::remove_if(v.begin(), v.end(), [](int n) { return (n % 4) == 0; }), v.end()); print(v); return 0; } /* Output: 1 2 3 4 5 6 7 8 9 10 1 2 3 4 6 7 8 9 10 2 4 6 8 10 2 6 10 */

Fuentes

Wikipedia "Borrar-eliminar modismo": La enciclopedia libre. Wikimedia Foundation, Inc. en.wikipedia.org/wiki/Erase-remove_idiom

Meyers, Scott (2001). STL eficaz: 50 formas específicas de mejorar el uso de la biblioteca de plantillas estándar. Addison-Wesley.