Как 2D-массивы в C становятся 1D-массивами? - PullRequest
5 голосов
/ 02 февраля 2012

Буду признателен, если кто-нибудь сможет объяснить мне следующее поведение:

Скажем, я объявляю статический 2D-массив

float buffer[NX][NY];

Теперь, если я хочу заполнить этот массив, я заметил, что это можно сделать следующим образом:

initarray(buffer, NX, NY);

#define INITDATAVAL 0.5

void initarray(void *ptr, int nx, int ny)
{
  int i, j;

  float *data = (float *) ptr;

  for (i=0; i < nx*ny; i++)
    {
      data[i] = INITDATAVAL;
    }
}

Мой вопрос: если буфер является 2D-массивом, как его можно использовать в качестве 1D-массива после его передачи в функцию initarray? Я изо всех сил пытаюсь понять это ...

Когда двумерные массивы статически выделяются, выделенная память является смежной, но можно ли использовать этот способ, если вместо нее динамически выделяется buffer?

Ответы [ 7 ]

7 голосов
/ 02 февраля 2012

2D-массив с 3 x 4 элементами (т.е. матрицей) выглядит в памяти следующим образом:

A1 A2 A3 A4 B1 B2 B3 B4 C1 C2 C3 C4

Поскольку базовое хранилище является непрерывным, можно просто преобразовать массив в указатель на первыйэлемент и доступ ко всем элементам, используя одно смещение (это «приведение», которое в таком контексте называется «распадением», происходит автоматически, когда buffer передается initarray).

(В этом примере компилятор переведет выражение, например, buffer[n][m] в buffer + n*NY+m По сути, 2D-массивы - это просто удобная запись для 2D-данных, хранящихся в 1D-массивах).

4 голосов
/ 02 февраля 2012

Массив - это непрерывный ряд объектов.

Массив массивов - это также непрерывный ряд объектов, но эти объекты оказываются массивами, которые сами по себе состоят из своих элементов, помещенных в конец.конец в памяти.Рисунок:

float a[2][3];
a[0]                      a[1]
+-------+-------+-------++-------+-------+-------+
|float  |float  |float  ||float  |float  |float  |
|a[0][0]|a[0][1]|a[0][2]||a[1][0]|a[1][1]|a[1][2]|
|       |       |       ||       |       |       |
+-------+-------+-------++-------+-------+-------+

Поскольку это серия ячеек в строке, содержащих числа с плавающей точкой, ее также можно просматривать как один массив из 6 чисел с плавающей точкой (если смотреть через соответствующий указатель).Новое изображение:

float* b(&a[0][0]);//The &a[0][0] here is not actually necessary
                   //(it could just be *a), but I think
                   //it makes it clearer.
+-------+-------+-------++-------+-------+-------+
|float  |float  |float  ||float  |float  |float  |
|*(b+0) |*(b+1) |*(b+2) ||*(b+3) |*(b+4) |*(b+5) |
|       |       |       ||       |       |       |
+-------+-------+-------++-------+-------+-------+
^       ^       ^        ^       ^       ^       
|       |       |        |       |       |       
b      b+1     b+2      b+3     b+4     b+5

Как видите, a[0][0] становится b[0], а a[1][0] становится b[3].Весь массив можно рассматривать только как серию чисел с плавающей точкой, а не как серию массивов с плавающей точкой.

4 голосов
/ 02 февраля 2012

Для начала initarray должен принимать аргумент float*, а не void*.

Когда вы конвертируете массив в указатель, вы теряете информацию о типе измерения. Вы действительно конвертируете его в указатель на первый элемент и признаете, что хранилище непрерывно.

char foo [2][2] = { {'a','b'}, {'c','d'} }; // Stored as 'a', 'b', 'c', 'd'

Вы можете сохранить информацию о размерах с помощью шаблонов.

template <int W, int H>
void initarray (float (&input)[W][H]) {
    for (int x = 0; x < W; ++x) {
        for (int y = 0; y < H; ++y) {
            input [x][y] = INITDATAVAL;
        }
    }
}

int main () {
    float array [3][4];
    initarray (array);
}

Здесь input является ссылкой на массив данного типа (а размерность является частью полного типа). Вывод аргумента шаблона приведет к перегрузке initarray с W=3, H=4. Извините за жаргон, но вот как это работает.

Между прочим, вы не сможете вызвать эту версию initarray с аргументом указателя, но вы можете предоставить перегрузки, если хотите. Я часто пишу такие вещи

extern "C" void process (const char * begin, const char * end);

