Una forma adecuada de crear una matriz en C++

Question

Quiero crear una matriz de adyacencia para un gráfico. Como he leído que no es seguro usar matrices del formulario matrix[x][y] porque no comprueban el rango, decidí usar la clase de plantilla vectorial del stl. Todo lo que necesito almacenar en la matriz son valores booleanos. Así que mi pregunta es si usar std::vector<std::vector<bool>* >* produce demasiada sobrecarga o si hay una manera más simple para una matriz y cómo puedo inicializarla adecuadamente.

EDIT: Muchas gracias por las respuestas rápidas. Me di cuenta de que, por supuesto, no necesito punteros. El tamaño de la matriz se inicializará al principio y no cambiará hasta el final del programa. Es para un proyecto escolar, así que sería bueno escribir un código "agradable", aunque técnicamente el rendimiento no es demasiado importante. Usar el STL está bien. Usar algo como boost, probablemente no sea apreciado.

Answer 1

Considere también cuán grande es su gráfica/matriz, ¿el rendimiento importa mucho? ¿Es el gráfico estático o puede crecer con el tiempo, p. agregando nuevos bordes?

Answer 2

Tenga en cuenta que también se puede utilizar boost.ublas para la creación y manipulación de matrices y también boost.graph para representar y manipular gráficos en un número de maneras, así como el uso de algoritmos sobre ellos, etc.

Edición: De todos modos, haciendo una versión de gama-cheque de un vector para sus propósitos no es una cosa difícil:

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

en cuenta que también tendría que añadir la versión const de los operadores, y/o iteradores, y el extraño uso de excepciones, pero entiendes la idea.

Answer 3

Recuerde std::vector no hace la verificación de rango también.

Answer 4

Lo que haría sería crear mi propia clase para manejar matrices (probablemente como una matriz [x * y] porque estoy más acostumbrado a C (y tendría mi propia comprobación de límites), pero podría usar vectores o cualquier otra subestructura en esa clase).

Haga que sus cosas funcionen primero y luego preocúpese de qué tan rápido se ejecutan. Si diseña la clase correctamente, puede extraer su implementación de matriz [x * y] y reemplazarla con vectores o máscaras de bits o lo que quiera sin cambiar el resto del código.

no estoy totalmente seguro, pero creo que eso es lo que las clases eran para, la capacidad de abstraer la aplicación fuera de la vista y proporcionar sólo la interfaz :-)

Answer 5

mejor manera:

Haga su propia clase matricial, de esa manera puede controlar hasta el último aspecto de la misma, incluida la comprobación de rango.

por ejemplo. Si le gusta la notación "[x] [y]", haga esto:

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. Si programa así, entonces C++ es tan seguro como todos esos otros idiomas "seguros".

Answer 6

Además de todas las respuestas que se han publicado hasta ahora, puede hacer bien en consultar el C++ FAQ Lite. Las preguntas 13.10 - 13.12 y 16.16 - 16.19 cubren varios temas relacionados con la creación de su propia clase de matriz. Verá un par de formas diferentes de almacenar los datos y sugerencias sobre cómo escribir mejor los operadores de subíndices.

Además, si su gráfica es lo suficientemente escasa, es posible que no necesite una matriz. Puede usar std::multimap para asignar cada vértice a los que conecta.

Answer 7

El vector estándar NO realiza la comprobación de rango por defecto.

es decir, el operador [] no realiza una comprobación de rango.

El método en() es similar a [] pero hace una comprobación de rango.
Lanzará una excepción fuera de rango.

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

Otras notas: ¿Por qué un vector de punteros < >?
Puede tener fácilmente un vector <Objeto>. Ahora no hay necesidad de preocuparse por la administración de la memoria (es decir, fugas).

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

Nota: Vector <bool> está sobrecargado y no muy eficiente (es decir, esta estructura se ha optimizado para el tamaño no velocidad) (Es algo que ahora se reconoce como probablemente un error por el comité de estándares).

Si conoce el tamaño de la matriz en tiempo de compilación, podría usar std :: bitset?

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

o si se define el tiempo de ejecución uso impulso :: dynamic_bitset

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

Todo lo anterior le permitirá hacer:

m[6][3] = true; 

Answer 8

Si desea 'C' rendimiento de la matriz , pero con seguridad adicional y semántica similar a STL (iteradores, begin() & end() etc.), use boost::array.

Básicamente es una envoltura con plantilla para matrices 'C' con algunos NDEBUG-comprobaciones de rango escalables (y también algunos accessors de lanzamiento de excepciones std::range_error).

yo uso cosas como

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

en lugar de

float m[4][4]; 

todo el tiempo y funciona muy bien (con typedefs apropiadas para mantener el nivel de detalle abajo, de todos modos).

---

ACTUALIZACIÓN: Después de alguna discusión en los comentarios aquí del rendimiento relativo de boost::array vs boost::multi_array, me gustaría señalar que este código, compilado con g++ -O3 -DNDEBUG en Debian/Lenny amd64 en un Q9450 con DDR3 de 1333 MHz RAM toma 3.3s para boost::multi_array vs 0.6s para 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

Probablemente, no es relevante ya que esto es una cuestión de edad, pero se puede usar la biblioteca Armadillo, que ofrece muchos tipos de datos orientados álgebra lineal y funciones.

A continuación se muestra un ejemplo para su problema específico:

// 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

mi forma favorita para almacenar un gráfico es vector<set<int>>; n elementos en el vector (nodos 0..n-1),> = 0 elementos en cada conjunto (bordes). Simplemente no olvides agregar una copia inversa de cada borde bidireccional.