c++ - 四嵌套 unordered_map 怪物的替代方案？

Question

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

从技术上讲，以下是我需要它做的事情，但是明显的禁忌:

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 保存组件。它之前的每个类型都有一个映射(组件的子类)。后者是这样的，当我检索它们时，我可以完全安全地动态地将它们转换为它们的类型，因为我知道 TYPE HashMap 只包含它们类型的指针，还允许使用计数来快速检查某个 ID 是否存在某些东西. 接下来的 map 按层存储它们，第一个 map 按场景存储它们。在任何时候，将举行大约 30-50 个场景，每个场景包含大约 6-10 个层，每个层包含大约 30-40 个类型，每个类型包含 1 到 500 个对象。

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

毫无疑问，有一些疯狂的(阅读:常见的)习语可以帮助我摆脱困境，但我从未听说过。 有人认识吗？ 到目前为止，我提出的所有替代方案都 Not Acceptable ，但无论如何我都会列出它们:

选项 1:

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

Component 保存它来自哪个类型、场景和图层，每当我们遍历所有条目时，我们都会忽略那些不是来自当前场景或图层的条目。或者，按顺序存储它们，这样您只需在一定范围内迭代。 vector 包含组件，当我们需要访问某种类型的组件时，我们会在 vector 中进行搜索。不理想，因为它需要一个周期进行多次搜索。或者使用 unordered_map 代替 vector 。

选项 2:

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

选项 3:

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

(类型/图层/场景/ID)->组件* 使用 vector 的索引简单地存储所有组件。有一个 unordered_map，其中包含主存储 vector 中的索引 vector 。当我们检查两者之间的冲突时，ID 和字符串哈希都可以存在(不太可能)。场景、图层和类型的名称必须是唯一的。 ID 返回该 ID 的组件部分的所有索引的 vector ，名称或类型返回包含该类型或场景的所有索引的 vector 。这些 vector 的所有这些迭代感觉很老套。

选项 4:

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

Answer 1

指定您自己的 key ，具有散列函数和相等函数。

   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 毫秒内迭代包含 50,000 个组件的 map 中的一个图层。