¿Por qué las matrices de longitud variable no son parte del estándar C ++?

326

No he usado mucho C en los últimos años. Cuando leí esta pregunta hoy me encontré con una sintaxis de C con la que no estaba familiarizado.

Aparentemente en C99 la siguiente sintaxis es válida:

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

Esto parece una característica bastante útil. ¿Hubo alguna vez una discusión sobre cómo agregarlo al estándar C ++ y, de ser así, por qué se omitió?

Algunas posibles razones:

  • Peludo para los vendedores de compiladores para implementar
  • Incompatible con alguna otra parte del estándar.
  • La funcionalidad se puede emular con otras construcciones de C ++

El estándar C ++ establece que el tamaño de la matriz debe ser una expresión constante (8.3.4.1).

Sí, por supuesto, me doy cuenta de que en el ejemplo del juguete se podría usar std::vector<int> values(m);, pero esto asigna memoria del montón y no de la pila. Y si quiero una matriz multidimensional como:

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

la vectorversión se vuelve bastante torpe:

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

Los sectores, filas y columnas también se extenderán potencialmente por toda la memoria.

Al observar la discusión comp.std.c++, está claro que esta pregunta es bastante controvertida con algunos nombres muy pesados ​​en ambos lados de la discusión. Ciertamente no es obvio que a std::vectores siempre una mejor solución.

Andreas Brinck
fuente
3
Solo por curiosidad, ¿por qué necesita ser asignado en la pila? ¿Te asustan los problemas de rendimiento de asignación de montón?
Dimitri C.
32
@Dimitri En realidad no, pero no se puede negar que la asignación de la pila será más rápida que la asignación del montón. Y en algunos casos esto puede importar.
Andreas Brinck
11
La principal ventaja de las matrices de longitud variable es que todos los datos están muy juntos, por lo que cuando itera por esta matriz, lee y escribe bytes uno al lado del otro. Sus datos se obtienen en el caché y la CPU puede trabajar en ellos sin obtener y enviar los bytes a / desde la memoria.
Calmarius
44
Las matrices de longitud variable también se pueden usar para reemplazar las constantes del preprocesador con variables constantes estáticas. Además, en C no tiene otras opciones para VLA, y a veces es necesario escribir código C / C ++ portátil (compatible con ambos compiladores).
Yury
2
aparte, parece que clang ++ permite VLA.
user3426763

Respuestas:

204

Recientemente hubo una discusión sobre esto que comenzó en Usenet: ¿Por qué no hay VLA en C ++ 0x ?

Estoy de acuerdo con aquellas personas que parecen estar de acuerdo en que tener que crear una gran matriz potencial en la pila, que generalmente tiene poco espacio disponible, no es bueno. El argumento es que, si conoce el tamaño de antemano, puede usar una matriz estática. Y si no conoce el tamaño de antemano, escribirá un código inseguro.

Los CLA VLA podrían proporcionar un pequeño beneficio al poder crear arreglos pequeños sin desperdiciar espacio o llamar a constructores para elementos no utilizados, pero introducirán cambios bastante grandes en el sistema de tipos (debe poder especificar tipos dependiendo de los valores de tiempo de ejecución) aún no existe en C ++ actual, a excepción de newlos especificadores de tipo de operador, pero se tratan especialmente, de modo que el tiempo de ejecución no escapa al alcance del newoperador).

Puede usar std::vector, pero no es lo mismo, ya que usa memoria dinámica, y hacer que use el propio asignador de pila no es exactamente fácil (la alineación también es un problema). Tampoco resuelve el mismo problema, porque un vector es un contenedor redimensionable, mientras que los VLA son de tamaño fijo. La propuesta de C ++ Dynamic Array tiene la intención de introducir una solución basada en biblioteca, como alternativa a un VLA basado en lenguaje. Sin embargo, no será parte de C ++ 0x, que yo sepa.

