Идиома «Стереть–удалить»

Идиома стирания-удаления — это распространенный метод C++ для исключения элементов, соответствующих определенному критерию, из контейнера стандартной библиотеки C++ .

Мотивация

Распространенной задачей программирования является удаление из коллекции всех элементов, имеющих определенное значение или удовлетворяющих определенному критерию . В C++ этого можно добиться с помощью написанного вручную цикла. Однако для таких задач предпочтительнее использовать алгоритм из стандартной библиотеки C++.

Функция-член erase может использоваться для удаления элемента из коллекции, но для контейнеров, основанных на массиве, таких как vector, все элементы после удаленного элемента необходимо переместить вперед, чтобы избежать «пробелов» в коллекции. Вызов стирания несколько раз в одном и том же контейнере приводит к большим накладным расходам при перемещении элементов.

The algorithm библиотека предоставляет remove и remove_if алгоритмы для этого. Поскольку эти алгоритмы работают с диапазоном элементов, обозначенным двумя прямыми итераторами, они не знают базового контейнера или коллекции.

Эти алгоритмы не удаляют элементы из контейнера, а перемещают все элементы, которые не соответствуют критериям удаления, в начало диапазона, сохраняя относительный порядок элементов. Это делается за один проход по диапазону данных.

Поскольку никакие элементы фактически не удаляются и контейнер сохраняет тот же размер, длина хвоста массива равна количеству «удаленных» элементов; эти элементы остаются в памяти, но в неопределенном состоянии. remove возвращает итератор, указывающий на первый из этих хвостовых элементов, чтобы их можно было удалить с помощью одного вызова erase.

Делаем то же самое, используя только erase приводит к такому количеству проходов, сколько элементов нужно удалить. Для каждого из этих проходов необходимо переместить все элементы после стертого элемента, что занимает больше времени, чем перемещение элементов за один проход.

С++20

Начиная с C++20, свободные функции std::erase и std::erase_if предоставляются для контейнеров STL. Эти удобные функции можно использовать для правильного стирания элементов, не требуя от программиста явного использования идиомы стирания-удаления.

Ограничение

Идиому стереть-удалить нельзя использовать для контейнеров, которые возвращают const_iterator (например: набор )

std::remove и/или std::remove_if не сохранять удаленные элементы (в отличие от std::partition, std::stable_partition). Таким образом, метод стирания-удаления можно использовать только с контейнерами, содержащими элементы с полноценной семантикой, без утечек ресурсов.

Пример

Компилятор Explorer

// Use g++ -std=c++11 or clang++ -std=c++11 to compile.

#include <algorithm>  // remove and remove_if
#include <iostream>
#include <vector>

void Print(const std::vector<int>& vec) {
  for (auto val : vec) {
    std::cout << val << ' ';
  }
  std::cout << '\n';
}

int main() {
  std::vector<int> v = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  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(), [](int val) { return val & 1; }),
          v.end());
  Print(v);
}

/*
Output:
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 6 7 8 9
0 2 4 6 8
*/