programacion - matriz dinamica c++
¿Cómo manejo las matrices multidimensionales dinámicas en C/C++? (10)
¿Cuál es la forma aceptada / más comúnmente utilizada para manipular matrices multidimensionales dinámicas (con todas las dimensiones no conocidas hasta el tiempo de ejecución) en C y / o C ++?
Estoy tratando de encontrar la manera más limpia de lograr lo que hace este código Java:
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int rows=sc.nextInt();
int cols=sc.nextInt();
int[][] data=new int[rows][cols];
manipulate(data);
}
public static void manipulate(int[][] data){
for(int i=0;i<data.length;i++)
for(int j=0;j<data[0].length.j++){
System.out.print(data[i][j]);
}
}
(lee de std_in solo para aclarar que las dimensiones no se conocen hasta el tiempo de ejecución).
Editar: noté que esta pregunta es bastante popular, aunque es bastante antigua. En realidad, no estoy de acuerdo con la respuesta más votado. Creo que la mejor opción para C es usar una matriz unidimensional como dice Guge a continuación "Puedes asignar filas cols sizeof (int) y acceder a ellas por la tabla [row * cols + col]".
Hay una serie de opciones con C ++, si realmente te gusta boost o stl, entonces las respuestas a continuación podrían ser preferibles, pero la opción más simple y probablemente más rápida es usar una única matriz dimensional como en C.
Otra opción viable en C y C ++ si quieres la sintaxis [] [] es que la respuesta de lillq en la parte inferior es construir manualmente la matriz con muchos malloc.
Aquí está la manera fácil de hacer esto en C:
void manipulate(int rows, int cols, int (*data)[cols]) {
for(int i=0; i < rows; i++) {
for(int j=0; j < cols; j++) {
printf("%d ", data[i][j]);
}
printf("/n");
}
}
int main() {
int rows = ...;
int cols = ...;
int (*data)[cols] = malloc(rows*sizeof(*data));
manipulate(rows, cols, data);
free(data);
}
Esto es perfectamente válido desde C99, sin embargo, no es C ++ de ningún estándar: C ++ requiere que los tamaños de los tipos de matriz sean constantes de tiempos de compilación. En ese sentido, C ++ ahora está quince años detrás de C. Y esta situación no va a cambiar pronto (la propuesta de matriz de longitud variable para C ++ 17 no se acerca a la funcionalidad de las matrices de longitud variable C99).
Hay dos formas de representar una matriz de 2 dimensiones en C ++. Uno siendo más flexible que el otro.
Matriz de matrices
Primero haga una serie de punteros, luego inicialice cada puntero con otra matriz.
// First dimension
int** array = new int*[3];
for( int i = 0; i < 3; ++i )
{
// Second dimension
array[i] = new int[4];
}
// You can then access your array data with
for( int i = 0; i < 3; ++i )
{
for( int j = 0; j < 4; ++j )
{
std::cout << array[i][j];
}
}
El problema con este método es que su segunda dimensión se asigna a tantas matrices, por lo que no facilita el trabajo del asignador de memoria. Es probable que tu memoria esté fragmentada, lo que da como resultado un peor rendimiento. Sin embargo, proporciona más flexibilidad ya que cada matriz en la segunda dimensión podría tener un tamaño diferente.
Gran matriz para contener todos los valores
El truco aquí es crear una matriz masiva para contener todos los datos que necesita. La parte más difícil es que todavía necesita la primera matriz de punteros si desea poder acceder a los datos utilizando la sintaxis de la matriz [i] [j].
int* buffer = new int[3*4];
int** array = new int*[3];
for( int i = 0; i < 3; ++i )
{
array[i] = array + i * 4;
}
La matriz int * no es obligatoria, ya que podría acceder a sus datos directamente en el búfer al calcular el índice en el búfer desde las coordenadas bidimensionales del valor.
// You can then access your array data with
for( int i = 0; i < 3; ++i )
{
for( int j = 0; j < 4; ++j )
{
const int index = i * 4 + j;
std::cout << buffer[index];
}
}
La REGLA a tener en cuenta
La memoria de la computadora es lineal y seguirá siendo durante mucho tiempo. Tenga en cuenta que las matrices de 2 dimensiones no se admiten de forma nativa en una computadora, por lo que la única forma es "linealizar" la matriz en una matriz de 1 dimensión.
La forma estándar sin usar boost es usar std :: vector:
std::vector< std::vector<int> > v;
v.resize(rows, std::vector<int>(cols, 42)); // init value is 42
v[row][col] = ...;
Eso se ocupará de eliminar / borrar la memoria que necesita automáticamente. Pero es bastante lento, ya que std::vector no está diseñado principalmente para usarlo de esa manera (nesting std::vector dentro de cada uno). Por ejemplo, toda la memoria no está asignada en un bloque, sino separada para cada columna. Además, las filas no tienen que ser todas del mismo ancho. Más rápido es usar un vector normal, y luego hacer un cálculo de índice como col_count * row + col para obtener una determinada fila y col:
std::vector<int> v(col_count * row_count, 42);
v[col_count * row + col) = ...;
Pero esto perderá la capacidad de indexar el vector usando [x][y] . También debe almacenar la cantidad de filas y columnas en algún lugar, mientras usa la solución anidada puede obtener la cantidad de filas usando v.size() y la cantidad de columnas usando v[0].size() .
Usando boost, puede usar boost::multi_array , que hace exactamente lo que quiere (vea la otra respuesta).
También existe la forma cruda utilizando matrices nativas de C ++. Esto implica bastante trabajo y de ninguna manera es mejor que la solución de vector anidado:
int ** rows = new int*[row_count];
for(std::size_t i = 0; i < row_count; i++) {
rows[i] = new int[cols_count];
std::fill(rows[i], rows[i] + cols_count, 42);
}
// use it... rows[row][col] then free it...
for(std::size_t i = 0; i < row_count; i++) {
delete[] rows[i];
}
delete[] rows;
Debe almacenar la cantidad de columnas y filas que creó en algún lugar dado que no puede recibirlas del puntero.
Las matrices de estilo C 2D en C y C ++ son un bloque de memoria de rows * columns * sizeof(datatype) de tamaño rows * columns * sizeof(datatype) tamaño de rows * columns * sizeof(datatype) bytes.
Las dimensiones reales [fila] [columna] existen solo estáticamente en tiempo de compilación. ¡No hay nada allí dinámicamente en tiempo de ejecución!
Entonces, como otros han mencionado, puedes implementar
int array [ rows ] [ columns ];
Como:
int array [ rows * columns ]
O como:
int * array = malloc ( rows * columns * sizeof(int) );
Siguiente: Declarando una matriz de tamaño variable. En C esto es posible:
int main( int argc, char ** argv )
{
assert( argc > 2 );
int rows = atoi( argv[1] );
int columns = atoi( argv[2] );
assert(rows > 0 && columns > 0);
int data [ rows ] [ columns ]; // Yes, legal!
memset( &data, 0, sizeof(data) );
print( rows, columns, data );
manipulate( rows, columns, data );
print( rows, columns, data );
}
En C puede simplemente pasar la matriz de tamaño variable alrededor de la misma como una matriz de tamaño no variable:
void manipulate( int theRows, int theColumns, int theData[theRows][theColumns] )
{
for ( int r = 0; r < theRows; r ++ )
for ( int c = 0; c < theColumns; c ++ )
theData[r][c] = r*10 + c;
}
Sin embargo, en C ++ eso no es posible. Debe asignar la matriz mediante la asignación dinámica, por ejemplo:
int *array = new int[rows * cols]();
o preferiblemente (con administración automática de memoria)
std::vector<int> array(rows * cols);
Entonces las funciones se deben modificar para aceptar datos de 1 dimensión:
void manipulate( int theRows, int theColumns, int *theData )
{
for ( int r = 0; r < theRows; r ++ )
for ( int c = 0; c < theColumns; c ++ )
theData[r * theColumns + c] = r*10 + c;
}
No hay forma de determinar la longitud de una matriz dada en C ++. La mejor forma sería pasar la longitud de cada dimensión de la matriz y usarla en lugar de la propiedad .length de la matriz misma.
Puede asignar filas cols sizeof (int) y acceder a ellas por la tabla [row * cols + col].
Puede usar malloc para lograr esto y aún así tenerlo accesible a través de la matriz normal [] [], en comparación con el método de la matriz [rows * cols + cols].
main()
{
int i;
int rows;
int cols;
int **array = NULL;
array = malloc(sizeof(int*) * rows);
if (array == NULL)
return 0; // check for malloc fail
for (i = 0; i < rows; i++)
{
array[i] = malloc(sizeof(int) * cols)
if (array[i] == NULL)
return 0; // check for malloc fail
}
// and now you have a dynamically sized array
}
Recientemente me encontré con un problema similar. No tenía Boost disponible. Los vectores de vectores resultaron ser bastante lentos en comparación con los arreglos simples. Tener una serie de punteros hace que la inicialización sea mucho más laboriosa, porque tiene que iterar a través de cada dimensión e inicializar los punteros, posiblemente con algunos tipos bastante poco manejables y en cascada en el proceso, posiblemente con muchos typedefs.
DESCARGO DE RESPONSABILIDAD: No estaba seguro de si debería publicar esto como respuesta, ya que solo responde una parte de su pregunta. Mis disculpas por lo siguiente:
- No cubrí cómo leer las dimensiones de la entrada estándar, como comentaron otros comentaristas.
- Esto es principalmente para C ++.
- Solo he codificado esta solución para dos dimensiones.
Decidí publicar esto de todos modos, porque veo vectores de vectores que aparecen con frecuencia en respuesta a preguntas sobre arreglos multidimensionales en C ++, sin que nadie mencione los aspectos de rendimiento de la misma (si te importa).
También interpreté que el tema central de esta pregunta era cómo obtener matrices multidimensionales dinámicas que se pueden usar con la misma facilidad que el ejemplo de Java a partir de la pregunta, es decir, sin la molestia de tener que calcular los índices con un pseudo- matriz unidimensional multidimensional.
No vi extensiones de compilador mencionadas en las otras respuestas, como las proporcionadas por GCC / G ++ para declarar matrices multidimensionales con límites dinámicos de la misma manera que lo hace con los límites estáticos. Por lo que entiendo, la pregunta no restringe las respuestas a C / C ++ estándar. ISO C99 aparentemente los admite, pero en C ++ y versiones anteriores de C parecen ser extensiones específicas del compilador. Vea esta pregunta: Arrays dinámicos en C sin malloc?
Se me ocurrió una manera que a la gente le puede gustar para C ++, porque es un código pequeño, tiene la facilidad de uso de las matrices multidimensionales estáticas incorporadas, y es igual de rápido.
template <typename T>
class Array2D {
private:
std::unique_ptr<T> managed_array_;
T* array_;
size_t x_, y_;
public:
Array2D(size_t x, size_t y) {
managed_array_.reset(new T[x * y]);
array_ = managed_array_.get();
y_ = y;
}
T* operator[](size_t x) const {
return &array_[x * y_];
}
};
Puedes usarlo así Las dimensiones no
auto a = Array2D<int>(x, y);
a[xi][yi] = 42;
Puede agregar una aserción, al menos para todas las dimensiones menos la última y ampliar la idea a más de dos dimensiones. He hecho una publicación en mi blog sobre formas alternativas de obtener matrices multidimensionales. También soy mucho más específico sobre el rendimiento relativo y el esfuerzo de codificación allí.
Si está utilizando C en lugar de C ++, es posible que desee ver la abstracción Array_T en la biblioteca de Dave Hanson, Interfaces e Implementaciones . Es excepcionalmente limpio y bien diseñado. Mis alumnos hacen una versión bidimensional como ejercicio. Puede hacer eso o simplemente escribir una función adicional que haga una asignación de índice, por ejemplo,
void *Array_get_2d(Array_T a, int width, int height, int i, int j) {
return Array_get(a, j * width, i, j);
}
Es un poco más limpio tener una estructura separada donde almacenar el ancho, la altura y un puntero a los elementos.
Use boost::multi_array .
Como en su ejemplo, lo único que necesita saber en tiempo de compilación es el número de dimensiones. Aquí está el primer ejemplo en la documentación:
#include "boost/multi_array.hpp"
#include <cassert>
int
main () {
// Create a 3D array that is 3 x 4 x 2
typedef boost::multi_array<double, 3> array_type;
typedef array_type::index index;
array_type A(boost::extents[3][4][2]);
// Assign values to the elements
int values = 0;
for(index i = 0; i != 3; ++i)
for(index j = 0; j != 4; ++j)
for(index k = 0; k != 2; ++k)
A[i][j][k] = values++;
// Verify values
int verify = 0;
for(index i = 0; i != 3; ++i)
for(index j = 0; j != 4; ++j)
for(index k = 0; k != 2; ++k)
assert(A[i][j][k] == verify++);
return 0;
}
Editar: Como se sugiere en los comentarios, aquí hay una aplicación de ejemplo "simple" que le permite definir el tamaño de matriz multidimensional en tiempo de ejecución, solicitando desde la entrada de la consola. Aquí hay un ejemplo de salida de esta aplicación de ejemplo (compilada con la constante que dice que tiene 3 dimensiones):
Multi-Array test!
Please enter the size of the dimension 0 : 4
Please enter the size of the dimension 1 : 6
Please enter the size of the dimension 2 : 2
Text matrix with 3 dimensions of size (4,6,2) have been created.
Ready!
Type ''help'' for the command list.
>read 0.0.0
Text at (0,0,0) :
""
>write 0.0.0 "This is a nice test!"
Text "This is a nice test!" written at position (0,0,0)
>read 0.0.0
Text at (0,0,0) :
"This is a nice test!"
>write 0,0,1 "What a nice day!"
Text "What a nice day!" written at position (0,0,1)
>read 0.0.0
Text at (0,0,0) :
"This is a nice test!"
>read 0.0.1
Text at (0,0,1) :
"What a nice day!"
>write 3,5,1 "This is the last text!"
Text "This is the last text!" written at position (3,5,1)
>read 3,5,1
Text at (3,5,1) :
"This is the last text!"
>exit
Las partes importantes en el código son la función principal donde obtenemos las dimensiones del usuario y creamos la matriz con:
const unsigned int DIMENSION_COUNT = 3; // dimension count for this test application, change it at will :)
// here is the type of the multi-dimensional (DIMENSION_COUNT dimensions here) array we want to use
// for this example, it own texts
typedef boost::multi_array< std::string , DIMENSION_COUNT > TextMatrix;
// this provide size/index based position for a TextMatrix entry.
typedef std::tr1::array<TextMatrix::index, DIMENSION_COUNT> Position; // note that it can be a boost::array or a simple array
/* This function will allow the user to manipulate the created array
by managing it''s commands.
Returns true if the exit command have been called.
*/
bool process_command( const std::string& entry, TextMatrix& text_matrix );
/* Print the position values in the standard output. */
void display_position( const Position& position );
int main()
{
std::cout << "Multi-Array test!" << std::endl;
// get the dimension informations from the user
Position dimensions; // this array will hold the size of each dimension
for( int dimension_idx = 0; dimension_idx < DIMENSION_COUNT; ++dimension_idx )
{
std::cout << "Please enter the size of the dimension "<< dimension_idx <<" : ";
// note that here we should check the type of the entry, but it''s a simple example so lets assume we take good numbers
std::cin >> dimensions[dimension_idx];
std::cout << std::endl;
}
// now create the multi-dimensional array with the previously collected informations
TextMatrix text_matrix( dimensions );
std::cout << "Text matrix with " << DIMENSION_COUNT << " dimensions of size ";
display_position( dimensions );
std::cout << " have been created."<< std::endl;
std::cout << std::endl;
std::cout << "Ready!" << std::endl;
std::cout << "Type ''help'' for the command list." << std::endl;
std::cin.sync();
// we can now play with it as long as we want
bool wants_to_exit = false;
while( !wants_to_exit )
{
std::cout << std::endl << ">" ;
std::tr1::array< char, 256 > entry_buffer;
std::cin.getline(entry_buffer.data(), entry_buffer.size());
const std::string entry( entry_buffer.data() );
wants_to_exit = process_command( entry, text_matrix );
}
return 0;
}
Y puede ver que para acceder a un elemento en la matriz, es realmente fácil: solo usa el operador () como en las siguientes funciones:
void write_in_text_matrix( TextMatrix& text_matrix, const Position& position, const std::string& text )
{
text_matrix( position ) = text;
std::cout << "Text /"" << text << "/" written at position ";
display_position( position );
std::cout << std::endl;
}
void read_from_text_matrix( const TextMatrix& text_matrix, const Position& position )
{
const std::string& text = text_matrix( position );
std::cout << "Text at ";
display_position(position);
std::cout << " : "<< std::endl;
std::cout << " /"" << text << "/"" << std::endl;
}
Nota: compilé esta aplicación en VC9 + SP1, obtuve algunas advertencias olvidables.