替代四巢式unordered_map怪物？

Question

我一直在尝试寻找一种有效的方法来存储和检索多个对象。让我解释一下我想要达到的目标，然后列出我想出的选择(但我不满意)。

从技术上讲，下面是我需要它做的事情，但它是一个明显的-no：

std::unordered_map<uint32_t, std::unordered_map<uint32_t, std::unordered_map<uint32_t, std::unordered_map<uint32_t, Component*>>>>
//Scene -> Layer -> Type -> Id -> Component*         

最内部的映射基于它们的ID来保存组件。在它之前的映射是每个类型的映射(组件的子类)。后一种方法是在检索它们时，我可以在完全安全的情况下动态地将它们转换为它们的类型，因为类型哈希映射只包含它们类型的指针，还允许使用count来快速检查某个ID是否存在某种东西。在任何时候，将举行大约30-50个场景，每个场景包含大约6-10个层，每个层包含30-40个类型，每种类型包含1到500个对象。

每一个周期，我们将根据指针的类型，一层一层地迭代指针。场景很少改变(每2-3分钟一次)。使用Type和Id组合访问组件。代码通常检查同一Id中存在哪些其他组件类型。场景、层和类型通过其名称进行访问，该名称存储为32位CRC散列。速度是至关重要的。ID是由代码分配的数字，简单地从0到更高。ID在每个场景中都是唯一的。

毫无疑问，有一些疯狂的(阅读:常见的)成语帮助我，我从来没有听说过。任何人都知道吗?到目前为止，我想出的任何替代方案都是可以接受的，但我会列出它们，不管怎么说：

选项1:

std::unordered_map<uint32_t, std::vector<Component*>>
ID -> Component*

组件保存它来自哪个类型、场景和层，每当我们迭代所有条目时，我们忽略那些不是来自当前场景或层的条目。或者，按照顺序存储它们，这样您只需要在某个范围内进行迭代。向量保存组件，当我们需要访问某个类型的组件时，我们搜索该向量。这并不理想，因为它需要一个周期的许多搜索。或者使用unordered_map代替向量。

备选方案2:

与嵌套映射相同，但带有向量。映射将Id转换为向量内的索引。

选项3:

std::vector<Component*>
std::unordered_map<uint32_t, std::vector<int>>

(类型/层/场景/ Id) ->组件*用向量的索引存储所有组件。在主存储向量中有一个包含索引向量的unordered_map。当我们检查两者之间的冲突时，ID和字符串散列都可以存在(不太可能)。对于场景、层和类型，名称必须是唯一的。ID返回该ID的组件部分的所有索引的向量，名称或类型返回包含该类型或场景的所有索引的向量。感觉很讨厌，所有这些向量的迭代。

备选方案4:

组件获取一个'Component* next‘指针来迭代属于同一个实体的组件。最后一个组件链接到第一个组件。组件再次获得类型和场景/层成员。

Answer 1

使用散列函数和等号函数指定您自己的键。

   class cKey
    {
    public:
      size_t scene;
      size_t layer;
      size_t type;
      size_t id;
    };

    unordered_map< cKey, Component*,
     hashkey, equalkey  >

一个人将如何迭代所有组件，比如说，一个层？

cKey key;
key.scene = S;
key.layer = L;

for( key.type = 0; key.type< LastType; key.type ++ ) {
for( key.id = 0; key.id < LastID; key.id++ ) {
   Component * pC = the_map.find( key ).second;
   ...

您可以在https://gist.github.com/JamesBremner/d71b158b32e4dd8ffaf8cbe93cf3f180中找到一个实现，它在由250个组件组成的映射中的一个层上迭代。

Answer 2

我建议把这些地图划分成多幅地图：

std::unordered_map<std::uint32_t, std::vector<std::uint32_t>> layer_by_scene;
std::unordered_map<std::uint32_t, std::vector<std::uint32_t>> entity_by_layer;
std::unordered_map<uint32_t, std::vector<std::uint32_t>> component_by_entity;
std::unordered_map<uint32_t, Component*> components;

但是，请注意，在通常的实体-组件-系统中，您将试图避免指针追逐和跳跃在基于节点的容器中。