[C++] Как правильно выделить память для двумерного массива и удалить?

[The Nameless One]

Скажите, пожалуйста, так верно?

Код:

Type **type;

Alloc(int N, int M)
{
   type=new Type[N]; 
   for(int i=0; i<N; i++)
   {
          type[i]=new Type[M];
   }
}

...

delete []type;
      

[Finch]

Удаление не верно. Будет происходить утечка памяти. Тут как со скобками, сколько раз было new, столько раз и delete только в обратной последовательности.

[The Nameless One]

Спасибо, а остальное точно верно?

[Finch]

Ну есть еше одна маленькая ошибка, на которую должен компилятор рассказать о тебе все, что он думает. А именно нарущение L уровня в этой строке type=new Type[N];  Ты все таки создаеш массив указателей, а не масив Type. Следовательно  type=new Type* [N];
На форуме только я наверно раза три отвечал на подобные вопросы. Учимся пользоваться поиском.

Ну и на последок, Alloc у тебя определена не правильно Но это я сношу на технологию copy-paste

[The Nameless One]

Finch, спасибо большое. У Alloc забыл указать тип.

[Джон]

А так не проще?

type = new Type[N*M];

[Finch]

Джон, Тут чуть сложнее в работе. Не слишком явные действия. Хотя быстродействие выше.

[Алексей++]

обернуть в класс ) Ещё и удобнее станет

[The Nameless One]

А так не проще?

type = new Type[N*M];

Лучше бы и так, только не могу придумать, как тогда получить очень быстро доступ к элементу, расположенному на клетку выше/ниже текущего элемента? Потом на две клетки, три клетки, может больше.
Только если прибавлять/вычитать к текущему индексу число, условно обозначающее число элементов в  строке?

При условии, что элементы массива выстроены в виде прямоугольной матрицы?

[Алексей++]

Код:

для array1[M][N] или array2[M*N] :

индекс_zb(m_zb,n_zb) = N*m_zb+n_zb

array1[5][10] == *(array1+N*5+10)

array2[5*10] == *(array2+N*5+10)

[The Nameless One]

Вот - вот. Эти умножения уже дорого в моём случае.

[Джон]

Лучше бы и так, только не могу придумать, как тогда получить очень быстро доступ к элементу, расположенному на клетку выше/ниже текущего элемента? Потом на две клетки, три клетки, может больше.
Только если прибавлять/вычитать к текущему индексу число, условно обозначающее число элементов в  строке?

При условии, что элементы массива выстроены в виде прямоугольной матрицы?

Эммм... а какое отношение, я стесняюсь спросить, ВЫДЕЛЕНИЕ памяти под массив (а именно об этом идёт речь) имеет к АДРЕСАЦИИ элементов массива? Как уже неоднократно говорилось, в С++ физически нет двумерных массивов (см. в поиске на форуме, на эту тему я повторяться не буду). Таким образом тебе надо выделить просто непрерывный кусок памяти. А адресация осуществляется как тебе удобно. Лёшка в #9 привёл различные варианты, выбирай какой нравится.

[Джон]

Блин, только ща дошло. Я как-то не вникал в твой изначальный код. Я бы сказал это совсем не то. У тебя в твоём случае получается не двумерный массив, а одномерный массив указателей на объекты такого же типа разбросанные в куче где попало.
Таким образом доступ у тебя случайный, что гораздо медленней, чем при работе с непрерывным куском памяти. Если уж ты решил использовать массив, то и надо использовать его основное преимущество. Я уже говори о неэффективном использовании памяти.

Смотри, допустим размер объекта Type больше чем 32 бит (ведь он у тебя не содерит только одно поле данных целого типа, верно, иначе нафига его вобще делать, можно взять просто int). Сначала ты выделяешь память размером N*sizeof(Type), а используешь из неё только 32 бит*N, на 32х разрядной системе указатель занимает 32 бита:

Код:

type[i]=new Type[M];

Значит остальная память отведённая под Type не используется.

Finch, уже заметил, что тебе надо бы создать массив размером N*размер указателя. Но всё-равно, скорость доступа к элементам такого "массива" гораздо ниже, чем к элементам настоящего массива.

Так что память надо выделять одним куском.

[RXL]

