Como esse pedaço de código determina o tamanho da matriz sem usar sizeof ()?

134

Passando por algumas perguntas da entrevista em C, encontrei uma pergunta dizendo "Como encontrar o tamanho de uma matriz em C sem usar o operador sizeof?", Com a seguinte solução. Funciona, mas não consigo entender o porquê.

#include <stdio.h>

int main() {
    int a[] = {100, 200, 300, 400, 500};
    int size = 0;

    size = *(&a + 1) - a;
    printf("%d\n", size);

    return 0;
}

Como esperado, ele retorna 5.

edit: as pessoas apontaram esta resposta, mas a sintaxe difere um pouco, ou seja, o método de indexação

size = (&arr)[1] - arr;

então acredito que ambas as perguntas são válidas e têm uma abordagem ligeiramente diferente para o problema. Obrigado a todos pela imensa ajuda e explicação completa!

janojlic
fonte
13
Bem, não consigo encontrá-lo, mas parece estritamente falando. O Anexo J.2 declara explicitamente: O operando do operador unário * tem um valor inválido é um comportamento indefinido. Aqui &a + 1não está apontando para nenhum objeto válido, portanto é inválido.
Eugene Sh.
5
Relacionado: É *((*(&array + 1)) - 1)seguro usar para obter o último elemento de uma matriz automática? . tl; dr *(&a + 1)invoca Undefined Behvaior
Spikatrix 16/05/19
5
Possível duplicado de tamanho Find of array sem usar sizeof em C
Alma Do
@AlmaDo bem, a sintaxe difere um pouco, ou seja, a parte da indexação, por isso acredito que essa questão ainda é válida por si só, mas posso estar errado. Obrigado por apontar!
janojlic 17/05/19
1
@janojlicz Eles são essencialmente iguais, porque (ptr)[x]é o mesmo que *((ptr) + x).
SS Anne

Respostas:

135

Quando você adiciona 1 a um ponteiro, o resultado é a localização do próximo objeto em uma sequência de objetos do tipo apontado (isto é, uma matriz). Se papontar para um intobjeto, p + 1apontará para o próximo intem uma sequência. Se papontar para uma matriz de 5 elementos de int(nesse caso, a expressão &a), p + 1apontará para a próxima matriz de 5 elementos deint uma sequência.

Subtrair dois ponteiros (desde que ambos apontem para o mesmo objeto de matriz ou um esteja apontando um além do último elemento da matriz) gera o número de objetos (elementos da matriz) entre esses dois ponteiros.

A expressão &aproduz o endereço de ae tem o tipo int (*)[5](ponteiro para a matriz de 5 elementos de int). A expressão &a + 1origina o endereço da próxima série 5-elemento de intsequência a, e tem também o tipo int (*)[5]. A expressão *(&a + 1)desreferencia o resultado de &a + 1, de modo que produz o endereço do primeiro intapós o último elemento de a, e possui o tipo int [5], que nesse contexto "decai" para uma expressão do tipo int *.

Da mesma forma, a expressão a"decai" para um ponteiro para o primeiro elemento da matriz e tem tipo int *.

Uma imagem pode ajudar:

int [5]  int (*)[5]     int      int *

+---+                   +---+
|   | <- &a             |   | <- a
| - |                   +---+
|   |                   |   | <- a + 1
| - |                   +---+
|   |                   |   |
| - |                   +---+
|   |                   |   |
| - |                   +---+
|   |                   |   |
+---+                   +---+
|   | <- &a + 1         |   | <- *(&a + 1)
| - |                   +---+
|   |                   |   |
| - |                   +---+
|   |                   |   |
| - |                   +---+
|   |                   |   |
| - |                   +---+
|   |                   |   |
+---+                   +---+

São duas visualizações do mesmo armazenamento - à esquerda, estamos vendo-o como uma sequência de matrizes de 5 elementos int, enquanto à direita, estamos vendo-o como uma sequência de int. Eu também mostro as várias expressões e seus tipos.

Esteja ciente de que a expressão *(&a + 1)resulta em um comportamento indefinido :

...
Se o resultado apontar um para além do último elemento do objeto de matriz, ele não deverá ser usado como o operando de um operador unário * avaliado.

C Online Draft de 2011 , 6.5.6 / 9

John Bode
fonte
13
O texto “não deve ser usado” é oficial: C 2018 6.5.6 8.
Eric Postpischil
@EricPostpischil: Você tem um link para o rascunho pré-pub de 2018 (semelhante ao N1570.pdf)?
John Bode
1
@ JohnBode: Esta resposta tem um link para a Wayback Machine . Verifiquei o padrão oficial na minha cópia comprada.
Eric Postpischil
7
Então, se alguém escrevesse size = (int*)(&a + 1) - a;esse código seria completamente válido? : o
Gizmo
@ Gizmo eles provavelmente não escreveram isso porque dessa forma você precisa especificar o tipo de elemento; o original provavelmente foi escrito definido como uma macro para uso genérico em diferentes tipos de elementos.
Leushenko 17/05/19
35

Esta linha é da maior importância:

size = *(&a + 1) - a;

Como você pode ver, ele primeiro pega o endereço de ae adiciona um. Em seguida, desreferencia esse ponteiro e subtrai o valor original adele.

A aritmética do ponteiro em C faz com que isso retorne o número de elementos na matriz, ou 5. Adicionando um e &aé um ponteiro para a próxima matriz de 5 ints depois a. Depois disso, esse código desreferencia o ponteiro resultante e subtrai a(um tipo de matriz que se deteriorou para um ponteiro) disso, fornecendo o número de elementos na matriz.

