C++17 STL Стандартная библиотека шаблонов - Яцек Галовиц
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 << ", ";
}
std::cout << 'n';
}
5. Нам осталось реализовать только две функции quick_remove_at. Этим и займемся. (Обратите внимание: они должны быть как минимум объявлены до функции main. Так что просто определим их там.)
Обе функции принимают ссылку на вектор, содержащий значения некоторого типа (в нашем случае это int), так что мы не решаем за пользователя, какой тип вектора он задействует. Для нас это будет вектор, содержащий значения типа T. Первая функция quick_remove_at принимает значения индекса, которые представляют собой числа, вследствие чего ее интерфейс выглядит следующим образом:
template <typename T>
void quick_remove_at(std::vector<T> &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<T>. Получить такой обобщенный тип несложно, поскольку для контейнеров STL уже определены подобные типы.
template <typename T>
void quick_remove_at(std::vector<T> &v,
typename std::vector<T>::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();
По логике, мы меняем местами выбранный и последний элементы. Но в коде мы не делаем этого, а лишь перемещаем последний элемент на место выбранного. Почему? Если бы мы действительно меняли местами элементы, нам пришлось бы сохранить выбранный элемент во временной переменной, переместить последний элемент на место выбранного, а затем сохранить временное значение в последней позиции. Это выглядит бессмысленно, поскольку мы все равно будем удалять последний элемент.
Ладно, значит, менять элементы местами бесполезно, и односторонняя перезапись нам больше подходит. Убедившись в этом, мы можем решить, что такое действие можно выполнить просто с помощью операции *it = v.back();, верно? Да, совершенно верно. Но представьте хранение на каждой позиции очень больших строк или даже другого вектора или ассоциативного массива — в такой ситуации эта небольшая операция присваивания приведет к очень затратной операции копирования. Вызов std::move, вставленный посередине (между = и v.back()), ускоряет выполнение кода. В случае со строками элемент вектора указывает на большую строку в куче. Нам не нужно ее копировать. Вместо этого при перемещении строки адрес исходной строки меняется на адрес места назначения. Исходный элемент остается прежним, но сам по себе он бесполезен, что нас устраивает, поскольку мы все равно его удаляем.
Получаем доступ к экземплярам класса std::vector быстрым или безопасным способом
Контейнер std::vector, возможно, является наиболее широко используемым контейнером STL, поскольку хранит данные аналогично массивам, но работать с ним гораздо удобнее. Однако неверное обращение к элементам вектора может быть опасным. Если вектор содержит 100 элементов, а наш код пытается получить доступ к элементу с индексом 123, то это, очевидно, плохо. Такая программа в лучшем случае даст сбой, поскольку подобное поведение явно указывает на ошибку в коде! Если программа не дает сбой, то мы наверняка заметим ее странное поведение, что куда хуже, чем аварийно завершившая программа. Опытный программист может добавить проверки перед непосредственным обращением к элементу вектора по индексу. Такие проверки не повышают читабельность кода, и многие разработчики не знают, что контейнер std::vector уже поддерживает подобные встроенные проверки!
Как это делается
В этом примере мы попытаемся двумя способами
