Как динамический 2D-массив хранится в памяти?

Как двумерный массив хранится в памяти?

Я подумал о следующем подходе, когда строки хранятся как непрерывные блоки памяти.

|_________||___< em>______|______ __|________|.. .|_________|

Доступ к элементам осуществляется как (i,j) -> n*i+j, где n — размер матрицы (предположим, что это nxn).

Но что, если я хочу добавить к нему новый столбец? Мне пришлось бы обновлять каждый (n+1)-й элемент в каждой строке, а также сдвигать их вправо, но это слишком затратно в вычислительном отношении.

Другой вариант — скопировать матрицу в новое место и обновить строки элементами нового столбца на лету. Но это тоже не слишком эффективно, если массив большой.

И, наконец, третий вариант, о котором я подумал, - выделить фиксированный объем памяти для каждой строки, и когда я добавляю новый столбец, мне не нужно сдвигать строки вправо.

У меня не может быть пробелов в памяти, поэтому все блоки должны быть смежными.

Я не прошу реализацию C с использованием указателей и фактической оперативной памяти, мне просто любопытен теоретический подход к хранению динамического 2D-массива в памяти, чтобы к нему было легко добавлять новые строки или столбцы. .

Есть ли другие более эффективные подходы?


c memory-management multidimensional-array
person flowerpower    schedule 04.01.2012    source источник
comment
С какими размерами вы работаете? мы говорим о 10 элементах из 1.000.000 элементов?   -  person Martin Kristiansen    schedule 05.01.2012

Ответы (2)


arrow_upward
4
arrow_downward

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

  • удвоить размер ассигнований
  • скопировать все данные из старого массива в новый
  • освободить старый массив

Это было бы двумерным расширением распространенного метода выделения динамических одномерных массивов.

person Greg Hewgill    schedule 04.01.2012
comment
Хорошая идея, но мне интересно, нарушает ли это его требование, чтобы память была непрерывной. - person Jim Clay; 05.01.2012
comment
Это требование было добавлено после того, как был задан исходный вопрос. Я не знаю, означает ли блок конкретную строку или всю структуру данных. - person Greg Hewgill; 05.01.2012
comment
Я имел в виду, что у меня не может быть пробелов в памяти. Предположим, я хочу сохранить его в двоичном файле, я думаю, это подойдет для моего сценария памяти. - person flowerpower; 05.01.2012
comment
В этом случае у вас есть несколько вариантов: (1) хранить память в одном непрерывном блоке, что означает, что вам придется переупорядочивать все, когда вы добавляете новый столбец; (2) используйте схему хранения, как я предлагаю, но записывайте в двоичный файл только активные элементы данных; (3) разрешить пробелы в вашем двоичном файле (вам понадобится заголовок, чтобы описать, в какой форме находятся следующие данные). - person Greg Hewgill; 05.01.2012

arrow_upward
1
arrow_downward

Если вам нужно, чтобы массивы расширялись и были непрерывными в памяти, один из способов добиться этого — просто использовать массив 1d и «подделать» 2-е измерение.

Если ваш первоначальный массив 1d имеет больше места, чем требуется всем вашим массивам 2d, он не потребует перемещения в памяти (потенциально избегая пробелов). Однако в зависимости от того, как вы его реализуете, вставка, которая заставляет один из подмассивов расти, может потребовать перетасовки более поздних элементов (у вас также могут быть пробелы в вашем массиве, но я считаю, что это нарушает ваше требование отсутствия пробелов).

Если вам действительно нужно 2 измерения, то ответ Грега - это то, что вам нужно. Если вы знаете размер ваших данных для начала, это значительно упрощает задачу.

person cjh    schedule 04.01.2012