四重嵌套unordered_map怪兽的替代品吗? [英] Alternative for quad-nested unordered_map monstrosity?

问题描述

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

I've been trying out to figure an effective way to store and retrieve a number of objects. Let me explain what I'm trying to achieve, then list the options I've come up with (But am unhappy with).

以下内容在技术上可以满足我的需要，但是是明显的禁忌:

The following technically does what I need it to do, but is an obvious no-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保存组件.每个类型前面都有一个映射(Component的子类).这样做是为了在我检索它们时，可以完全安全地将它们动态地转换为它们的类型，知道TYPE哈希图仅包含其类型的指针，还允许使用count来快速检查某个ID是否存在. 接下来的地图按层存储它们，第一个地图按场景存储它们.在任何时候，将保留大约30-50个场景，每个场景包含大约6-10层，每个场景包含大约30-40种类型，每种类型包含1到500个对象.

The most inner map holds the Components based on their ID. The one before it has a map per type (Subclasses of Component). The latter is done so that when I retrieve them, I can dynamically cast them to their type with full safety knowing the TYPE hash map only contains pointers of their type, also allowing the use of count for quickly checking if something exists at a certain ID. The map following that stores them by layer, the first map stores them by scene. At any point, about 30-50 scenes will be held, which each contain about 6-10 layers which each contain about 30-40 types, which per type contains anywhere from 1 to 500 objects.

每个周期，我们将根据指针的类型遍历指针，一次迭代一层.场景变化很少(每2-3分钟一次).可以使用类型和ID的组合来访问组件.代码会定期检查在同一ID中还存在哪些其他Component类型. 场景，图层和类型通过其名称进行访问，名称存储为32位CRC哈希.速度至关重要. ID是由代码分配的数字，仅从0开始.每个场景中的ID都是唯一的.

Each cycle we'll be iterating over the pointers based on their type, one layer at a time. Scenes change rarely (Every 2-3 minutes). Components are accessed with a combination of Type and Id. Code routinely checks which other Component types are present at the same Id. Scenes, layers and types are access through their name, which is stored as a 32 bits CRC hash. Speed is crucial. IDs are numbers assigned by the code, simply going from 0 and up. IDs are unique within each scene.

毫无疑问，有一些疯狂的(惯用的)成语可以帮助我，但我从未听说过. 有人认识吗? 到目前为止，我没有提出任何备选方案，但是无论如何，我都会列出它们:

No doubt there's some crazy (read: common) idiom that helps me out and I have never heard about. Any one know one? So far none of the alternatives I've come up with are acceptable, but I'll list them regardless:

选项1:

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

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

Component holds which type, scene and layer it is from, whenever we iterate over all entries we ignore the ones not from the current scene or layer. Alternatively, store them in order so that you only have to iterate over a certain range. The vector holds the Components and when we need to access a component of a certain type we search through the vector. Not ideal as it would require many searches a cycle. Alternatively use an unordered_map in place of the vector.

选项2:

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

The same as the nested maps, but with vectors. A map converts Id to index inside the vector.

选项3:

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

(类型/图层/场景/ID)->组件* 只需将向量的索引存储在所有分量中即可.有一个unordered_map，它在主存储向量中包含索引向量.当我们检查两者之间的冲突时，ID和字符串散列都可以存在(不太可能).场景，图层和类型的名称必须唯一. ID返回该ID的组成部分的所有索引的向量，名称或类型返回包含该类型或场景的所有索引的向量.这些向量的所有迭代都让人感到骇俗.

(Type / Layer / Scene / Id) -> Component* Store all components simply with the index of the vector. Have an unordered_map which contains vectors of indexes in the main storage vector. Both IDs and string hashes can exist as we check for collision between the two (Unlikely). Names need to be unique for scenes, layers and types. IDs return a vector of all the indexes for components part of that ID, Name or types return vectors containing all indexes of that type or scene. Feels hackish, all those iterations of those vectors.

选项4:

Components获得一个"Component * next"指针，以遍历属于同一实体的组件.最后一个组件链接到第一个.组件再次获得类型和场景/图层成员.

Components gets a 'Component* next' pointer to iterate through components that belong to the same entity. Last component links to the first. Components once again get type and scene / layer members.

推荐答案

使用散列函数和均等函数指定您自己的密钥.

Specify you own key, with hashing function and equal function.

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

    unordered_map< cKey, Component*,
     hashkey, equalkey  >

一个人如何遍历一层这样的所有组件?

How would one iterate over all components of say, one layer?

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个组件的映射中的一层进行迭代.

You can find an implementation at https://gist.github.com/JamesBremner/d71b158b32e4dd8ffaf8cbe93cf3f180 which iterates over a layer in a map of 50,000 components in 250msecs.

这篇关于四重嵌套unordered_map怪兽的替代品吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！