c++ - 带有 Vector3 键的 std::map 与使用复合索引的 std::vector

Question

我现在正在创建一个 tilemap 并尝试决定如何存储和引用每个 tile。我当前的 2 个选项介于两者之间:

1. 一个 std::vector，其中我使用复合 x、y、z 计算作为键；
2. 或者使用 Vector3i 作为键的 std::map。

我的问题是:根据易用性和/或性能，我应该倾向于/更喜欢哪种方法。我想不同方法之间的内存/大小/存储也可能会产生影响。欢迎批评，因为在我的引擎基于此之前我想听听一些意见。

这是一个使用复合 vector 的例子:

#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;
};

这里是一个使用 std::map 方法的例子:

#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;
};

好的，非常感谢!

Answer 1

使用单个 vector 来存储整个瓦片 map 需要整个瓦片 map 位于连续的内存块中。根据 tilemap 的大小，这可能是也可能不是问题(对于您当前的大小，它不会，但是如果它被扩展到更大的 3D 空间，它很容易变得太大而无法尝试分配在一个连续的 block 中)。

如果您需要以某种有序的方式遍历 3D 空间， map 将不是您最好的容器(因为这些项目不一定符合您想要显示的逻辑顺序)。

另一种可能的解决方案是使用 vector 的 vector vector 到图 block ，这将允许在 3D 空间中轻松迭代，同时也不需要大量连续的数据 block (只需要一维的图 block 行)连续)。