Detalhes sobre como a aritmética do ponteiro funciona:

Digamos que você tenha um ponteiro xyzque aponte para um inttipo e contenha o valor (int *)160. Quando você subtrai qualquer número de xyz, C especifica que a quantidade real subtraída xyzé esse número vezes o tamanho do tipo para o qual aponta. Por exemplo, se você subtraísse 5de xyz, o valor xyzresultante seria xyz - (sizeof(*xyz) * 5)se a aritmética do ponteiro não se aplicasse.

Como aé uma matriz de 5 inttipos, o valor resultante será 5. No entanto, isso não funcionará com um ponteiro, apenas com uma matriz. Se você tentar isso com um ponteiro, o resultado será sempre 1.

Aqui está um pequeno exemplo que mostra os endereços e como isso é indefinido. O lado esquerdo mostra os endereços:

a + 0 | [a[0]] | &a points to this
a + 1 | [a[1]]
a + 2 | [a[2]]
a + 3 | [a[3]]
a + 4 | [a[4]] | end of array
a + 5 | [a[5]] | &a+1 points to this; accessing past array when dereferenced

Isso significa que o código está subtraindo ade &a[5](ou a+5), dando 5.

Observe que esse é um comportamento indefinido e não deve ser usado sob nenhuma circunstância. Não espere que o comportamento disso seja consistente em todas as plataformas e não o use em programas de produção.

SS Anne
fonte
27

Hmm, eu suspeito que isso é algo que não teria funcionado nos primeiros dias de C. É inteligente, no entanto.

Executando as etapas uma por vez:

  • &a obtém um ponteiro para um objeto do tipo int [5]
  • +1 obtém o próximo objeto, assumindo que há uma matriz desses
  • * efetivamente converte esse endereço em ponteiro de tipo para int
  • -a subtrai os dois ponteiros int, retornando a contagem de instâncias int entre eles.

Não tenho certeza de que seja completamente legal (neste caso, quero dizer advogado jurídico - não funcionará na prática), considerando algumas operações do tipo em andamento. Por exemplo, você só pode "subtrair" dois ponteiros quando eles apontam para elementos na mesma matriz. *(&a+1)foi sintetizado acessando outra matriz, embora uma matriz pai, portanto não é realmente um ponteiro para a mesma matriz que a. Além disso, enquanto você pode sintetizar um ponteiro após o último elemento de uma matriz e pode tratar qualquer objeto como uma matriz de 1 elemento, a operação de dereferencing ( *) não é "permitida" nesse ponteiro sintetizado, mesmo que não tem comportamento neste caso!

Suspeito que, nos primeiros dias de C (sintaxe K&R, alguém?), Uma matriz se decompôs em um ponteiro muito mais rapidamente, portanto, *(&a+1)pode retornar apenas o endereço do próximo ponteiro do tipo int **. As definições mais rigorosas do C ++ moderno permitem que o ponteiro para o tipo de matriz exista e saiba o tamanho da matriz, e provavelmente os padrões C seguiram o exemplo. Todo o código de função C usa apenas ponteiros como argumentos, portanto a diferença técnica visível é mínima. Mas estou apenas adivinhando aqui.

Esse tipo de pergunta detalhada sobre legalidade geralmente se aplica a um intérprete C ou a uma ferramenta do tipo fiapo, em vez do código compilado. Um interpretador pode implementar uma matriz 2D como uma matriz de ponteiros para matrizes, porque há menos um recurso de tempo de execução a ser implementado; nesse caso, desmarcando o +1 seria fatal e, mesmo que funcionasse, daria a resposta errada.

Outra possível fraqueza pode ser que o compilador C possa alinhar a matriz externa. Imagine se fosse uma matriz de 5 caracteres ( char arr[5]), quando o programa o executa &a+1, está invocando o comportamento da "matriz da matriz". O compilador pode decidir que uma matriz de matriz de 5 caracteres ( char arr[][5]) é realmente gerada como uma matriz de matriz de 8 caracteres ( char arr[][8]), para que a matriz externa se alinhe bem. O código que estamos discutindo agora reportaria o tamanho da matriz como 8, e não 5. Não estou dizendo que um compilador em particular faria isso definitivamente, mas poderia.

Gem Taylor
fonte
Justo. No entanto, por razões difíceis de explicar, todo mundo usa sizeof () / sizeof ()?
Gem Taylor
5
A maioria das pessoas faz. Por exemplo, sizeof(array)/sizeof(array[0])fornece o número de elementos em uma matriz.
SS Anne
É permitido ao compilador C alinhar a matriz, mas não estou convencido de que seja permitido alterar o tipo da matriz depois de fazer isso. O alinhamento seria implementado de maneira mais realista ao inserir bytes de preenchimento.
22419 Kevin
1
Subtrair ponteiros não se limita a apenas dois ponteiros na mesma matriz - também é permitido que os ponteiros estejam um após o final da matriz. &a+1é definido. Como observa John Bollinger, *(&a+1)não é, pois tenta desreferenciar um objeto que não existe.
Eric Postpischil
5
Um compilador não pode implementar um char [][5]as char arr[][8]. Uma matriz é apenas os objetos repetidos nela; não há preenchimento. Além disso, isso quebraria o exemplo (não normativo) 2 em C 2018 6.5.3.4 7, que nos diz que podemos calcular o número de elementos em uma matriz com sizeof array / sizeof array[0].
Eric Postpischil