Quantos níveis de ponteiros podemos ter?

443

Quantos ponteiros ( *) são permitidos em uma única variável?

Vamos considerar o seguinte exemplo.

int a = 10;
int *p = &a;

Da mesma forma, podemos ter

int **q = &p;
int ***r = &q;

e assim por diante.

Por exemplo,

int ****************zz;
Parag
fonte
582
Se isso já se torna um problema real para você, você está fazendo algo muito errado.
ThiefMaster
279
Você pode continuar adicionando níveis de indicadores até que seu cérebro exploda ou o compilador derreta - o que acontecer mais cedo.
precisa saber é o seguinte
47
Como um ponteiro para um ponteiro é novamente, bem, apenas um ponteiro, não deve haver nenhum limite teórico. Talvez o compilador não será capaz de lidar com isso além de algum limite ridiculamente alta, mas bem ...
Christian Rau
73
com o mais novo c ++ você deve usar algo comostd::shared_ptr<shared_ptr<shared_ptr<...shared_ptr<int>...>>>
josefx
44
@josefx - isso mostra um problema no padrão C ++ - não há como elevar ponteiros inteligentes a potências. Devemos exigir imediatamente uma extensão para apoiar, por exemplo, (pow (std::shared_ptr, -0.3))<T> x;-0,3 níveis de indireção.
Steve314

Respostas:

400

O Cpadrão especifica o limite inferior:

5.2.4.1 Limites de conversão

276 A implementação deve poder traduzir e executar pelo menos um programa que contenha pelo menos uma instância de cada um dos seguintes limites: [...]

279 - 12 declaradores de ponteiro, array e função (em qualquer combinação) modificando um tipo aritmético, estrutura, união ou vazio em uma declaração

O limite superior é específico da implementação.

PP
fonte
121
O C ++ padrão "recomenda" que um apoio à implementação, pelo menos, 256. (Readability recomenda que você não exceder 2 ou 3, e mesmo assim: mais de um deve ser excepcional.)
James Kanze
22
Esse limite é sobre quantos em uma única declaração; não impõe um limite superior a quanto indireto você pode conseguir através de vários typedefs.
Kaz
11
@ Kaz - sim, isso é verdade. Porém, como a especificação (sem trocadilhos) especifica um limite inferior obrigatório, é o limite superior efetivo que todos os compiladores compatíveis com as especificações precisam dar suporte. Pode ser menor que o limite superior específico do fornecedor, é claro. Reformulado de forma diferente (para alinhá-lo com a pergunta do OP), é o máximo permitido pela especificação (qualquer outra coisa seria específica do fornecedor). Um pouco fora da tangente, os programadores devem (pelo menos no caso geral) tratar isso como seu limite superior (a menos que eles tenham um motivo válido para confiar em um limite superior específico do fornecedor) ... pensa-me.
Luis.espinal
5
Em outra nota, eu ia começar a me cortar se eu tivesse que trabalhar com o código que tinham cadeias dereferencing longo-burro (especialmente quando liberalmente salpicado por todo o lugar .)
luis.espinal
11
@beryllium: Normalmente, esses números vêm de uma pesquisa de software de pré-padronização. Nesse caso, presumivelmente, eles examinaram programas C comuns e compiladores C existentes e encontraram pelo menos um compilador que teria problemas com mais de 12 e / ou nenhum programa que quebrasse se você o restringisse a 12.
155

Na verdade, os programas C geralmente fazem uso de indiretos infinitos. Um ou dois níveis estáticos são comuns. Indireção tripla é rara. Mas infinito é muito comum.

O indireto infinito do ponteiro é obtido com a ajuda de uma estrutura, é claro, não com um declarador direto, o que seria impossível. E uma estrutura é necessária para que você possa incluir outros dados nessa estrutura nos diferentes níveis em que isso pode terminar.

struct list { struct list *next; ... };

agora você pode ter list->next->next->next->...->next. Isto é realmente apenas várias indireções ponteiro: *(*(..(*(*(*list).next).next).next...).next).next. E o .nexté basicamente um noop quando é o primeiro membro da estrutura, então podemos imaginar isso como ***..***ptr.

