Редкая задача в программировании решается без контейнеров. В 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
выполняет два шага:
-
Перемещает элементы вектора, которые следуют за удаляемой частью, на место удаляемых элементов.
-
Удаляет последние элементы, освободившиеся после перемещения.
# Исходный вектор #
[ 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