C++ Std :: vector best practice a due dimensioni

Question

Sto costruendo un'app che deve supportare supporti di array bidimensionali per contenere una griglia di dati. Ho una classe Map che contiene una griglia di dati 2d. Voglio usare i vettori piuttosto che gli array e mi chiedevo quali fossero le migliori pratiche per l'utilizzo dei vettori 2d. Dovrei avere un vettore di vettori di MapCells? o dovrebbe essere un vettore di vettori di indicatori di MapCells? o riferimenti 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); 
     } 
    } 
} 

Fondamentalmente ciò modo di fare questo sta per arrivare me nel minor numero di problemi (per quanto riguarda la gestione della memoria o qualsiasi altra cosa)?

Answer 1

Quando si desidera una griglia quadrata o 2d, fare qualcosa di simile a ciò che il compilatore fa per gli array multidimensionali (quelli reali, non una matrice di puntatori agli array) e memorizzare un singolo array grande che si indicizza correttamente.

Esempio utilizzando la classe Matrix di seguito:

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

Varianti di classi matrice abbondano, e ci sono molti modi per adeguare per uso specifico. Ecco un esempio in meno di 100 linee che si ottiene l'80% o più di quello che ti serve:

#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

Se l'intera matrice ha larghezza e altezza per lo più costanti, è possibile utilizzare anche un singolo vector e le celle di indirizzo con (row * columnCount) + column. In questo modo l'intera operazione verrà archiviata in un singolo blocco di memoria anziché in diversi blocchi frammentati per ogni riga. (Anche se stai facendo la cosa giusta per concludere questo concetto in una nuova classe - Sto solo parlando dell'implementazione dietro le quinte.)

Un vettore di vettori ha la sfortunata proprietà che se tu inserire una riga nella parte superiore, std::vector eseguirà una costruzione di copia (o assegnazione, possibilmente) per tutte le altre righe mentre le sposta di una posizione. Ciò a sua volta comporta la riallocazione dello spazio di archiviazione per ogni riga e la copia individuale degli elementi nelle celle di ogni riga. (C++ 0x sarà probabilmente meglio in questo.)

Se sai che farai spesso questo tipo di cose, il vantaggio di un unico grande blocco di memoria è che puoi inserire una nuova riga in cima e std::vector dovrà solo spostare tutte le celle in avanti di columnCount posizioni, quindi ridurrà seriamente il numero di operazioni heap (liberando/riallocando i singoli blocchi).

Sebbene, come suggerito, un vettore di puntatori ai vettori avrebbe l'ulteriore vantaggio che sarebbe necessario solo spostare in avanti molti valori di puntatore e la dimensione del blocco contenente tutti i puntatori di riga sarà molto più piccola, riducendo ulteriormente l'impatto delle operazioni heap.

Ovviamente, l'unico modo per essere sicuri dell'impatto effettivo di queste cose sulle prestazioni di un'applicazione è crearlo con varie implementazioni e confrontarle. Questo è il motivo per cui stai facendo esattamente la cosa giusta nascondendo questi dettagli all'interno di una nuova classe.

Answer 3

Usare un vettore e tradurre le 2 dimensioni a una dimensione. E.g. se la tua matrice ha una larghezza di W e un'altezza di H, allora la mappatura di x, y all'indice nel vettore è semplicemente x * W + y.

Se la matrice è scarsa, si consiglia di utilizzare una mappa std :: dove la chiave è una coppia (xey).

Answer 4

Nei miei progetti uso spesso questo simple grid class.