C++ Two Dimensional std::vector best practices

Question

I am building an app that needs to have support for two dimensional arrays to hold a grid of data. I have a class Map that contains a 2d grid of data. I want to use vectors rather than arrays, and I was wondering what the best practices were for using 2d vectors. Should I have a vector of vectors of MapCells? or should it be a vector of vectors of pointers to MapCells? or references to MapCells?

class Map {
private:
    vector<vector<MapCell>> cells;

public:
    void loadMap() {
        cells.clear();
        for (int i = 0; i < WIDTH; i++) {
            //How should I be allocating these?
            vector<MapCell> row(HEIGHT);
            for (int j = 0; j < HEIGHT; j++) {
                //Should I be dynamically allocating these?
                MapCell cell;
                row.push_back(cell);
            }
            cells.push_back(row);
        }
    }
}

Basically what way of doing this is going to get me in the least amount of trouble (with respect to memory management or anything else)?

Answer 1

If the whole matrix has a mostly constant width and height, you may as well use a single vector, and address cells with (row * columnCount) + column. That way the whole thing will be stored in a single memory block instead of in several fragmented blocks for each row. (Though of course you are doing the right thing to wrap this concept up in a new class - I'm just talking about the behind-the-scenes implementation.)

A vector of vectors has the unfortunate property that if you insert a row at the top, std::vector will perform a copy construction (or assignment, possibly) for all the other rows as it shifts them down by one place. This in turn involves reallocating the storage for every row and individually copying the items in the cells of every row. (C++0x will probably be better at this.)

If you know that you will be doing that kind of thing often, the advantage of a single large memory block is that you can insert a new row at the top and std::vector will only have to shift all the cells forward by columnCount places, so it will seriously reduce the number of heap operations (freeing/reallocating of individual blocks).

Although as you suggest, a vector of pointers to vectors would have the further advantage that it would only need to shift forward a lot of pointer values, and the size of the block containing all the row pointers will be much smaller, further lessening the impact of heap operations.

Of course, the only way to be sure of the actual impact of these things on the performance of an application is to time it with various implementations and compare them. This is why you're doing exactly the right thing by hiding these details inside a new class.

Answer 2

When you want a square or 2d grid, do something similar to what the compiler does for multidimensional arrays (real ones, not an array of pointers to arrays) and store a single large array which you index correctly.

Example using the Matrix class below:

struct Map {
private:
  Matrix<MapCell> cells;

public:
  void loadMap() {
    Matrix<MapCell> cells (WIDTH, HEIGHT);

    for (int i = 0; i < WIDTH; i++) {
      for (int j = 0; j < HEIGHT; j++) {
        // modify cells[i][j]
      }
    }

    swap(this->cells, cells);
    // if there's any problem loading, don't modify this->cells
    // Matrix swap guarantees no-throw (because vector swap does)
    // which is a common and important aspect of swaps
  }
};

Variants of matrix classes abound, and there are many ways to tailor for specific use. Here's an example in less than 100 lines that gets you 80% or more of what you need:

#include <algorithm>
#include <memory>
#include <vector>

template<class T, class A=std::allocator<T> >
struct Matrix {
  typedef T value_type;
  typedef std::vector<value_type, A> Container;

  Matrix() : _b(0) {}
  Matrix(int a, int b, value_type const& initial=value_type())
  : _b(0)
  {
    resize(a, b, initial);
  }
  Matrix(Matrix const& other)
  : _data(other._data), _b(other._b)
  {}

  Matrix& operator=(Matrix copy) {
    swap(*this, copy);
    return *this;
  }

  bool empty() const { return _data.empty(); }
  void clear() { _data.clear(); _b = 0; }

  int dim_a() const { return _b ? _data.size() / _b : 0; }
  int dim_b() const { return _b; }

  value_type* operator[](int a) {
    return &_data[a * _b];
  }
  value_type const* operator[](int a) const {
    return &_data[a * _b];
  }

  void resize(int a, int b, value_type const& initial=value_type()) {
    if (a == 0) {
      b = 0;
    }
    _data.resize(a * b, initial);
    _b = b;
  }

  friend void swap(Matrix& a, Matrix& b) {
    using std::swap;
    swap(a._data, b._data);
    swap(a._b,    b._b);
  }

  template<class Stream>
  friend Stream& operator<<(Stream& s, Matrix const& value) {
    s << "<Matrix at " << &value << " dimensions "
      << value.dim_a() << 'x' << value.dim_b();
    if (!value.empty()) {
      bool first = true;
      typedef typename Container::const_iterator Iter;
      Iter i = value._data.begin(), end = value._data.end();
      while (i != end) {
        s << (first ? " [[" : "], [");
        first = false;
        s << *i;
        ++i;
        for (int b = value._b - 1; b; --b) {
          s << ", " << *i;
          ++i;
        }
      }
      s << "]]";
    }
    s << '>';
    return s;
  }

private:
  Container _data;
  int _b;
};

Answer 3

Use a vector and translate the 2 dimensions to one dimension. E.g. if your matrix has a width of W and a height of H, then mapping x,y to the index in the vector is simply x*W+y.

If your matrix is sparse you may want to use an std::map where the key is a pair (x and y).

Answer 4

In my projects I often use this simple grid class.