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

Question

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

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.