Realmente não há limite para isso, porque os links podem ser percorridos com um loop, em vez de uma expressão gigante como essa; além disso, a estrutura pode ser facilmente circular.

Portanto, em outras palavras, as listas vinculadas podem ser o exemplo final da adição de outro nível de indireção para resolver um problema, já que você o faz dinamicamente a cada operação de envio. :)

Kaz
fonte
48
Essa é uma questão completamente diferente - uma estrutura contendo um ponteiro para outra estrutura é muito diferente de um ponteiro-ponteiro. Um int ***** é um tipo distinto de um int ****.
fofo
12
Não é "muito" diferente. A diferença é fofa. Está mais próximo da sintaxe do que da semântica. Um ponteiro para um objeto ponteiro ou um ponteiro para um objeto de estrutura que contém um ponteiro? É o mesmo tipo de coisa. Chegar ao décimo elemento de uma lista são dez níveis de endereçamento indireto. (Naturalmente, a capacidade de exprimir uma estrutura infinita depende do tipo de estrutura serem capazes de apontar para si próprio através do tipo de estrutura incompleta de modo que list->nexte list->next->nextsão do mesmo tipo; caso contrário, teria que construir um tipo de infinito.)
Kaz
34
Eu não percebi conscientemente que seu nome é fofo quando usei a palavra "fofo". Influência subconsciente? Mas tenho certeza de que já usei a palavra dessa maneira antes.
Kaz
3
Lembre-se também de que, na linguagem de máquina, você pode iterar em algo como LOAD R1, [R1], desde que R1 seja um ponteiro válido a cada etapa. Não existem tipos envolvidos além de "palavra que contém um endereço". A existência ou não de tipos declarados não determina a indireção e quantos níveis ela possui.
Kaz
4
Não se a estrutura for circular. Se R1contém o endereço de um local que aponta para si mesmo, LOAD R1, [R1]pode ser executado em um loop infinito.
Kaz
83

Teoricamente:

Você pode ter quantos níveis de indireções desejar.

Praticamente:

Obviamente, nada que consome memória pode ser indefinido; haverá limitações devido aos recursos disponíveis no ambiente host. Portanto, praticamente existe um limite máximo para o que uma implementação pode suportar e a implementação deve documentá-la adequadamente. Portanto, em todos esses artefatos, o padrão não especifica o limite máximo, mas especifica os limites inferiores.

Aqui está a referência:

C99 Padrão 5.2.4.1 Limites de conversão:

- 12 declaradores de ponteiro, array e função (em qualquer combinação) modificando um tipo aritmético, de estrutura, união ou vazio em uma declaração.

Isso especifica o limite inferior que toda implementação deve suportar. Observe que em uma nota de rodapé, o padrão diz ainda:

18) As implementações devem evitar impor limites fixos de conversão sempre que possível.

Alok Save
fonte
16
Indireções não sobrecarregam nenhuma pilha!
Basile Starynkevitch
1
Corrigido, tive essa sensação de ler e responder ao q como limite de parâmetros sendo passados ​​para a função. Não sei porque ?!
Alok Salvar
2
@ basile - eu esperaria que a profundidade da pilha fosse um problema no analisador. Muitos algoritmos formais de análise têm uma pilha como componente principal. A maioria dos compiladores C ++ provavelmente usa uma variante de descendência recursiva, mas mesmo isso se baseia na pilha do processador (ou, de forma pedestre, na linguagem que age como se houvesse uma pilha do processador). Mais aninhamento de regras gramaticais significa uma pilha mais profunda.
Steve314
8
Indireções não sobrecarregam nenhuma pilha! -> Não! pilha do analisador pode transbordar. Como a pilha se relaciona com a indireção do ponteiro? Pilha do analisador!
Pavan Manjunath
Se *estiver sobrecarregado para um número de classes em uma linha, e cada sobrecarga retornar um objeto de outro tipo na linha, poderá haver um fluxo de pilha para essas chamadas de função em cadeia.
Nawaz 27/05
76

Como as pessoas disseram, não há limite "em teoria". No entanto, por interesse, executei isso com o g ++ 4.1.2 e funcionou com tamanho de até 20.000. A compilação foi bem lenta, então não tentei mais alto. Então, eu acho que o g ++ também não impõe nenhum limite. (Tente configurar size = 10e procurar no ptr.cpp se não for imediatamente óbvio.)

