Custom data structures with various access methods

Question

So what I've got is a Grid class and a Tile class. ATM Grid contains two dimensional vector of Tiles (vector<vector<Tile>>). These Tiles hold info about their x, y and z (it's a top down map) and f.e. erosion rate etc.

My problem is with that is that I need to effectively access these tiles by their x/y coordinates, find a tile with median (or other 0 to 1 value, median being 0.5) value from all z coordinates (to set sea level) and also loop through all of them from highest z to the lowest (for creating erosion map.

What would you suggest would be the best data structure to hold these in so I can effectively do everything I listed above and maybe something else as well if I find out later I need it. Right now I just create a temporary sorted structure or map to do the thing, copying all the tiles into it and working with it, which is really slow.

The options I've considered are map which doesn't have a direct access and is also always sorted which would make picking tiles by their x/y hard.
Then a single vector which would allow direct access but if I was to sort the tiles the direct access would be pointless because the position of Tile in vector would be the same as it's x + y * width.

Here is a small sample code:

Class Grid {
public:
   Class Tile {
      unsigned x;
      unsigned y;
      float z; // used for drawing height map
      static float seaLevel; // static value for all the tiles
      unsigned erosionLevel; //used for drawing erosion map

   void setSeaLevel(float pos) { 
      // set seaLevel to z of tile on pos from 0 to 1 in tile grid
   }

   void generateErosionMap() {
      // loop thorugh all tiles from highest z to lowest z and set their erosion
   }

   void draw() {
      // loop through all tiles by their x/y and draw them
   }

   vector<vector<Tile>> tileGrid;

}

Answer 1

The C++ library provides a basic set of containers. Each container is optimized for access in a specific way.

When you have a requirement to be able to optimally access the same set of data in different ways, the way to do this is to combine several containers together, all referencing the same underlying data, with each container being used to locate a single chunk of data in one particular way.

Let's take two of your requirements, as an example:

1. Locate a Grid object based on its X and Y coordinates, and

2. Iterate over all Grids in monotonically increasing or decreasing order, by their z coordinates.

We can implement the first requirement by using a simple two-dimensional vector:

typedef std::vector<std::vector<std::shared_ptr<Grid>>> lookup_by_xy_t;

lookup_by_xy_t lookup_by_xy;

This is rather obvious, on its face value. But note that the vector does not store the actual Grids, but a std::shared_ptr to these objects. If you are not familiar with std::shared_ptrs, read up on them, and understand what they are.

This is fairly basic: you construct a new Grid:

auto g = std::make_shared<Grid>( /* arguments to Grid's constructor */);

// Any additional initialization...
//
// g->foo(); g->bar=4;
//
// etc...

and simply insert it into the lookup vector:

lookup_by_xy[g->x][g->y]=g;

Now, we handle your second requirement: being able to iterate over all these objects by their z coordinates:

typedef std::multimap<double, std::shared_ptr<Grid>> lookup_by_z_t;

lookup_by_z_t lookup_by_z;

This is assuming that your z coordinate is a double. The multimap will, by default, iterate over its contents in strict weak ordering according to the key, from lowest to the highest key. You can either iterate over the map backwards, or use the appropriate comparison class with the multimap, to order its keys from highest to lowest values.

Now, simply insert the same std::shared_ptr into this lookup container:

lookup_by_z.insert(std::make_pair(g->z, g));

Now, you can find each Grid object by either its x/y coordinate, or iterate over all objects by their z coordinates. Both of the two-dimensional vector, and the multimap, contain shared_ptrs to the same Grid objects. Either one can be used to access them.

Simply create other containers, as needed, to access the same underlying objects, in different ways.

Now, of course, all of this additional framework does impose some additional overhead, in terms of dynamic memory allocations, and the overhead for each container itself. There is no free lunch. A custom allocator might become necessary if the amount of raw data becomes an issue.

Answer 2

So after asking this question on my university and getting bit deeper explanation, I've come to this solution.
If you need a data structure that needs various access methods(like in my case direct access by x/y, linear access through sorted z etc.) best solution is to make you own class for handling it. Also using shared_ptr is much slower than uniqu_ptr and shouldn't be used unless necessary. So in my case the implementation would look something like this:

#ifndef TILE_GRID_H
#define TILE_GRID_H

#include "Tile.h"
#include <memory>
#include <vector>

using Matrix = std::vector<std::vector<std::unique_ptr<Tile>>>;
using Sorted = std::vector<Tile*>;

class TileGrid {
public:
    TileGrid(unsigned w, unsigned h) : width(w), height(h) {
        // Resize _dA to desired size
        _directAccess.resize(height);
        for (unsigned j = 0; j < height; ++j)
            for (unsigned i = 0; i < width; ++i)
                _directAccess[j].push_back(std::make_unique<Tile>(i, j));

        // Link _sZ to _dA
        for (auto& i : _directAccess)
            for (auto& j : i)
                _sortedZ.push_back(j.get());
    }

    // Sorts the data by it's z value
    void sortZ() {
        std::sort(_sortedZ.begin(), _sortedZ.end(), [](Tile* a, Tile* b) { return b->z < a->z; });
    }

    // Operator to read directly from this container
    Tile& operator()(unsigned x, unsigned y) {
        return *_directAccess[y][x];
    }

    // Operator returning i-th position from sorted tiles (in my case used for setting sea level)
    Tile& operator()(float level) {
        level = fmax(fmin(level, 1), 0);
        return *_sortedZ[width * height * level];
    }

    // Iterators
    auto begin() { return _sortedZ.begin(); }
    auto end() { return _sortedZ.end(); }
    auto rbegin() { return _sortedZ.rbegin(); }
    auto rend() { return _sortedZ.rend(); }

    const unsigned width; // x dimensoin
    const unsigned height; // y dimension
private:
    Matrix _directAccess;
    Sorted _sortedZ;
};

#endif // TILE_GRID_H

You could also use template, but in my case I only needed this for the Tile class. So as you can see, the main _directAccess matrix holds all the unique_ptr while _sortedZ has only raw pointers to data stored in _dA. This is much faster and also safe because of these pointers being tied to one class, and all of them being deleted at the same time. Also I've added overloaded () operators for accessing the data and reused iterators from the _sortedZ vector. And again the width and height being const is only because of the intended usage for this data structure(not resizable, immovable tiles etc.).
If you have any questions or suggestions on what to improve, feel free to comment.