template <typename N>
void process (const char * (&string_list) [N]) {
    process (string_list, string_list + N);
}

Идея состоит в том, чтобы предоставить наиболее общий из возможных интерфейсов, реализовать его один раз в отдельном модуле перевода или библиотеке, или в любом другом месте, а затем предоставить более дружественные и безопасные интерфейсы.

const char * strings [] = {"foo", "bar"};
int main () {
    process (strings);
}

Теперь, если я изменю strings, мне не нужно менять код в другом месте. Мне также не нужно думать о раздражающих деталях, например, правильно ли я поддерживал NUMBER_OF_STRINGS=2.

1 голос
/ 02 февраля 2012

Двумерный массив расположен в памяти непрерывно, поэтому при правильном наборе типа вы можете обработать его , как если бы он был объявлен как одномерный массив:

T a[N][M];
T *p = (&a[0][0]);

, поэтому

a[i][j] == p[i*N + j]

За исключением случаев, когда это операнд оператора sizeof или унарный & или строковый литерал, используемый для инициализации массива в объявлении, выражение типа "N-элемент"массив T "преобразуется в выражение типа" указатель на T ", а его значением является адрес первого элемента массива.

При вызове

initarray(buffer, NX, NY);

выражение buffer заменяется выражением типа "указатель на NY -элемент массива float" или float (*)[NY], и это выражение передается в initarray.

Теперь значения выражений buffer и &buffer[0][0] совпадают (адрес массива совпадает с адресом первого элемента в массиве),но типы не (float (*)[NY] в отличие от float *).Это имеет значение в некоторых контекстах.

В C вы можете присваивать значения void * другим указателям на объекты и наоборот без приведения;это не верно в C ++.Мне было бы интересно посмотреть, если G ++ выдает какие-либо предупреждения об этом.

Если бы это был я, я бы явно передал адрес первого элемента буфера:

initarray(&buffer[0][0], NX, NY);

и изменил бы тип первого параметра с void * на float *просто чтобы все было как можно более прямым:

void initarray(float *data, int nx, int ny)
{
  ...
  data[i] = ...;
  ...
}
1 голос
/ 02 февраля 2012

Частичный ответ на ваш отредактированный вопрос:

Когда статически выделяются двумерные массивы, выделенная память является смежной, но можно ли использовать этот способ, если вместо этого динамически выделяется буфер?

Причина, по которой вы можете рассматривать статически размещенный 2D-массив как одномерный массив, заключается в том, что компилятор знает размеры измерений, поэтому может выделить непрерывный блок, а затем вычисляет индекс в этой памяти, когда вы используете операторы индекса, как в буфер [х] [у].

Когда вы распределяете память динамически, вы можете выбрать, чтобы она была 1D или 2D, но вы не можете обрабатывать ее так же, как и в случае статически распределенного массива, потому что компилятор не будет знать размер вашего внутреннего измерения. Так что вы можете:

  • Выделите массив указателей, а затем для каждого из них выделите одномерный массив. Затем вы можете использовать буфер [x] [y] синтаксис.
  • Выделите одномерный массив, но затем вы должны вручную рассчитать индекс самостоятельно в буфере из буфера [y * x_dim + x]
1 голос
/ 02 февраля 2012

Данные просто хранятся последовательно на диске.Вот так:

0:              buffer[0][0],
1:              buffer[0][1],
.                ...
NY-2:           buffer[0][NY-2],
NY-1:           buffer[0][NY-1],
NY:             buffer[1][0],
NY+1:           buffer[1][1],
.                ...
NY*2-2:         buffer[1][NY-2],
NY*2-1:         buffer[1][NY-1],
.                ...
NY*(NX-1):      buffer[NX-1][0],
NY*(NX-1)+1:    buffer[NX-1][1],
.                ...
NY*(NX-1)+NY-2: buffer[NX-1][NY-2],
NY*(NX-1)+NY-1: buffer[NX-1][NY-1],

Массив по сути является указателем на первый элемент.Таким образом, в цикле for вы последовательно заполняете данные, в то время как данные также можно интерпретировать как один массив, содержащий целый блок данных (float[]) или как указатель (float*).

Стоит отметить, что в некоторых (старых / специфических) системах данные могут быть дополнены.Но все системы x86 дополняют 32-битную границу (которая является размером с плавающей точкой), а компиляторы обычно (по крайней мере, MSVC) упаковывают в 32-битное выравнивание, поэтому обычно это нормально.

1 голос
/ 02 февраля 2012

Вся память для двумерного массива была выделена непрерывно.

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...