Стоит вспомнить, что в современных процессорах целочисленные вычисления производятся очень быстро - быстрее, чем промах кеша и последующая загрузка данных из памяти. Т.ч. в оптимизации по быстродействию надо ориентироваться прежде всего на расположение обрабатываемых данных в кеше, а стоимостью вычислением индекса можно пренебречь.
Разброс объектов по памяти еще приводит к тому, что описания страниц виртуальной памяти могут отсутствовать в кеше TLB и процессору их тоже придется подгружать из памяти.

Исходя из этого считаю, что разовое выделение new Type[N*M] эффективнее. У таких объектов больше шансов оказаться в кеше во время обработки. Удаление: delete[] ptr;

У меня валяются старые номера (2001-2002) давно закрывшегося журнала Программист. Там были статьи по оптимизации Криса Касперски. Одна из статей была посвящена оптимальному расположению набора небольших однотипных объектов.
Например, вместо выделения N раз памяти под каждый объект, можно выделить сразу пул под >= N объектов. Это особенно эффективно для структур типа связанных списков. При этом объекты могут ссылаться друг на друга уже не указателями, а индексами. Вычислений становится немного больше, а эффективность выше.

[Вад]

В порядке упражнения, можно попробовать разработать тип "двумерный массив", который будет размещаться в непрерывном блоке памяти и поддерживать изменение размеров и построчную адресацию, предоставляя удобный интерфейс и скрывая пресловутое умножение
И тут уже можно реализовать оптимизацию, связанную с тем, что внутреннее представление массива будет резервировать под каждую строку память по степеням двойки Оно так в кэш ровнее ложиться будет, и построчное смещение считать быстрее.

[The Nameless One]

Большое спасибо каждому участнику, мне это очень помогает)
Я отказался от двумерного массива сразу же, теперь new Type[N*M]
Т.е. теперь память не будет в куче вразброс выделена под это дело?
И просто перебор одномерного массива будет эффективен?

Хочу расставить точки над i еще вот над чем.
Неоднократно слышал, что std::vector быстрее обычного массива, если размер вектора заранее подготовить под то число элементов, которые в нем будут обрабатываться.
Я не смотрел внутреннее устройство STL, может ли это быть правдой?

И третий момент.
Если создать так (в стеке, если не ошибаюсь)
Type array[10][10] = {{n0}, ...{n9}}; - память будет одним куском?

[RXL]

С вектором врут — эффективность ровно та же, что и с одномерным массивом. Т.к. это фактически одно и тоже.

[Алексей++]

Если создать так (в стеке, если не ошибаюсь)
Type array[10][10] = {{n0}, ...{n9}}; - память будет одним куском?

ну так одним куском в стеке и будет

[The Nameless One]

Спасибо, я ещё на шаг ближе к полному пониманию С++

[Алексей++]

полное понимание с++  -это та ещё задача ) Думаю, никто, кроме самого Страуструпа, так не умеет )

[sd]

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

[Dimka]

sd, а в C/C++ нет многомерных массивов. Это уже низкий уровень. Поэтому любая хорошая книжка по C/C++.

[sd]

Если не трудно, скажи название книжки.

[Dimka]

Например, вузовский учебник Подбельского и Фомина.

[sd]

В книге, которую посоветовал Dimka в #23, я не нашел интересующей меня информации, поэтому спрошу тут. Объясните пожалуйста принципиальное отличие между

Код:

BYTE* Array=new BYTE [x_max*y_max];

и

Код:

BYTE** Array=new BYTE* [y_max];
for(int i=0; i<y_max; i++)
{
	Array[i]=new BYTE[x_max];
}

То, что в первом случае массив в памяти сплошной (элементы идут следом друг за другом), а во втором сплошные только подмассивы, а сами подмассивы могут быть "не рядом" это я понял. Расскажите, пожалуйста, подробней где для каждого из случая выделяется память и как работать с такими массивами?
Я уже писал, что мне надо реализовать класс двумерного массива. Я буду пробовать, потом, то, что напишу, скину сюда, а вы оцените, ок?

[Алексей++]

sd, в обоих случаях память выделяется в куче. А где именно - одному компутеру известно, хотя можешь адреса глянуть, если интересно сильно ))

