Como lidar melhor com matrizes dinâmicas multidimensionais em C / C ++?

Qual é a maneira aceita / mais comumente usada para manipular matrizes multidimensionais dinâmicas (com todas as dimensões não conhecidas até o tempo de execução) em C e / ou C ++.

Estou tentando encontrar a maneira mais limpa de realizar o que esse código Java faz:

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

(lê de std_in apenas para esclarecer que as dimensões não são conhecidas até o tempo de execução).

Edit: Notei que esta questão é bastante popular, embora seja muito antiga. Eu realmente não concordo com a resposta mais votada. Eu acho que a melhor escolha para C é usar uma matriz unidimensional como Guge disse abaixo “Você pode alocar fils cols sizeof (int) e acessá-la pela tabela [row * cols + col].”

Há uma série de opções com C ++, se você realmente gosta de boost ou stl, então as respostas abaixo podem ser preferíveis, mas a escolha mais simples e provavelmente a mais rápida é usar um array dimensional único como em C.

Outra opção viável em C e C ++, se você quiser que a syntax [] [] seja a resposta de lillq na parte inferior, está construindo manualmente a matriz com muitos malloc’s.

Use boost :: multi_array .

Como no seu exemplo, a única coisa que você precisa saber em tempo de compilation é o número de dimensões. Aqui está o primeiro exemplo na documentação:

 #include "boost/multi_array.hpp" #include  int main () { // Create a 3D array that is 3 x 4 x 2 typedef boost::multi_array 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 sugerido nos comentários, aqui está um aplicativo de exemplo “simples” que permitem definir o tamanho do array multidimensional em tempo de execução, perguntando a partir da input do console. Aqui está um exemplo de saída deste aplicativo de exemplo (compilado com a constante dizendo que são 3 dimensões):

 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 

As partes importantes no código são a principal function onde obtemos as dimensões do usuário e criamos o array com:

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

E você pode ver que para acessar um elemento na matriz, é muito fácil: basta usar o operador () como nas seguintes funções:

 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: Eu compilei este aplicativo no VC9 + SP1 - recebi apenas alguns avisos esquecíveis.

Existem duas maneiras de representar uma matriz de duas dimensões em C ++. Um sendo mais flexível que o outro.

Matriz de matrizes

Primeiro, faça uma matriz de pointers e, em seguida, inicialize cada ponteiro com outra 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]; } } 

O problema com esse método é que sua segunda dimensão é alocada como muitos arrays, portanto, não facilita o trabalho do alocador de memory. Sua memory provavelmente será fragmentada, resultando em um desempenho pior. Ele oferece mais flexibilidade, já que cada array na segunda dimensão pode ter um tamanho diferente.

Grande matriz para manter todos os valores

O truque aqui é criar uma matriz enorme para armazenar todos os dados de que você precisa. A parte difícil é que você ainda precisa da primeira matriz de pointers se quiser poder acessar os dados usando a syntax [i] [j] da matriz.

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

A matriz int * não é obrigatória, pois você pode acessar seus dados diretamente no buffer calculando o índice no buffer a partir das coordenadas de duas dimensões do 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]; } } 

A regra para ter em mente

A memory do computador é linear e ainda será por muito tempo. Tenha em mente que as matrizes de 2 dimensões não são suportadas nativamente em um computador, portanto, a única maneira é "linearizar" a matriz em uma matriz de 1 dimensão.

Você pode alocar fils cols sizeof (int) e acessá-lo pela tabela [row * cols + col].

A maneira padrão sem usar boost é usar std :: vector:

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

Isso vai cuidar de novo / excluir a memory que você precisa automaticamente. Mas é bastante lento, já que o std::vector não é projetado principalmente para usá-lo assim (aninhando std::vector entre si). Por exemplo, toda a memory não é alocada em um bloco, mas separada para cada coluna. Além disso, as linhas não precisam ser todas da mesma largura. Mais rápido é usar um vetor normal e, em seguida, fazer o cálculo do índice como col_count * row + col para obter uma determinada linha e col:

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

Mas isso perderá a capacidade de indexar o vetor usando [x][y] . Você também tem que armazenar a quantidade de linhas e cols em algum lugar, enquanto usa a solução aninhada você pode obter a quantidade de linhas usando v.size() e a quantidade de cols usando v[0].size() .

Usando boost, você pode usar boost::multi_array , que faz exatamente o que você quer (veja a outra resposta).


Há também o caminho bruto usando matrizes nativas do C ++. Isso envolve bastante trabalho e não é de forma alguma melhor que a solução vetorial aninhada:

 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; 

Você tem que armazenar a quantidade de colunas e linhas que você criou em algum lugar desde que você não pode recebê-los do ponteiro.

