std :: map с ключом Vector3 VERSUS std :: вектор с использованием составного индекса

Question

Я создаю tilemap в данный момент и пытаюсь решить, как хранить и ссылаться на каждую плитку. Мои 2 текущих варианта находятся между:

1. Std :: vector где я использую составные х, y, z calc как ключ;
2. Или std :: map с использованием Vector3i в качестве ключа.

Мой вопрос: какой метод следует наклонять в сторону/предпочитаю в зависимости от простоты использования и/или производительности. Я думаю, что память/размер/хранение между различными методами также могут прийти к решению. Критика приветствуется, поскольку я хотел бы получить некоторые мнения, прежде чем основывать мой движок на этом.

Ниже приведен пример использования составного вектора:

#include <vector> 
#include <algorithm> 
#include <iostream> 

unsigned int mapWidth = 10, mapHeight = 10, mapDepth = 2; 

struct Vector3i { 
    Vector3i() {}; 
    Vector3i(unsigned int x, unsigned int y, unsigned int z) : x(x), y(y), z(z) {} 
    unsigned int x, y, z; 
}; 

struct Tile { 
    Tile() {}; 
    std::vector<unsigned int> children; 
    bool visible; 
    Vector3i coord; 
}; 

unsigned int getIndex(unsigned int x, unsigned int y, unsigned int z) { 
    return (y*mapWidth) + x + (z * (mapWidth * mapHeight)); 
} 

int main() { 

    std::vector<Tile> tiles; 
    tiles.resize(mapWidth * mapHeight * mapDepth); 

    for(int x = 0; x < mapWidth; x++) { 
     for(int y = 0; y < mapHeight; y++) { 
      for(int z = 0; z < mapDepth; z++) { 
       unsigned int idx = getIndex(x,y,z); 
       tiles[idx].coord = Vector3i(x,y,z); 
       tiles[idx].visible = true; 
       tiles[idx].children.push_back(1); 
      } 
     } 
    } 

    std::for_each(tiles.begin(), tiles.end(), [&] (const Tile& tile) { 
     std::cout << tile.coord.x << "," << tile.coord.y << "," << tile.coord.z << std::endl; 
    }); 

    const Tile& myTile = tiles[getIndex(1,1,1)]; 
    std::cout << '\n' << myTile.coord.x << "," << myTile.coord.y << "," << myTile.coord.z << std::endl; 

    return 0; 
}; 

А вот пример использования метода станд :: Карта:

#include <vector> 
#include <map> 
#include <iostream> 
#include <algorithm> 
#include <functional> 

struct Vector3i { 
    Vector3i() {}; 
    Vector3i(unsigned int x, unsigned int y, unsigned int z) : x(x), y(y), z(z) {} 
    unsigned int x, y, z; 
}; 

struct Tile { 
    std::vector<unsigned int> children; 
    bool visible; 
    Vector3i coord; 
}; 

class comparator { 
    public: 
     bool operator()(const Vector3i& lhs, const Vector3i& rhs) const { 
      return lhs.x < rhs.x 
       || (lhs.x == rhs.x && (lhs.y < rhs.y 
       || (lhs.y == rhs.y && lhs.z < rhs.z))); 
     } 
}; 

int main() { 
    unsigned int mapWidth = 5, mapHeight = 5, mapDepth = 2; 
    std::map<Vector3i, Tile, comparator> tiles; 

    for(int x = 0; x < mapWidth; x++) { 
     for(int y = 0; y < mapHeight; y++) { 
      for(int z = 0; z < mapDepth; z++) { 
       Vector3i key(z,y,x); 

       Tile tile; 
       tile.coord = Vector3i(x,y,z); 
       tile.visible = true; 
       tile.children.push_back(1); 

       tiles.insert(std::make_pair<Vector3i, Tile>(key, tile)); 
      } 
     } 
    } 

    for(std::map<Vector3i, Tile, comparator>::iterator iter = tiles.begin(); iter != tiles.end(); ++iter) { 
     std::cout << iter->second.coord.x << "," << iter->second.coord.y << "," << iter->second.coord.z << std::endl; 
    } 

    auto found = tiles.find(Vector3i(1,1,1)); 
    const Tile& myTile = found->second; 
    std::cout << '\n' << myTile.coord.x << "," << myTile.coord.y << "," << myTile.coord.z << std::endl; 

    return 0; 
}; 

Ok, спасибо кучу!

Answer 1

Использование одного вектора для хранения всего вашего tilemap потребует, чтобы весь tilemap был в непрерывном блоке памяти. В зависимости от размера tilemap это может быть или не быть проблемой (с вашими текущими размерами этого не будет, но если бы он когда-либо расширялся до большего 3D-пространства, он мог бы легко стать слишком большим, чтобы попытаться выделить в одном непрерывном блоке).

Если вам нужно пройти через 3D-пространство в некотором упорядоченном порядке, карта не будет вашим лучшим контейнером (так как элементы не обязательно будут в логическом порядке, который вы хотите для отображения).

Другим потенциальным решением является использование вектора вектора векторов для плит, что позволило бы упростить итерацию через ваше 3D-пространство, а также не требовать массивного непрерывного блока данных (только 1-я строка черепицы должна была бы быть смежным).