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

в 10:15, , рубрики: c++, erase, std, vector

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

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

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

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

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

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

Object.hpp
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;
    }
};

Object.cpp
#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 объектов нашего класса, удалим один элемент и посмотрим на результат.

main.cpp
#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.

Object.hpp
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;
    }
};

Object.cpp
#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).

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

Автор: makeyavelly

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js