Maneira estranha de alocar array bidimensional?

110

Em um projeto, alguém empurrou esta linha:

double (*e)[n+1] = malloc((n+1) * sizeof(*e));

O que supostamente cria uma matriz bidimensional de (n + 1) * (n + 1) duplas.

Supostamente , digo, porque até agora ninguém a quem eu perguntei poderia me dizer o que isso faz, exatamente, nem de onde se originou ou por que deveria funcionar (que supostamente funciona, mas ainda não estou comprando).

Talvez esteja faltando algo óbvio, mas agradeceria se alguém pudesse explicar acima da linha para mim. Porque pessoalmente, eu me sentiria muito melhor se usássemos algo que realmente entendêssemos.

User1291
fonte
15
Mesmo se funcionar, dispare o empurrador.
Martin James,
22
@MartinJames Por quê? De outra forma, como você alocaria um array 2D na memória adjacente? Uma matriz 1D mutilada? Isso é programação dos anos 90, temos VLAs agora.
Lundin,
43
Para o registro, essa é a única maneira de alocar dinamicamente uma matriz 2D real.
Quentin
15
@Kninnug Não, isso declararia uma matriz de ponteiros, não uma matriz 2D. Se você deseja um array 2D, não há razão para alocar um array de ponteiros. Ele é lento devido à fragmentação do heap e à baixa utilização da memória cache, e não é seguro porque você não pode usá-lo como um array (com memcpy etc). Além disso, o código está inchado. Você precisaria de várias chamadas free () e seria fácil causar vazamentos de memória. Por mais difundido que esse código seja, ele é simplesmente ruim.
Lundin,
15
Este problema teria sido mais claro para explicar / responder se a amostra não tivesse usado as mesmas dimensões avaliadas, n+1mas em vez dissodouble (*e)[rows] = malloc(columns * sizeof *e);
chux - Reintegrar Monica em

Respostas:

87

A variável eé um ponteiro para uma matriz de n + 1elementos do tipo double.

Usar o operador dereference em efornece o tipo base eque é "matriz de n + 1elementos do tipo double".

A mallocchamada simplesmente pega o tipo base de e(explicado acima) e obtém seu tamanho, multiplica-o por n + 1e passa esse tamanho para a mallocfunção. Essencialmente, alocando um array de n + 1arrays de n + 1elementos de double.

Algum cara programador
fonte
3
@MartinJames sizeof(*e)é equivalente a sizeof(double [n + 1]). Multiplique isso por n + 1e você terá o suficiente.
Algum programador cara
24
@MartinJames: O que há de errado nisso? Não é tão penetrante, ele garante que as linhas alocadas sejam contíguas e você pode indexá-lo como qualquer outro array 2D. Eu uso muito esse idioma no meu próprio código.
John Bode,
3
Pode parecer óbvio, mas isso só funciona para matrizes quadradas (mesmas dimensões).
Jens
18
@Jens: Apenas no sentido de que se você colocar n+1para ambas as dimensões, o resultado será quadrado. Se você fizer isso double (*e)[cols] = malloc(rows * sizeof(*e));, o resultado terá qualquer número de linhas e colunas que você especificou.
user2357112 suporta Monica em
9
@ user2357112 Agora que eu prefiro ver. Mesmo que isso signifique que você precisa adicionar int rows = n+1e int cols = n+1. Deus nos salve do código inteligente.
candied_orange
56

Essa é a maneira típica de alocar arrays 2D dinamicamente.

  • eé um ponteiro de array para um array do tipo double [n+1].
  • sizeof(*e)portanto, fornece o tipo do tipo apontado, que é o tamanho de um double [n+1]array.
  • Você aloca espaço para n+1essas matrizes.
  • Você define o ponteiro do array epara apontar para o primeiro array neste array de arrays.
  • Isso permite que você use ecomo e[i][j]para acessar itens individuais na matriz 2D.

Pessoalmente, acho que esse estilo é muito mais fácil de ler:

double (*e)[n+1] = malloc( sizeof(double[n+1][n+1]) );
Lundin
fonte
12
Boa resposta, exceto que discordo do seu estilo sugerido, preferindo o ptr = malloc(sizeof *ptr * count)estilo.
chux - Reintegrar Monica em
Boa resposta e gosto do seu estilo preferido. Uma pequena melhoria pode ser apontar que você precisa fazer isso dessa maneira, porque pode haver preenchimento entre as linhas que precisa ser levado em consideração. (Pelo menos, acho que é o motivo pelo qual você precisa fazer isso.) (Avise-me se estiver errado.)
davidbak
2
@davidbak É a mesma coisa. A sintaxe do array é meramente um código autodocumentado: ele diz "aloque espaço para um array 2D" com o próprio código-fonte.
Lundin,
1
@davidbak Nota: Uma pequena desvantagem do comentário malloc(row*col*sizeof(double)) ocorre quando row*col*sizeof()estoura, mas sizeof()*row*colisso não acontece. (ex .: linha, coluna int)
chux - Reintegrar Monica em
7
@davidbak: sizeof *e * (n+1)é mais fácil de manter; se você decidir alterar o tipo de base (de doublepara long double, por exemplo), então você só precisa alterar a declaração de e; você não precisa modificar a sizeofexpressão na mallocchamada (o que economiza tempo e protege você de alterá-la em um lugar, mas não no outro). sizeof *esempre lhe dará o tamanho certo.
John Bode
39

