如何在C++中创建高效的二维网格？

Question

我想创建一个非常易于使用的2D网格，每个网格单元都需要能够存储大量数据。理想情况下，我希望能够逐个单元地遍历网格，并获得任何网格单元的相邻单元。

我的第一个想法是将指向单元相邻元素的指针向量存储起来（总共4个），然后创建leftNeighbour、rightNeighbour等方便的函数，在初始化后连接网格。

std :: vector应该是一个动态可调整大小的数组，因此如果我只要硬编码指针的位置（0 == left，1 == right等），这对我来说似乎是不必要的。然而，它确实提供了一种更好的遍历单元的相邻单元的方法。另一件事我必须考虑的是，如果单元在与网格边缘相邻（是否测试或仅隐式扩展网格一个单元，以使这永远不会发生）。

有人能提出更好的替代方案吗？还是这听起来像一个合理的设计？

谢谢，丹

- Dan

Answer 1

如果你想要一个四个方向的迭代器，可以自己创建：

template<typename T, int width, int height>
class Grid {
    public:
        T data[width * height];

        iterator begin() {
            return iterator(data);
        }

        iterator end() {
            return iterator(data + width * height);
        }

        class iterator {
            public:
                iterator(const iterator &other) :
                    ptr(other.ptr)
                {
                }

                iterator &left() const {
                    return iterator(ptr - 1);
                }

                iterator &right() const {
                    return iterator(ptr + 1);
                }

                iterator &up() const {
                    return iterator(ptr - width);
                }

                iterator &down() const {
                    return iterator(ptr + width);
                }

                iterator &operator++() {
                    ++ptr;
                    return *this;
                }

                iterator &operator--() {
                    --ptr;
                    return *this;
                }

                iterator operator++(int) {
                    ++*this;
                    return iterator(ptr + 1);
                }

                iterator operator--(int) {
                    --*this;
                    return iterator(ptr - 1);
                }

                T operator*() const {
                    return *ptr;
                }

            private:
                iterator();
                iterator(T *ptr_) :
                    ptr(ptr_)
                {
                }

                T *ptr;

                friend class Grid;
        };
};

你可能想要检测是否到达了网格边缘，还有其他需要实现的功能。

- strager

---

有一件事我不太明白： 为什么你会在left、right等方法中返回新的迭代器，而在++和--中返回this呢？ - fho

Answer 2

我会选择Boost.MultiArray。

- yabcok

Answer 3

看一下GIL，这是一个通用的图像处理库。除其他功能外，它还具有用于迭代图像的2D迭代器。由于其通用性，您可能也可以直接将其用于自己的项目中。它肯定值得一看，以了解如何实现。

- Anteru

Answer 4

我假设您不想使用std::vector<std::vector<T> >这种我会首先考虑的方法，而是想要一些允许更复杂结构的东西。在那种情况下，为什么不创建一个Node类（或结构体）：

template<typename T>
class Node {
    public:
        typedef Node<T> *iterator;
        // and const_iterator

        T data;

        Node(T data_ = T()) :
            data(data_)
        {
        }

        Node<T> *&left() {
            return neighbors[0];
        }

        // etc.

        iterator begin() {
            return neighbors;
        }

        iterator end() {
            return neighbors + 4;
        }

    private:
        Node<T> *neighbors[4];
};

这是可迭代的（符合你的标准之一），并且不使用动态分配来存储邻居。

- strager

---

不要使用vector<vector<T>>，因为它由于没有缓存局部性而具有可怕的性能。相反，请使用一个平面的vector<T>，并使用y*w+x进行索引（这可以很容易地封装）。 - Iraimbilanja

@Iraimbilanja，我同意你的观点，但如果在X方向上改变地图大小，则会非常昂贵。如果大小是静态的，则平面数组可能是最好的选择。 - strager