Johannes Schaub - litb
fuente
22
+1 y aceptado. Sin embargo, un comentario, creo que el argumento de seguridad es un poco débil ya que hay muchas otras formas de causar desbordamientos de la pila. El argumento de seguridad podría usarse para respaldar la posición de que nunca debe usar la recursividad y que debe asignar todos los objetos del montón.
Andreas Brinck
17
Entonces, ¿estás diciendo que debido a que hay otras formas de causar desbordamientos de pila, también podríamos alentar más?
jalf
3
@Andreas, de acuerdo sobre la debilidad. Pero para la recursividad, se necesita una gran cantidad de llamadas hasta que se agota la pila, y si ese puede ser el caso, la gente usaría la iteración. Sin embargo, como dicen algunas personas en el hilo de usenet, este no es un argumento en contra de los VLA en todos los casos, ya que a veces definitivamente puede conocer un límite superior. Pero en esos casos, por lo que veo, una matriz estática también puede ser suficiente, ya que de todos modos no desperdiciaría mucho espacio (si lo hiciera , entonces tendría que preguntar si el área de la pila es lo suficientemente grande nuevamente).
Johannes Schaub - litb
10
También observe la respuesta de Matt Austern en ese hilo: la especificación del lenguaje de los VLA probablemente sería considerablemente más compleja para C ++, debido a las coincidencias de tipo más estrictas en C ++ (ejemplo: C permite asignar a T(*)[]a a T(*)[N]- en C ++ esto no está permitido, ya que C ++ no sabe sobre "compatibilidad de tipos": requiere coincidencias exactas), parámetros de tipo, excepciones, con- y destructores y otras cosas. No estoy seguro de si los beneficios de los VLA realmente pagarían todo ese trabajo. Pero entonces, nunca he usado VLA en la vida real, por lo que probablemente no conozco buenos casos de uso para ellos.
Johannes Schaub - litb
1
@AHelps: Quizás lo mejor para eso sería un tipo que se comporta de manera similar vectorpero requiere un patrón de uso de LIFO fijo y mantiene uno o más buffers asignados estáticamente por subproceso que generalmente se dimensionan de acuerdo con la asignación total más grande que tiene el subproceso alguna vez utilizado, pero que podría recortarse explícitamente. En el caso común, una "asignación" normal no requeriría más que una copia de puntero, sustracción de puntero de puntero, comparación de enteros y adición de puntero; la desasignación simplemente requeriría una copia del puntero. No mucho más lento que un VLA.
supercat
217

(Antecedentes: tengo algo de experiencia en la implementación de compiladores C y C ++).

Las matrices de longitud variable en C99 fueron básicamente un paso en falso. Para soportar los VLA, C99 tuvo que hacer las siguientes concesiones al sentido común:

  • sizeof xya no es siempre una constante de tiempo de compilación; el compilador a veces debe generar código para evaluar una sizeofexpresión en tiempo de ejecución.

  • Permitir VLA bidimensionales (int A[x][y] ) necesaria una nueva sintaxis para declarar funciones que toman 2D VLA como parámetros: void foo(int n, int A[][*]).

  • Menos importante en el mundo de C ++, pero extremadamente importante para el público objetivo de programadores de sistemas integrados de C, declarar un VLA significa cortar una porción arbitrariamente grande de su pila. Este es un desbordamiento de pila y un bloqueo garantizados . (Cada vez que declaras int A[n], estás afirmando implícitamente que tienes 2GB de pila de sobra. Después de todo, si sabes que " ndefinitivamente es menos de 1000 aquí", entonces simplemente declararías int A[1000]. Sustituyendo el entero de 32 bitsn para 1000es una admisión que no tienes idea de cuál debería ser el comportamiento de tu programa).

Bien, pasemos ahora a hablar de C ++. En C ++, tenemos la misma distinción fuerte entre "sistema de tipos" y "sistema de valores" que C89 ... pero realmente hemos comenzado a confiar en ella de formas que C no tiene. Por ejemplo:

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

Si nno fuera una constante de tiempo de compilación (es decir, si Afuera de tipo variablemente modificado), entonces ¿cuál sería el tipo de S? Would Stipo 's también se determinaría solo en tiempo de ejecución?

¿Qué hay de esto?

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

El compilador debe generar código para alguna instanciación de myfunc. ¿Cómo debería ser ese código? ¿Cómo podemos generar estáticamente ese código, si no sabemos el tipo deA1 en tiempo de compilación?

Peor, ¿y si resulta que en tiempo de ejecución eso n1 != n2, así que !std::is_same<decltype(A1), decltype(A2)>()? En ese caso, la llamada a myfunc ni siquiera debería compilar , ¡porque la deducción de tipo de plantilla debería fallar! ¿Cómo podríamos emular ese comportamiento en tiempo de ejecución?

Básicamente, C ++ se está moviendo en la dirección de impulsar más y más decisiones en tiempo de compilación : generación de código de plantilla, constexprevaluación de funciones, etc. Mientras tanto, C99 estaba ocupado empujando decisiones tradicionalmente en tiempo de compilación (por ejemplo sizeof) en el tiempo de ejecución . Con esto en mente, ¿tiene sentido gastar algún esfuerzo? tratando de integrar VLA de estilo C99 en C ++?

