Avoiding iterator invalidation using indices, maintaining clean interface

c++, c++11, invalidation, iterator, vector

Solution

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());
}

Problem

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?

Original source