Avoiding iterator invalidation using indices, maintaining clean interface

Question

I have created a MemoryManager<T> class which is basically a wrapper around two vectors of pointers that manage lifetime of heap-allocated objects.

One vector stores the "alive" objects, the other one stores the object that will be added on next MemoryManager<T>::refresh.

This design was chosen to avoid iterator invalidation when looping over the MemoryManager<T>, as adding a new object directly to the MemoryManager<T>::alive vector can invalidate existing iterators (if it grows in size).

template<typename T> struct MemoryManager {
    std::vector<std::unique_ptr<T>> alive;
    std::vector<T*> toAdd;

    T& create() { 
        auto r(new T); 
        toAdd.push_back(r); 
        return *r; 
    }

    T& refresh() { 
         // Use erase-remove idiom on dead objects
         eraseRemoveIf(alive, [](const std::unique_ptr<T>& p){ return p->alive; });

         // Add all "toAdd" objects and clear the "toAdd" vector
         for(auto i : toAdd) alive.emplace_back(i); 
         toAdd.clear(); 
    }  

    void kill(T& mItem)  { mItem.alive = false; }

    IteratorType begin() { return alive.begin(); }
    IteratorType end()   { return alive.end(); }
}

I use it in my game engine to store entities, and update every "alive" entity every frame:

void game() {
    MemoryManager<Entity> mm;

    while(gameLoop) {
        mm.refresh();
        for(auto e : mm) processEntity(e);
        auto& newEntity = mm.create();
        // do something with newEntity
    }
}

This has allowed me to constantly create/kill entities without having to worry about their lifetime too much.

---

However, I've recently come to the conclusion that using two std::vector is unnecessary. I could simply use a single vector and store an iterator to the "last alive object", adding the newly create objects immediately after the aforementioned iterator:

The idea, in my mind, works fine... but I cannot actually use a iterator type for end (as shown in the diagram), as it could get invalidated after the addition of some new elements to the vector. I've tested it, and this happens often, causing a crash.

The other solution I can think of is using an index instead of an iterator. This would solve the crashing, but I wouldn't be able to use the cool C++11 for(x : y) foreach loop because MemoryManager<T>::begin and MemoryManager<T>::end need to return an iterator.

Is there a way to achieve the current behavior with a single vector and still maintain a clear interface that can be used with C++11 for-each loops?

Answer 1

You can implement your own iterator class.

Something like the following may help.

template <typename T, typename... Ts>
class IndexIterator : public std::iterator<std::random_access_iterator_tag, T>
{
public:
    IndexIterator(std::vector<T, Ts...>& v, std::size_t index) : v(&v), index(index) {}

    // if needed.
    typename std::vector<T, Ts...>::iterator getRegularIterator() const { return v->begin() + index; }

    T& operator *() const { return v->at(index); }
    T* operator ->() const { return &v->at(index); }

    IndexIterator& operator ++() { ++index; return *this;}
    IndexIterator& operator ++(int) { IndexIterator old(*this); ++*this; return old;}
    IndexIterator& operator +=(std::ptrdiff_t offset) { index += offset; return *this;}
    IndexIterator operator +(std::ptrdiff_t offset) const { IndexIterator res (*this); res += offset; return res;}

    IndexIterator& operator --() { --index; return *this;}
    IndexIterator& operator --(int) { IndexIterator old(*this); --*this; return old;}
    IndexIterator& operator -=(std::ptrdiff_t offset) { index -= offset; return *this;}
    IndexIterator operator -(std::ptrdiff_t offset) const { IndexIterator res (*this); res -= offset; return res;}

    std::ptrdiff_t operator -(const IndexIterator& rhs) const { assert(v == rhs.v); return index - rhs.index; }

    bool operator == (const IndexIterator& rhs) const { assert(v == rhs.v); return index == rhs.index; }
    bool operator != (const IndexIterator& rhs) const { return !(*this == rhs); }

private:
    std::vector<T, Ts...>* v;
    std::size_t index;
};

template <typename T, typename... Ts>
IndexIterator<T, Ts...> IndexIteratorBegin(std::vector<T, Ts...>& v)
{
    return IndexIterator<T, Ts...>(v, 0);
}

template <typename T, typename... Ts>
IndexIterator<T, Ts...> IndexIteratorEnd(std::vector<T, Ts...>& v)
{
    return IndexIterator<T, Ts...>(v, v.size());
}