使用索引避免迭代器失效,保持干净的接口

Question

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

一个向量存储"活动"对象,另一个向量存储将在下一个添加的对象MemoryManager<T>::refresh.

选择此设计是为了避免在循环时使用迭代器失效MemoryManager<T>,因为直接向MemoryManager<T>::alive向量添加新对象会使现有迭代器无效(如果它的大小增大).

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

我在我的游戏引擎中使用它来存储实体,并且每帧更新每个"活着"实体:

void game() {
    MemoryManager<Entity> mm;

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

这使我能够不断地创建/杀死实体,而不必担心他们的生命太多.

---

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

在我看来,这个想法运行良好......但我实际上不能使用迭代器类型end(如图所示),因为在向量中添加一些新元素后它可能会失效.我测试了它,这经常发生,导致崩溃.

我能想到的另一个解决方案是使用索引而不是迭代器.这将解决崩溃,但我无法使用酷C++ 11 for(x : y)foreach循环,因为MemoryManager<T>::begin并且MemoryManager<T>::end需要返回迭代器.

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

Answer 1

获得稳定迭代器(和引用)的最简单方法之一就是使用std::list<T>.除非你需要T成为多态基类的指针,否则最好使用std::list<T>,而不是std::list<std::unique_ptr<T>>.

另一方面,如果你Entity是一个多态基础,那么考虑使用std::vector<std::unique_ptr<T>>.虽然您不能依赖于仍然有效的迭代器,但您可以依赖指针和引用来Entity保持有效std::vector<std::unique_ptr<T>>.

在您的game()示例中,您永远不会利用稳定的迭代器或指针.您可以轻松(并且更简单地)做:

void game() {
    std::vector<Entity> mm;

    while(gameLoop) {
        mm.erase(std::remove_if(mm.begin(), mm.end(), [](const Entity& e)
                                                      { return e.alive; }),
                                                      mm.end());
        for(auto e : mm) processEntity(e);
        mm.push_back(create());
        auto& newEntity = mm.back();
        // do something with newEntity
    }
}

在processEntity循环期间,无法使迭代器无效.如果你这样做了,最好不要使用基于范围的for,因为结束迭代器只在循环开始时被评估一次.

但是如果你真的需要稳定的迭代器/引用,那么替换std::list<Entity>就很容易了.我会改用erase/remove使用list的成员remove_if.它会更有效率.

如果你这样做,并且性能测试(而不是猜测)表明你的性能已经超过现有MemoryManager,你可以list通过使用"堆栈分配器" 进行优化,例如这里演示的那个:

http://howardhinnant.github.io/stack_alloc.html

这允许您预分配空间(可以在堆栈上,可以在堆上),并让您的容器从中分配.在预先分配的空间耗尽之前,这将是高性能和缓存友好的.而且你仍然有你的迭代器/指针/参考稳定性.

综上所述:

1. 找出/告诉我们是否unique_ptr<Entity>真的有必要因为Entity是基类.身高container<Entity>超过container<unique_ptr<Entity>>.

2. 你真的需要迭代器/指针/参考稳定性吗？您的示例代码没有.如果您实际上并不需要它,请不要付钱.使用vector<Entity>(或vector<unique_ptr<Entity>>如果必须).

3. 如果你真的需要container<unique_ptr<Entity>>,你可以在牺牲迭代器稳定性的同时逃脱指针/参考稳定性吗？如果是,那vector<unique_ptr<Entity>>就是要走的路.

4. 如果你确实需要迭代器稳定性,强烈考虑使用std::list.

5. 如果您std::list通过测试使用和发现它存在性能问题,请使用符合您需求的分配器对其进行优化.

6. 如果以上所有方法都失败了,那么就开始设计自己的数据结构.如果你做到这一点,要知道这是最困难的路线,一切都需要通过正确性和性能测试来备份.

Answer 2

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

像下面这样的东西可能会有所帮助.

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