Por que as matrizes de comprimento variável não fazem parte do padrão C++?

Question

Não usei muito C nos últimos anos.Quando eu li essa questão hoje me deparei com alguma sintaxe C com a qual não estava familiarizado.

Aparentemente em Capítulo 99 a seguinte sintaxe é válida:

void foo(int n) {
    int values[n]; //Declare a variable length array
}

Este parece ser um recurso bastante útil.Já houve uma discussão sobre adicioná-lo ao padrão C++ e, em caso afirmativo, por que foi omitido?

Algumas razões potenciais:

• É difícil para os fornecedores de compiladores implementarem
• Incompatível com alguma outra parte do padrão
• A funcionalidade pode ser emulada com outras construções C++

O padrão C++ afirma que o tamanho do array deve ser uma expressão constante (8.3.4.1).

Sim, claro que percebo que no exemplo do brinquedo poderíamos usar std::vector<int> values(m);, mas isso aloca memória do heap e não da pilha.E se eu quiser um array multidimensional como:

void foo(int x, int y, int z) {
    int values[x][y][z]; // Declare a variable length array
}

o vector versão fica bem desajeitada:

void foo(int x, int y, int z) {
    vector< vector< vector<int> > > values( /* Really painful expression here. */);
}

As fatias, linhas e colunas também serão potencialmente espalhadas por toda a memória.

Olhando para a discussão em comp.std.c++ está claro que esta questão é bastante controversa, com alguns nomes de peso em ambos os lados da discussão.Certamente não é óbvio que um std::vector é sempre uma solução melhor.

Answer 1

Recentemente, houve uma discussão sobre isso iniciada na Usenet: Por que não há VLAs em C++ 0x.

Concordo com aquelas pessoas que parecem concordar que ter que criar um array potencialmente grande na pilha, que geralmente tem pouco espaço disponível, não é bom.O argumento é que, se você souber o tamanho de antemão, poderá usar um array estático.E se você não souber o tamanho de antemão, escreverá um código inseguro.

Os VLAs C99 podem fornecer um pequeno benefício de serem capazes de criar pequenos arrays sem desperdiçar espaço ou chamar construtores para elementos não utilizados, mas eles introduzirão mudanças bastante grandes no sistema de tipos (você precisa ser capaz de especificar tipos dependendo dos valores de tempo de execução - isso ainda não existe no C++ atual, exceto para new especificadores de tipo de operador, mas eles são tratados especialmente, para que o tempo de execução não escape do escopo do new operador).

Você pode usar std::vector, mas não é exatamente a mesma coisa, pois usa memória dinâmica e fazê-lo usar o próprio alocador de pilha não é exatamente fácil (o alinhamento também é um problema).Também não resolve o mesmo problema, porque um vetor é um contêiner redimensionável, enquanto os VLAs têm tamanho fixo.O Matriz Dinâmica C++ proposta pretende introduzir uma solução baseada em biblioteca, como alternativa a um VLA baseado em linguagem.No entanto, até onde eu sei, não fará parte do C++ 0x.

Answer 2

(Fundo:Tenho alguma experiência na implementação de compiladores C e C++.)

Matrizes de comprimento variável no C99 foram basicamente um passo em falso.Para apoiar os VLAs, o C99 teve que fazer as seguintes concessões ao bom senso:

• sizeof x não é mais sempre uma constante em tempo de compilação;o compilador às vezes deve gerar código para avaliar um sizeof-expressão em tempo de execução.

• Permitindo VLAs bidimensionais (int A[x][y]) exigiu uma nova sintaxe para declarar funções que usam VLAs 2D como parâmetros: void foo(int n, int A[][*]).

• Menos importante no mundo C++, mas extremamente importante para o público-alvo de programadores de sistemas embarcados do C, declarar um VLA significa mastigar um arbitrariamente grande pedaço de sua pilha.Isto é um garantido estouro de pilha e falha.(Sempre que você declarar int A[n], você está afirmando implicitamente que tem 2 GB de pilha sobrando.Afinal, se você sabe "n é definitivamente menor que 1000 aqui", então você simplesmente declararia int A[1000].Substituindo o número inteiro de 32 bits n para 1000 é uma admissão de que você não tem ideia de como deveria ser o comportamento do seu programa.)

Ok, então vamos falar sobre C++ agora.Em C++, temos a mesma forte distinção entre "sistema de tipos" e "sistema de valores" que C89 tem... mas realmente começamos a confiar nisso de uma forma que C não tem.Por exemplo:

