c++ - 了解缓存友好、面向数据的对象和句柄

Question

using namespace std;

考虑一个传统的OOP 方法来进行实体/对象管理:

struct Entity { bool alive{true}; }

struct Manager {        
    vector<unique_ptr<Entity>> entities; // Non cache-friendly

    void update() {
        // erase-remove_if idiom: remove all !alive entities
        entities.erase(remove_if(begin(entities), end(entities),
            [](const unique_ptr<Entity>& e){ return !e->alive; }));
    }
};

struct UserObject {
    // Even if Manager::entities contents are re-ordered
    // this reference is still valid (if the entity was not deleted)
    Entity& entity;
};

不过，我想尝试一种面向数据的方法:不是动态分配 Entity 实例，而是将它们存储在缓存中线性内存。

struct Manager {
    vector<Entity> entities; // Cache-friendly
    void update() { /* erase-remove_if !alive entities */ }
};

struct UserObject {
    // This reference may unexpectedly become invalid
    Entity& entity;
};

看起来不错。但是...如果 std::vector 需要重新分配其内部数组，所有对实体的引用都将失效。

解决方案是使用句柄类。

struct Entity { bool alive{true}; };
struct EntityHandle { int index; };

struct Manager {
    vector<Entity> entities; // Cache-friendly      
    void update() { /* erase-remove_if !alive entities */ }
    Entity& getEntity(EntityHandle h) { return entities[h.index]; }
};

struct UserObject { EntityHandle entity; };

如果我只是在 vector 后面添加/删除实体，它似乎可以工作。我可以使用 getEntity 方法来检索我想要的实体。

但是如果我从 vector 中间移除一个 Entity 会怎样？所有 EntityHandle 实例现在都将保存不正确的索引，因为所有内容都已移动。示例:

---

句柄指向索引:2

---

实体 A 在 update() 期间被移除

现在句柄指向错误的实体。

---

这个问题通常是如何处理的？

句柄索引是否更新？

死实体是否被占位符替换？

---

澄清一下:

This和 this是我所说的缓存友好设计的例子。

此外，Artemis 等组件系统声称采用线性缓存友好型设计，它们使用类似于句柄的解决方案。他们如何处理我在这个问题中描述的问题？

Answer 1

insomniac 做了一个很棒的 powerpoint，他们的解决方案是这样的

template<typename T, size_t SIZE>
class ResourceManager
{
    T data[SIZE];
    int indices[SIZE];
    size_t back;

    ResourceManager() : back(0)
    {
        for(size_t i=0; i<SIZE; i++)
            indices[i] = static_cast<int>(i);
    }

    int Reserve()
    { return indices[back++]; }

    void Release(int handle)
    {
        for(size_t i=0; i<back; i++)
        {
            if(indices[i] == handle)
            {
                back--;
                std::swap(indices[i], indices[back]);
                return;
            }
        }
    }

    T GetData(size_t handle)
    { return data[handle]; }
};

我希望这个例子能清楚地说明这个想法。