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

Question

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

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

| _ __ _ __ _ __ || _ __ _ __ _ __ | __ _ __ _ __ | _ __ _ __ _ _ | ... | _ __ _ __ _ __ |

Элементы принимаются как (i, j) -> n * i + j, где n - размерность матрицы (предполагается, что это nxn).

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

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

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

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

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

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

Answer 1

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

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

Это было бы 2D-расширение общего метода для выделения динамических одномерных массивов.

Answer 2

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

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

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