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

tipos de arreglos en c++

Question

No he usado mucho C en los últimos años. Cuando leí esta pregunta hoy me encontré con una sintaxis 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 agregarlo al estándar de C ++ y, de ser así, por qué se omitió?

Algunas posibles razones:

• Peludo para los proveedores de compiladores para implementar
• Incompatible con alguna otra parte de la norma.
• La funcionalidad se puede emular con otras construcciones de C ++

El estándar de C ++ indica 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 de juguete se podrían usar los std::vector<int> values(m); , pero esto asigna memoria del montón y no 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 versión vector vuelve bastante torpe:

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

Los segmentos, filas y columnas también se distribuirán en toda la memoria.

Mirando la discusión en comp.std.c++ está claro que esta pregunta es bastante controvertida con algunos nombres muy pesados ​​en ambos lados del argumento. Ciertamente no es obvio que un std::vector sea ​​siempre una mejor solución.

Answer 1

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

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

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

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

• Menos importante en el mundo de C ++, pero extremadamente importante para la audiencia objetivo de programadores de sistemas embebidos de C, declarar un VLA significa cortar una porción arbitrariamente grande de su pila. Esto es un desbordamiento de pila garantizado y la caída. (Cada vez que declara int A[n] , está afirmando implícitamente que tiene 2 GB de pila de sobra. Después de todo, si sabe que " n es definitivamente menos de 1000 aquí", entonces simplemente declararía int A[1000] . Sustituir el entero de 32 bits n por 1000 es una admisión de que no tiene idea de cuál debería ser el comportamiento de su programa.)

Bien, entonces vamos a hablar de C ++ ahora. En C ++, tenemos la misma distinción fuerte entre "sistema de tipos" y "sistema de valores" que C89 hace ... pero realmente hemos empezado a confiar en él de manera que C no lo ha hecho. Por ejemplo:

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

Si n no fuera una constante de tiempo de compilación (es decir, si A fuera de un tipo modificado de forma variable), entonces, ¿qué demonios sería el tipo de S ? ¿El tipo de S también se determinaría solo en el tiempo de ejecución?

¿Qué pasa con 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 algunos ejemplos de myfunc . ¿Cómo debería ser ese código? ¿Cómo podemos generar estáticamente ese código, si no conocemos el tipo de A1 en el momento de la compilación?

Peor aún, ¿qué pasa si en el tiempo de ejecución resulta que n1 != n2 , de modo que !std::is_same<decltype(A1), decltype(A2)>() ? En ese caso, la llamada a myfunc no debería compilarse , ¡porque la deducción del 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, evaluación de función constexpr , etc. Mientras tanto, C99 estaba ocupado presionando tradicionalmente las decisiones en tiempo de compilación (por ejemplo, sizeof ) en el tiempo de ejecución . Teniendo esto en cuenta, ¿realmente tiene sentido dedicar algún esfuerzo al intentar integrar VLA de estilo C99 en C ++?

Como ya han señalado todos los demás respondedores, C ++ proporciona muchos mecanismos de asignación de pila ( std::unique_ptr<int[]> A = new int[n]; o std::vector<int> A(n); obvias) cuando realmente desea transmitir la idea "No tengo idea de cuánta RAM necesito". Y C ++ proporciona un ingenioso modelo de manejo de excepciones para hacer frente a la situación inevitable de que la cantidad de RAM que necesita es mayor que la cantidad de RAM que tiene. Pero espero que esta respuesta te dé una buena idea de por qué los VLA de estilo C99 no eran adecuados para C ++, y en realidad ni siquiera eran buenos para C99. ;)

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

Answer 2

Arreglos como este son parte de C99, pero no son parte de C ++ estándar. como han dicho otros, un vector siempre es una solución mucho mejor, y es probablemente la razón por la cual las matrices de tamaño variable no están en la norma C ++ (o en el estándar propuesto de C ++ 0x).

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

Answer 3

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.

Answer 4

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

No estoy diciendo que nunca es necesario insertar buffers de tamaño variable en la pila de la CPU. Honestamente, me sorprendí cuando descubrí que esto no era estándar, ya que ciertamente parece que el concepto encaja bien en el lenguaje. Para mí, sin embargo, los requisitos "tamaño variable" y "deben estar ubicados físicamente en la pila de la CPU" nunca han surgido juntos. Ha sido sobre la velocidad, así que hice mi propio tipo de "pila paralela para buffers de datos".

Answer 5

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

De todos modos, sería menos útil en C ++ ya que ya tenemos std::vector para cumplir este rol.

Answer 6

Hay situaciones en las que asignar memoria de pila es muy costoso en comparación con las operaciones realizadas. Un ejemplo es la matriz matemática. Si trabajas con matrices más pequeñas, digamos de 5 a 10 elementos y haces mucha aritmética, la sobrecarga de Malloc será realmente significativa. Al mismo tiempo, hacer que el tamaño de una compilación constante de tiempo parece muy inútil e inflexible.

Creo que C ++ es tan inseguro en sí mismo que el argumento de "tratar de no agregar más funciones inseguras" no es muy sólido. Por otro lado, como C ++ es posiblemente la función de lenguaje de programación más eficiente en tiempo de ejecución, lo que lo hace más útil, por lo que siempre son útiles: las personas que escriben programas críticos para el rendimiento utilizarán C ++ en gran medida, y necesitan el mayor rendimiento posible. Mover cosas de un montón a otro es una de esas posibilidades. Reducir el número de bloques de pila es otra. Permitir VLAs como miembros de objetos sería una forma de lograr esto. Estoy trabajando en tal sugerencia. Es un poco complicado de implementar, es cierto, pero parece bastante factible.

Answer 7

Necesita una expresión constante para declarar una matriz en C / C ++.

Para matrices de tamaño dinámico, debe asignar memoria en el montón y luego administrar el tiempo de actividad de esta memoria.

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

Answer 8

Parece que estará disponible en C ++ 14:

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

Actualización: No lo hizo en C ++ 14.

Answer 9

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

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

Los VLA de C99 podrían proporcionar un pequeño beneficio de poder crear arreglos pequeños sin desperdiciar espacio o llamar a los constructores para los 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, esto aún no existe en C ++ actual, a excepción de los new especificadores de tipo de operador, pero se tratan de manera especial, de modo que el tiempo de ejecución no escapa al alcance del new operador).

Puede usar std::vector , pero no es exactamente lo mismo, ya que usa la memoria dinámica, y hacer que use su 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 de tamaño variable, mientras que los VLA son de tamaño fijo. La propuesta de C ++ Dynamic Array está diseñada para introducir una solución basada en bibliotecas, como alternativa a un VLA basado en lenguaje. Sin embargo, no va a ser parte de C ++ 0x, que yo sepa.

Answer 10

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 use un asignador de pila (alloca), ya que el asignador es un parámetro de plantilla.

Answer 11

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 mencionó en la página de manual de Mac OS X para alloca (3), "La función alloca () depende de la máquina y del compilador; su uso se desactiva". Solo para que sepas.

Answer 12

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 utilícela bajo su propio riesgo, pero aprovecha el ensamblaje 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. Superar los límites de la matriz destruiría otras variables y el posible código 3. Esto no funciona en un bit de 64 bits. construir ... necesita un ensamblaje diferente para ese (pero una macro podría resolver ese problema). 4. Específico del compilador (puede tener problemas para moverse entre compiladores). No lo he intentado así que realmente no lo sé.

Answer 13

Usa 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.