значения. Для этого сначала определим функцию-предикат, которая принимает число в качестве параметра и возвращает значение
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
, по сути, лишь перемещает элементы и не удаляет их, она пригодна для структур данных наподобие массивов, которые не могут изменять размер. При работе с массивом можно переписать значения после конечного итератора некоторыми граничными значениями, например '\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
, но на сей раз применим перегруженную версию предыдущей, которая принимает в качестве параметров итераторы. Данная функция также не реализована.
qu
ick_remove_at(v, std::find(std::begin(v), std::end(v), 123));
for (int i : v) {
std::cout << i << ", ";
}
std::cout << '\n';
}
5. Нам осталось реализовать только две функции
quick_remove_at
. Этим и займемся. (Обратите внимание: они должны быть как минимум объявлены до функции main. Так что просто определим их там.)Обе функции принимают ссылку на вектор, содержащий значения некоторого типа (в нашем случае это
int
), так что мы не решаем за пользователя, какой тип вектора он задействует. Для нас это будет вектор, содержащий значения типа