Un modo corretto per creare una matrice in C++

Question

Voglio creare una matrice di adiacenza per un grafico. Da quando ho letto non è sicuro utilizzare gli array del modulo matrix[x][y] perché non controllano l'intervallo, ho deciso di utilizzare la classe template vettoriale di stl. Tutto quello che devo memorizzare nella matrice sono valori booleani. Quindi la mia domanda è, se usare std::vector<std::vector<bool>* >* produce troppo overhead o se c'è un modo più semplice per una matrice e come posso inizializzarlo correttamente.

MODIFICA: Grazie mille per le risposte rapide. Mi sono appena reso conto che ovviamente non ho bisogno di alcun suggerimento. La dimensione della matrice verrà inizializzata all'inizio e non cambierà fino alla fine del programma. È per un progetto scolastico, quindi sarebbe bello scrivere un codice "carino", anche se tecnicamente le prestazioni non sono troppo importanti. Usare l'STL va bene. Usare qualcosa come boost, probabilmente non è apprezzato.

Answer 1

Considerate anche quanto è grande il vostro grafico/matrice, le prestazioni contano molto? Il grafico è statico o può crescere nel tempo, ad es. aggiungendo nuovi bordi?

Answer 2

Si noti che anche è possibile utilizzare boost.ublas per la creazione matrice e la manipolazione e anche boost.graph per rappresentare e manipolare grafici in un certo numero di modi, così come l'utilizzo di algoritmi su di loro, ecc

Edit: In ogni caso, fare una versione di gamma-check di un vettore per i vostri scopi, non è una cosa difficile:

template <typename T> 
class BoundsMatrix 
{ 
     std::vector<T> inner_; 
     unsigned int dimx_, dimy_; 

public: 
     BoundsMatrix (unsigned int dimx, unsigned int dimy) 
       : dimx_ (dimx), dimy_ (dimy) 
     { 
       inner_.resize (dimx_*dimy_); 
     } 

     T& operator()(unsigned int x, unsigned int y) 
     { 
       if (x >= dimx_ || y>= dimy_) 
         throw 0; // ouch 
       return inner_[dimx_*y + x]; 
     } 
}; 

Nota che si avrebbe anche bisogno di aggiungere la versione const degli operatori, e/o iteratori, e lo strano uso di eccezioni, ma tu hai l'idea.

Answer 3

Si prega di std::vector non esegue il controllo di intervallo pure.

Answer 4

Quello che vorrei fare è creare la mia classe per trattare le matrici (probabilmente come un array [x * y] perché sono più abituato a C (e avrei i miei limiti di controllo), ma potreste utilizzare i vettori o qualsiasi altra sotto-struttura in quella classe).

Prima di tutto, fai in modo che le tue cose funzionino, quindi preoccupati della velocità di esecuzione. Se si progetta correttamente la classe, è possibile estrarre l'implementazione dell'array [x * y] e sostituirla con vettori o maschere di bit o qualsiasi altra cosa si desideri senza modificare il resto del codice.

Io non sono del tutto sicuro, ma io cosa che è quello che le classi erano per, la capacità di astrarre l'implementazione ben fuori di vista e di fornire solo l'interfaccia :-)

Answer 5

migliore dei modi:

Crea la tua classe matrix, in questo modo controlli ogni aspetto di essa, incluso il controllo dell'intervallo.

es. Se ti piace la notazione "[x] [y]", fai questo:

class my_matrix { 
    std::vector<std::vector<bool> >m; 
public: 
    my_matrix(unsigned int x, unsigned int y) { 
    m.resize(x, std::vector<bool>(y,false)); 
    } 
    class matrix_row { 
    std::vector<bool>& row; 
    public: 
    matrix_row(std::vector<bool>& r) : row(r) { 
    } 
    bool& operator[](unsigned int y) { 
     return row.at(y); 
    } 
    }; 
    matrix_row& operator[](unsigned int x) { 
    return matrix_row(m.at(x)); 
    } 
}; 
// Example usage 
my_matrix mm(100,100); 
mm[10][10] = true; 

nb. Se si programma in questo modo, C++ è sicuro come tutte le altre lingue "sicure".

Answer 6

Oltre a tutte le risposte che sono state pubblicate finora, si potrebbe fare bene a dare un'occhiata allo C++ FAQ Lite. Le domande 13.10 - 13.12 e 16.16 - 16.19 coprono diversi argomenti relativi alla rotazione della propria classe matrice. Vedrete un paio di modi diversi per archiviare i dati e i suggerimenti su come scrivere al meglio gli operatori di pedici.

