std::vector::erase. Что-то здесь не так

Редкая задача в программировании решается без контейнеров. В C++ наиболее часто используемый контейнер — std::vector (возможно кто-то не согласится и скажет: «Зачем std::vector, когда есть boost», но это дела не меняет).

При работе с std::vector часто возникает задача — удалить из него элемент (или несколько элементов). На помощь приходит метод erase. И это работает! Но иногда мы можем столкнуться с ситуацией, когда что-то идёт не так.

Что же может пойти не так?

Рассмотрим небольшой пример. Исходный код лежит в репозитории.

С чего начиналось

Есть класс, который в деструкторе производит некоторую очистку (например удаляет запись о себе из базы данных).

class Object { public:     explicit Object(int id);     ~Object();  private:     int m_id;      template      friend T &operator<<(T &stream, const Object &object) {         stream << object.m_id;         return stream;     } };

#include "Object.hpp" #include <iostream>  Object::Object(int id)     : m_id(id) {     std::cout << "Create: " << m_id << std::endl; }  Object::~Object() {     std::cout << "Delete: " << m_id << std::endl; }

При создании и удалении объекта выводим отладочную информацию, для понимания что где вызывается.

Создадим тестовую программу, в которой создадим std::vector объектов нашего класса, удалим один элемент и посмотрим на результат.

#include <iostream> #include <vector> #include "Object.hpp"  using Objects = std::vector;  void print(const Objects &objects) {     std::cout << "Objects: ";     for (const auto &object : objects) {         std::cout << object << " ";     }     std::cout << std::endl; }  int main() {     constexpr int SIZE = 6;      Objects objects;     objects.reserve(SIZE);     for (int i = 0; i < SIZE; ++i) {         objects.emplace_back(i);     }      print(objects);      std::cout << "~~~ EraseBegin ~~~" << std::endl;     objects.erase(objects.begin() + 3);     std::cout << "~~~ EraseEnd ~~~" << std::endl;      print(objects);      return 0; }

Соберём этот пример. Запустим и посмотрим вывод.

Create: 0 Create: 1 Create: 2 Create: 3 Create: 4 Create: 5 Objects: 0 1 2 3 4 5 ~~~ EraseBegin ~~~ Delete: 5 ~~~ EraseEnd ~~~ Objects: 0 1 2 4 5 Delete: 0 Delete: 1 Delete: 2 Delete: 4 Delete: 5

Что мы видим?

При попытке удалить элемент 3 вызовом erase удаляется элемент 5.

Что-то напутали?

Нет. После вызова erase в контейнере действительно исчез элемент 3.

Что в итоге получается?

Элемент 3 не удаляется, а элемент 5 удаляется дважды.

Окунемся в метод erase

Что же делает метод erase на самом деле?

Метод erase для std::vector выполняет два шага:

1. Перемещает элементы вектора, которые следуют за удаляемой частью, на место удаляемых элементов.

2. Удаляет последние элементы, освободившиеся после перемещения.

# Исходный вектор # [   0   ][   1   ][   2   ][   3   ][   4   ][   5   ]  # Шаг 1 # [   0   ][   1   ][   2   ][   3   ][   4   ][   5   ]                                <- move <-  [   0   ][   1   ][   2   ][   4   ][   4   ][   5   ]                                         <- move <-  [   0   ][   1   ][   2   ][   4   ][   5   ][   5   ]  # Шаг 2 # [   0   ][   1   ][   2   ][   4   ][   5   ][   5   ]                                       resize(size - 1)  [   0   ][   1   ][   2   ][   4   ][   5   ]

Теперь понятно, почему у нас удаляется элемент 5 два раза. Но что же с этим делать?

Решение (одно из нескольких возможных)

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

Рассмотрим модификацию класса Object.

class Object { public:     explicit Object(int id);      Object(Object &other) = delete;     Object &operator=(Object &other) = delete;      Object(Object &&other);     Object &operator=(Object &&other);      ~Object();      void clear();  private:     int m_id;      template      friend T &operator<<(T &stream, const Object &object) {         stream << object.m_id;         return stream;     } };

#include "Object.hpp"  #include   constexpr int INVALID_ID = -1;  Object::Object(int id)     : m_id(id) {     std::cout << "Create: " << m_id << std::endl; }  Object::Object(Object &&other)     : m_id(other.m_id) {         other.m_id = INVALID_ID; }  Object &Object::operator=(Object &&other) {     clear();     m_id = other.m_id;     other.m_id = INVALID_ID;     return *this; }  Object::~Object() {     std::cout << "Destroy: " << m_id << std::endl;     clear(); }  void Object::clear() {     if (m_id != INVALID_ID) {         std::cout << "Delete: " << m_id << std::endl;     } }

Что мы видим?

Добавилась проверка на валидность идентификатора при очистке. Очистка вызывается в деструкторе и при перемещении.

Добавим дополнительное сообщение в деструктор, чтобы понимать, когда мы в него заходим.

Тестовая программа не изменилась.

Соберём, запустим и посмотрим вывод.

Create: 0 Create: 1 Create: 2 Create: 3 Create: 4 Create: 5 Objects: 0 1 2 3 4 5 ~~~ EraseBegin ~~~ Delete: 3 Destroy: -1 ~~~ EraseEnd ~~~ Objects: 0 1 2 4 5 Destroy: 0 Delete: 0 Destroy: 1 Delete: 1 Destroy: 2 Delete: 2 Destroy: 4 Delete: 4 Destroy: 5 Delete: 5

Как видим, при вызове erase происходит удаление нужного элемента 3, а также вызывается деструктор с невалидным идентификатором (это освобождается место от перемещённого элемента 5).

Спасибо за внимание!