g++ create.cpp -o create ; ./create > ptr.cpp ; g++ ptr.cpp -o ptr ; ./ptr

create.cpp

#include <iostream>

int main()
{
    const int size = 200;
    std::cout << "#include <iostream>\n\n";
    std::cout << "int main()\n{\n";
    std::cout << "    int i0 = " << size << ";";
    for (int i = 1; i < size; ++i)
    {
        std::cout << "    int ";
        for (int j = 0; j < i; ++j) std::cout << "*";
        std::cout << " i" << i << " = &i" << i-1 << ";\n";
    }
    std::cout << "    std::cout << ";
    for (int i = 1; i < size; ++i) std::cout << "*";
    std::cout << "i" << size-1 << " << \"\\n\";\n";
    std::cout << "    return 0;\n}\n";
    return 0;
}
BoBTFish
fonte
72
Não consegui mais do que 98242 quando tentei. (Fiz o script em Python, dobrando o número *até obter um que falhou e o anterior que passou; fiz uma pesquisa binária nesse intervalo para o primeiro que falhou. O teste inteiro levou menos de um segundo )
James Kanze
63

Parece divertido de verificar.

  • Visual Studio 2010 (no Windows 7), você pode ter 1011 níveis antes de receber este erro:

    erro fatal C1026: estouro de pilha do analisador, programa muito complexo

  • gcc (Ubuntu), 100k + *sem falhas! Eu acho que o hardware é o limite aqui.

(testado apenas com uma declaração variável)

mihai
fonte
5
De fato, as produções para operadores unários são recursivas à direita, o que significa que um analisador de redução de turno deslocará todos os *nós para a pilha antes de poder fazer uma redução.
Kaz
28

Não há limite, veja o exemplo aqui .

A resposta depende do que você quer dizer com "níveis de indicadores". Se você quer dizer "Quantos níveis de indireção você pode ter em uma única declaração?" a resposta é "pelo menos 12."

int i = 0;

int *ip01 = & i;

int **ip02 = & ip01;

int ***ip03 = & ip02;

int ****ip04 = & ip03;

int *****ip05 = & ip04;

int ******ip06 = & ip05;

int *******ip07 = & ip06;

int ********ip08 = & ip07;

int *********ip09 = & ip08;

int **********ip10 = & ip09;

int ***********ip11 = & ip10;

int ************ip12 = & ip11;

************ip12 = 1; /* i = 1 */

Se você quer dizer "Quantos níveis de ponteiro você pode usar antes que o programa seja difícil de ler", isso é uma questão de gosto, mas há um limite. Ter dois níveis de indireção (um ponteiro para um ponteiro para alguma coisa) é comum. Mais do que isso, fica um pouco mais difícil pensar facilmente; não faça isso a menos que a alternativa seja pior.

Se você quer dizer "Quantos níveis de indireção de ponteiro você pode ter em tempo de execução", não há limite. Este ponto é particularmente importante para listas circulares, nas quais cada nó aponta para o próximo. Seu programa pode seguir os ponteiros para sempre.

Nandkumar Tekale
fonte
7
Há quase certamente um limite, já que o compilador deve acompanhar as informações em uma quantidade finita de memória. ( g++Anula com um erro interno em 98242 na minha máquina eu espero que o limite real vai depender da máquina e a carga Eu também não espere que este seja um problema no código real...)
James Kanze
2
Sim, @MatthieuM. : Eu apenas considerei teoricamente :) Obrigado James por responder
Nandkumar Tekale 10/04/12
3
Bem, listas ligadas não são realmente um ponteiro para um ponteiro, que é um ponteiro para uma estrutura que contém um ponteiro (ou isso ou você acaba fazendo um monte de fundição desnecessário)
Random832
1
@ Random832: Nand disse 'Se você quer dizer "Quantos níveis de indireto de ponteiro você pode ter em tempo de execução" ", ele estava removendo explicitamente a restrição de apenas falar de ponteiros para ponteiros (* n).
Larsh
1
Não entendi seu argumento: ' Não há limite, veja o exemplo aqui. 'O exemplo não prova que não há limite. Isso prova apenas que uma indireção de 12 estrelas é possível. Nenhum deles prova o circ_listexemplo da pergunta do OP: o fato de você poder percorrer uma lista de ponteiros não implica que o compilador possa compilar um indireto n-stars.
Alberto
24

