Способы динамического выделения и освобождения памяти
В С++ имеется два способа работы с динамической памятью:
• использование операций new и delete (основной способ, принятый в С++)
• использование функций malloc (calloc, realloc) и free (способ, доставшийся в наследство от языка С).
Первым способом мы уже пользовались в предыдущей главе для динамического формирования массивов (раздел 1.). Напомним, что операция new выделяет память в динамической области для переменной, исходя из её типа, и возвращает указатель на эту переменную (при захвате памяти под массив обязательно нужно указать количество элементов массива). Операция delete выполняет противоположное действие – она освобождает память, которую занимала переменная, т.е. делает эту область памяти доступной для захвата другими переменными. Для того, чтобы освободить всю память, которая захватывалась под массив, используется синтаксис delete[].
В качестве примера использования операций new и delete на этот раз покажем один из вариантов динамического формирования двумерного массива (матрицы из n строк и m столбцов).
// Пример 2.1 Динамическое формирование двумерного массива
#include <iostream>
using namespace std;
int main()
{
int n, m;
cout<<"n=7"; cin>>n;
int **c=new int*[n]; //сформировали массив указателей на строки
cout<< "m=? "; cin >> m;
for(int i=0;i<n;i++) {
c[i]=new int[m]; // а тут выделяем память для каждой строки
for (int j=0; j<m;j++){
c[i][j]=i+j; // как-то заполняем матрицу значениями
cout.width(4); cout<<c[i][j];
} cout<<endl;
} //пусть матрица больше не нужна - освободим память
for(int i=0;i<n;i++) delete[] c[i];
//освободили память, которую занимал массив указателей
delete[] c;
system("pause");
return 0;
}
Второй способ (принятый в С), кратко поясним, поскольку он тоже иногда используется в программах на С++. Для выделения памяти в этом случае используются функции malloc и calloc, функция realloc используется для изменения размера захваченной ранее области памяти, а для освобождения памяти используется функция free.
Особенности использования функций malloc, calloc и realloc заключаются в следующем:
· размер захватываемой области памяти явно задаётся в байтах, для вычисления размера, исходя из типа, обычно используется операция sizeof
· функции возвращают нетипизированный указатель (их результат имеет тип void*), поэтому для приведения результата к нужному типу обычно используется операция явного преобразования типа (тип *).
Например, для того, чтобы выделить память под массив из n элементов типа double (предполагаем, что значение n ранее было задано в программе), можно использовать функцию malloc или функцию calloc:
double *t=(double *)malloc(n*sizeof(double));
double *t=(double *)calloc(n, sizeof(double));
А чтобы увеличить размер памяти для массива в два раза, можно воспользоваться функцией realloc
double *t=(double *)realloc(t, 2*n*sizeof(double));
Очевидно, синтаксис функций из примеров понятен – не очень удобно, но можно привыкнуть. Добавим только, что если в функции realloc указатель t изначально имеет значение NULL, она выполняется как malloc.
Функция free освобождает память, которая была ранее выделена при помощи любой из выше перечисленных функций. Для нашего примера:
free(t);
Далее мы кратко коснёмся вопросов реализации на С++ динамических структур данных, которые позволяют во многих случаях использовать память более рационально, чем встроенные массивы. Сразу скажем, что уже рассмотренные ранее типы vector и string имеют внутреннюю реализацию, основанную на динамических структурах (если говорить точно – они представляют собой сочетание динамических структур со встроенными массивами). В следующем разделе мы рассмотрим некоторые, на наш взгляд, важные моменты работы с динамическими структурами данных.
Динамические структуры данных
Основные понятия
Определим структуру данных как совокупность элементов данных, между которыми установлены определенные отношения (связи).
В теории и практике программирования наработано большое количество разнообразных структур данных, которые различаются, в основном, способом представления отношений (связей) между данными.
Несмотря на широкое разнообразие структур данных, имеется всего два альтернативных принципа их внутренней организации:
· непрерывная организация — размещение всех элементов структуры по порядку в одной непрерывной области памяти, в результате чего соседние элементы занимают соседние ячейки памяти, и нет необходимости в указании связей между ними явно;
· связная (цепная) организация — отдельные элементы могут располагаться в памяти как угодно (теоретически), но каждый элемент хранит, кроме своего значения, указатели на связанные с ним элементы.
В С++ непрерывная организация используется для встроенных составных типов данных (массивы, struct и union). Ещё раз обратим внимание, что при таком способе требуется сразу выделить память для всех элементов структуры, чтобы обеспечить её непрерывность. Даже при динамическом выделении памяти под массив при помощи операции new или функции malloc (calloc) память всегда выделяется в виде непрерывной области заданного размера.
Для организации связных структур в С++ в большинстве случаев используются указатели. Например, каждый элемент связной структуры может содержать указатель на следующий (предыдущий) элемент или два указателя на два соседних с ним элемента. Из этого следует, что каждый элемент такой структуры состоит из двух различных по значению частей: содержательной (информационной) и указующей (рисунок 2.2). Всодержательной части хранятся данные, для обработки которых и существует данная структура. В указующую часть помещаются указатели на связанные элементы.
 |
