Матрицы против массивов массивов в C ++ и их динамическое распределение - PullRequest
Новая
       20

Матрицы против массивов массивов в C ++ и их динамическое распределение

1 голос
/ 25 марта 2012

Есть еще кое-что, что я до сих пор не совсем понимаю, о том, как матрицы и другие многомерные массивы представлены в C и C + и как их динамически распределять.

Рассмотрим следующий сегмент кода: 

int main()
{
    int n;
    cin >> n;
    int a[n][n];
    ...
}

Если я правильно понимаю, это выделяет матрицу целых чисел n в n в стеке.К (i, j) -ому элементу матрицы можно получить доступ с помощью [i] [j].Компилятор автоматически преобразует это в доступ к (n * i + j) -ому элементу фактически размещенного одномерного массива.

Предположим теперь, что я хотел бы выделить n по n матрице a накуча, а не стек.Затем я могу сделать следующее: 

int main()
{
    int n;
    cin >> n;
    int** a;
    a = new int*[n];
    for (int i=0;i<n;i++) a[i] = new int[n];
    ...
}

Теперь я снова могу получить доступ к (i, j) -ому элементу как [i] [j].Тем не менее, это не совсем эквивалентно ситуации, описанной выше, так как мне фактически пришлось выделить место для n * n int и n указателей на int.Кроме того, доступ к [i] [j] теперь влечет за собой два доступа к памяти вместо одного.С другой стороны, вычисление индекса n * i + j избегается.

Предположим теперь, что меня интересует n по m матриц, где m мало, например, m = 2.Использование массива указателей строк приводит к потере 33% пространства.Есть ли способ избежать этого?

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

Любая информация будет оценена!

Ответы [ 5 ]

1 голос
/ 25 марта 2012

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

class Matrix
{
    public:
        Matrix(int iRows, int iCols)
        : mRows(iRows), mCols(iCols), m(new int[mRows*mCols]) { }
        ~Matrix() { delete [] m; }

        int &element(int iRow, int iCol) { return m[iRow * mCols + iCol]; }

        int mRows, mCols, *m;
};
1 голос
/ 25 марта 2012

Вы можете отменить порядок распределения.Если вы обеспокоены тем, что из-за указателей «строки» 33% или что-то еще занимает память, почему бы просто не превратить строки в столбцы и наоборот?Тогда вместо [i][j] вы получите доступ к элементу с [j][i].Конечно, это может или не может быть практичным в вашей ситуации, трудно сказать без дополнительной информации.

Но на самом деле, я не вижу проблем с использованием математики индекса, в этом нет ничего плохого по своей сути.

1 голос
/ 25 марта 2012

Скорее вы бы выделили один линейный массив целых чисел: 

int main()
{
    int n;
    cin >> n;
    int *a;
    a = new int[n*n];
}

Выполнение математики индекса - это хороший путь

1 голос
/ 25 марта 2012

Вы могли бы сделать 

 int *mat = new int[n*n];

затем используйте mat[n*i+j]

0 голосов
/ 25 марта 2012

Вы не можете сделать 

int n;
cin >> n;
int a[n][n];

потому что компилятор должен знать точный размер, который вам понадобится в стеке во время компиляции. Это невозможно, когда вы просите об этом во время выполнения :-) С другой стороны, вы можете сделать 

#define N 10
int a[N][N];

В остальных случаях вы должны использовать динамическое распределение.

И выделение в C работает так же, как если бы вы выделяли один фрагмент непрерывной памяти, индексы, такие как [i] [j], являются просто синтаксическим сахаром для перехода в эту память, вы также можете сделать * (a + k * i + j), где k - размер внутреннего массива.

...