How to create an efficient 2D grid in C++?

Question

Hi,

I want to create a really easy to use 2D Grid. Each cell in the grid needs to be able to store a load of data. Ideally I would like to be able to traverse through the grid one cell at a time, as well as obtain the immediate neighbours of any of the grid cells.

My first thought was to store a vector of pointers to a Cell's neighbours (4 in total), then create convenience functions for leftNeighbour, rightNeighbour, etc. Connecting up the grid after initialization.

The std::vector is supposed to be a dynamically resizeable array, so this strikes me as rather unnecessary if I'm only going to hard-code the positions of the pointers (0 == left, 1 == right, etc). However, it does allow a nicer way of iterating through the neighbours of a cell. The other thing I have to consider is if the cell is on a border with the edge of the grid (whether to test for this or just implicitly extend the grid by one cell so that this will never happen).

Can anyone suggest a better alternative, or does this sound like a reasonable design?

Thanks, Dan

Answer 1

I would go for Boost.MultiArray

Answer 2

I assume you don't want the I-would-think-of-this-first method of std::vector<std::vector<T> >, but rather something which allows more complicated structures.

In that case, why not make a Node class (or struct):

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

This is iterable (which is one of your criteria) and doesn't use dynamic allocation for storing the neighbors.

Answer 3

If you want a four-direction iterator, make your own:

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

You may want to detect if you hit the edge of your grid, among other things, and that would have to be implemented.

Answer 4

Take a look at the GIL, which is a generic image processing library. Among other things, it has 2D iterators for iterating over images, and being really generic, you might be able to use it directly for your stuff as well. It's surely at least worth a look how this could be implemented.