Подтвердить что ты не робот

С++ Двухмерные std::vector лучшие практики

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

Пример использования класса 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 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;
};

Ответ 2

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

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

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

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

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

Ответ 3

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

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