Como todos los demás respondedores ya han señalado, C ++ proporciona muchos mecanismos de asignación de almacenamiento dinámico ( std::unique_ptr<int[]> A = new int[n];o std::vector<int> A(n);son los obvios) cuando realmente desea transmitir la idea "No tengo idea de la cantidad de RAM que podría necesitar". Y C ++ proporciona un ingenioso modelo de manejo de excepciones para lidiar con la situación inevitable de que la cantidad de RAM que necesita es mayor que la cantidad de RAM que tiene. Pero es de esperar que esta respuesta le dé una buena idea de por qué los VLA de estilo C99 no se ajustaban bien a C ++, y ni siquiera se ajustaban bien a C99. ;)


Para obtener más información sobre el tema, consulte N3810 "Alternativas para extensiones de matriz" , documento de Bjarne Stroustrup de octubre de 2013 sobre VLA. El punto de vista de Bjarne es muy diferente al mío; N3810 se enfoca más en encontrar una buena sintaxis ish de C ++ para las cosas y en desalentar el uso de matrices en bruto en C ++, mientras que me concentré más en las implicaciones para la metaprogramación y el sistema de tipos. No sé si considera las implicaciones de metaprogramación / sistema de tipos resueltas, solucionables o simplemente sin interés.


Una buena publicación de blog que alcanza muchos de estos mismos puntos es "Uso legítimo de matrices de longitud variable" (Chris Wellons, 2019-10-27).

Quuxplusone
fuente
15
Estoy de acuerdo en que los VLA estaban equivocados. La implementación mucho más amplia y mucho más útil alloca()debería haberse estandarizado en C99. Los VLA son lo que sucede cuando un comité de estándares se adelanta a las implementaciones, en lugar de al revés.
MadScientist
10
El sistema de tipo modificado de forma variable es una gran adición IMO, y ninguno de sus puntos de viñeta viola el sentido común. (1) el estándar C no distingue entre "tiempo de compilación" y "tiempo de ejecución", por lo que esto no es un problema; (2) El *es opcional, puede (y debe) escribir int A[][n]; (3) Puede usar el sistema de tipos sin declarar realmente ningún VLA. Por ejemplo, una función puede aceptar una matriz de tipo modificado de forma variable, y se puede invocar con matrices 2-D que no sean VLA de diferentes dimensiones. Sin embargo, haces puntos válidos en la última parte de tu publicación.
MM
3
"declarar un VLA significa cortar una porción arbitrariamente grande de su pila. Esto es un desbordamiento y bloqueo garantizado de la pila. (Cada vez que declara int A [n], está afirmando implícitamente que tiene 2GB de pila de sobra" es empíricamente falso. Acabo de ejecutar un programa VLA con una pila de menos de 2GB sin ningún desbordamiento de pila.
Jeff
3
@Jeff: ¿Cuál fue el valor máximo de nen su caso de prueba y cuál era el tamaño de su pila? Le sugiero que intente ingresar un valor por lo nmenos tan grande como el tamaño de su pila. (Y si no hay forma de que el usuario controle el valor de nsu programa, le sugiero que simplemente propague el valor máximo de ndirectamente en la declaración: declare int A[1000]o lo que sea que necesite. Los VLA solo son necesarios y solo peligrosos, cuando el valor máximo de nno está limitado por una pequeña constante de tiempo de compilación.)
Quuxplusone
2
Dado que alloca () puede implementarse usando tales intrínsecos, es por definición cierto que alloca () podría implementarse en cualquier plataforma, como una función estándar del compilador. No hay razón para que el compilador no pueda detectar la primera instancia de alloca () y organizar los tipos de marcas y lanzamientos que se incrustarán en el código, y no hay razón para que un compilador no pueda implementar alloca () usando el montón si No se puede hacer con la pila. Lo que es difícil / no portátil es tener alloca () implementado en la parte superior de un compilador de C, para que funcione en una amplia gama de compiladores y sistemas operativos.
MadScientist
26

Siempre puede usar alloca () para asignar memoria en la pila en tiempo de ejecución, si lo desea:

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

Ser asignado en la pila implica que se liberará automáticamente cuando la pila se desenrolle.

Nota rápida: Como se menciona en la página de manual de Mac OS X para alloca (3), "La función alloca () depende de la máquina y el compilador; su uso no está recomendado". Solo para que sepas.