[Антон (LogRus)]

и как работать с такими массивами?

sd, полагаю стоит просто реализовать оба варианта
работы на полчаса, ну или на час если захочется красивых интерфейсов и прочих рюшек

[sd]

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

Код: (C++)

class MatrixType {
        int xSize;
        int ySize;
        int *mtrx;
        void SetMatrix(const MatrixType &obj);
public:
        MatrixType(void): xSize(0), ySize(0), mtrx(0) {}
        MatrixType(int ySz, int xSz);
        MatrixType(const MatrixType &obj);
        ~MatrixType(void) {delete []mtrx;}

        MatrixType& operator=(const MatrixType &obj);
        friend ostream &operator<<(ostream &stream, MatrixType &obj);

        int GetElement(int yIndx, int xIndx) const;
        void SetElement(int yIndx, int xIndx, int val);
        int GetRows(void) {return ySize;}
        int GetCols(void) {return xSize;}
};

.cpp файл

Код: (C++)

#include "MatrixType.h"


MatrixType::MatrixType(int ySz, int xSz) {
        xSize=xSz;
        ySize=ySz;

        try {
                mtrx=new int [ySize*xSize];
        }
        catch (bad_alloc ba) {
                cout<<ba.what()<<endl;
        }

        for(int y=0; y<ySize; y++)
                for(int x=0; x<xSize; x++)
                        *(mtrx+xSize*y+x)=0;
}

void MatrixType::SetMatrix(const MatrixType &obj) {
        xSize=obj.xSize;
        ySize=obj.ySize;

        try {
                mtrx=new int [ySize*xSize];
        }
        catch (bad_alloc ba) {
                cout<<ba.what()<<endl;
        }

        for(int y=0; y<ySize; y++)
                for(int x=0; x<xSize; x++)
                        *(mtrx+xSize*y+x)=*(obj.mtrx+xSize*y+x);
}

MatrixType::MatrixType(const MatrixType &obj) {
        SetMatrix(obj);
}

MatrixType &MatrixType::operator=(const MatrixType &obj) {
        if(&obj==this)
                return *this;

        delete []mtrx;

        SetMatrix(obj);

        return *this;
}

int MatrixType::GetElement(int yIndx, int xIndx) const {
        return *(mtrx+xSize*yIndx+xIndx);
}

void MatrixType::SetElement(int yIndx, int xIndx, int val) {
        *(mtrx+xSize*yIndx+xIndx)=val;
}

ostream &operator<<(ostream &stream, MatrixType &obj) {
        for(int y=0; y<obj.ySize; y++) {
                for(int x=0; x<obj.xSize; x++)
                        stream<<*(obj.mtrx+obj.xSize*y+x)<<" ";
                stream<<endl;
        }

        return stream;
}

[Dimka]

В книге, которую посоветовал Dimka в #23, я не нашел интересующей меня информации

А между тем там прямым текстом разъясняется разница именно для случая двумерного массива и массива динамических массивов.

Речь идёт о старой редакции для языка Си. В учебнике для C++ может быть этот момент пропущен.

[Вад]

1) Я бы сделал класс шаблонным (мало ли, какой конкретно тип захочется хранить в массиве),
2) добавил бы метод at(x,y), возвращающий ссылку на элемент (в двух вариантах - обычную, если значение захочется поменять, и константную, если не захочется),
2a) реализовал бы обращение к элементу двумя способами: с проверкой выхода за границы индексов и без проверки.
3) не стал бы делать оператор вывода членом класса (зачем? это же контейнер)
4) Убрал бы дублирующийся код, включая ненужный метод SetMatrix. Считается хорошей практикой делать копирующий оператор с помощью копирующего конструктора временного объекта, с последующим обменом содержимого временного объекта и this.
5) Не перехватывал бы исключения работы с памятью (и уж точно не писал бы их просто так в лог, не давая знать "наверх", что произошла проблема)

И, возможно, сделал бы реализацию квадратных скобок, чтобы было удобнее работать в привычной нотации двумерных массивов (типа,  a[i][j] = 0;) - это потребовало бы, чтобы строка тоже была контейнером (или выступала как прокси, что, может быть, лучше с т.з. контроля за операциями над нею).