c++ - programming - ¿Puedo tratar una matriz 2D como una matriz 1D contigua?

max subarray geeksforgeeks

Question

Considera el siguiente código:

int a[25][80];
a[0][1234] = 56;
int* p = &a[0][0];
p[1234] = 56;

¿La segunda línea invoca un comportamiento indefinido? ¿Qué tal la cuarta línea?

Answer 1

Ambas líneas dan como resultado un comportamiento indefinido.

La subscripción se interpreta como adición de puntero seguida de una indirección, es decir, a[0][1234] / p[1234] es equivalente a *(a[0] + 1234) / *(p + 1234) . De acuerdo con [expr.add]/4 (aquí cito el borrador más nuevo, mientras que para el momento en que se propone OP, puede consultar este comentario , y la conclusión es la misma):

Si la expresión P apunta al elemento x [i] de un objeto de matriz x con n elementos, las expresiones P + J y J + P (donde J tiene el valor j) apuntan al elemento (posiblemente hipotético) x [i + j] si 0≤i + j≤n; de lo contrario, el comportamiento no está definido.

como a[0] (decaído a un puntero a a[0][0] ) / p apunta a un elemento de a[0] (como una matriz), y a[0] solo tiene un tamaño de 80, el comportamiento es indefinido .

Una cosa interesante es que en el momento en que se propone OP (antes de C ++ 17), lo siguiente está bien definido:

int* p = &a[0][0];
p[80] = 56;
p += 80; // p now passes the end of a[0], and points to a[1][0] at the same time
p[80] = 56; // ok because p points to an element of a[1]

de acuerdo a

Si un objeto de tipo T está ubicado en una dirección A, se dice que un puntero de tipo cv T * cuyo valor es la dirección A apunta a ese objeto, independientemente de cómo se obtuvo el valor. [ Nota: por ejemplo, se consideraría que la dirección anterior al final de una matriz ([expr.add]) apunta a un objeto no relacionado del tipo de elemento de la matriz que podría estar ubicado en esa dirección. Existen otras restricciones sobre los punteros a objetos con duración de almacenamiento dinámica; ver [basic.stc.dynamic.safety]. - nota final]

Sin embargo, esto ya no está permitido después de C ++ 17. La fraseología anterior se cambia a

Un valor de un tipo de puntero que sea un puntero o pase del final de un objeto representa la dirección del primer byte en la memoria ([intro.memory]) ocupada por el objeto o el primer byte en la memoria después del final del almacenamiento ocupado por el objeto, respectivamente. [Nota: un puntero más allá del final de un objeto ([expr.add]) no se considera que apunta a un objeto no relacionado del tipo del objeto que podría estar ubicado en esa dirección. Un valor de puntero pierde validez cuando el almacenamiento que denota alcanza el final de su duración de almacenamiento; ver [basic.stc]. - nota final]

por P0137 .

Answer 2

Depende de la interpretación. Si bien los requisitos de contigüidad de las matrices no dejan mucho que desear a la imaginación en términos de cómo diseñar una matriz multidimensional (esto ya se ha señalado anteriormente), observe que cuando hace p[1234] está indexando el 1234º elemento de la fila cero de solo 80 columnas. Algunos interpretan que los únicos índices válidos son 0..79 ( &p[80] siendo un caso especial).

La información de C FAQ que es la sabiduría recopilada de Usenet en asuntos relevantes para C. (No creo que C y C ++ difieran en ese asunto y que esto es muy relevante).

Answer 3

Eres libre de reinterpretar la memoria de la forma que quieras. Siempre que el múltiplo no exceda la memoria lineal. Incluso puede mover una a 12, 40 y usar índices negativos.

Answer 4

La memoria referenciada por a es tanto int[25][80] como int[2000] . Entonces dice el Estándar, 3.8p2:

[Nota: la vida útil de un objeto de matriz comienza tan pronto como se almacena con el tamaño y la alineación adecuados, y su vida útil finaliza cuando el almacenamiento que ocupa la matriz se reutiliza o libera. 12.6.2 describe la vida útil de los subobjetos de base y miembro. - nota final]

a tiene un tipo particular, es un lvalue de tipo int[25][80] . Pero p es solo int* . No es " int* apuntando a un int[80] " o algo por el estilo. De hecho, el int apuntado es un elemento de int[25][80] llamado a , y también un elemento de int[2000] ocupa el mismo espacio.

Como p y p+1234 son elementos del mismo objeto int[2000] , la aritmética del puntero está bien definida. Y como p[1234] significa *(p+1234) , también está bien definido.

El efecto de esta regla para la vida útil de la matriz es que puede usar libremente la aritmética de puntero para moverse a través de un objeto completo.

Desde std::array se mencionó en los comentarios:

Si uno tiene std::array<std::array<int, 80>, 25> a; entonces no existe una std::array<int, 2000> . Existe un int[2000] . Estoy buscando cualquier cosa que requiera sizeof (std::array<T,N>) == sizeof (T[N]) (y == N * sizeof (T) ). En ausencia de eso, debe suponer que podría haber lagunas que ensucian el recorrido de std::array anidado.

Answer 5

Sí, puede (no, no es UB), está garantizado indirectamente por el estándar. He aquí cómo: una matriz 2D es una matriz de matrices. Se garantiza que una matriz tiene memoria contigua y sizeof(array) es sizeof(elem) número de elementos. De esto se sigue que lo que estás tratando de hacer es perfectamente legal.

Answer 6

Su compilador arrojará un montón de advertencias / errores debido a subíndices fuera de rango (línea 2) y tipos incompatibles (línea 3), pero mientras la variable real (int en este caso) sea uno de los tipos base intrínsecos, es guardar para hacer en C y C ++. (Si la variable es una clase / struct, probablemente todavía funcione en C, pero en C ++ todas las apuestas están desactivadas).

Por qué querrías hacer esto ... Para la primera variante: si tu código depende de este tipo de problemas, será propenso a errores y difícil de mantener a largo plazo.

Puedo ver un poco de uso para la segunda variante cuando la optimización del rendimiento gira sobre arreglos 2D reemplazándolos por un puntero 1D ejecutado sobre el espacio de datos, pero un buen compilador de optimización a menudo lo hará por sí solo de todos modos. Si el cuerpo del bucle es tan grande / complejo, el compilador no puede optimizar / reemplazar el bucle por una ejecución 1D por sí mismo, la ganancia de rendimiento al hacerlo manualmente tampoco será significativa.