template<typename T> struct S { ... };
int A[n];
S<decltype(A)> s;  // equivalently, S<int[n]> s;

Se n não eram uma constante em tempo de compilação (ou seja, se A eram de tipo variavelmente modificado), então qual seria o tipo de S?Seria Stipo de também ser determinado apenas em tempo de execução?

E quanto a isso:

template<typename T> bool myfunc(T& t1, T& t2) { ... };
int A1[n1], A2[n2];
myfunc(A1, A2);

O compilador deve gerar código para alguma instanciação de myfunc.Como deveria ser esse código?Como podemos gerar esse código estaticamente, se não sabemos o tipo de A1 em tempo de compilação?

Pior, e se acontecer em tempo de execução que n1 != n2, para que !std::is_same<decltype(A1), decltype(A2)>()?Nesse caso, a chamada para myfunc nem deveria compilar, porque a dedução do tipo de modelo deve falhar!Como poderíamos emular esse comportamento em tempo de execução?

Basicamente, C++ está caminhando na direção de empurrar cada vez mais decisões para tempo de compilação:geração de código de modelo, constexpr avaliação de função e assim por diante.Enquanto isso, o C99 estava ocupado promovendo tradicionalmente tempo de compilação decisões (por ex. sizeof) no tempo de execução.Com isso em mente, realmente faz sentido despender algum esforço tentando integrar VLAs estilo C99 em C++?

Como todos os outros respondentes já apontaram, C++ fornece muitos mecanismos de alocação de heap (std::unique_ptr<int[]> A = new int[n]; ou std::vector<int> A(n); Sendo os óbvios) quando você realmente deseja transmitir a idéia "Não tenho idéia de quanta carneiro eu preciso". E o C ++ fornece um modelo bacana de manipulação de exceções para lidar com a situação inevitável de que a quantidade de RAM necessária é maior que a quantidade de RAM que você possui.Mas espero esse A resposta dá uma boa ideia de por que os VLAs do estilo C99 foram não uma boa opção para C++ — e nem mesmo uma boa opção para C99.;)

---

Para saber mais sobre o tema, veja N3810 "Alternativas para extensões de array", artigo de Bjarne Stroustrup de outubro de 2013 sobre VLAs.O ponto de vista de Bjarne é muito diferente do meu;N3810 se concentra mais em encontrar um bom C++ish sintaxe para as coisas e em desencorajar o uso de arrays brutos em C++, enquanto me concentrei mais nas implicações para a metaprogramação e o sistema de tipos.Não sei se ele considera as implicações da metaprogramação/sistema de tipos resolvidas, solucionáveis ​​ou simplesmente desinteressantes.

Answer 3

Você sempre pode usar alloca() para alocar memória na pilha em tempo de execução, se desejar:

void foo (int n)
{
    int *values = (int *)alloca(sizeof(int) * n);
}

Ser alocado na pilha implica que ele será liberado automaticamente quando a pilha for desenrolada.

Nota rápida:Conforme mencionado na página man do Mac OS X para alloca(3), "A função alloca() depende da máquina e do compilador;seu uso é desencorajado." Só para você saber.

Answer 4

Em meu próprio trabalho, percebi que toda vez que eu queria algo como arrays automáticos de comprimento variável ou alloca(), eu realmente não me importava que a memória estivesse fisicamente localizada na pilha da CPU, apenas que ela veio de algum alocador de pilha que não incorresse em viagens lentas para a pilha geral.Portanto, eu tenho um objeto por thread que possui alguma memória a partir da qual pode enviar/popar buffers de tamanho variável.Em algumas plataformas eu permito que isso cresça via mmu.Outras plataformas têm um tamanho fixo (geralmente acompanhado por uma pilha de CPU de tamanho fixo porque não há mmu).De qualquer forma, uma plataforma com a qual trabalho (um console de jogos portátil) tem pouca pilha de CPU porque reside em uma memória rápida e escassa.

Não estou dizendo que nunca será necessário colocar buffers de tamanho variável na pilha da CPU.Honestamente, fiquei surpreso quando descobri que isso não era padrão, pois certamente parece que o conceito se encaixa bem na linguagem.Para mim, porém, os requisitos "tamanho variável" e "deve estar fisicamente localizado na pilha da CPU" nunca surgiram juntos.O que importa é velocidade, então criei meu próprio tipo de "pilha paralela para buffers de dados".

