Как создать эффективную 2D сетку в C ++?

Question

Я хочу создать действительно простую в использовании 2D Grid. Каждая ячейка в сетке должна иметь возможность хранить множество данных. В идеале я хотел бы иметь возможность проходить через сетку по одной ячейке за раз, а также получать непосредственных соседей любой из ячеек сетки.

Моей первой мыслью было сохранить вектор указателей на соседей ячейки (всего 4), затем создать вспомогательные функции для leftNeighbour, rightNeighbour и т. Д. Подключение сетки после инициализации.

Предполагается, что std :: vector является динамически изменяемым массивом, так что это может показаться мне ненужным, если я собираюсь жестко закодировать позиции указателей (0 == слева, 1 == справа, так далее). Тем не менее, он позволяет лучше обходить соседей ячейки. Еще одна вещь, которую я должен рассмотреть, - это если ячейка находится на границе с краем сетки (нужно ли проверять это или просто неявно расширять сетку на одну ячейку, чтобы это никогда не происходило).

Кто-нибудь может предложить лучшую альтернативу, или это звучит как разумный дизайн?

Спасибо, Дэн

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

Возможно, вы захотите определить, попадаете ли вы на край вашей сетки, помимо прочего, и это должно быть реализовано.

Answer 2

Я бы пошел на Boost.MultiArray

Answer 3

Взгляните на GIL , которая является общей библиотекой обработки изображений. Помимо прочего, у него есть 2D итераторы для перебора изображений, и, будучи действительно универсальным, вы можете использовать его непосредственно для своих вещей. По крайней мере, стоит посмотреть, как это можно реализовать.

Answer 4

Полагаю, вам не нужен метод "100% *", который я бы подумал, а скорее метод, который допускает более сложные структуры.

В таком случае, почему бы не создать 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];
};

Это итеративно (это один из ваших критериев) и не использует динамическое распределение для хранения соседей.