C ++ Two Dimensional std :: vector лучшие практики

Question

Я создаю приложение, которое должно иметь поддержку двухмерных массивов для хранения сетки данных. У меня есть класс Map, который содержит двумерную сетку данных. Я хочу использовать векторы, а не массивы, и мне было интересно, как лучше всего использовать двухмерные векторы. Должен ли я иметь вектор векторов MapCells? или это должен быть вектор векторов указателей на MapCells? или ссылки на 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);
        }
    }
}

В принципе, какой способ сделать это доставит мне меньше всего хлопот (в отношении управления памятью или чего-либо еще)?

Answer 1

Если вам нужна квадратная или двумерная сетка, сделайте что-то похожее на то, что делает компилятор для многомерных массивов (реальных, а не массив указателей на массивы) и сохраните один большой массив, который вы правильно индексировали.

Пример использования класса Matrix ниже:

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

Вариантов матричных классов предостаточно, и есть много способов адаптировать их для конкретного использования. Вот пример из менее чем 100 строк, который дает вам 80% или более того, что вам нужно:

#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 2

Если вся матрица имеет в основном постоянную ширину и высоту, вы также можете использовать одну vector и адресовать ячейки с (row * columnCount) + column.Таким образом, все будет храниться в одном блоке памяти, а не в нескольких фрагментированных блоках для каждой строки.(Хотя, конечно, вы делаете правильную вещь, чтобы обернуть эту концепцию в новом классе - я просто говорю о закулисной реализации.)

Вектор векторов обладает неудачным свойством, чтоесли вы вставите строку вверху, std::vector выполнит построение копирования (или, возможно, присваивание) для всех остальных строк, поскольку оно сдвигает их вниз на одно место.Это, в свою очередь, включает перераспределение хранилища для каждой строки и индивидуальное копирование элементов в ячейках каждой строки.(C ++ 0x, вероятно, будет лучше в этом.)

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

Хотя, как вы предлагаетевектор указателей на векторы будет иметь дополнительное преимущество, заключающееся в том, что ему потребуется только сдвинуть вперед много значений указателей, а размер блока, содержащего все указатели строк, будет намного меньше, что еще больше уменьшит влияние операций кучи.

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

Answer 3

В своих проектах я часто использую простой класс сетки .

Answer 4

Используйте вектор и переведите 2 измерения в одно измерение.Например, если ваша матрица имеет ширину W и высоту H, то отображение x, y на индекс в векторе будет просто x * W + y.

Если ваша матрица разрежена, вы можете использоватьstd :: map, где ключом является пара (x и y).