std::vector - optimization during game loop

Question

I'm simply having some questions regarding optimization of my design.

All the game objects in the game inherit from the base class

class Environment;

The game iterates over a vector and updates and renders each object:

for (auto& env : this->listEnvironment)
{
    if (env->GetIsMarkedForDeletion()==false)
    {
        env->Update();
        env->Render();
    }
}

as long as the object is not marked for deletion.

So this is what I'm wondering, is it better to create a separate loop and delete all the objects from the vector that are marked for deletion, simply leave them be in the vector and don't render them or should I do it in the same loop as the rendering?

From what I understand the performance decreases a lot if i resize the vector during the loop but I might have misunderstood this.

Answer 1

Here's a method that gives you almost zero overhead in keeping your environment list clean:

edit 2: probably as efficient as it gets. Thanks for the inspiration in the comments:

struct Environment {
    virtual bool GetIsMarkedForDeletion() const;
    virtual void Render() const;
    virtual void Update();
};

struct World {

    using environment_container = std::vector<std::unique_ptr<Environment>>;
    environment_container listEnvironment;

    static bool is_removable(const environment_container::value_type& ptr)
    {
        return ptr->GetIsMarkedForDeletion();
    }

    void do_update_and_render()
    {
        listEnvironment.erase(std::remove_if(begin(listEnvironment),
                                        end(listEnvironment),
                                        is_removable),
                              end(listEnvironment));

        for (auto& env : this->listEnvironment)
        {
                env->Update();
                env->Render();
        }
    }
};

edit: in response to AlchemicalApples' concern over memory fragmentation, version 2 is offered, which does not deallocate memory unless the environment grows in size beyond it's high watermark:

struct Environment {
    virtual bool GetIsMarkedForDeletion() const;
    virtual void Render() const;
    virtual void Update();
};

struct World {

    using environment_container = std::vector<std::unique_ptr<Environment>>;
    environment_container listEnvironment;
    environment_container survivingEnvironment; // = {}

    void do_update_and_render()
    {
        if (survivingEnvironment.capacity() < listEnvironment.size()) {
            survivingEnvironment.reserve(listEnvironment.size());
        }
        for (auto& env : this->listEnvironment)
        {
            if (env->GetIsMarkedForDeletion()==false)
            {
                env->Update();
                env->Render();
                survivingEnvironment.push_back(move(env));
            }
        }
        survivingEnvironment.swap(listEnvironment);
        survivingEnvironment.clear();   // note-does not clear memory so fragmentation is prevented
    }
};

the original is here for comparison:

struct Environment {
    virtual bool GetIsMarkedForDeletion() const;
    virtual void Render() const;
    virtual void Update();
};

struct World {

    using environment_container = std::vector<std::unique_ptr<Environment>>;
    environment_container listEnvironment;

    void do_update_and_render()
    {
        environment_container new_objects;
        new_objects.reserve(listEnvironment.size());
        for (auto& env : this->listEnvironment)
        {
            if (env->GetIsMarkedForDeletion()==false)
            {
                env->Update();
                env->Render();
                new_objects.push_back(move(env));
            }
        }
        swap(new_objects, listEnvironment);
    }
};

Version doing the update in-place, without allocating a potentially large new vector:

void do_update_and_render_in_place()
{
    auto cursor = this->listEnvironment.begin();
    auto sentry = this->listEnvironment.end();
    while(sentry != cursor)
    {
        auto &element = **cursor;
        if(element.GetIsMarkedForDeletion()) { break; }
        element.Update();
        element.Render();
        ++cursor;
    }
    if(sentry == cursor) { return; }
    auto trailing = cursor; // beginning of deleted elements
    ++cursor;
    for(; sentry != cursor; ++cursor) {
        auto &element = **cursor;
        if(false == element.GetIsMarkedForDeletion()) { continue; }
        element.Update();
        element.Render();
        swap(*cursor, *trailing);
        ++trailing;
    }
    this->listEnvironment.erase(trailing, sentry);
}