Na verdade, é ainda mais engraçado com ponteiro para funções.

#include <cstdio>

typedef void (*FuncType)();

static void Print() { std::printf("%s", "Hello, World!\n"); }

int main() {
  FuncType const ft = &Print;
  ft();
  (*ft)();
  (**ft)();
  /* ... */
}

Como ilustrado aqui, isso fornece:

Olá Mundo!
Olá Mundo!
Olá Mundo!

E não envolve nenhuma sobrecarga de tempo de execução, portanto, você provavelmente pode empilhá-las o quanto quiser ... até que o compilador engasgue com o arquivo.

Matthieu M.
fonte
20

Não há limite . Um ponteiro é um pedaço de memória cujo conteúdo é um endereço.
Como você disse

int a = 10;
int *p = &a;

Um ponteiro para um ponteiro também é uma variável que contém o endereço de outro ponteiro.

int **q = &p;

Aqui qestá o ponteiro para o ponteiro que contém o endereço do pqual já está segurando o endereço dea .

Não há nada de especial em um ponteiro para um ponteiro.
Portanto, não há limite para a cadeia de ponitores que estão mantendo o endereço de outro ponteiro.
ie

 int **************************************************************************z;

é permitido.

Sachin Mhetre
fonte
17

Todo desenvolvedor de C ++ deveria ter ouvido falar do (in) famoso programador de três estrelas

E realmente parece haver alguma "barreira de ponteiro" mágica que precisa ser camuflada

Citação de C2:

Programador Três Estrelas

Um sistema de classificação para programadores C. Quanto mais indiretos forem seus indicadores (ou seja, quanto mais "*" antes de suas variáveis), maior será sua reputação. Os programadores C sem estrela são praticamente inexistentes, pois praticamente todos os programas não triviais exigem o uso de ponteiros. A maioria são programadores de uma estrela. Nos velhos tempos (bem, eu sou jovem, então esses parecem os velhos tempos), ocasionalmente, alguém encontrava um pedaço de código feito por um programador de três estrelas e tremia de admiração. Algumas pessoas até alegaram ter visto código de três estrelas com indicadores de função envolvidos, em mais de um nível de indireção. Pareceu tão real quanto OVNIs para mim.

Mare Infinitus
fonte
2
github.com/psi4/psi4public/blob/master/src/lib/libdpd/… e similares foram escritos por um programador de 4 estrelas. Ele também é um amigo meu e, se você ler o código o suficiente, entenderá o motivo pelo qual vale 4 estrelas.
21415 Jeff
13

Observe que existem duas perguntas possíveis aqui: quantos níveis de indireto de ponteiro podemos obter em um tipo C e quantos níveis de indireto de ponteiro podemos inserir um único declarador.

O padrão C permite que um máximo seja imposto ao primeiro (e fornece um valor mínimo para isso). Mas isso pode ser contornado através de várias declarações typedef:

typedef int *type0;
typedef type0 *type1;
typedef type1 *type2; /* etc */

Portanto, em última análise, esse é um problema de implementação conectado à idéia de quão grande / complexo um programa C pode ser criado antes de ser rejeitado, o que é muito específico do compilador.

Kaz
fonte
4

Eu gostaria de salientar que produzir um tipo com um número arbitrário de * 's é algo que pode acontecer com a metaprogramação de modelos. Esqueço o que estava fazendo exatamente, mas foi sugerido que eu pudesse produzir novos tipos distintos que tivessem algum tipo de meta-manobra entre eles usando recursivas tipos T * .

A metaprogramação de modelos é uma lenta descida à loucura, portanto, não é necessário dar desculpas ao gerar um tipo com vários milhares de níveis de indireção. É apenas uma maneira prática de mapear números inteiros peano, por exemplo, na expansão de modelos como uma linguagem funcional.

JDługosz
fonte
Admito que não entendo sua resposta completamente, mas isso me deu uma nova área para explorar. :)
ankush981
3