Answer 5

Existem situações em que a alocação de memória heap é muito cara em comparação com as operações executadas.Um exemplo é a matemática matricial.Se você trabalha com matrizes pequenas, digamos de 5 a 10 elementos e faz muita aritmética, a sobrecarga do malloc será realmente significativa.Ao mesmo tempo, tornar o tamanho uma constante em tempo de compilação parece um desperdício e inflexibilidade.

Acho que o C++ é tão inseguro por si só que o argumento para "tentar não adicionar mais recursos inseguros" não é muito forte.Por outro lado, como C++ é indiscutivelmente a linguagem de programação mais eficiente em tempo de execução, os recursos que o tornam ainda mais útil são sempre úteis:Pessoas que escrevem programas de desempenho crítico usarão em grande parte C++ e precisam do máximo de desempenho possível.Mover coisas de uma pilha para outra é uma dessas possibilidades.Reduzir o número de blocos de heap é outra.Permitir VLAs como membros do objeto seria uma maneira de conseguir isso.Estou trabalhando nessa sugestão.É um pouco complicado de implementar, é certo, mas parece bastante factível.

Answer 6

Parece que estará disponível em C++ 14:

https://en.wikipedia.org/wiki/C%2B%2B14#Runtime-sized_one_dimensional_arrays

Atualizar:Não foi incluído no C++ 14.

Answer 7

Isso foi considerado para inclusão em C++/1x, mas foi descartado (esta é uma correção ao que eu disse anteriormente).

De qualquer forma, seria menos útil em C++, pois já temos std::vector para preencher esse papel.

Answer 8

Use std::vector para isso.Por exemplo:

std::vector<int> values;
values.resize(n);

A memória será alocada no heap, mas isso apresenta apenas uma pequena desvantagem de desempenho.Além disso, é aconselhável não alocar grandes blocos de dados na pilha, pois seu tamanho é bastante limitado.

Answer 9

C99 permite VLA.E coloca algumas restrições sobre como declarar o VLA.Para detalhes, consulte 6.7.5.2 da norma.C++ não permite VLA.Mas o g++ permite isso.

Answer 10

Matrizes como essa fazem parte do C99, mas não fazem parte do C++ padrão.como outros já disseram, um vetor é sempre uma solução muito melhor, e é provavelmente por isso que matrizes de tamanho variável não estão no padrão C++ (ou no padrão C++ 0x proposto).

Aliás, para perguntas sobre "por que" o padrão C++ é do jeito que é, o grupo de notícias moderado da Usenet comp.std.c++ é o lugar para ir.

Answer 11

Se você souber o valor em tempo de compilação, poderá fazer o seguinte:

template <int X>
void foo(void)
{
   int values[X];

}

Editar:Você pode criar um vetor que usa um alocador de pilha (alloca), já que o alocador é um parâmetro de modelo.

Answer 12

Eu tenho uma solução que realmente funcionou para mim.Eu não queria alocar memória por causa da fragmentação de uma rotina que precisava ser executada muitas vezes.A resposta é extremamente perigosa, então use por sua conta e risco, mas aproveita a montagem para reservar espaço na pilha.Meu exemplo abaixo usa uma matriz de caracteres (obviamente outra variável de tamanho exigiria mais memória).

void varTest(int iSz)
{
    char *varArray;
    __asm {
        sub esp, iSz       // Create space on the stack for the variable array here
        mov varArray, esp  // save the end of it to our pointer
    }

    // Use the array called varArray here...  

    __asm {
        add esp, iSz       // Variable array is no longer accessible after this point
    } 
}

Os perigos aqui são muitos, mas vou explicar alguns:1.Alterar o tamanho variável no meio do caminho mataria a posição 2 da pilha.O excesso de limites de matriz destruiria outras variáveis ​​e o possível código 3.Isso não funciona em uma compilação de 64 bits ...precisa de uma montagem diferente para aquela (mas uma macro pode resolver esse problema).4.Específico do compilador (pode ter problemas para alternar entre compiladores).Eu não tentei, então realmente não sei.

Answer 13

Você precisa de uma expressão constante para declarar um array em C/C++.

Para matrizes de tamanho dinâmico, você precisa alocar memória no heap e, em seguida, gerenciar o tempo de elevação dessa memória.

void foo(int n) {
    int* values = new int[n]; //Declare a variable length array
    [...]
    delete [] values;
}