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

  std::cout << '\n';

}

5. Нам осталось реализовать только две функции quick_remove_at. Этим и займемся. (Обратите внимание: они должны быть как минимум объявлены до функции main. Так что просто определим их там.)

Обе функции принимают ссылку на вектор, содержащий значения некоторого типа (в нашем случае это int), так что мы не решаем за пользователя, какой тип вектора он задействует. Для нас это будет вектор, содержащий значения типа T. Первая функция quick_remove_at принимает значения индекса, которые представляют собой числа, вследствие чего ее интерфейс выглядит следующим образом:

template

void quick_remove_at(std::vector &v, std::size_t idx)

{

6. Сейчас перейдем к самому главному — быстрому удалению элементов. При этом нужно постараться не перемещать слишком большого количества оставшихся элементов. Во-первых, просто возьмем значение последнего элемента вектора и запишем его на место элемента, который должен быть удален. Во-вторых, отбросим последний элемент. Вот и все, только два шага. Мы добавим в этот код небольшую проверку безопасности. Если значение индекса очевидным образом выходит за пределы вектора, мы не станем ничего делать. В противном случае код будет давать сбой для пустого вектора.

  if (idx < v.size()) {

    v[idx] = std::move(v.back());

    v.pop_back();

  }

}

7. Другая реализация метода quick_remove_at работает аналогично. Вместо того чтобы принимать численный индекс, она принимает итератор для вектора std::vector. Получить такой обобщенный тип несложно, поскольку для контейнеров STL уже определены подобные типы.

template

void quick_remove_at(std::vector &v,

                     typename std::vector::iterator it)

{

8. Теперь получим доступ к значению, на которое указывает итератор. Как и в другой функции, перепишем его с помощью последнего элемента вектора. Поскольку мы работаем не с числовым индексом, а с итератором, следует выполнять более аккуратную проверку на безопасность. Если итератор указывает на специальную конечную позицию, то разыменовывать его нельзя.

  if (it != std::end(v)) {

9. Внутри этого блока if делаем то же самое, что и раньше: переписываем значение удаляемого элемента с последней позиции, а затем отбрасываем последний элемент вектора:

    *it = std::move(v.back());

    v.pop_back();

  }

}

10. Вот и все. Компиляция и запуск программы дадут следующий результат:

$ ./main

123, 456, 200, 100,

100, 456, 200,

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

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

Оба шага в коде примера выглядят следующим образом:

v.at(idx) = std::move(v.back());

v.pop_back();

В версии с итераторами шаги выглядят примерно так же:

*it = std::move(v.back());

v.pop_back();

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