A regra 17.5 da norma MISRA C 2004 proíbe mais de 2 níveis de indicação indireta.

kostmo
fonte
15
Certamente essa é uma recomendação para programadores, não para compiladores.
Cole Johnson
3
Eu li o documento com a regra 17.5 sobre mais de 2 níveis de indicação indireta. E não necessariamente proíbe mais de 2 níveis. Ele afirma que a decisão deve ser seguida, já que mais de 2 níveis estão de acordo "non-compliant"com seus padrões. A palavra ou frase importante em suas decisões é o uso da palavra "should"desta declaração: Use of more than 2 levels of indirection can seriously impair the ability to understand the behavior of the code, and should therefore be avoided.Estas são diretrizes definidas por esta organização em oposição às regras definidas pelo padrão de idioma.
Francis Cugler
1

Não existe limite real, mas o limite existe. Todos os ponteiros são variáveis ​​que geralmente são armazenadas na pilha e não na pilha . A pilha geralmente é pequena (é possível alterar seu tamanho durante alguns links). Então, digamos que você tenha uma pilha de 4 MB, o que é tamanho bastante normal. Digamos que tenhamos ponteiro com tamanho de 4 bytes (o tamanho do ponteiro não é o mesmo, dependendo das configurações de arquitetura, destino e compilador).

Nesse caso 4 MB / 4 b = 1024, o número máximo possível seria 1048576, mas não devemos ignorar o fato de que outras coisas estão na pilha.

No entanto, alguns compiladores podem ter um número máximo de cadeias de ponteiros, mas o limite é o tamanho da pilha. Portanto, se você aumentar o tamanho da pilha durante o vínculo com o infinito e tiver uma máquina com memória infinita, que executa o SO que gerencia essa memória, assim você terá uma cadeia de ponteiros ilimitada.

Se você usar int *ptr = new int;e colocar o ponteiro na pilha, essa não é a maneira mais usual de limitar o tamanho da pilha, não a pilha.

EDIT Apenas perceba isso infinity / 2 = infinity. Se a máquina tiver mais memória, o tamanho do ponteiro aumentará. Portanto, se a memória é infinita e o tamanho do ponteiro é infinito, então são más notícias ... :)

ST3
fonte
4
A) Os ponteiros podem ser armazenados na pilha ( new int*). B) Um int*e um int**********têm o mesmo tamanho, pelo menos em arquiteturas razoáveis.
@rightfold A) Sim, os ponteiros podem ser armazenados na pilha. Mas seria algo muito diferente como criar contêiner que contém ponteiros que apontam para o próximo ponteiro anterior. B) Naturalmente int*e int**********com o mesmo tamanho, eu não disse que eles são diferentes.
ST3
2
Então não vejo como o tamanho da pilha é remotamente relevante.
@ rightfold Eu estive pensando sobre a maneira usual de distribuição de dados quando todos os dados estão no heap e na pilha, são apenas indicadores para esses dados. Seria a maneira usual , mas concordo que é possível colocar ponteiros na pilha.
ST3 30/07
"É claro que int * e um int ********** têm o mesmo tamanho" - o padrão não garante isso (embora eu não conheça nenhuma plataforma onde isso não seja verdade).
Martin Bonner apoia Monica
0

Depende do local onde você armazena os ponteiros. Se eles estão na pilha, você tem um limite bastante baixo . Se você armazená-lo na pilha, o limite é muito, muito, muito maior.

Veja este programa:

#include <iostream>

const int CBlockSize = 1048576;

int main() 
{
    int number = 0;
    int** ptr = new int*[CBlockSize];

    ptr[0] = &number;

    for (int i = 1; i < CBlockSize; ++i)
        ptr[i] = reinterpret_cast<int *> (&ptr[i - 1]);

    for (int i = CBlockSize-1; i >= 0; --i)
        std::cout << i << " " << (int)ptr[i] << "->" << *ptr[i] << std::endl;

    return 0;
}

Ele cria ponteiros de 1 milhão e, na mostra, em que ponto é fácil perceber o que a cadeia vai para a primeira variável number.

Entre. Ele usa 92KRAM, então imagine o quão profundo você pode ir.

ST3
fonte