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

Não usei muito C nos últimos anos. Quando li essa pergunta hoje, deparei-me com uma sintaxe C com a qual não estava familiarizada.

Aparentemente, em C99, a seguinte sintaxe é válida:

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

Parece um recurso bastante útil. Houve alguma discussão sobre como adicioná-lo ao padrão C ++ e, se sim, por que ele foi omitido?

Algumas razões possíveis:

• Cabeludo 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 da matriz deve ser uma expressão constante (8.3.4.1).

Sim, é claro que percebo que no exemplo de brinquedo se poderia usar std::vector<int> values(m);, mas isso aloca memória da pilha e não da pilha. E se eu quiser uma matriz multidimensional como:

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

a vectorversão se torna bastante 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 comp.std.c++, fica claro que essa questão é bastante controversa com alguns nomes muito pesados ​​nos dois lados do argumento. Certamente não é óbvio que a std::vectoré sempre uma solução melhor.

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

Eu concordo com as pessoas que parecem concordar que ter que criar uma grande variedade potencial na pilha, que geralmente tem apenas pouco espaço disponível, não é bom. O argumento é que, se você souber o tamanho de antemão, poderá usar uma matriz estática. E se você não souber o tamanho de antemão, escreverá um código não seguro.

Os VLAs C99 podem fornecer um pequeno benefício de poder criar matrizes pequenas 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 especificar tipos dependendo dos valores de tempo de execução - isso ainda não existe no C ++ atual, exceto newos especificadores de tipo de operador, mas eles são tratados especialmente, para que o tempo de execução não escape do escopo do newoperador).

Você pode usar std::vector, mas não é o mesmo, 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 são de tamanho fixo. A proposta C ++ Dynamic Array visa apresentar uma solução baseada em biblioteca, como alternativa a um VLA baseado em linguagem. No entanto, não fará parte do C ++ 0x, tanto quanto eu sei.

(Histórico: 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 dar suporte aos VLAs, o C99 teve que fazer as seguintes concessões ao bom senso:

• sizeof xnem sempre é uma constante em tempo de compilação; o compilador às vezes deve gerar código para avaliar uma sizeofexpressão em tempo de execução.

• Permitindo VLAs bidimensionais ( int A[x][y]) necessária uma nova sintaxe para declarar funções que levam 2D VLAs 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 da C, declarar um VLA significa mastigar um pedaço arbitrariamente grande da sua pilha. Este é um estouro e empilhamento garantidos da pilha. (Sempre que você declara int A[n], está implicitamente afirmando que possui 2 GB de pilha de sobra. Afinal, se você sabe que " né definitivamente menor que 1000 aqui", então basta declarar int A[1000]. Substituir o número inteiro de 32 bits npor 1000é uma admissão que você não tem idéia de qual deve 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 o C89 possui ... mas realmente começamos a confiar nele de maneiras 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 nnão fosse uma constante em tempo de compilação (ou seja, se Afosse do tipo modificado de forma variável), qual seria o tipo de terra S? O Stipo também seria determinado apenas em tempo de execução?

Que tal 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 deve ser esse código? Como podemos gerar estaticamente esse código, se não sabemos o tipo de A1em tempo de compilação?

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

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

Como todos os outros respondentes já apontaram, o C ++ fornece muitos mecanismos de alocação de heap ( std::unique_ptr<int[]> A = new int[n];ou std::vector<int> A(n);os mais óbvios) quando você realmente deseja transmitir a idéia "Não faço ideia de quanta RAM eu possa precisar". E o C ++ fornece um modelo bacana de tratamento 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 que esta resposta lhe dê uma boa idéia de por que os VLAs no estilo C99 não eram adequados para C ++ - e nem mesmo para C99. ;)

Para obter mais informações sobre o assunto, consulte N3810 "Alternativas para extensões de matriz" , artigo de outubro de 2013 de Bjarne Stroustrup sobre VLAs. O ponto de vista de Bjarne é muito diferente do meu; O N3810 se concentra mais em encontrar uma boa sintaxe C ++ ish para as coisas e em desencorajar o uso de matrizes brutas em C ++, enquanto eu 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 meramente desinteressantes.

Uma boa publicação no blog que atinge muitos desses mesmos pontos é "Uso legítimo de matrizes de comprimento variável" (Chris Wellons, 27/10/2019).

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 ela será automaticamente liberada quando a pilha se desenrolar.

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

Em meu próprio trabalho, percebi que toda vez que desejava algo como matrizes automáticas de comprimento variável ou alloca (), 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 teve viagens lentas para o heap geral. Então, eu tenho um objeto por thread que possui alguma memória a partir da qual ele pode enviar / armazenar buffers de tamanho variável. Em algumas plataformas, permito que isso cresça via mmu. Outras plataformas têm um tamanho fixo (geralmente acompanhado por uma pilha de CPU de tamanho fixo também porque não há mmu). Uma plataforma com a qual eu trabalho (um console de jogos portátil) possui uma preciosa pilha de CPU, pois reside em uma memória rápida e escassa.

Não estou dizendo que nunca é 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, os requisitos "tamanho variável" e "devem estar fisicamente localizados na pilha da CPU" nunca surgiram juntos. Tem sido sobre velocidade, então fiz meu próprio tipo de "pilha paralela para buffers de dados".

Há 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, diga 5 a 10 elementos e faça muita aritmética, a sobrecarga do malloc será realmente significativa. Ao mesmo tempo, tornar o tamanho um tempo de compilação constante parece muito dispendioso e inflexível.

Eu acho que o C ++ é tão inseguro que o argumento para "tentar não adicionar mais recursos não seguros" não é muito forte. Por outro lado, como o C ++ é sem dúvida o recurso de linguagem de programação mais eficiente em tempo de execução, o que o torna ainda mais útil: as pessoas que escrevem programas críticos de desempenho usam, em larga medida, o C ++ e precisam de tanto desempenho quanto possível. Mover coisas de pilha para pilha é uma dessas possibilidades. Reduzir o número de blocos de heap é outro. 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.

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

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

Atualização: não foi incluída no C ++ 14.

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

De qualquer forma, seria menos útil em C ++, pois já temos std::vectorque preencher essa função.

Use std :: vector para isso. Por exemplo:

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

A memória será alocada no heap, mas isso contém 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.

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

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 as matrizes de tamanho variável não estão no padrão C ++ (ou no padrão C ++ 0x proposto).

BTW, para perguntas sobre "por que" o padrão C ++ é como é, o grupo de notícias moderado da Usenet comp.std.c ++ é o lugar para onde ir.

Se você conhece o valor no momento da compilação, pode fazer o seguinte:

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

}

Editar: você pode criar um vetor que use um alocador de pilha (alloca), pois o alocador é um parâmetro de modelo.

Eu tenho uma solução que realmente funcionou para mim. Eu não queria alocar memória por causa da fragmentação em uma rotina que precisava ser executada várias vezes. A resposta é extremamente perigosa; portanto, use-a por seu próprio 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 explicarei alguns: 1. Alterar o tamanho da variável no meio eliminaria a posição da pilha 2. Ultrapassar os limites da matriz destruiria outras variáveis ​​e possíveis códigos 3. Isso não funciona em 64 bits construir ... precisa de uma montagem diferente para essa (mas uma macro pode resolver esse problema). 4. Específico do compilador (pode haver problemas ao se mover entre compiladores). Eu não tentei, então realmente não sei.