Рисунок 2.2Элемент связной структуры данных
При таком подходе нет никакой необходимости выделять память для всех элементов сразу – можно будет захватывать память под каждый новый элемент по мере необходимости. Связные структуры на основе указателей, элементы которых создаются по мере необходимости в динамической памяти, часто называют динамическими структурами данных.Динамические структуры, в которых все элементы, за исключением (возможно) концевых, имеют по одному предыдущему и одному следующему элементу, называют линейными структурами илилинейными списками (связными списками).
В процессе разработки программы часто приходится решать вопрос о выборе подходящей структуры организации данных, при этом часто альтернативными вариантами являются массивы и связные списки. Для полной ясности разберём плюсы и минусы каждого из вариантов.
· Организация данных в виде связных структур на основе указателей обеспечивает более эффективное использование памяти по сравнению с массивами в случае, когда даже ориентировочно заранее не известно количество данных. При использовании массива в такой ситуации приходится резервировать память с большим избытком. С другой стороны, связная структура требует дополнительной памяти для хранения указателей, которая иногда может превышать размер полезной информации;
· Для вставки и удаления элементов в заданной позиции связной структуры не требуется передвигать элементы, как при использовании массивов, достаточно только поменять значения указующих полей соседних элементов. Это преимущество любой связной структуры, независимо от того, как она реализована.
· Основным недостатком связных структур является отсутствие прямого доступа к элементам по индексу. Сам принцип организации связных структур порождает последовательный способ доступа к их элементам (продвижение по цепочке, начиная с самого крайнего элемента, до тех пор, пока не будет достигнут нужный элемент данных).
Сравнение показывает, что ни одна из структур хранения не является идеальной, поэтому довольно часто используются структуры данных, в которых комбинируются непрерывная и связная организация.
Примеры реализации динамических структур на основе указателей
В качестве примеров рассмотрим реализацию двух часто используемых структур данных – стека и очереди. В связи с большой востребованностью в стандартной библиотеке C++ имеются шаблонные типы stack и queue, на основании которых можно создавать стеки и очереди с любым типом элементов (например, stack<int>, queue<char> и т.д.). Так что наши примеры имеют чисто учебное назначение. Тем не менее, на них можно хорошо понять логику реализации любой динамической структуры.
Стек (stack) — это специальный тип списка, в котором все вставки и удаления элементов выполняются только на одном конце, называемом вершиной (top). Такой метод доступа обозначается аббревиатурой LIFO (last-in-first-out — последним пришел — первым вышел).
Основные операции со стеками имеют сложившиеся названия, которыми мы, естественно, воспользуемся.
· Вставка значения х в вершину стека (элемент заталкивается в стек) — операция Push.
· Извлечение элемента с вершины непустого стека (элемент выталкивается из стека) — операция Pop;
· Проверка стека на наличие в нем хотя бы одного элемента – логическая функция empty
· Добавим ещё дополнительную функцию size, которая вычисляет количество элементов в стеке, - с её помощью можно продемонстрировать обход стека.
память под каждый новый элемент, помещаемый на вершину стека, выделяется динамически, поэтому теоретически размер стека не ограничен (на практике, конечно, существуют разумные ограничения). При удалении элемента занимаемая им память немедленно освобождается, таким образом, вся структура занимает ровно столько ячеек памяти, сколько ей требуется в данный момент. Но не нужно забывать, что каждый элемент стека требует больше памяти, чем при реализации с помощью массива, так как в каждом элементе нужно хранить еще и указатель на предыдущий элемент.
Рисунок 2.3. поясняет идею cсылочной реализации стека. Отдельный указатель содержит адрес самого последнего элемента, который будет вершиной стека ( top).
Рисунок 2.3. Ссылочная реализация стека с помощью списка
в динамической памяти
При такой организации можно легко добавлять элементы на вершину, а также удалять их.
Для вставки необходимо:
· захватить память под новый элемент, заполнить данными содержательную часть;
· указующей части присвоить значение указателя на вершину;
· присвоить указателю на вершину адрес нового элемента (он теперь будет вершиной).
· Для извлечения элемента:
· запомнить в буфере данные, хранящиеся в последнем элементе;
· освободить память, которую занимал последний элемент;
· изменить указатель на вершину стека (теперь вершиной будет предпоследний элемент);
· возвратить последний элемент из буфера.
Представленный листинг программы содержит реализацию всех перечисленных операций над стеком – каждая в виде отдельной функции. Конечно, мы могли бы представить здесь и шаблонный класс, как в стандартной библиотеке, но не будем забегать вперёд в процессе обучения. А для того, чтобы сделать реализацию относительно независимой от типа элементов стека, воспользуемся скромными возможностями оператора typedef.
Обратите внимание, что в функции push и pop указатель передаётся по ссылке (*&top).
Пример получился довольно объёмным, потому что в функции main() представлена одна из задач, для решения которой удобно использовать стек. Суть задачи такова – вводится выражение, содержащее круглые скобки. Требуется скобки самого глубокого уровня вложенности оставить без изменения, скобки следующего уровня заменить на квадратные, а все остальные скобки заменить на фигурные.
// Пример 2.2 - реализация стека с примером использования стека
// для замены скобок в скобочном выражении
#include <iostream>
using namespace std;
typedef int type_of_data; // тип элементов (может быть любым, int - пример)
struct item //структура каждого элемента стека
{
type_of_data data; // данные
item *prev; // указатель на предыдущий элемент
};
// прототипы функций
void push (type_of_data, item *&); // поместить значение в стек
type_of_data pop(item *&);// извлечь элемент с вершины стека
int size(item *); //размер стека
bool empty(item *top) {return top==NULL;} // проверка на пустоту
void push (type_of_data x, item *&top)
{
item *p=new item; p->data=x; p->prev=top; // добавили элемент
top=p; // изменили указатель на вершину top
}
type_of_data pop ( item *&top)
{
if (empty(top)) {cerr<< "Error"; return 1;} // аварийная ситуация
type_of_data d=top->data; // запомнили данные последнего элемента
item *p=top; top=top->prev;delete p;//удалили элемент и изменили top
return d; // возвратили данные
}
int size(item *top)
{
item *p=top; int cnt=0;
while (p) {p=p->prev; cnt++;} //обошли все элементы стека
return cnt;
}
int main(){ замена круглых скобок на квадратные и фигурные
item *top=NULL; // создали пустой стек
char s[80]; cout<<"? "; cin.getline(s,80);
int l; //Уровень вложенности скобок в данный момент
for (int i=0; s[i]!=0; i++)
{
if (s[i]=='(') {push(i,top); l=1;}
if (s[i]==')')
if (empty(top)) {cout<<"Error!!!";}
else
{
int p=pop(top);
if (l==2) {s[p]='['; s[i]=']';}
if (l>2) {s[p]='{'; s[i]='}';}
l++;
}
}
if (!empty(top)) cout<<"Error!!!";
else cout << s;
system("pause"); return 0;
}
Здесь хотелось бы обратить внимание на тот факт, что в процессе извлечения данных из стека может возникнуть аварийная (исключительная) ситуация, если стек оказался пустым. Проблема корректной обработки исключительных ситуаций будет далее подробно обсуждаться в пособии, в данном случае мы пошли по самому простому пути – вывода сообщения об ошибке в выходной поток cerr (вместо cout). Такой способ сейчас используется редко, но другого мы пока не знаем.
Очередь(queue) - это другой специальный тип списка, где элементы вставляются в конец списка, называемый хвостом, а удаляются из начала списка, называемого головой. Очереди также называют "списками типа FIFO" (аббревиатура FIFO расшифровывается как first-in-first-out: первым вошел — первым вышел). Операции, выполняемые с очередями, аналогичны операциям со стеками.
Для обозначения операций над очередью воспользуемся теми же словами push и pop, как и для стека, поскольку так они обозначаются в стандартной библиотеке. Для головы и хвоста очереди тоже будем использовать обозначении из библиотеки – front (начало, голова) и back (конец, хвост).
Для реализации очереди, как и стека, достаточно иметь в каждом элементе по одному указателю на следующий элемент, как показано на рисунке 2.4. Но поскольку вставка и удаление выполняются на разных концах, то для эффективной реализации нужно хранить два дополнительных указателя — на хвост и голову очереди.
Рисунок 2.4 Представление очереди при помощи связного списка
Выполнение операций добавления и удаления элементов выполняются немного сложнее, чем для стека, поэтому поясним их рисунками 2.5. и 2.6.
При добавлении элемента в хвост очереди достаточно:
· захватить под него память, заполнить информационную часть данными, указателю присвоить пустое значение;
· изменить указующую часть элемента, бывшего последним;
· присвоить указателю на хвост адрес добавленного элемента — он теперь будет хвостом очереди (рисунок 2.5)
Рис.2.5. Добавление элемента в очередь
Удаление из головы очереди также выполняется просто — достаточно изменить указатель на голову и освободить память, которую занимал элемент, воспользовавшись буферной переменной (рисунок 2.6).
Рисунок 2.6 Удаление (извлечение) элемента из очереди
Ниже приведена реализация очереди в динамической памяти. Функция main на этот раз просто демонстрирует работоспособность основных функций для работы с очередью.
// Пример 2.3 - реализация очереди
#include <iostream>
using namespace std;
typedef int type_of_data; // тип элементов (может быть любым, int - пример)
struct item //структура каждого элемента очереди (аналогична стеку)
{
type_of_data data; // данные
item *next; // указатель на следующий элемент
};
void push (type_of_data, item *&, item *&);// добавить элемент
type_of_data pop(item *&);// извлечь элемент
void show_queue(item *); //вывести элементы очереди на экран
bool empty(item *front) {return front==NULL;} // проверка на пустоту
void push (type_of_data x, item *&front, item *&back)
{
if (empty(front)) //добавление первого элемента в пустую очередь
{ front=new item; front->data=x; front->next=NULL; back=front;
}
else // добавление в непустую очередь
{
item *i=new item; i->data=x;
i->next=NULL; back->next=i; back=i;
}
}
type_of_data pop ( item *&front)
{
if (empty(front)) { cerr << "Error!"; return 1; }
// запомнили данные и указатель
type_of_data x=front->data; item *i=front->next;
delete front; front=i; // удалили голову и переставили указатель
return x; // возвратили данные
}
void show_queue(item *front)
{
item *p=front;
while (p) {
// выводим элемент и идём дальше
cout << p->data <<' '; p=p->next;
}
cout<<endl;
}
int main(){
item *front=NULL, *back=NULL;
for( int i=1; i<=10; i++) push(i, front,back);
show_queue(front);
cout<<pop(front)<<endl; show_queue(front);
system("pause"); return 0;
}
Заметим, что кроме традиционных указателей, в C++ можно (и рекомендуется) использовать так называемые "умные" указатели, реализованные в виде шаблонных классов − о них речь пойдёт в главе 8.