¿Cómo manejo mejor las matrices multidimensionales dinámicas en C/C++?

Question

¿Cuál es la forma aceptada/más comúnmente utilizada para manipular matrices multidimensionales dinámicas (con todas las dimensiones no conocidas hasta el tiempo de ejecución) en C y/o C++.

estoy tratando de encontrar la manera más limpia para llevar a cabo lo que hace este código Java:

public static void main(String[] args){ 
Scanner sc=new Scanner(System.in); 
int rows=sc.nextInt(); 
int cols=sc.nextInt(); 
int[][] data=new int[rows][cols]; 
manipulate(data); 
} 

public static void manipulate(int[][] data){ 
    for(int i=0;i<data.length;i++) 
    for(int j=0;j<data[0].length.j++){ 
     System.out.print(data[i][j]);  
    }  
} 

(lee de std_in sólo para aclarar que las dimensiones no se conocen hasta el tiempo de ejecución).

Editar: Me di cuenta de que esta pregunta es bastante popular a pesar de que es bastante viejo. En realidad, no estoy de acuerdo con la respuesta más votado. Creo que la mejor opción para C es usar una matriz unidimensional como dice Guge a continuación "Puede asignar filas cols sizeof (int) y acceder a ella por la tabla [row * cols + col].".

Hay una serie de opciones con C++, si realmente te gusta impulso o STL a continuación las respuestas a continuación puede ser preferible, pero la opción más simple y probablemente más rápida es utilizar una matriz unidimensional como en C.

Otra opción viable en C y C++ si quieres la sintaxis [] [] es que la respuesta de lillq en la parte inferior es construir manualmente la matriz con muchos malloc.

Answer 1

No hay forma de determinar la longitud de una matriz dada en C++. La mejor forma sería pasar la longitud de cada dimensión de la matriz y usarla en lugar de la propiedad .length de la matriz misma.

Answer 2

Puede asignar filas cols sizeof (int) y acceder a ella por la tabla [row * cols + col].

Answer 3

Use boost::multi_array.

Como en su ejemplo, lo único que necesita saber en tiempo de compilación es el número de dimensiones. Aquí es el primer ejemplo en la documentación:

#include "boost/multi_array.hpp" 
#include <cassert> 

int 
main() { 
    // Create a 3D array that is 3 x 4 x 2 
    typedef boost::multi_array<double, 3> array_type; 
    typedef array_type::index index; 
    array_type A(boost::extents[3][4][2]); 

    // Assign values to the elements 
    int values = 0; 
    for(index i = 0; i != 3; ++i) 
    for(index j = 0; j != 4; ++j) 
     for(index k = 0; k != 2; ++k) 
     A[i][j][k] = values++; 

    // Verify values 
    int verify = 0; 
    for(index i = 0; i != 3; ++i) 
    for(index j = 0; j != 4; ++j) 
     for(index k = 0; k != 2; ++k) 
     assert(A[i][j][k] == verify++); 

    return 0; 
} 

Edit: Como se sugiere en los comentarios, here is a "simple" example aplicación que le permiten definir el tamaño de la matriz multidimensional en tiempo de ejecución, pidiendo desde la entrada de la consola. Aquí es un ejemplo de salida de esta aplicación de ejemplo (compilado con la constante diciendo que es 3 dimensiones):

Multi-Array test! 
Please enter the size of the dimension 0 : 4 

Please enter the size of the dimension 1 : 6 

Please enter the size of the dimension 2 : 2 

Text matrix with 3 dimensions of size (4,6,2) have been created. 

Ready! 
Type 'help' for the command list. 

>read 0.0.0 
Text at (0,0,0) : 
    "" 

>write 0.0.0 "This is a nice test!" 
Text "This is a nice test!" written at position (0,0,0) 

>read 0.0.0 
Text at (0,0,0) : 
    "This is a nice test!" 

>write 0,0,1 "What a nice day!" 
Text "What a nice day!" written at position (0,0,1) 

>read 0.0.0 
Text at (0,0,0) : 
    "This is a nice test!" 

>read 0.0.1 
Text at (0,0,1) : 
    "What a nice day!" 

>write 3,5,1 "This is the last text!" 
Text "This is the last text!" written at position (3,5,1) 

>read 3,5,1 
Text at (3,5,1) : 
    "This is the last text!" 

>exit 

Las partes importantes en el código son la principal función de donde obtenemos las dimensiones del usuario y crear la matriz con:

const unsigned int DIMENSION_COUNT = 3; // dimension count for this test application, change it at will :) 

// here is the type of the multi-dimensional (DIMENSION_COUNT dimensions here) array we want to use 
// for this example, it own texts 
typedef boost::multi_array< std::string , DIMENSION_COUNT > TextMatrix; 

