Por que um array precisa ter um tamanho constante? O que impede ele de ter um tamanho variável?
3 Respostas
Confusão na pergunta
Nada impede, ele pode ser dinâmico segundo o padrão C99, ainda que raramente isso seja usado. Note que ele não é nada mágico, é só um truque para dar a ilusão de que o tamanho varia.
Mas o comum realmente é ser estático.
Ser estático não significa que ele não possa ter seu tamanho definido em tempo de execução, muito pelo contrário. Então a pergunta do título é até um pouco esquisita (ainda que compreensível). Porque a inicialização do array é variável sim, mesmo em arrays estáticos. Esses arrays não podem ter seu tamanho mudado em tempo de execução.
Dificuldade de ter tamanho elástico
O tamanho de nenhum tipo de dado pode ser variável por questão da organização da memória. Tudo o que você vê que tem tamanho variável na verdade é uma estrutura que usa algum truque para mudar de tamanho. Os truques mais comuns são:
- copiar o objeto para outro lugar, o mais usado;
- ter uma lista ligada, uma árvore ou outra estrutura de dados que quebra uma estrutura maior em pequenos pedaços interligados, então abstratamente você vê uma coisa só, mas no concreto existem vários dados com tamanho constante;
- outro tipo de estrutura que consiga gerar essa elasticidade, em geral algo híbrido ou derivado dessas, por exemplo uma árvore.
Este problema é semelhante ao que causa fragmentação de arquivos. Não é uma limitação dos computadores, menos ainda do C, é uma limitação físico-matemática.
Pense que a memória é um caminhão, você vai colocando caixas dentro dele, como você vai mudar o tamanho de uma caixa?
Vamos dizer que ela tivesse a capacidade de crescer sozinha, teria que empurrar todas as outras para trás. Essa seria uma possibilidade, mas imagine o custo de mudar todos os outros dados que podem estar atrás do array que quer aumentar de tamanho. E imagine que mudando de lugar teria que mudar todos os apontadores para aquele dado. É mais fácil abandonar ele e usar um novo maior.
Não importa se o dado, neste caso o array, será alocado na stack ou no heap, ele precisa reservar um espaço específico de memória. Depois que isto for alocado outra coisa pode ser alocada logo em seguida.
Como aumentar o tamanho do dado anterior se logo em seguida foi alocada outra coisa?
Memória
-------------------------------------------------------------------
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
-------------------------------------------------------------------
\_______________________________________/\______/\/\__/
array de char total 20 bytes int char short
Mostra pra mim como você aumentaria o tamanho do array? Vai movimentar tudo o que está depois?
O máximo que poderia fazer seria diminuir o tamanho, mas aí ficaria um buraco na memória e o custo de administrar esses buracos não costuma compensar o ganho que teria, desperdiça memória.
Alocação na memória
Em C os arrays costumam ser reservados na stack. Como é uma pilha, em tese seria possível aumentar o tamanho se mais nada for colocado em cima dela, mas para saber se tem alguma coisa ou não complicaria o funcionamento da própria pilha, fazendo ela ficar pior no uso geral para ter uma ganho marginal no caso específico.
Se for diminuir não adianta porque o que está empilhado acima teria que ser mudado de lugar, o que também derrotaria o propósito de usar uma pilha organizada e não um monte geral (heap). E para que mexer em algo que provavelmente vai desaparecer em breve?
Arrays na stack costumam ser simples e raramente precisam ter seu tamanho mudado, em geral quando há esta necessidade é um bom indicador que deveria estar usando o heap. Não dá para realocar no stack, há menos controle.
Em computação tudo é tradeoff. Aí poderia se perguntar, por que não ter só stack que é melhor que o heap? Ou perguntar, por que não ter só heap que resolve todos os casos? São soluções para problemas diferentes. Assim como você pode escolher a forma de simular a variabilidade do tamanho de uma estrutura de dados de acordo com cada necessidade.
No heap os "arrays" funcionam de forma mais livre, em geral são representados por um ponteiro para uma área alocada. Você pode usar um realloc()
quando precisa mudar seu tamanho, mas cai naquele truque de mudar o dado de lugar. Não existe uma forma milagrosa de resolver isso, afinal dois corpos não podem ocupar o mesmo lugar ao mesmo tempo.
O uso de arrays no heap é um pouco mais complicado que isto, mas é melhor eu simplificar a definição para este propósito
Entenda que arrays não são ponteiros de fato, como muitas pessoas acham que são em C. Ponteiros são usados para simular o comportamento de um array e a notação de acesso de array pode ser usada para acessar endereços de memória a partir de um ponteiro. E obviamente que é possível usar o array mesmo no heap, mas isto é mais comum dentro de outra estrutura para reservar espaço dentro dela, afinal a função do array em C é reservar memória, e com ponteiros para o heap a alocação geralmente é feita com malloc()
já reservado o espaço.
Realocar não é tão caro
A própria memória costuma ser uma lista ligada de páginas (ou alguma outra estrutura que dá flexibilidade no mapeamento), então mover pode custar mais barato do que parece, já que ela pode só rearranjar os ponteiros para as páginas (nós) ao invés de mexer no dado. Isto depende do sistema operacional ou de um alocador de maior nível que pode ser usado em cima da alocação nativa do SO.
Outra otimização que é comum para evitar realocações é que estas estruturas de dados costumam alocar um tamanho maior do que realmente precisa evitando várias realocações. E isso costuma crescer exponencialmente, então quanto mais realoca mais espaço é reservado para evitar novas realocações porque esse padrão tende a se manter. É comum você esgotar a memória de um computador "parrudão" antes de fazer 30 realocações, sendo raro chegar perto disto e as primeiras serão mais baratas (quando não houver outras otimizações). Principalmente em casos onde se espera muitas realocações é comum iniciar o array com tamanho extra sobrando.
É melhor perder um pouco de memória do que exigir tanto processamento.
Estruturas de dados de alto nível
Talvez exceto por C todas as linguagens mainstream possuem estruturas de dados em sua biblioteca padrão que manipulam o array fixo para ter seu tamanho variável de forma transparente, usando um dos truques mencionados. Em geral usa-se um vector
ou list
ou um array
mais abstrato.
Todo programador C acaba descobrindo uma biblioteca extra ou fazendo sua própria estrutura de dados que facilite este tipo de coisa, mas a maioria dos estudantes de C nunca se tornam programadores profissionais em C, então eles nunca precisam muito disto já que nunca trabalham com problemas reais. Para os exercícios de faculdade ou estudo livre seguindo algum livro ou tutorial ele só terá que lidar com problemas simples que dá para fazer tudo na mão sem precisar de melhores abstrações.
Também há uma certa cultura entre os programadores C de não usar muitas abstrações que podem piorar a performance, consumo de memória ou mesmo esconder o que está sendo feito. Dá para gerenciar essa variabilidade na mão sem ser transparente.
Conclusão
Dá para inicializar um array com um tamanho desconhecido, não dá para ser variável até porque nada é inicializado com algo variável.
-
vi que tu marcou a minha postagem string “ilimitada” no entanto não ficou claro para mim qual a relação entre elas, embora eu tenha achado tua explicação aqui bem interessante, a minha dúvida permanece, o que eu entendi (com base no que perguntei e na tua referencia a este link) é que a única forma de criar uma string sem um limite preestabelecido seria por meio de uma pilha de
char
, ou seja, criar uma estrutura de dados inteira para receber valores verdadeiramente modulares, é isso mesmo?– bruno101Commented 30/05/2016 às 4:44 -
@bruno aqui deixa claro que não é possível criar nada ilimitado, algo que seja elástico de verdade. O que pode fazer é algo que abstraia a capacidade de trocar o tamanho do dado, mas ele ser ilimitado mesmo não é possível. Se eu fosse responder lá, basicamente iria responder o que está escrito aqui, talvez um pouco menos, mas certamente nada a mais, então não tem porque duplicar respostas.Acho que precisa ler o texto de novo, prestar atenção e seguir os links.Uma string "ilimitada" é simulada por uma lista de
char
c/ array que troca sua alocação sempre que não há mais espaço suficiente– Maniero ♦Commented 30/05/2016 às 11:10 -
Sim, eu entendo que quando se trata de recurso computacional é fisicamente impossível criar algo ilimitado, por isso das aspas, mas ainda não ficou claro para mim a forma que seria feito, pois até onde eu entendo, tanto por array quanto por ponteiro há a necessidade de se declarar o espaço alocado, no entanto o problema proposto seria no caso de não saber quanto de espaço o usuário gostaria de alocar, como o notepad, que pode ser escrito um caracter ou um textão, ao ler a tua explicação, o que entendi foi que o melhor caminho para isto seria através de uma pilha, ou entendi errado?– bruno101Commented 30/05/2016 às 22:26
-
Não, eu não falei de usar pilha para isto, o que eu falo de pilha é outra coisa, é justamente o fato de haver limitação. Tem que fazer uma lista ligada ou árvore ou fazer realocação quando o tamanho muda. Criei uma seção só para isto no final e destaquei bem os 2 truques da solução no começo.– Maniero ♦Commented 30/05/2016 às 23:12
-
Ah ok, acho que consegui entender a ideia, mas fiquei confuso quanto a forma de se utilizar o
realloc()
(achei um pouco vago o exemplo e a explicação do site oficial), mas vou dar uma estudada aqui, ver alguns livros, manuais, tutoriais sobre. Obrigado.– bruno101Commented 31/05/2016 às 1:28
De forma simplista, um array em C nada mais é do que um ponteiro que aponta para uma região de memória alocada cujo tamanho é resultado da multiplicação da quantidade de elementos pelo tamanho em bytes de cada um.
Na prática, nada impede de você usar quantos elementos quiser, além do limite superior dos elementos, entretanto como você não reservou aquele espaço, as chances são de que você vai acabar lendo ou escrevendo alguma outra estrutura e possivelmente disparando um erro em sistemas com memória protegida.
O que confunde quem usa C após contato com linguagens de mais alto nível é o comportamento esperado de certas estruturas de dados, isto é, que elas façam algum controle automático em determinadas situações.
Isso seria possível se um array fosse um objeto, adicionando determinada lógica ao método de adicionar elementos, ou se o acesso ao array fosse delegado a alguma rotina de sistema ao invés de ir direto na memória. Porém, em ambos os casos se perde justamente a vantagem da linguagem C, que é a eficiência máxima no acesso, pois o código é compilado diretamente para referências em memória e não em chamadas à rotinas intermediárias.
Nada impede um array de ter tamanho variável:
#include <stdio.h>
int main(void) {
int tamanho;
scanf("%i", &tamanho);
int array[tamanho];
}
-
3Os VLA (Variable Length Array) foram introduzidos em C na versão C99. Os compiladores para versões anteriores da linguagem não contemplam esta capacidade (o compilador da Microsoft, Visual Studio 2013, por exemplo).– pmgCommented 5/01/2016 às 10:18