Inoltre, se il grafico è sufficientemente spargolo, potrebbe non essere necessaria una matrice. È possibile utilizzare std::multimap per associare ciascun vertice a quelli che collega.

Answer 7

Il vettore standard NON esegue il controllo dell'intervallo per impostazione predefinita.

Ad esempio, l'operatore [] non esegue un controllo di intervallo.

Il metodo su() è simile a [] ma esegue un controllo di intervallo.
Genererà un'eccezione fuori intervallo.

std::vector::at()
std::vector::operator[]()

Altre note: Perché un vettore <Puntatori>?
Si può facilmente avere un vettore <Oggetto>. Ora non c'è bisogno di preoccuparsi della gestione della memoria (cioè perdite).

std::vector<std::vector<bool> > m; 

Nota: vettore <bool> è sovraccarico e non molto efficiente (vale a dire tale struttura è stata ottimizzata per le dimensioni non di velocità) (E 'qualcosa che è ormai riconosciuto come probabilmente un errore da parte del comitato di standardizzazione).

Se si conosce la dimensione della matrice in fase di compilazione, è possibile utilizzare std :: bitset?

std::vector<std::bitset<5> > m; 

o se è tempo di esecuzione definito uso boost :: dynamic_bitset

std::vector<boost::dynamic_bitset> m; 

Tutto quanto sopra vi permetterà di fare:

m[6][3] = true; 

Answer 8

Se si desidera prestazioni dell'array 'C' , ma con una maggiore sicurezza e semantica simile a STL (iteratori, begin() ecc.), utilizzare boost::array.

Fondamentalmente si tratta di un wrapper basato su modelli per 'C'-array con alcune NDEBUG - asserzioni di controllo intervallo modificabili (e anche alcuni accessor di lancio di eccezioni std::range_error).

Io uso roba come

boost::array<boost::array<float,4>,4> m; 

invece di

float m[4][4]; 

tutto il tempo e funziona benissimo (con typedef appropriate per mantenere il livello di dettaglio basso, comunque).

---

UPDATE: Dopo qualche discussione nei commenti qui di performance relativa boost::array vs boost::multi_array, mi piacerebbe sottolineare che questo codice, compilato con g++ -O3 -DNDEBUG su Debian/Lenny amd64 su un Q9450 con DDR3 a 1333MHz La RAM richiede 3,3 s per boost::multi_array rispetto a 0,6 s per boost::array.

#include <iostream> 
#include <time.h> 
#include "boost/array.hpp" 
#include "boost/multi_array.hpp" 

using namespace boost; 

enum {N=1024}; 

typedef multi_array<char,3> M; 
typedef array<array<array<char,N>,N>,N> C; 

// Forward declare to avoid being optimised away 
static void clear(M& m); 
static void clear(C& c); 

int main(int,char**) 
{ 
    const clock_t t0=clock(); 

    { 
    M m(extents[N][N][N]); 
    clear(m); 
    } 

    const clock_t t1=clock(); 

    { 
    std::auto_ptr<C> c(new C); 
    clear(*c); 
    } 

    const clock_t t2=clock(); 

    std::cout 
    << "multi_array: " << (t1-t0)/static_cast<float>(CLOCKS_PER_SEC) << "s\n" 
    << "array  : " << (t2-t1)/static_cast<float>(CLOCKS_PER_SEC) << "s\n"; 

    return 0; 
} 

void clear(M& m) 
{ 
    for (M::index i=0;i<N;i++) 
    for (M::index j=0;j<N;j++) 
     for (M::index k=0;k<N;k++) 
    m[i][j][k]=1; 
} 


void clear(C& c) 
{ 
    for (int i=0;i<N;i++) 
    for (int j=0;j<N;j++) 
     for (int k=0;k<N;k++) 
    c[i][j][k]=1; 
} 

Answer 9

Probabilmente, non è rilevante in quanto questa è una vecchia questione, ma è possibile utilizzare la libreria Armadillo, che fornisce molti tipi di dati di algebra lineare orientata e funzioni.

Di seguito è riportato un esempio per il vostro problema specifico:

// In C++11 
Mat<bool> matrix = { 
    { true, true}, 
    { false, false}, 
}; 

// In C++98 
Mat<bool> matrix; 
matrix << true << true << endr 
     << false << false << endr; 

Answer 10

il mio modo preferito per memorizzare un grafico è vector<set<int>>; n elementi nel vettore (nodi 0..n-1),> = 0 elementi in ogni insieme (bordi). Non dimenticare di aggiungere una copia inversa di ogni bordo bidirezionale.