// this provide size/index based position for a TextMatrix entry. 
typedef std::tr1::array<TextMatrix::index, DIMENSION_COUNT> Position; // note that it can be a boost::array or a simple array 

/* This function will allow the user to manipulate the created array 
    by managing it's commands. 
    Returns true if the exit command have been called. 
*/ 
bool process_command(const std::string& entry, TextMatrix& text_matrix); 

/* Print the position values in the standard output. */ 
void display_position(const Position& position); 

int main() 
{ 
    std::cout << "Multi-Array test!" << std::endl; 

    // get the dimension informations from the user 
    Position dimensions; // this array will hold the size of each dimension 

    for(int dimension_idx = 0; dimension_idx < DIMENSION_COUNT; ++dimension_idx) 
    { 
     std::cout << "Please enter the size of the dimension "<< dimension_idx <<" : "; 
     // note that here we should check the type of the entry, but it's a simple example so lets assume we take good numbers 
     std::cin >> dimensions[dimension_idx]; 
     std::cout << std::endl; 

    } 

    // now create the multi-dimensional array with the previously collected informations 
    TextMatrix text_matrix(dimensions); 

    std::cout << "Text matrix with " << DIMENSION_COUNT << " dimensions of size "; 
    display_position(dimensions); 
    std::cout << " have been created."<< std::endl; 
    std::cout << std::endl; 
    std::cout << "Ready!" << std::endl; 
    std::cout << "Type 'help' for the command list." << std::endl; 
    std::cin.sync(); 


    // we can now play with it as long as we want 
    bool wants_to_exit = false; 
    while(!wants_to_exit) 
    { 
     std::cout << std::endl << ">" ; 
     std::tr1::array< char, 256 > entry_buffer; 
     std::cin.getline(entry_buffer.data(), entry_buffer.size()); 

     const std::string entry(entry_buffer.data()); 
     wants_to_exit = process_command(entry, text_matrix); 
    } 

    return 0; 
} 

Y se puede ver que adherirse a un elemento de la matriz, que es muy fácil: sólo tiene que utilizar el operador() como en las siguientes funciones:

void write_in_text_matrix(TextMatrix& text_matrix, const Position& position, const std::string& text) 
{ 
    text_matrix(position) = text; 
    std::cout << "Text \"" << text << "\" written at position "; 
    display_position(position); 
    std::cout << std::endl; 
} 

void read_from_text_matrix(const TextMatrix& text_matrix, const Position& position) 
{ 
    const std::string& text = text_matrix(position); 
    std::cout << "Text at "; 
    display_position(position); 
    std::cout << " : "<< std::endl; 
    std::cout << " \"" << text << "\"" << std::endl; 
} 

Nota: compilé esta aplicación en VC9 + SP1, recibí solo algunas advertencias olvidables.

Answer 4

Si está utilizando C en lugar de C++, es posible que desee ver la abstracción Array_T en la biblioteca de Dave Hanson C Interfaces and Implementations. Es excepcionalmente limpio y bien diseñado. Mis alumnos hacen una versión bidimensional como ejercicio. Puede hacerlo o simplemente escribir una función adicional que haga un mapeo de índice, p.,

void *Array_get_2d(Array_T a, int width, int height, int i, int j) { 
    return Array_get(a, j * width, i, j); 
} 

Es un poco más limpio para tener una estructura separada en la que almacena la anchura, la altura, y un puntero a los elementos.

Answer 5

La manera estándar sin necesidad de impulso es utilizar std :: vector:

std::vector< std::vector<int> > v; 
v.resize(rows, std::vector<int>(cols, 42)); // init value is 42 
v[row][col] = ...; 

que se hará cargo de la nueva/borrar la memoria que necesita de forma automática. Pero es bastante lento, ya que std::vector no está diseñado principalmente para usarlo así (anidando std::vector entre sí). Por ejemplo, toda la memoria no está asignada en un bloque, sino separada para cada columna. Además, las filas no tienen que ser todas del mismo ancho. Más rápido es el uso de un vector normal, y luego hacer el cálculo del índice como col_count * row + col para llegar a una determinada fila y columna:

std::vector<int> v(col_count * row_count, 42); 
v[col_count * row + col) = ...; 

Pero esto va a perder la capacidad de indexar el vector usando [x][y]. También debe almacenar la cantidad de filas y columnas en algún lugar, mientras usa la solución anidada puede obtener la cantidad de filas usando v.size() y la cantidad de columnas usando v[0].size().

Usando boost, puede usar boost::multi_array, que hace exactamente lo que quiere (vea la otra respuesta).

