C++ Двумерный станд.:: векторные лучшие практики
Я создаю приложение, которое должно иметь поддержку двумерных матриц для содержания сетки данных. У меня есть класс Map это содержит 2-ю сетку данных. Я хочу использовать векторы, а не массивы, и я задавался вопросом, чем лучшие практики были для использования 2-х векторов. У меня должен быть вектор векторов 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);
}
}
}
В основном, что способ сделать это собирается получить меня в наименьшем количестве суммы проблемы (относительно управления памятью или чего-либо еще)?
4 ответа
Если вам нужна квадратная или двумерная сетка, сделайте что-то подобное тому, что компилятор делает для многомерных массивов (реальных, а не массива указателей на массивы) и сохраните один большой массив, который вы правильно индексируете.
Пример использования класса 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;
};
В своих проектах я часто использую это класс простой сетки .
Если вся матрица имеет в основном постоянную ширину и высоту, вы можете использовать один вектор, и обращаться к ячейкам по (row * columnCount) + column. Таким образом, все будет храниться в одном блоке памяти, а не в нескольких фрагментированных блоках для каждой строки. (Хотя, конечно, вы правильно делаете, что оборачиваете эту концепцию в новый класс - я просто говорю о закулисной реализации).
Вектор векторов обладает тем неприятным свойством, что если вы вставите строку сверху, std::vector выполнит построение копии (или присвоение, возможно) для всех остальных строк, поскольку он сдвигает их вниз на одно место. Это, в свою очередь, включает перераспределение памяти для каждой строки и индивидуальное копирование элементов в ячейках каждой строки. (C++0x, вероятно, справится с этим лучше.)
Если вы знаете, что будете делать такие вещи часто, преимущество одного большого блока памяти в том, что вы можете вставить новую строку сверху и std::vector должен будет сдвинуть все ячейки вперед только на columnCount мест, что серьезно сократит количество операций с кучей (освобождение/перераспределение отдельных блоков).
Хотя, как вы предлагаете, вектор указателей на векторы будет иметь дополнительное преимущество в том, что ему нужно будет сдвинуть вперед только множество значений указателей, а размер блока, содержащего все указатели на строки, будет намного меньше, что еще больше уменьшит влияние операций с кучей.
Конечно, единственный способ убедиться в фактическом влиянии этих вещей на производительность приложения - это провести время с различными реализациями и сравнить их. Вот почему вы поступаете совершенно правильно, скрывая эти детали в новом классе.
Используйте вектор и переведите два измерения в одно измерение. Например. если ваша матрица имеет ширину W и высоту H, то сопоставление x, y с индексом в векторе просто x * W + y.
Если ваша матрица разреженная, вы можете использовать std :: map, где ключ представляет собой пару (x и y).