program - C++ Twodimensional std:: vector mejores prácticas

vector c++ español

Question

Estoy construyendo una aplicación que necesita tener soporte para matrices bidimensionales para contener una grilla de datos. Tengo un Map clase 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, ¿qué manera de hacer esto me va a poner en la menor cantidad de problemas (con respecto a la gestión de la 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 las matrices multidimensionales (las reales, no una matriz de punteros a las matrices) y almacene una única matriz grande que indice correctamente.

Ejemplo usando la clase Matrix a 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
  }
};

Las variantes de las clases de matriz abundan, y hay muchas maneras de adaptarlas para un uso específico. Aquí hay un ejemplo en menos de 100 líneas que le proporciona 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

En mis proyectos, a menudo uso esta clase de grilla simple .

Answer 3

Si toda la matriz tiene un ancho y una altura en su mayoría constantes, también puede usar un único 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; solo estoy hablando de la implementación detrás de escena).

Un vector de vectores tiene la propiedad desafortunada de que si inserta 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 hará ese tipo de cosas a menudo, la ventaja de un único bloque de memoria grande es que puede insertar una nueva fila en la parte superior y std::vector solo tendrá que desplazar todas las celdas hacia adelante por los lugares de columnCount , 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, reduciendo aún más el impacto de operaciones de montón.

Por supuesto, la única manera de estar seguro 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 4

Use un vector y traduzca las 2 dimensiones a una dimensión. Por ejemplo, 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, puede usar un std :: map donde la clave sea un par (xey).