---

También existe la forma cruda utilizando matrices nativas de C++. Esto conlleva bastante trabajo y no es en absoluto mejor que la solución vectorial anidado:

int ** rows = new int*[row_count]; 
for(std::size_t i = 0; i < row_count; i++) { 
    rows[i] = new int[cols_count]; 
    std::fill(rows[i], rows[i] + cols_count, 42); 
} 

// use it... rows[row][col] then free it... 

for(std::size_t i = 0; i < row_count; i++) { 
    delete[] rows[i]; 
} 

delete[] rows; 

usted tiene que almacenar la cantidad de columnas y filas que ha creado algún lugar ya que no puede recibirlos desde el puntero.

Answer 6

Arrays 2D de estilo C en C y C++ son un bloque de memoria de tamaño rows * columns * sizeof(datatype) bytes.

Las dimensiones reales [fila] [columna] solo existen estáticamente en el momento de la compilación. ¡No hay nada allí dinámicamente en tiempo de ejecución!

Así que, como otros han mencionado, se puede implementar

int array [ rows ] [ columns ]; 

Como:

int array [ rows * columns ] 

O como:

int * array = malloc (rows * columns * sizeof(int)); 

---

siguiente: Declarar una matriz de tamaño variable . En C esto es posible:

int main(int argc, char ** argv) 
{ 
    assert(argc > 2); 

    int rows = atoi(argv[1]); 
    int columns = atoi(argv[2]); 

    assert(rows > 0 && columns > 0); 
    int data [ rows ] [ columns ]; // Yes, legal! 

    memset(&data, 0, sizeof(data)); 

    print(rows, columns, data); 
    manipulate(rows, columns, data); 
    print(rows, columns, data); 
} 

---

En C que sólo puede pasar la matriz de tamaño variable alrededor de la misma como una matriz no de tamaño variable:

void manipulate(int theRows, int theColumns, int theData[theRows][theColumns]) 
{ 
    for ( int r = 0; r < theRows; r ++) 
    for (int c = 0; c < theColumns; C++ ) 
     theData[r][c] = r*10 + c; 
} 

Sin embargo, en C++ eso no es posible.Es necesario para asignar la matriz mediante la asignación dinámica, por ejemplo:

int *array = new int[rows * cols](); 

o preferiblemente (con gestión de memoria automatizada)

std::vector<int> array(rows * cols); 

entonces las funciones deben ser modificados para aceptar datos 1-dimensional:

void manipulate(int theRows, int theColumns, int *theData) 
{ 
    for ( int r = 0; r < theRows; r ++) 
    for (int c = 0; c < theColumns; C++ ) 
     theData[r * theColumns + c] = r*10 + c; 
} 

Answer 7

Hay dos formas de representar una matriz de 2 dimensiones en C++. Uno siendo más flexible que el otro.

matriz de matrices

En primer lugar crea un array de punteros, entonces inicializar cada puntero con otra matriz.

// First dimension 
int** array = new int*[3]; 
for(int i = 0; i < 3; ++i) 
{ 
    // Second dimension 
    array[i] = new int[4]; 
} 

// You can then access your array data with 
for(int i = 0; i < 3; ++i) 
{ 
    for(int j = 0; j < 4; ++j) 
    { 
     std::cout << array[i][j]; 
    } 
} 

El problema con este método es que su segunda dimensión se asigna el mayor número de matrices, por lo que no alivia el trabajo del asignador de memoria. Es probable que tu memoria esté fragmentada, lo que da como resultado un peor rendimiento. Sin embargo, proporciona más flexibilidad ya que cada matriz en la segunda dimensión podría tener un tamaño diferente.

Arsenal grande para contener todos los valores

El truco aquí es crear un arsenal masivo para contener todos los datos que necesita. La parte más difícil es que todavía necesita la primera matriz de punteros si desea poder acceder a los datos utilizando la sintaxis de la matriz [i] [j].

int* buffer = new int[3*4]; 
int** array = new int*[3]; 

for(int i = 0; i < 3; ++i) 
{ 
    array[i] = array + i * 4; 
} 

El int * array no es obligatoria ya que se podía acceder a sus datos directamente en tampón calculando el índice en el búfer partir de las coordenadas 2-dimensión de valor.

// You can then access your array data with 
for(int i = 0; i < 3; ++i) 
{ 
    for(int j = 0; j < 4; ++j) 
    { 
     const int index = i * 4 + j; 
     std::cout << buffer[index]; 
    } 
} 

la regla a tener en cuenta

