C++17 STL Стандартная библиотека шаблонов - Яцек Галовиц

нашем примере много значений 2, удалим их:

  const auto new_end (remove(begin(v), end(v), 2));

5. Что интересно, это был лишь первый шаг. Вектор все еще имеет прежний размер. Мы укоротим его по-настоящему, написав такую строку:

  v. erase(new_end, end(v));

6. Остановимся и выведем на экран содержимое вектора, а затем продолжим:

  for (auto i : v) {

    cout << i << ", ";

  }

  cout << 'n';

7. Теперь удалим целый класс элементов, а не конкретные значения. Для этого сначала определим функцию-предикат, которая принимает число в качестве параметра и возвращает значение true, если переданное число нечетное:

  const auto odd ([](int i) { return i % 2 != 0; });

8. Используем функцию remove_if, передавая ей значения с помощью функции-предиката. Вместо удаления элементов за два шага теперь делаем это за один:

  v. erase(remove_if(begin(v), end(v), odd), end(v));

9. Мы удалили все нечетные элементы, но емкость вектора все еще соответствует старым десяти элементам. На последнем шаге мы сократим эту емкость до реального размера вектора. Обратите внимание: это может привести к тому, что код обслуживания вектора выделит новый фрагмент памяти, который будет иметь соответствующий размер, и переместит все элементы из старого фрагмента в новый:

  v.shrink_to_fit();

10. Теперь выведем на экран содержимое вектора после второго раунда удаления элементов и закончим с примером:

  for (auto i : v) {

    cout << i << ", ";

  }

  cout << 'n';

}

11. Скомпилировав и запустив программу, вы увидите следующие строки, показывающие результат выполнения операций по удалению элементов:

$ ./main

1, 3, 5, 6, 4, 8,

6, 4, 8,

Как это работает 

Из данного примера стало очевидно: при удалении элементов из середины вектора их нужно сначала убрать, а затем стереть. По крайней мере функции, которые мы использовали, имеют соответствующие имена. Это может запутать, но рассмотрим их подробнее, чтобы разобраться в том, что происходит на каждом шаге.

Код, удаляющий все значения 2 из вектора, выглядел так:

const auto new_end (remove(begin(v), end(v), 2));

v.erase(new_end, end(v));

Функции std::begin и std::end принимают в качестве параметра экземпляр вектора и соответственно возвращают итераторы, которые указывают на первый элемент и на позицию, находящуюся после последнего элемента, как показано на рис. 2.1.

После того как мы передадим их и значение 2 функции std::remove, она переместит все значения, кроме 2, вперед точно так же, как если бы мы сделали это вручную с помощью цикла. С первого взгляда рисунок может показаться непонятным. На шаге 2 все еще можно найти значение 2, а сам вектор должен был стать короче, поскольку содержал четыре таких значения. Вместо этого значения 4 и 8, присутствовавшие в оригинальном массиве, встречаются дважды. Что происходит?

Рассмотрим только элементы, находящиеся в рамках диапазона от итератора begin, показанного на рис. 2.1, до итератора new_end. Элемент, на который указывает итератор new_end, является первым элементом за пределами диапазона, поэтому он не включается. Сконцентрировавшись на заданном участке (в нем содержатся элементы от 1 до 8 включительно), мы понимаем, что перед нами корректный диапазон, из которого удалены все значения 2.

Здесь вступает в дело функция erase: мы должны указать вектору, что все элементы между итераторами new_end и end больше к нему не относятся. Вектор легко с этим справится, поскольку может просто перевести конечный итератор в позицию, обозначенную new_end. Обратите внимание: итератор new_end является возвращаемым значением вызова std::remove, следовательно, можно просто им воспользоваться.

 

 Заметьте: вектор выполнил больше манипуляций, нежели просто передвинул внутренний указатель. Если бы вектор состоял из более сложных объектов, то ему пришлось бы вызвать деструкторы для всех удаляемых элементов.

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

Чтобы вектор занимал ровно столько памяти, сколько ему нужно, в конце работы мы вызываем метод shrink_to_fit. Во время этого вызова выделяется ровно необходимый объем памяти, все элементы перемещаются и освобождается более крупный фрагмент памяти, который уже не нужен.

В шаге 8 мы определили функцию-предикат и использовали ее вместе с функцией std::remove_if. Это работает, поскольку независимо от того, какой итератор вернет функция, его можно будет безопасно применить в функции вектора erase. Если мы не найдем нечетных элементов, то функция std::remove_if не выполнит никаких действий и вернет конечный итератор. Далее вызов наподобие v.erase(end, end); также ни к чему не приведет.

Дополнительная информация

Функция std::remove работает и для других контейнеров. При ее вызове для std::array обратите внимание, что массив не поддерживает вызов функции erase из второго шага, поскольку вы не можете изменять его размер автоматически. Несмотря на то что функция std::remove, по сути, лишь перемещает элементы и не удаляет их, она пригодна для структур данных наподобие массивов, которые не могут изменять размер. При работе с массивом можно переписать значения после конечного итератора некоторыми граничными значениями, например '' для строк.

Удаляем элементы из неотсортированного объекта класса std::vector за время O(1)

Удаление элементов из середины вектора занимает O(n) времени. При этом образовавшийся промежуток должен быть заполнен: все элементы, стоящие после него, перемещаются на одну позицию влево.

Такое перемещение с сохранением порядка может оказаться затратным по времени, если перемещаемые элементы сложны и/или велики и содержат много объектов. Если порядок сохранять не требуется, можно оптимизировать процесс, как показано в этом разделе.

Как это делается

В этом примере мы заполним экземпляр класса std::vector некими числами, а затем реализуем функцию быстрого удаления, которая удаляет любой элемент из вектора за время O(1).

1. Сначала включим необходимые заголовочные файлы:

#include <iostream>

#include <vector>

#include <algorithm>

2. Далее определим функцию main, где создадим вектор, заполненный числами:

int main()

{

  std::vector<int> v {123, 456, 789, 100, 200};

3. Очередной шаг заключается в том, чтобы