Come allocare un array 2D utilizzando l'istruzione One malloc

Question

In un'intervista mi è stato chiesto come allocare un array 2-D e di seguito la mia soluzione.

#include <stdlib.h> 

int **array; 
array = malloc(nrows * sizeof(int *)); 

for(i = 0; i < nrows; i++) 
{ 
    array[i] = malloc(ncolumns * sizeof(int)); 
    if(array[i] == NULL) 
    { 
     fprintf(stderr, "out of memory\n"); 
     exit or return 
    } 
} 

pensavo di aver fatto un buon lavoro, ma poi mi ha chiesto di farlo utilizzando uno malloc() dichiarazione non due. Non ho idea di come ottenerlo.

Qualcuno può suggerirmi qualche idea di farlo in singolo malloc()?

Answer 1

Basta calcolare la quantità totale di memoria necessaria per entrambe le nrows fila punti, ei dati effettivi, aggiungere il tutto, e fare una sola chiamata:

int **array = malloc(nrows * sizeof *array + (nrows * (ncolumns * sizeof **array)); 

Se pensi che questo sembra troppo complesso, è possibile dividerlo e renderlo un auto-documentazione po nominando i diversi termini dell'espressione dimensioni:

int **array; /* Declare this first so we can use it with sizeof. */ 
const size_t row_pointers_bytes = nrows * sizeof *array; 
const size_t row_elements_bytes = ncolumns * sizeof **array; 
array = malloc(row_pointers_bytes + nrows * row_elements_bytes); 

È quindi necessario passare attraverso e inizializzare la riga puntatori in modo che i punti di puntatore di ogni fila al primo elemento di quella particolare fila:

size_t i; 
int * const data = array + nrows; 
for(i = 0; i < nrows; i++) 
    array[i] = data + i * ncolumns; 

si noti che la struttura risultante è sottilmente diverso da quello che si ottiene se si fa ad esempio int array[nrows][ncolumns], perché abbiamo puntatori di riga espliciti, il che significa che per un array allocato in questo modo, non esiste un vero requisito che tutte le righe abbiano lo stesso numero di colonne.

Significa anche che un accesso come array[2][3] fa qualcosa di diverso da un accesso di aspetto simile in un vero array 2d. In questo caso, l'accesso più interno viene eseguito per primo e array[2] legge un puntatore dal terzo elemento in array. Quel puntatore è quindi trattato come la base di una matrice (colonna), nella quale indichiamo per ottenere il quarto elemento.

Al contrario, per qualcosa come

int array2[4][3]; 

quali è un "ricco" matrice 2D corretto occupare la pena di spazio soli 12 numeri interi, l'accesso come array[3][2] rompe semplicemente verso il basso per l'aggiunta di un offset alla base indirizzo per ottenere l'elemento.

Answer 2

int **array = malloc (nrows * sizeof(int *) + (nrows * (ncolumns * sizeof(int))); 

Questo funziona perché in C, gli array sono solo tutti gli elementi uno dopo l'altro come un gruppo di byte. Non ci sono metadati o altro. malloc() non sa se si sta allocando per l'uso come char, inte o linee in un array.

Poi, si deve inizializzare:

int *offs = &array[nrows]; /* same as int *offs = array + nrows; */ 
for (i = 0; i < nrows; i++, offs += ncolumns) { 
    array[i] = offs; 
} 

Answer 3

Dovreste essere in grado di fare questo con (po 'brutto con tutto il casting però):

int** array; 
size_t pitch, ptrs, i; 
char* base; 
pitch = rows * sizeof(int); 
ptrs = sizeof(int*) * rows; 
array = (int**)malloc((columns * pitch) + ptrs); 
base = (char*)array + ptrs; 
for(i = 0; i < rows; i++) 
{ 
    array[i] = (int*)(base + (pitch * i)); 
} 

Answer 4

Ecco un altro approccio.

Se si conosce il numero di colonne in fase di compilazione, si può fare qualcosa di simile:

#define COLS ... // integer value > 0 
... 
size_t rows; 
int (*arr)[COLS]; 
...    // get number of rows 
arr = malloc(sizeof *arr * rows); 
if (arr) 
{ 
    size_t i, j; 
    for (i = 0; i < rows; i++) 
    for (j = 0; j < COLS; j++) 
     arr[i][j] = ...; 
} 

Se stai lavorando in C99, è possibile utilizzare un puntatore ad un VLA:

size_t rows, cols; 
...    // get rows and cols 
int (*arr)[cols] = malloc(sizeof *arr * rows); 
if (arr) 
{ 
    size_t i, j; 
    for (i = 0; i < rows; i++) 
    for (j = 0; j < cols; j++) 
     arr[i][j] = ...; 
} 

Answer 5

Non sono un fan di questo "array di puntatori ad array" per risolvere il paradigma dell'array multidimensionale. Ha sempre privilegiato un array a dimensione singola, accedendo all'elemento con array [row * cols + col]? Nessun problema che incapsula tutto in una classe e che implementa un metodo 'at'.

Se si desidera accedere ai membri dell'array con questa notazione: Matrix [i] [j], è possibile eseguire una piccola magia C++. La soluzione @ John cerca di farlo in questo modo, ma richiede che il numero della colonna sia noto al momento della compilazione. Con un po 'C++ e ignorando l'operatore [], è possibile ottenere questo completamente:

class Row 
{ 
private: 
    int* _p; 

public: 
    Row(int* p)     { _p = p; } 
    int& operator[](int col)  { return _p[col]; } 
}; 


class Matrix 
{ 
private: 
    int* _p; 
    int _cols; 

public: 
    Matrix(int rows, int cols) { _cols=cols; _p = (int*)malloc(rows*cols); } 
    Row operator[](int row)  { return _p + row*_cols; } 
}; 

Così ora, è possibile utilizzare l'oggetto Matrix, per esempio per creare una tabella di moltiplicazione:

Matrix mtrx(rows, cols); 
for(i=0; i<rows; ++i) { 
    for(j=0; j<rows; ++j) { 
     mtrx[i][j] = i*j; 
    } 
} 

Si dovrebbe ora che l'ottimizzatore sta facendo la cosa giusta e non ci sono funzioni di chiamata o altri tipi di sovraccarico. Nessun costruttore è chiamato. Finché non si sposta la matrice tra le funzioni, anche la variabile _cols non viene creata. La dichiarazione mtrx [i] [j] fondamentalmente fa mtrx [i * cols + j].

Answer 6

È possibile allocare i byte di memoria (row*column) * sizeof(int) utilizzando malloc. Ecco uno snippet di codice da dimostrare.

int row = 3, col = 4; 
int *arr = (int *)malloc(row * col * sizeof(int)); 

int i, j, count = 0; 
for (i = 0; i < r; i++) 
    for (j = 0; j < c; j++) 
    *(arr + i*col + j) = ++count; //row major memory layout 

for (i = 0; i < r; i++) 
    for (j = 0; j < c; j++) 
    printf("%d ", *(arr + i*col + j)); 

Answer 7

Come facciamo a destinare una matrice 2D utilizzando One dichiarazione malloc (?)

Nessuna risposta, finora, allocare memoria per una matrice 2D vero.

int **array è un pointer to pointer to int. array non è un puntatore a un array 2D.

int a[2][3] è un esempio di un array 2D vero o array 2 of array 3 of int

---

Per allocare memoria per una vera array 2D, con C99, utilizzare malloc() e salvare un puntatore a una variable-length array (VLA)

// Simply allocate and initialize in one line of code 
int (*c)[nrows][ncolumns] = malloc(sizeof *c); 

if (c == NULL) { 
    fprintf(stderr, "out of memory\n"); 
    return; 
} 
// Use c 
(*c)[1][2] = rand(); 
... 
free(c); 

Senza supporto VLA, se le dimensioni sono costanti, il codice può utilizzare

#define NROW 4 
#define NCOL 5 
int (*d)[NROW][NCOL] = malloc(sizeof *d);