PfhorSlayer
fuente
44
Además, el alcance de alloca () es la función completa, no solo el bloque de código que contiene la variable. Por lo tanto, usarlo dentro de un bucle aumentará continuamente la pila. Un VLA no tiene este problema.
sashoalm
3
Sin embargo, los VLA que tienen el alcance del bloque envolvente significa que son significativamente menos útiles que alloca () con el alcance de la función completa. Considere: if (!p) { p = alloca(strlen(foo)+1); strcpy(p, foo); } esto no se puede hacer con VLA, precisamente debido a su alcance de bloque.
MadScientist
1
Eso no responde a la pregunta de por qué de OP . Por otra parte, esta es una Csolución similar, y no realmente C++-ish.
Adrian W
13

En mi propio trabajo, me di cuenta de que cada vez que quería algo como arreglos automáticos de longitud variable o alloca (), realmente no me importaba que la memoria estuviera ubicada físicamente en la pila de la CPU, solo que provenía de algún asignador de pila que no incurrió en viajes lentos al montón general. Por lo tanto, tengo un objeto por subproceso que posee algo de memoria desde la cual puede empujar / explotar buffers de tamaño variable. En algunas plataformas, permito que esto crezca a través de mmu. Otras plataformas tienen un tamaño fijo (generalmente acompañado de una pila de CPU de tamaño fijo también porque no mmu). Una plataforma con la que trabajo (una consola de juegos portátil) tiene una pequeña pila de CPU preciosa de todos modos porque reside en la memoria escasa y rápida.

No digo que nunca sea necesario empujar buffers de tamaño variable en la pila de CPU. Honestamente, me sorprendí cuando descubrí que esto no era estándar, ya que ciertamente parece que el concepto se ajusta bastante bien al lenguaje. Sin embargo, para mí, los requisitos "tamaño variable" y "deben estar ubicados físicamente en la pila de la CPU" nunca se han unido. Se trata de la velocidad, así que hice mi propio tipo de "pila paralela para memorias intermedias de datos".

Eric
fuente
12

Hay situaciones en las que asignar memoria de almacenamiento dinámico es muy costoso en comparación con las operaciones realizadas. Un ejemplo es la matriz matemática. Si trabaja con matrices más pequeñas, diga de 5 a 10 elementos y haga muchas operaciones aritméticas, la sobrecarga de malloc será realmente significativa. Al mismo tiempo, hacer que el tamaño sea un tiempo de compilación constante parece muy derrochador e inflexible.

Creo que C ++ es tan inseguro en sí mismo que el argumento de "tratar de no agregar más características inseguras" no es muy fuerte. Por otro lado, dado que C ++ es posiblemente las características del lenguaje de programación más eficientes en tiempo de ejecución, lo que lo hace aún más útil siempre: las personas que escriben programas críticos para el rendimiento usarán en gran medida C ++, y necesitan tanto rendimiento como sea posible. Mover cosas del montón al montón es una de esas posibilidades. Reducir el número de bloques de montón es otra. Permitir VLA como miembros de objeto sería una forma de lograr esto. Estoy trabajando en tal sugerencia. Es un poco complicado de implementar, sin duda, pero parece bastante factible.

Bengt Gustafsson
fuente
12

Parece que estará disponible en C ++ 14:

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

Actualización: no llegó a C ++ 14.

Viktor Sehr
fuente
interesante. Herb Sutter lo analiza aquí en Dynamic Arrays : isocpp.org/blog/2013/04/trip-report-iso-c-spring-2013-meeting (esta es la referencia para la información de Wikipedia)
Predeterminado
1
"Las matrices y el dynarray de tamaño de tiempo de ejecución se han trasladado a la especificación técnica de las extensiones de matriz", escribió 78.86.152.103 en Wikipedia el 18 de enero de 2014: en.wikipedia.org/w/…
extraño
10
Wikipedia no es una referencia normativa :) Esta propuesta no llegó a C ++ 14.
MM
2
@ViktorSehr: ¿Cuál es el estado de este wrt C ++ 17?
einpoklum
@einpoklum No tengo idea, use boost :: container :: static_vector
Viktor Sehr
7

Esto se consideró para su inclusión en C ++ / 1x, pero se descartó (esto es una corrección de lo que dije anteriormente).

Sería menos útil en C ++ de todos modos ya que ya tenemos std::vectorque cumplir este rol.

