Três alternativas para alocação dinâmica de array bidimensional (matriz) em C++

Com alguma frequencia sou consultado por alunos de outras disciplinas que estão precisando alocar dinamicamente um array 2D (matriz) em C++. Existem  diversas soluções, com suas vantagens e desvantagens. Irei apresentar algumas alternativas para criação dinâmica de uma matriz de N linhas e M colunas de um tipo T, sendo os valores de N e M conhecidos em tempo de execução.

1) Alocação dinâmica como um array de arrays

Nesta solução, alocamos um vetor com N ponteiros para T e, para cada um destes ponteiros, alocamos um array de tamanho M. Como o primeiro array a ser alocado é um vetor de ponteiros, precisamos armazenar seu endereço em um ponteiro para ponteiro para T.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

#include <iostream> using namespace std; int main() { int n; cout << "N: "; cin >> n; //Num linhas int m; cout << "M: "; cin >> m; //Num colunas // Aloca dinamicamente um array de N ponteiros para float float **mat = new float*[n]; // Para cada um dos N ponteiros é alocado um array de M floats for(int i=0; i<n; ++i) mat[i] = new float[m]; // TODO: testar bad_alloc em ambos os casos // Usa como uma matriz normal for(int i=0; i<n; ++i) { for(int j=0; j<m; ++j) { mat[i][j] = (i * j)/2.0; cout << mat[i][j] << '\t'; } cout << endl; } // Deleta o array de cada uma das linhas for(int i=0; i<n; ++i) delete[] mat[i]; // Deleta o array de ponteiros delete[] mat; return 0; }

Desvantagens:  a) Muito código; b) Fraca localidade de referência (localidade espacial) entre as linhas; c) Dificulta para mudar o tamanho (de qualquer dimensão) depois dela ter sido alocada;
Vantagens: a) Acesso com a notação natural de matrix [i][j]; b) Como cada linha é alocada individualmente, não precisariam ter o mesmo tamanho, ou seja, podemos ter uma matriz não retangular.

 2) Alocar como um único array

Outra alternativa é alocar como um único array de tamanho N*M. Como um array C++ sempre é contíguo na memória, podemos usar aritmética de endereços para localizar os valores dentro deste. Uma matriz seria armazenada por linhas, então primeiro temos os elementos da linha [0], depois da [1] e assim por diante. Sendo M o tamanho de cada linha, a posição m[i][j] no array bidimensional corresponde ao elemento m[i+(j*M)] em um unidimensional.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

#include <iostream> using namespace std; int main() { int n; cout << "N: "; cin >> n; //Num linhas int m; cout << "M: "; cin >> m; //Num colunas // Aloca dinamicamente um array de N*M floats // TODO: testar bad_alloc float *mat = new float[n*m]; // Usa a "matriz" for(int i=0; i<n; ++i) { for(int j=0; j<m; ++j) { // m[i][j] está na memória no endereço (i+(j*m)) mat[j + i*m] = (i * j)/2.0; cout << mat[j + i*m] << '\t'; } cout << endl; } // Deleta o array delete[] mat; return 0; }

Desvantagens:  a) Não usa  a notação natural de matrix [i][j]. Poderia ser criada uma classe para encapsular o código e sobrecarregar operador (int i, int j) para retornar uma referência ao elemento [i][j] ou criar um vetor de acesso indireto, com N ponteiros para o primeiro elemento de cada uma das linhas; b) A matriz precisa ser retangular; c) Dificulta mudar o tamanho (de qualquer dimensão) depois dela ter sido alocada.
Vantagens: a) Localidade de referência ótima, pois toda a matriz está sequencial na memória, da mesma forma que as matrizes "normais" (não alocadas dinamicamente). b) Mais fácil de interfacear com bibliotecas externas que aceitem matrizes tradicionais como parâmetro.

3) Criar como um vector<vector<T>>

Sempre que viável, recomendo usar os containers da STL para armazenamento de dados. Neste caso criaremos a matriz como um vector de vector de T.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

#include <iostream> #include <vector> using namespace std; int main() { int n; cout << "N: "; cin >> n; //Num linhas int m; cout << "M: "; cin >> m; //Num colunas // 'mat' é um vector de vector de float // Foi construído como um vector de N elementos, cada um deles inicializado com um vector de floats tamanho M vector<vector<float>> mat(n, vector<float>(m)); // Usa como uma matriz normal for(int i=0; i<n; ++i) { for(int j=0; j<m; ++j) { mat[i][j] = (i * j)/2.0; cout << mat[i][j] << '\t'; } cout << endl; } return 0; }

Desvantagens:  a) Fraca localidade espacial;
Vantagens: a) Código conciso; b) A classe vector gerencia a memória alocada (não precisa delete); c) A matriz não precisa ser retangular. d) É possível redimensionar facilmente a matriz depois de criada. Para acrencentar um novo elemento à linha i, basta mat[i].push_back(valor); Para adicionar uma nova linha de tamanho m, basta: mat.push_back(move(vector<float>(m)));

Quanto ao uso com bibliotecas externas, existem muitas que são compatíveis com a STL então pode não ser um problema. Na própria biblioteca padrão encontramos <numeric> e <valarray> que poderiam facilmente ser aproveitadas nesta alternativa. Se a biblioteca foi criada para ter interface binária com C puro então teríamos problema de compatibilidade.  Então, não coloco este ponto nem como vantagem nem desvantagem.

Conclusão

Considerando-se as vantagens e desvantagens de cada solução a terceira alternativa se destaca e é a que eu recomendaria, a priori, sem conhecer os requisitos do problema em questão. Mas, como sempre, a melhor solução depende do caso. Se o desempenho for fundamental ou for necessário no projeto uma biblioteca como a BLAS ou MPI, aí a segunda alternativa é mais apropriada (toda a matriz poderia ser transmitida em um único MPI_Send, por exemplo).
Como quarta alternativa, caso o seu projeto já estiver usando a BOOST, ou você pretende fazer uso desta importante ferramenta, vale a pena dar uma olhada na Boost.MultiArray.

Qual vocês optam? Comentem aí!