Двунаправленная структура данных для этой ситуации

Я изучаю небольшую часть своего игрового движка и задаюсь вопросом как оптимизировать некоторые части.

Ситуация довольно проста и выглядит следующим образом:

• У меня есть карта Tiles (, хранящаяся в двумерном -массиве)(~260 тыс. тайлов, но предполагаю, что намного больше)
• У меня есть список Items, которые всегда находятся как минимум и не более чем в плитке
• A Tileможет логически содержать бесконечное количество Items
• Во время выполнения игры многие Items непрерывно создаются и начинают со своегоTile
• Каждый Itemнепрерывно меняет свой Tileна одного из соседей (вверх, вправо, вниз, влево)

До сих пор каждый Itemимеет ссылку на свой фактический Tile, и я просто сохраняю список элементов. Каждый раз, когда Itemперемещается на соседний тайл, я просто обновляю item->tile =.., и все в порядке.Это работает нормально, но однонаправленно.

При расширении движка я понял, что мне нужно найти все элементы, содержащиеся в тайле, много раз, и это эффективно снижает производительность (, особенно в некоторых ситуациях, когда мне нужно найти все элементы для диапазона тайлов., один за другим ).

Это означает, что я хотел бы найти структуру данных, подходящую для поиска всех элементов определенного Tileлучше, чем в O (n), но я хотел бы избежать больших накладных расходов в фаза "переход от одного тайла к другому" (теперь это просто присвоение указателя, хотелось бы избежать выполнения там многих операций, так как это довольно часто ).

Я думаю о пользовательской структуре данных, чтобы использовать тот факт, что элементы всегда перемещаются в соседнюю ячейку, но сейчас я блуждаю в темноте! Любые советы будут оценены, даже хитрые или загадочные подходы. К сожалению, я не могу просто тратить память, поэтому для этого необходим хороший обмен -.

Я разрабатываю его на C++ с STL, но без Boost. (Да, я знаю о multimap, меня это не устраивает, но я попробую, если не найду ничего лучше)