Aqui está a maneira mais fácil de fazer isso em 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); } 

Isto é perfeitamente válido desde C99, no entanto, não é C ++ de qualquer padrão: C ++ requer que os tamanhos dos tipos de array sejam constantes de tempos de compilation. A esse respeito, C ++ está agora quinze anos atrás de C. E essa situação não vai mudar tão cedo (a proposta de matriz de tamanho variável para C ++ 17 não se aproxima da funcionalidade de matrizes de comprimento variável C99).

Matrizes 2D no estilo C em C e C ++ são um bloco de memory de tamanho de rows * columns * sizeof(datatype) bytes.

As dimensões reais [row] [column] existem apenas estaticamente em tempo de compilation. Não há nada lá dinamicamente em tempo de execução!

Então, como outros já mencionaram, você pode implementar

  int array [ rows ] [ columns ]; 

Como:

  int array [ rows * columns ] 

Ou como:

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

Próximo: Declarando uma matriz de tamanho variável. Em C isso é possível:

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

Em C, você pode simplesmente passar o array de tamanho variável da mesma forma que um array de tamanho não variável:

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

No entanto, em C ++ isso não é possível. Você precisa alocar a matriz usando alocação dinâmica, por exemplo:

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

ou preferencialmente (com gerenciamento de memory automatizado)

 std::vector array(rows * cols); 

Então as funções devem ser modificadas para aceitar dados unidimensionais:

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

Se você estiver usando C em vez de C ++, você pode querer olhar para a abstração Array_T na biblioteca C Interfaces and Implementations de Dave Hanson. É excepcionalmente limpo e bem projetado. Eu tenho meus alunos fazendo uma versão bidimensional como um exercício. Você poderia fazer isso ou simplesmente escrever uma function adicional que faça um mapeamento de índice, por exemplo,

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

É um pouco mais limpo ter uma estrutura separada onde você armazena a largura, a altura e um ponteiro para os elementos.

Recentemente me deparei com um problema semelhante. Eu não tinha o Boost disponível. Vetores de vetores mostraram-se bastante lentos em comparação com matrizes simples. Ter uma matriz de pointers torna a boot muito mais trabalhosa, porque você precisa percorrer todas as dimensões e inicializar os pointers, possivelmente tendo alguns tipos em cascata bastante complicados no processo, possivelmente com muitos typedefs.

ISENÇÃO DE RESPONSABILIDADE: Eu não tinha certeza se deveria postar isso como uma resposta, porque só responde parte da sua pergunta. Minhas desculpas pelo seguinte:

  • Eu não cobri como ler as dimensões da input padrão, como outros comentaristas haviam observado.
  • Isso é principalmente para C ++.
  • Eu codifiquei apenas esta solução para duas dimensões.

Eu decidi postar isso de qualquer maneira, porque vejo vetores de vetores trazidos com frequência em resposta a perguntas sobre matrizes multidimensionais em C ++, sem que ninguém mencione os aspectos de desempenho dele (se você se preocupa com isso).

Eu também interpretei a questão central desta questão para ser sobre como obter matrizes multidimensionais dinâmicas que podem ser usadas com a mesma facilidade que o exemplo Java da questão, ou seja, sem o incômodo de ter que calcular os índices com uma pseudo- matriz unidimensional multidimensional.

Não vi as extensões do compilador mencionadas nas outras respostas, como as fornecidas pelo GCC / G ++ para declarar matrizes multidimensionais com limites dynamics da mesma maneira que você faz com limites estáticos. Pelo que entendi, a questão não restringe as respostas ao padrão C / C ++. O ISO C99 aparentemente os suporta, mas em C ++ e versões anteriores de C eles parecem ser extensões específicas do compilador. Veja esta pergunta: Matrizes dinâmicas em C sem malloc?

Eu criei uma maneira que as pessoas possam gostar para C ++, porque é um código pequeno, tem a facilidade de uso dos arrays multidimensionais estáticos integrados e é tão rápido quanto.

 template  class Array2D { private: std::unique_ptr 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_]; } }; 

Você pode usá-lo assim. As dimensões não

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

Você pode adicionar uma afirmação, pelo menos a todas, exceto a última dimensão, e estender a ideia para mais de duas dimensões. Eu fiz um post no meu blog sobre formas alternativas de obter matrizes multidimensionais. Eu também sou muito mais específico sobre o desempenho relativo e o esforço de codificação lá.

Desempenho de matrizes dinâmicas multi-dimensionais em C ++

Não há como determinar o tamanho de um determinado array em C ++. A melhor maneira seria passar o comprimento de cada dimensão da matriz e usá-la em vez da propriedade .length da matriz.

Você poderia usar o malloc para realizar isto e ainda tê-lo acessível através do método normal de array [] [], verso do método array [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 }