Как выделить 2-D массив с помощью одного оператора malloc

Question

В одном из интервью меня спросили, как мне выделить двумерный массив, и ниже было мое решение для него.

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

Я думал, что хорошо поработал, но потом он попросил меня сделать это, используя одно malloc() утверждение, а не два. Я понятия не имею, как этого добиться.

Может кто-нибудь предложить мне идею сделать это в сингле malloc()?

Answer 1

Просто вычислите общий объем памяти, необходимый как для nrows указателей строк, так и для фактических данных, сложите все это и выполните один вызов:

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

Если вы думаете, что это выглядитслишком сложный, вы можете разделить его и сделать его немного самодокументированным, назвав различные термины выражения размера:

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);

Затем вам нужно пройти и инициализировать указатели строк так, чтобы каждая строкауказатель указывает на первый элемент для этой конкретной строки:

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

Обратите внимание, что результирующая структура несколько отличается от того, что вы получите, например, int array[nrows][ncolumns], потому что у нас есть явные указатели строк, что означает, что длядля массива, выделенного следующим образом, нет реального требования, чтобы все строки имели одинаковое количество столбцов.

Это также означает, что такой доступ, как array[2][3], делает нечто отличное от аналогичного доступа в реальном 2d-массиве.,В этом случае самый внутренний доступ происходит первым, и array[2] считывает указатель с 3-го элемента в array.Этот указатель затем обрабатывается как основание массива (столбца), в который мы индексируем, чтобы получить четвертый элемент.

Напротив, для чего-то вроде

int array2[4][3];

, который является "упакованный "правильный 2d массив, занимающий всего 12 целых чисел, доступ, такой как array[3][2], просто разбивается на добавление смещения к базовому адресу, чтобы получить элемент.

Answer 2

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

Это работает, потому что в C массивы - это просто все элементы один за другим в виде набора байтов. Нет метаданных или чего-либо еще. Функция malloc () не знает, выделяется ли она для использования в качестве символов, целых или строк в массиве.

Затем вы должны инициализировать:

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

Answer 3

Вот другой подход.

Если вы знаете количество столбцов во время компиляции, вы можете сделать что-то вроде этого:

#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] = ...;
}

Если вы работаете в C99, вы можете использовать указатель на 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 4

Как мы можем выделить 2-D массив с помощью одного оператора malloc (?)

Пока нет ответов, пока не выделим память для настоящего 2D-массива.

int **array - это указатель на указатель на int .array не является указателем на двумерный массив.

int a[2][3] является примером истинного двумерного массива или массив 2 массива 3 типа int

---

Чтобы выделить память для истинного 2D-массива, с помощью C99 используйте malloc() и сохраните указатель на массив переменной длины (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);

Без поддержки VLA, если размеры постоянны, код может использовать

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

Answer 5

Вы должны быть в состоянии сделать это (хотя и уродливо со всеми приведениями):

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 6

Я не фанат этого «массива указателей на массив» для решения парадигмы многомерного массива. Всегда отдавал предпочтение одному массиву измерений, при доступе к элементу с массивом [row * cols + col]? Нет проблем с инкапсуляцией всего в классе и реализацией метода at.

Если вы настаиваете на доступе к членам массива с помощью этой записи: Matrix [i] [j], вы можете немного поработать над магией C ++. Решение @John пытается сделать это таким образом, но он требует, чтобы номер столбца был известен во время компиляции. С некоторым C ++ и переопределением оператора [], вы можете получить это полностью:

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

Итак, теперь вы можете использовать объект Matrix, например, для создания таблицы умножения:

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

Теперь вы должны сказать, что оптимизатор делает правильные вещи, и нет функции вызова или каких-либо других видов служебных данных. Никакой конструктор не вызывается. Пока вы не перемещаете матрицу между функциями, даже переменная _cols не создается. Утверждение mtrx [i] [j] в основном делает mtrx [i * cols + j].

Answer 7

Вы можете выделить (row*column) * sizeof(int) байтов памяти, используя malloc.Вот фрагмент кода для демонстрации.

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));