C++ Twodimensional std :: vector best practices

Question

Estoy creando una aplicación que necesita tener soporte para matrices bidimensionales para contener una grilla de datos. Tengo una clase Map que contiene una cuadrícula de datos 2d. Quiero usar vectores en lugar de matrices, y me preguntaba cuáles eran las mejores prácticas para usar vectores bidimensionales. ¿Debo tener un vector de vectores de MapCells? o debería ser un vector de vectores de punteros a MapCells? o referencias a 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); 
     } 
    } 
} 

Básicamente lo forma de hacer esto se va a poner a mí en la menor cantidad de problemas (con respecto a la gestión de memoria o cualquier otra cosa)?

Answer 1

Cuando desee una cuadrícula cuadrada o 2d, haga algo similar a lo que hace el compilador para matrices multidimensionales (reales, no una matriz de punteros a matrices) y almacene una única matriz grande que indice correctamente.

Ejemplo utilizando la clase Matrix continuación:

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

variantes de clases de matriz abundan, y hay muchas maneras de adaptar para el uso específico. He aquí un ejemplo en menos de 100 líneas que se obtiene el 80% o más de lo que necesita:

#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

Si toda la matriz tiene un ancho y una altura en su mayoría constantes, también puede utilizar un solo vector, y las celdas de dirección con (row * columnCount) + column. De esta forma, todo se almacenará en un único bloque de memoria en lugar de en varios bloques fragmentados para cada fila. (Aunque, por supuesto, está haciendo lo correcto para incluir este concepto en una nueva clase; estoy hablando de la implementación detrás de escena.)

Un vector de vectores tiene la desafortunada propiedad de que si inserte una fila en la parte superior, std::vector realizará una construcción de copia (o asignación, posiblemente) para todas las otras filas a medida que las desplaza hacia abajo en un lugar. Esto a su vez implica la reasignación del almacenamiento para cada fila y la copia individual de los elementos en las celdas de cada fila. (C++ 0x probablemente sea mejor en esto.)

Si sabe que va a hacer ese tipo de cosas a menudo, la ventaja de un solo bloque de memoria grande es que puede insertar una nueva fila en la parte superior y std::vector solo tendrán que desplazar todas las celdas hacia adelante por columnCount lugares, por lo que reducirá seriamente el número de operaciones de pila (liberación/reasignación de bloques individuales).

Aunque, como sugiere, un vector de punteros a vectores tendría la ventaja adicional de que solo necesitaría desplazar muchos valores de puntero, y el tamaño del bloque que contiene todos los punteros de fila será mucho más pequeño, disminuyendo aún más el impacto de las operaciones de montón.

Por supuesto, la única manera de estar seguros del impacto real de estas cosas en el rendimiento de una aplicación es medir el tiempo con varias implementaciones y compararlas. Es por eso que estás haciendo lo correcto al ocultar estos detalles dentro de una nueva clase.

Answer 3

uso de un vector y traducir las 2 dimensiones para una dimensión. P. ej. si su matriz tiene un ancho de W y una altura de H, entonces el mapeo de x, y para el índice en el vector es simplemente x * W + y.

Si su matriz es escasa, es posible que desee utilizar un std :: map donde la clave sea un par (x e y).

Answer 4

En mis proyectos, a menudo uso este simple grid class.