具有各种访问方法的自定义数据结构 [英] Custom data structures with various access methods

问题描述

所以我有一个 Grid 类和一个 Tile 类.ATM Grid 包含 Tiles 的二维向量(vector>).这些瓷砖保存有关它们的 x、y 和 z(这是一个自上而下的地图)和 f.e. 的信息.侵蚀率等

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.

我的问题是我需要通过它们的 x/y 坐标有效地访问这些图块，从所有 z 坐标中找到一个具有中值(或其他 0 到 1 值，中值为 0.5)值的图块(设置海level) 并从最高 z 到最低 (用于创建侵蚀图.

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.

我考虑过的选项是地图，它没有直接访问权限，并且总是经过排序，这会使按 x/y 选择图块变得困难.
然后是一个允许直接访问的向量，但如果我要对切片进行排序，那么直接访问将毫无意义，因为向量中的 Tile 位置将与其 x + y * 宽度相同.

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.

这是一个小示例代码:

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;

}

推荐答案

所以在我的大学问这个问题并得到更深入的解释后，我得出了这个解决方案.
如果您需要一个需要各种访问方法的数据结构(例如在我的情况下通过 x/y 直接访问，通过排序 z 进行线性访问等)，最好的解决方案是让您拥有自己的类来处理它.此外，使用shared_ptr 比 uniqu_ptr 慢得多，除非必要，否则不应使用.所以在我的情况下，实现看起来像这样:

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

您也可以使用模板，但就我而言，我只需要在 Tile 类中使用它.如您所见，主 _directAccess 矩阵包含所有 unique_ptr，而 _sortedZ 只有指向存储在 _dA 中的数据的原始指针.因为这些指针被绑定到一个类，并且所有这些指针同时被删除，所以这更快也更安全.此外，我还添加了用于访问数据的重载 () 运算符并重用了来自 _sortedZ 向量的迭代器.同样，宽度和高度为常量只是因为此数据结构的预期用途(不可调整大小、不可移动的图块等).
如果您对改进之处有任何问题或建议，请随时发表评论.

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.

这篇关于具有各种访问方法的自定义数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！