vector of unique_ptr deleting?

Question

I have an issue with a segfault that I can not figure out. It's from an EntityManager for a small game engine I'm working on. I can add the Ship Entity, and the Ship can add 1 Bullet Entity, but it segfaults if I try to add more than 1 Bullet. I've been trying to figgure this out for the past day now. Below is a small excerpt from the actual code.

#include <vector>
#include <memory>

struct EntityManager;
struct Entity {
    Entity(EntityManager* manager) : manager(manager) { }
    virtual ~Entity() { }
    virtual void update() = 0;

    EntityManager* manager;
};
struct EntityManager {
    void update() {
        for (auto& entity : entities) {
            entity->update();
        }
    }
    void add(Entity* e) {
        entities.emplace_back(e);
    }
    std::vector<std::unique_ptr<Entity>> entities;
};
struct Bullet : public Entity {
    Bullet(EntityManager* manager) : Entity(manager) { printf("Bullet ctor\n"); }

    virtual void update() override { }
};
struct Ship : public Entity {
    Ship(EntityManager* manager) : Entity(manager) { }

    virtual void update() override {
        printf("Adding Bullet\n");
        manager->add(new Bullet(manager));
    }
};
int main() {
    EntityManager manager;
    manager.add(new Ship(&manager));

    int loops{0};
    while (loops < 100) {
        manager.update();
        loops++;
        printf("Completed Loop #%d\n", loops);
    }
    return 0;
}

In the actual code, everything is in their own .h/.cpp files, and classes instead of structs, but the issue is the same. The output is `Adding Bullet // Bullet ctor // Completed Loop #1 // Adding Bullet // Bullet ctor // Signal: SIGSEGV (Segmentation fault)

The segfault happens in the EntityManager::update() on the entity->update(); line.

Answer 1

The problem is that this loop modifies the vector:

    for (auto& entity : entities) {
        entity->update();
    }

You are busy iterating through it when you modify the vector to add a new element, which invalidates the iterators being used to traverse the container.

The range-based for loop is expanded by the compiler to:

auto begin = entities.begin(), end = entities.end();
for (; begin != end; ++begin)
  begin->update();

The call to begin->update() adds a new element to the vector, which invalidates all iterators into the container, so the ++begin is undefined behaviour. In practical terms, begin no longer points into the vector (because it has reallocated and freed the old memory that begin pointed to) so the next begin->update() call dereferences an invalid iterator, accessing freed memory and seg-faulting.

To do it safely you probably want to use indices not iterators:

for (size_t i = 0, size = entities.size(); i != size; ++i)
  entities[i].update();

This captures the size at the start of the loop and so only iterates up to the last element that exists when the loop starts, so new elements added to the end will not get visited.

This still works when the vector is modified because you don't store iterators or pointers to elements, only an index. As long as you don't remove elements from the vector the index is still valid even after inserting new elements.