C++: руководство по vector.erase

Контейнер std::vector  —  бесценный инструмент при работе с динамическими массивами на C++. Многие предпочитают его за гибкость и производительность.

Чтобы использовать всю мощь std::vector, нужно понимать нюансы его методов. Сегодня разберем один из важнейших: vector.erase().

vector.erase()

Функция erase()  —  член класса std::vector, ею удаляются элементы из контейнера. Имеется две ее разновидности:

1. Удаление одного элемента.
2. Удаление диапазона элементов.

Рассмотрим их подробнее.

Удаление одного элемента

Для удаления одного элемента вызывается erase() с итератором, которым указывается на удаляемый элемент:

std::vector<int> numbers = {1, 2, 3, 4, 5};
auto it = numbers.begin() + 2; // Указывается на третий элемент «3»
numbers.erase(it);
// числа теперь такие: {1, 2, 4, 5}

Эта операция проста, но эффективна. Все элементы после удаленного сдвигаются, и пробел заполняется, так что смежное размещение вектора в памяти сохраняется.

Удаление диапазона

Диапазон элементов удаляется двумя итераторами: одним указывается на первый удаляемый элемент, другим  —  на следующий за последним удаляемым элементом:

std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
auto first = numbers.begin() + 2; // Указывается на «3»
auto last = numbers.begin() + 7;  // Указывается на «8»
numbers.erase(first, last);
// числа теперь такие: {1, 2, 8, 9, 10}

Эта разновидность erase() невероятно эффективна при удалении смежных элементов.

Производительность

vector.erase()  —  это мощный инструмент, но разберем его нюансы производительности:

1. Временна́я сложность: удаление с конца вектора  —  O(1), с начала или середины  —  O(n), где n  —  количество элементов после удалённой позиции.
2. Управление памятью: с erase() память не освобождается. Емкость вектора остается неизменной, хотя его размер уменьшается.
3. Инвалидация итератора: при удалении элементов осуществляется инвалидация итератора и ссылок на элементы в точке удаления или после нее.

Оптимизация операций erase()

Эффективность применения vector.erase() максимизируется такими приемами:

1. Идиома Erase-Remove

При удалении элементов, соответствующих условию, erase() сочетается с std::remove() или std::remove_if():

std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
numbers.erase(std::remove_if(numbers.begin(), numbers.end(),
                             [](int n) { return n % 2 == 0; }),
              numbers.end());
// числа теперь такие: {1, 3, 5, 7, 9}

Эта идиома эффективнее, чем повторный вызов erase() для каждого элемента.

2. Удаление с конца

Чтобы минимизировать сдвиг элементов, они по возможности удаляются с конца вектора:

std::vector<int> numbers = {1, 2, 3, 4, 5};
numbers.erase(numbers.end() - 1);
// числа теперь такие: {1, 2, 3, 4}

3. Замена и удаление

В неупорядоченных данных удаляемый элемент заменяется последним, затем применяется pop_back():

std::vector<int> numbers = {1, 2, 3, 4, 5};
std::swap(numbers[2], numbers.back());
numbers.pop_back();
// числа теперь такие: {1, 2, 5, 4}

Этим приемом предотвращается сдвиг элементов, но порядок следования не сохраняется.

Типичные ошибки и как их избежать

1. Использование невалидных итераторов: прежде чем вызывать erase(), всегда проверяйте валидность итераторов. Невалидные итераторы чреваты неопределенным поведением.
2. Необновленные итераторы: после операции erase() обновляйте любые итераторы, которыми обходите вектор.
3. Удаление в цикле: будьте осторожны при удалении элементов во время итерации. Безопасный способ  —  обратный обход или использовать идиому erase-remove.

Реальные применения

vector.erase() приходится кстати во многих практических сценариях:

1. Очистка данных: удаление из набора данных отклоняющихся значений или недопустимых точек данных.
2. Разработка игр: эффективное удаление из игрового мира уничтоженных объектов.
3. Управление памятью: реализация пользовательских пулов памяти или кэшей объектов.
4. Обработка текста: удаление из строкового вектора конкретных символов или слов.

Заключение

Освоение vector.erase()  —  важный шаг к совершенствованию навыков работы с контейнерами C++.

С пониманием его поведения, нюансов производительности и рекомендаций пишется более эффективный, сопровождаемый код. Ключ к эффективному использованию erase()  —  выбор правильного подхода для конкретного сценария и осознание его влияния на структуру вектора и итераторы.

Читайте также:

• C++: руководство по считыванию CSV-файлов
• C++: практическое руководство по priority_queue
• C++: подробное руководство по std::accumulate

Читайте нас в Telegram, VK и Дзен

---

Перевод статьи ryan: C++ vector.erase (How to Guide)