memoria de computadora es lineal y seguirá siendo durante mucho tiempo. Tenga en cuenta que las matrices de 2 dimensiones no se admiten de forma nativa en una computadora, por lo que la única forma es "linealizar" la matriz en una matriz de 1 dimensión.

Answer 8

Puede usar malloc para lograr esto y aún así tenerlo accesible a través de la matriz normal [] [], frente al método de la matriz [rows * cols + cols].

main() 
{ 
    int i; 
    int rows; 
    int cols; 
    int **array = NULL; 

    array = malloc(sizeof(int*) * rows); 
    if (array == NULL) 
     return 0; // check for malloc fail 

    for (i = 0; i < rows; i++) 
    { 
     array[i] = malloc(sizeof(int) * cols) 
     if (array[i] == NULL) 
      return 0; // check for malloc fail 
    } 

    // and now you have a dynamically sized array 
} 

Answer 9

Recientemente me encontré con un problema similar. No tenía Boost disponible. Los vectores de vectores resultaron ser bastante lentos en comparación con los arreglos simples. Tener una serie de punteros hace que la inicialización sea mucho más laboriosa, porque tiene que iterar a través de cada dimensión e inicializar los punteros, posiblemente con algunos tipos bastante poco manejables y en cascada en el proceso, posiblemente con muchos typedefs.

DESCARGO DE RESPONSABILIDAD: No estaba seguro de si debería publicar esto como respuesta, ya que solo responde a una parte de su pregunta. Mis disculpas por lo siguiente:

• No cubrí cómo leer las dimensiones de la entrada estándar, como comentaron otros comentaristas.
• Esto es principalmente para C++.
• Solo he codificado esta solución para dos dimensiones.

he decidido publicar esto de todos modos, porque veo vectores de vectores criados con frecuencia en respuesta a las preguntas sobre matrices multidimensionales en C++, sin que nadie mencionar los aspectos de rendimiento del mismo (si se preocupan por él).

También interpreté la cuestión central de esta pregunta sobre cómo obtener matrices multidimensionales dinámicas que se pueden usar con la misma facilidad que el ejemplo de Java de la pregunta, es decir, sin la molestia de tener que calcular los índices con una matriz unidimensional pseudo-multidimensional.

No vi extensiones de compilador mencionadas en las otras respuestas, como las proporcionadas por GCC/G ++ para declarar matrices multidimensionales con límites dinámicos de la misma manera que lo hace con los límites estáticos. Por lo que entiendo, la pregunta no restringe las respuestas a C/C++ estándar. ISO C99 aparentemente los admite, pero en C++ y versiones anteriores de C parecen ser extensiones específicas del compilador. Ver esta pregunta: Dynamic arrays in C without malloc?

Se me ocurrió una forma que a las personas les podría gustar para C++, porque es un código pequeño, tiene la facilidad de uso de las matrices multidimensionales estáticas incorporadas, y es igual de rápido.

template <typename T> 
class Array2D { 
private: 
    std::unique_ptr<T> managed_array_; 
    T* array_; 
    size_t x_, y_; 

public: 
    Array2D(size_t x, size_t y) { 
     managed_array_.reset(new T[x * y]); 
     array_ = managed_array_.get(); 
     y_ = y; 
    } 
    T* operator[](size_t x) const { 
     return &array_[x * y_]; 
    } 
}; 

Puede usarlo así. Las dimensiones no

auto a = Array2D<int>(x, y); 
a[xi][yi] = 42; 

Se puede añadir una afirmación, al menos para todos excepto para la última dimensión y extender la idea de que más de dos dimensiones. He hecho una publicación en mi blog sobre formas alternativas de obtener matrices multidimensionales. También soy mucho más específico sobre el rendimiento relativo y el esfuerzo de codificación allí.

Performance of Dynamic Multi-Dimensional Arrays in C++

Answer 10

Aquí es la manera fácil de hacer esto en C:

void manipulate(int rows, int cols, int (*data)[cols]) { 
    for(int i=0; i < rows; i++) { 
     for(int j=0; j < cols; j++) { 
      printf("%d ", data[i][j]);  
     } 
     printf("\n"); 
    } 
} 

int main() { 
    int rows = ...; 
    int cols = ...; 
    int (*data)[cols] = malloc(rows*sizeof(*data)); 
    manipulate(rows, cols, data); 
    free(data); 
} 

Esto es perfectamente válido, ya que el C99, sin embargo, no es C++ de cualquier estándar: C++ requiere los tamaños de los tipos de matriz ser tiempos de compilación constantes. En ese sentido, C++ ahora está quince años detrás de C. Y esta situación no va a cambiar pronto (la propuesta de matriz de longitud variable para C++ 17 no se acerca a la funcionalidad de las matrices de longitud variable C99).