среда, 26 сентября 2012 г.

Двумерный динамический массив в C++: эмулирование одномерным массивом

Этот пост - первый в коллекции "велосипедов" по работе с двумерными массивами в С++. Оказалось, что удобно иметь место, куда можно послать и где держать краткое описание с пояснениями. Гугление же как правило выдаёт не очень хороший результат: нужное в нём найти можно, но много мусора, а велосипед чаще всего оказывается "не той системы".

Известно, что в С++ поддерживаются команды динамического выделения непрерывной области памяти - под одномерные массивы, для чего сущестует расширенный "квадратными скобками" синтаксис операторов new и delete

  int *iptr = new int[100];//get memory for 100 elements
  delete [] iptr; //free memory

Ожидания многих новичков не оправдываются - оператор для двумерного массива в языке отсутсвует, т.е.
  new int[100][100];//!error
просто ошибка. С другой стороны, он особенно и не требуется, поскольку динамические массивы любой размерности прекрасно создаются при помощи одномерного массива. Для этого достаточно помнить, что в С/С++ массивы хранятся по строкам (в отличие от, например, фортрана). Это значит, что двумерная матрица
   1 2 3
   4 5 6
хранится как одномерный массив
   1 2 3 4 5 6

Иногда после этого начинающий в С/С++ пытается создать одномерный динамический массив и присвоить указатель на него переменной типа двумерного массива (или указателя на указатели)
  int **ptr = NULL;
  int *iptr = new int[100*100];
  ptr = iptr; //!error
Такое присваивание не позволит сделать компилятор, кроме случая явного приведения int** к int*. Но в последнем случае хотя и не будет происходить ошибки на стадии компиляции, при выполнении (как минимум на операциях записи в массив) программа будет остановлена по нарушению доступа к памяти. Это произойдёт потому, что в ptr[i][j] значение из ptr[i] будет рассматриваться как адрес одномерного массива длиной [j]. Поэтому мы не можем использовать нотацию [][] и должны самостоятельно пересчитивать индекс элемента внутри одномерного массива.
Если m и n - размерность требуемого двумерного массива (т.е. число строк и столбцов), то пересчет индексов (обращение к [i,j]-тому элементу) можно осуществлять как
  iptr[i*n+j]

Полный пример создания и использования двумерного динамического массива (на основе 1D-массива)

#include<stdio.h>   //to use memset

typedef long CT; // Cell Type of the array

///////////////////////////////////////////
//   Main function demonstrate 2D array  //
///////////////////////////////////////////
int main (int argc, char** argv)
{
    long n = 10; //variable to obtain 
                 //2D [n,n]-array size.
                 //Input is better, 
                 //but for example purposes
                 //we don't use io routines. 

    //HERE WE GET ARRAY
    //Pointer to and memory allocation for
    //1D-array of n*n elements
    CT *arr = new(nothrow) CT[n*n]; 

    if(!arr){ // no memory allocated
        return 1; //STOP. Put here your code
                  //for no-memory case.
    }

   //Fill array with char(0) values
   //for sizeof(int)*n*n bytes,
   //i.e. init memory with zeroes. 
    memset(arr, static_cast<char>(0),        
           (sizeof(long)/sizeof(char))*n*n);

    //and HERE WE USE ARRAY
    for( int i = 0; i < n; ++i){
       for( int j = 0; j < n; ++j){
           //set arr[x][y] => arr[x*n+y]
           arr[i*n+j]=i*100+j; //write some
       }
    }

    //Free memory when you don't need it 
    delete [] arr; 

    //Set pointer to the de-allocated chunk
    //of memory to NULL to prevent 
    //misuse of already freed memory.
    arr = NULL;

    return 0;
}

С другой стороны, приходится постоянно вручную писать пересчёт индексов [i*n+j], что черевато опечатками и как следствие плохо диагностируемымы ошибками. Поэтому иногда предпочитают определить функцию пересчёта индексов для иключения таких ошибок, например
inline CT& element(const int i, const int j, 
                   CT*const arr, 
                   const int size)
{
    return arr[i*size+j];
}

Тогда цикл обращения будет выглядеть как
    //and HERE WE USE ARRAY
    for( int i = 0; i < n; ++i)
       for( int j = 0; j < n; ++j)
           element(i,j,arr,n) = i*100+j;

Обратим внимание, что функция возвращает ссылку (CT&) на элемент массива, и именно это обеспечивает возможность присваивания element(i,j,arr,n) = 1. Если же возвращать не ссылку на значение, а значение типа CT, то изменять значения элемента массива не получится (хотя чтение так же как и в верхнем случае будет выполняться нормально). Передаваемые же в функцию параметры объявлены константными (const) "для порядку", т.к. внутри функции мы их не меняем.