C++17 STL Стандартная библиотека шаблонов - Яцек Галовиц
Шрифт:
Интервал:
Закладка:
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. Очередной шаг заключается в том, чтобы
