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();
По логике, мы меняем местами выбранный и последний элементы. Но в коде мы не делаем этого, а лишь перемещаем последний элемент на место выбранного. Почему? Если бы мы действительно меняли местами элементы, нам пришлось бы сохранить выбранный элемент во временной переменной, переместить последний элемент на место выбранного, а затем сохранить временное значение в последней позиции. Это выглядит бессмысленно, поскольку мы все равно будем удалять последний элемент.
Ладно, значит, менять элементы местами бесполезно, и односторонняя перезапись нам больше подходит. Убедившись в этом, мы можем решить, что такое действие можно выполнить просто с помощью операции
*it = v.back();
, верно? Да, совершенно верно. Но представьте хранение на каждой позиции очень больших строк или даже другого вектора или ассоциативного массива — в такой ситуации эта небольшая операция присваивания приведет к очень затратной операции копирования. Вызов std::move
, вставленный посередине (между =
и v.back()
), ускоряет выполнение кода. В случае со строками элемент вектора указывает на большую строку в куче. Нам не нужно ее копировать. Вместо этого при перемещении строки адрес исходной строки меняется на адрес места назначения. Исходный элемент остается прежним, но сам по себе он бесполезен, что нас устраивает, поскольку мы все равно его удаляем. Получаем доступ к экземплярам класса std::vector быстрым или безопасным способом
Контейнер
std::vector
, возможно, является наиболее широко используемым контейнером STL, поскольку хранит данные аналогично массивам, но работать с ним гораздо удобнее. Однако неверное обращение к элементам вектора может быть опасным. Если вектор содержит 100 элементов, а наш код пытается получить доступ к элементу с индексом 123, то это, очевидно, плохо. Такая программа в лучшем случае даст сбой, поскольку подобное поведение явно указывает на ошибку в коде! Если программа не дает сбой, то мы наверняка заметим ее странное поведение, что куда хуже, чем аварийно завершившая программа. Опытный программист может добавить проверки перед непосредственным обращением к элементу вектора по индексу. Такие проверки не повышают читабельность кода, и многие разработчики не знают, что контейнер std::vector
уже поддерживает подобные встроенные проверки!
Как это делается
В этом примере мы попытаемся двумя способами получить доступ к элементу контейнера
std::vector
, а затем рассмотрим, как можно применить их для написания более безопасных программ, не снижая читаемости кода.
1. Включим все необходимые заголовочные файлы и заполним вектор тысячей значений
123
, чтобы нам было с чем работать:
#include
#include
using namespace std;
int main()
{
const size_t container_size {1000};
vector v (container_size, 123);
2. Теперь обратимся к элементу, лежащему за пределами вектора, с помощью оператора
[]
:
cout << "Out of range element value: "
<< v[container_size + 10] << '\n';
3. Далее обратимся к элементу, лежащему за пределами вектора, с помощью функции
at
:
cout << "Out of range element value: "
<< v.at(container_size + 10) << '\n';
}
4. Запустим программу и посмотрим, что произойдет. Сообщение об ошибке характерно для GCC. Прочие компиляторы отправят другие, но аналогичные сообщения. Первая операция чтения будет выполнена успешно, но странным образом. Она не заставит программу дать сбой, но мы получим значение, отличное от
123
. Мы не можем увидеть результат второго обращения, поскольку оно намеренно сгенерировало сбой. Второй подход позволяет гораздо раньше выявить случайные выходы за границы контейнера.
Out of range element value: -726629391
terminate called after throwing an instance of 'std::out_of_range'
what(): array::at: n (which is 1010) >= _Nm (which is 1000)
Aborted (core dumped)
Как это работает
Контейнер
std::vector
предоставляет оператор []
и функцию at
, и они, по сути, делают одинаковую работу. Однако функция выполняет дополнительные проверки границ и генерирует исключение, если мы вышли за границы вектора. Такое свойство очень полезно в ситуациях вроде нашей, но работа программы при этом несколько замедляется.Оператор
[]
полезен при выполнении вычислений, для которых нужно очень быстро обращаться к проиндексированным элементам вектора. В любой другой ситуации функция at
помогает определять ошибки, при этом вы почти не теряете в производительности.
Широко практикуется использование функции