避免使用索引的迭代器无效，保持干净的接口 [英] Avoiding iterator invalidation using indices, maintaining clean interface

问题描述

我创建了一个 MemoryManager< T> 类，它基本上是两个指针向量的包装器，它们管理堆分配对象的生命周期。

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

一个向量存储活动对象，另一个向量存储将在下一个添加的对象 MemoryManager< T& / code>。

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

选择此设计是为了避免迭代器在 MemoryManager< T> 直接到 MemoryManager< T> :: alive 向量可以使现有迭代器无效（如果它的大小增加）。

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.

但是，我最近得出的结论是使用两个 std :: vector 是不必要的。我可以简单地使用一个单一的向量并存储一个迭代器到最后一个活动对象，添加新创建的对象后立即上述迭代器：

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:

这个想法，在我心中，工作正常...但我实际上不能使用 end （如图所示）的迭代器类型，因为它可能会在添加一些新元素后失效向量。我测试了它，这经常发生，导致崩溃。

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.

我可以想到的另一个解决方案是使用索引而不是迭代器。这将解决崩溃，但我不能使用酷C ++ 11 for（x：y） foreach循环，因为 MemoryManager< ; T> :: begin 和 MemoryManager< T> :: end 需要返回迭代器。

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.

有没有办法用单个向量实现当前行为，并仍然保持一个清晰的接口，可以用于C ++ 11 for-each循环？

推荐答案

您可以实现自己的迭代器类。

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

这篇关于避免使用索引的迭代器无效，保持干净的接口的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！