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

Текущий раздел посвящен вопросу удаления элементов из середины объекта вектора. Если элемент исчезает из вектора и при этом он находился между другими элементами, то все элементы, стоящие справа от него, должны сместиться на одну позицию влево (в результате время выполнения операции составляет O(n)). Многие начинающие программисты будут решать задачу с помощью цикла, ведь это так просто. К сожалению, при этом они, скорее всего, упустят потенциальные возможности оптимизации. В конечном счете цикл, написанный вручную, не быстрее и не читабельнее, чем способ решения задачи средствами STL, которые мы еще рассмотрим далее.

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

В этом примере мы наполним объект класса std::vector целыми числами, а затем выбросим из него конкретные элементы. При этом мы воспользуемся корректным способом удаления нескольких элементов из вектора.

1. Конечно, прежде чем начинать что-то делать, включим некоторые заголовочные файлы:

#include

#include

#include

2. Далее мы объявляем, что будем использовать пространство имен std, чтобы поменьше печатать:

using namespace std;

3. Теперь создадим вектор, состоящий из целых чисел, и заполним его некими числами:

int main()

{

  vector v {1, 2, 3, 2, 5, 2, 6, 2, 4, 8};

4. Удалим некоторые элементы. Что именно? В нашем примере много значений 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, присутствовавшие в оригинальном массиве, встречаются дважды. Что происходит?