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

Рассмотрим только элементы, находящиеся в рамках диапазона от итератора 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, по сути, лишь перемещает элементы и не удаляет их, она пригодна для структур данных наподобие массивов, которые не могут изменять размер. При работе с массивом можно переписать значения после конечного итератора некоторыми граничными значениями, например '\0' для строк.

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

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

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

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

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

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

#include

#include

#include

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

int main()

{

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

3. Очередной шаг заключается в том, чтобы удалить значение с индексом 2 (отсчет начинается с нуля, следовательно, это будет третье число, 789). Функция, которую мы будем использовать для данной задачи, еще не реализована. Мы сделаем это спустя несколько шагов. Затем выведем содержимое вектора:

  quick_remove_at(v, 2);

  for (int i : v) {

    std::cout << i << ", ";

  }

  std::cout << '\n';

4. Теперь удалим еще один элемент. Это будет значение 123. Предположим, что не знаем его индекс. Как следствие, нужно вызвать функцию std::find, которая принимает диапазон (наш вектор) и значение, а затем ищет позицию значения. После этого она возвращает итератор, указывающий на значение 123. Мы используем его для той же функции quick_remove_at, но на сей раз применим перегруженную версию предыдущей, которая принимает в качестве параметров итераторы. Данная функция также не реализована.

  quick_remove_at(v, std::find(std::begin(v), std::end(v), 123));

  for (int i : v) {

    std::cout << i << ", ";

  }