Esse idioma sai naturalmente da alocação de array 1D. Vamos começar alocando uma matriz 1D de algum tipo arbitrário T:

T *p = malloc( sizeof *p * N );

Simples, certo? A expressão *p tem tipo T, então sizeof *pdá o mesmo resultado que sizeof (T), então estamos alocando espaço suficiente para um Narray -element de T. Isso é verdade para qualquer tipoT .

Agora, vamos substituir Tpor um tipo de array como R [10]. Então nossa alocação se torna

R (*p)[10] = malloc( sizeof *p * N);

A semântica aqui é exatamente a mesma do método de alocação 1D; tudo o que mudou foi o tipo de p. Em vez de T *, é agora R (*)[10]. A expressão *ptem tipo Tque é tipo R [10], então sizeof *pé equivalente a sizeof (T)que é equivalente a sizeof (R [10]). Portanto, estamos alocando espaço suficiente para um array Npor 10elemento de R.

Podemos levar isso ainda mais longe, se quisermos; suponha que Rseja um tipo de array int [5]. Substitua isso Re teremos

int (*p)[10][5] = malloc( sizeof *p * N);

Mesma coisa - sizeof *pé o mesmo que sizeof (int [10][5]), e nós acabam alocando um pedaço contíguo de memória grande o suficiente para segurar uma Npor 10pelo 5conjunto de int.

Então esse é o lado da alocação; e o lado do acesso?

Lembre-se de que a []operação subscrito é definida em termos de aritmética de ponteiro: a[i]é definido como *(a + i)1 . Assim, o operador subscrito desreferencia [] implicitamente um ponteiro. Se pfor um ponteiro para T, você pode acessar o valor apontado desreferenciando explicitamente com o *operador unário :

T x = *p;

ou usando o []operador subscrito:

T x = p[0]; // identical to *p

Assim, se papontar para o primeiro elemento de uma matriz , você pode acessar qualquer elemento dessa matriz usando um subscrito no ponteiro p:

T arr[N];
T *p = arr; // expression arr "decays" from type T [N] to T *
...
T x = p[i]; // access the i'th element of arr through pointer p

Agora, vamos fazer nossa operação de substituição novamente e substituir Tpelo tipo de array R [10]:

R arr[N][10];
R (*p)[10] = arr; // expression arr "decays" from type R [N][10] to R (*)[10]
...
R x = (*p)[i];

Uma diferença imediatamente aparente; estamos desreferenciando explicitamente pantes de aplicar o operador subscrito. Não queremos subscrever em p, queremos subscrever em que p aponta (neste caso, o array arr[0] ). Desde unário *tem precedência menor do que o índice []operador, temos que usar parênteses para explicitamente grupo pcom *. Mas lembre-se de cima que *pé o mesmo que p[0], então podemos substituir isso por

R x = (p[0])[i];

ou apenas

R x = p[0][i];

Assim, se papontar para uma matriz 2D, podemos indexar nessa matriz da seguinte pforma:

R x = p[i][j]; // access the i'th element of arr through pointer p;
               // each arr[i] is a 10-element array of R

Levando isso à mesma conclusão acima e substituindo Rpor int [5]:

int arr[N][10][5];
int (*p)[10][5]; // expression arr "decays" from type int [N][5][10] to int (*)[10][5]
...
int x = p[i][j][k];

Isso funciona da mesma forma se papontar para um array regular ou se apontar para a memória alocada malloc.

Esse idioma tem os seguintes benefícios:

  1. É simples - apenas uma linha de código, em oposição ao método de alocação fragmentada
    T **arr = malloc( sizeof *arr * N );
    if ( arr )
    {
      for ( size_t i = 0; i < N; i++ )
      {
        arr[i] = malloc( sizeof *arr[i] * M );
      }
    }
    
  2. Todas as linhas da matriz alocada são * contíguas *, o que não é o caso com o método de alocação fragmentada acima;
  3. Desalocar o array é tão fácil com uma única chamada para free. Novamente, isso não é verdade com o método de alocação fragmentada, onde você precisa desalocar cada arr[i]antes de poder desalocar arr.

Às vezes, o método de alocação fragmentada é preferível, como quando seu heap está muito fragmentado e você não pode alocar sua memória como um bloco contíguo ou deseja alocar uma matriz "denteada" em que cada linha pode ter um comprimento diferente. Mas, em geral, esse é o melhor caminho a seguir.


1. Lembre-se de que os arrays não são ponteiros - em vez disso, as expressões de vetor são convertidas em expressões de ponteiro, conforme necessário.

John Bode
fonte
4
+1 Gosto da maneira como você apresenta o conceito: alocar uma série de elementos é possível para qualquer tipo, mesmo que esses elementos sejam arrays.
logo_writer
1
Sua explicação é muito boa, mas observe que a alocação de memória contígua não é um benefício até que você realmente precise dela. A memória contígua é mais cara do que a não contígua. Para matrizes 2D simples, não há diferença no layout da memória para você (exceto para o número de linhas para alocação e desalocação), então prefira usar memória não contígua.
Oleg Lokshyn