Альтернатива для вложенного четырехугольника unordered_map monstrosity? - PullRequest
Новая
       18

Альтернатива для вложенного четырехугольника unordered_map monstrosity?

3 голосов
/ 20 июня 2019

Я пытался найти эффективный способ хранения и извлечения нескольких объектов. Позвольте мне объяснить, чего я пытаюсь достичь, а затем перечислить варианты, которые я предложил ( Но я недоволен ).

Технически то, что мне нужно, выполняет следующее, но очевидно, нет-нет: 

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*

Самая внутренняя карта содержит Компоненты на основе их идентификатора. Тот, у которого есть карта, имеет тип (подклассы компонента). Последнее сделано для того, чтобы при извлечении их я мог динамически приводить их к их типу с полной безопасностью, зная, что хеш-карта TYPE содержит только указатели их типа, что также позволяет использовать счетчик для быстрой проверки, существует ли что-то с определенным идентификатором. , Карта, следующая за ними, хранит их по слоям, первая карта хранит их по сцене. В любой момент будет проведено около 30-50 сцен, каждый из которых содержит около 6-10 слоев, каждый из которых содержит около 30-40 типов, в каждом из которых содержится от 1 до 500 объектов.

Каждый цикл мы будем перебирать указатели в зависимости от их типа, по одному слою за раз. Сцены меняются редко (каждые 2-3 минуты). Компоненты доступны с помощью комбинации Type и Id. Код регулярно проверяет, какие другие типы компонентов присутствуют в том же Id. Доступ к сценам, слоям и типам осуществляется через их имя, которое хранится как 32-битный хэш CRC. Скорость имеет решающее значение. Идентификаторы - это числа, назначаемые кодом, просто начиная с 0 и выше. Идентификаторы уникальны в каждой сцене.

Без сомнения, есть какая-то безумная (читай: обычная) идиома, которая помогает мне, и о которой я никогда не слышал. Кто-нибудь знает один? Пока что ни одна из предложенных мною альтернатив не является приемлемой, но я перечислю их независимо от того:

Вариант 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>>

(Тип / Слой / Сцена / Идентификатор) -> Компонент * Храните все компоненты просто с индексом вектора. Иметь unordered_map, который содержит векторы индексов в главном векторе памяти. И идентификаторы, и строковые хэши могут существовать, поскольку мы проверяем их на наличие коллизий (маловероятно). Имена должны быть уникальными для сцен, слоев и типов. Идентификаторы возвращают вектор всех индексов для компонентов, входящих в этот идентификатор. Имена или типы возвращают векторы, содержащие все индексы этого типа или сцены. Все эти итерации этих векторов кажутся хакерскими.

Вариант 4:

Компоненты получают указатель «Компонент * следующий» для перебора компонентов, принадлежащих одному объекту. Последний компонент ссылается на первый. Компоненты снова получают тип и элементы сцены / слоя.

Ответы [ 2 ]

6 голосов
/ 20 июня 2019

Укажите свой собственный ключ с функцией хеширования и равной функцией. 

   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 который перебирает слой на карте из 50000 компонентов за 250 мсек.

4 голосов
/ 20 июня 2019

Я бы предложил разделить карты на несколько карт: 

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;

Тем не менее, обратите внимание, что в обычной Entity-Component-System вы должны избегать погони за указателями и скачков в контейнере на основе узлов.

...