c++ - 使用索引避免迭代器失效，保持干净的界面

Question

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

一个 vector 存储“活着的”对象，另一个存储将在下一次添加的对象 MemoryManager<T>::refresh .

选择此设计是为了避免在遍历 MemoryManager<T> 时迭代器失效, 将新对象直接添加到 MemoryManager<T>::alive vector 可以使现有的迭代器无效(如果它的大小增加)。

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是不必要的。我可以简单地使用单个 vector 并将迭代器存储到“最后一个事件对象”，在上述迭代器之后立即添加新创建的对象:

在我看来，这个想法工作得很好......但我实际上不能为 end 使用迭代器类型(如图所示)，因为在向 vector 添加一些新元素后它可能会失效。我已经测试过了，这种情况经常发生，导致崩溃。

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

有没有一种方法可以用单个 vector 实现当前的行为，同时仍然保持一个清晰的接口(interface)，可以与 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 期间循环，没有办法使迭代器无效。如果这样做，最好不要使用 range-based-for，因为结束迭代器仅在循环开始时计算一次。

但是如果你真的需要稳定的迭代器/引用，用 std::list<Entity> 代替会很容易。我会改变 erase/remove使用 list的成员(member)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. 如果以上都失败了，然后开始设计您自己的数据结构。如果你走到这一步，要知道这是最困难的路线，一切都需要通过正确性和性能测试来支持。