Як видалити елементи з контейнера в C ++

Як видалити елементи з контейнера - це поширене запитання для співбесіди на C ++, тому ви можете заробити трохи очок для брауні, якщо уважно прочитаєте цю сторінку.

Ідіома стирання-видалення - це техніка С ++ для усунення елементів, які відповідають певним критеріям, із контейнера. Однак можна усунути елементи за допомогою традиційного рукописного циклу, але ідіома видалення – видалення має ряд переваг.

Порівняння

// 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());

Як бачите, код із рукописним циклом вимагає трохи більше набору тексту, але він також має проблему з продуктивністю. Кожен eraseвиклик повинен переміщати вперед усі елементи після видаленого, щоб уникнути “прогалин” у колекції. Виклик eraseдекількох разів в одному контейнері генерує багато накладних витрат на переміщення елементів.

З іншого боку, код із ідіомою стирання – видалення є не тільки більш виразним, але й більш ефективним. По-перше, ви використовуєте remove_if/removeдля переміщення всіх елементів, які не відповідають критеріям видалення, в передню частину діапазону, зберігаючи відносний порядок елементів. Отже, після виклику remove_if/removeодин виклик eraseвидаляє всі елементи, що залишилися в кінці діапазону.

Приклад

#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 */

Джерела

“Видалити-видалити ідіому” Вікіпедія: Вільна енциклопедія. Wikimedia Foundation, Inc. en.wikipedia.org/wiki/Erase-remove_idiom

Мейерс, Скотт (2001). Ефективний STL: 50 конкретних способів покращити використання стандартної бібліотеки шаблонів. Аддісон-Веслі.