philsquared
fuente
42
No, no lo hacemos, std :: vector no asigna datos en la pila. :)
Kos
77
"la pila" es un detalle de implementación; el compilador puede asignar memoria desde cualquier lugar siempre que se cumplan las garantías sobre la vida útil del objeto.
MM
1
@MM: Muy bien, pero en la práctica todavía no se puede utilizar std::vectoren lugar de, por ejemplo, alloca().
einpoklum
@einpoklum en términos de obtener la salida correcta para su programa, puede hacerlo. El rendimiento es un problema de calidad de implementación
MM
1
La calidad de implementación de @MM no es portátil. y si no necesita rendimiento, no usa c ++ en primer lugar
amigo el
3

Use std :: vector para esto. Por ejemplo:

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

La memoria se asignará en el montón, pero esto solo tiene un pequeño inconveniente de rendimiento. Además, es aconsejable no asignar grandes bloques de datos en la pila, ya que su tamaño es bastante limitado.

Dimitri C.
fuente
44
Una aplicación importante para las matrices de longitud variable es la evaluación de polinomios de grado arbitrario. En ese caso, su "pequeño inconveniente de rendimiento" significa que "el código se ejecuta cinco veces más lento en casos típicos". Eso no es pequeño.
AHelps
1
¿Por qué no lo usas simplemente std::vector<int> values(n);? Al usar resizedespués de la construcción, está prohibiendo los tipos no móviles.
LF
1

C99 permite VLA. Y pone algunas restricciones sobre cómo declarar VLA. Para más detalles, consulte 6.7.5.2 de la norma. C ++ no permite VLA. Pero g ++ lo permite.

Jingguo Yao
fuente
¿Puede proporcionar un enlace al párrafo estándar que está señalando?
Vincent
0

Las matrices como esta son parte de C99, pero no parte de C ++ estándar. Como otros han dicho, un vector siempre es una solución mucho mejor, por lo que probablemente las matrices de tamaño variable no están en el estándar C ++ (o en el estándar C ++ 0x propuesto).

Por cierto, para preguntas sobre "por qué" el estándar C ++ es como es, el grupo de noticias moderado Usenet comp.std.c ++ es el lugar al que debe dirigirse.


fuente
66
-1 El vector no siempre es mejor. A menudo si. Siempre no. Si solo necesita una matriz pequeña, está en una plataforma donde el espacio de almacenamiento dinámico es lento y la implementación de su biblioteca de vectores utiliza espacio de almacenamiento dinámico, entonces esta característica podría ser mejor si existiera.
Patrick M
-1

Si conoce el valor en tiempo de compilación, puede hacer lo siguiente:

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

}

Editar: puede crear un vector que utilice un asignador de pila (alloca), ya que el asignador es un parámetro de plantilla.

Edouard A.
fuente
18
Si conoce el valor en tiempo de compilación, no necesita una plantilla en absoluto. Simplemente use X directamente en su función que no sea de plantilla.
Rob Kennedy el
3
A veces la persona que llama sabe en tiempo de compilación y la persona que llama no, para eso son buenas las plantillas. Por supuesto, en el caso general, nadie conoce X hasta el tiempo de ejecución.
Qwertie
No puede usar alloca en un asignador STL: la memoria asignada de alloca se liberará cuando se destruya el marco de la pila; es entonces cuando regresa el método que debería asignar la memoria.
Oliver
-5

Tengo una solución que realmente funcionó para mí. No quería asignar memoria debido a la fragmentación en una rutina que necesitaba ejecutarse muchas veces. La respuesta es extremadamente peligrosa, así que úsela bajo su propio riesgo, pero aprovecha el montaje para reservar espacio en la pila. Mi ejemplo a continuación utiliza una matriz de caracteres (obviamente, otra variable de tamaño requeriría más memoria).

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
    } 
}

Los peligros aquí son muchos, pero explicaré algunos: 1. Cambiar el tamaño de la variable a la mitad eliminaría la posición de la pila 2. Sobrepasar los límites de la matriz destruiría otras variables y el posible código 3. Esto no funciona en 64 bits construir ... necesita un ensamblaje diferente para ese (pero una macro podría resolver ese problema). 4. Compilador específico (puede tener problemas para moverse entre compiladores). No lo he intentado, así que realmente no lo sé.

Alan
fuente
... y si quieres tirar esto tú mismo, ¿tal vez usar una clase RAII?
einpoklum
Simplemente puede usar boost :: container :: static_vector mil.
Viktor Sehr
Esto no tiene equivalentes para otros compiladores que tienen más ensamblaje sin procesar que MSVC. Es probable que VC comprenda que espcambió y ajustará sus accesos a la pila, pero, por ejemplo, en GCC simplemente lo romperá por completo, al menos si usa optimizaciones y -fomit-frame-pointeren particular.
Ruslan