std::map with Vector3 key VERSUS std::vector using a composite index

Question

I'm creating a tilemap at the moment and trying to decide how to store and reference each tile. My 2 current options are between either :

1. A std::vector where I use a composite x,y,z calc as the key;
2. Or a std::map using a Vector3i as the key.

My question is : which method should I lean towards/prefer based on ease of use and/or performance. I guess memory/size/storage between the different methods could also come into the decision. Criticism is welcome as I'd like some opinions before basing my engine on this.

Here is an example using the composite 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;
};

And here is an example using the std::map method :

#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, thanks a bunch!

Answer 1

Using a single vector to store your entire tilemap will require that the entire tilemap be in a contiguous block of memory. Depending on the size of the tilemap, that may or may not be a problem (with your current sizes, it won't be, but if it was ever expanded to a larger 3D space, it could easily get too large to try to allocate in a single contiguous block).

If you need to iterate through the 3D space in some orderly fashion, a map won't be your best container (since the items won't necessarily be in the logical order you want for display purposes).

Another potential solution is to use a vector of vector of vectors to tiles, which would allow for ease of iteration through your 3D space while also not requiring a massive contiguous block of data (only a 1D row of tiles would need to be contiguous).