5.6. Динамические переменные и массивы
«Кофе в постель могу себе позволить,
но сначала нужно встать, одеться и сварить,
а потом раздеться, лечь и и выпить»
М.Жванецкий
Статический и динамический
Прежде всего, надо разобраться с терминологией статический/динамический применительно к переменным. В самом широком смысле в языках программирования они имеют отношение к моменту связывания свойств объектов программирования (типов данных, переменных, функций) с необходимыми для их существования элементами архитектуры компьютера (командами, адресами и т.п.). Связывание статического свойства объекта происходит при трансляции (компиляции) программы, свойство является динамическим, если связывание его происходит при выполнении программы (см. 1.7).
Процесс связывания свойств объекта программирования (переменной), не является одномоментным. Одни свойства могут быть связаны раньше, другие – позже. Даже одно свойство может связываться в течение нескольких этапов. Например, связывание переменной с ее типом всегда происходит при трансляции. Связывание в ней адреса памяти и значения может происходить в разное время:
глобальные (внешние) переменные размещаются в общем сегменте данных и получают в нем свои адреса уже при трансляции. Аналогично происходит их инициализация (присваивание начальных значений);
локальные переменные размещаются в стеке. Поскольку данные в стеке адресуются относительно текущего положения указателя стека, то при трансляции определяется смещение в текущем фрейме (кадре) стека, сформированном при вызове функции. Выделение памяти и, соответственно, размещение локальных переменных, а также их инициализация происходят во время выполнения при входе в функцию (продвижением указателя стека).
В Си имеет место некоторая путаница с термином статическая переменная. Если исходить из общего понимания термина «статический», то все известные нам до настоящего времени виды переменных (условно называемые нами глобальные и локальные, см.1.6) являются статическими. Это связано с общим для всех переменных подходом: тип переменной и ее размерность определяются при трансляции и в дальнейшем не меняются. Каждым тип данных имеет, аналогично, фиксированную размерность. Таким образом, транслятором осуществляется статическое распределение памяти под переменные программы, т.е. за переменными уже во время трансляции закрепляются известные адреса (или относительные смещения) в соответствующих сегментах памяти программы.
Отдельного обсуждения требуют локальные переменные. Хотя они и создаются в стеке уже при выполнении программы, их размерности, тем не менее, не могут быть изменены (например, размерности локальных массивов тоже должны быть константами). Поэтому это ничего не меняет в общем для всех именованных переменных тезисе: их количество, размерности и суммарный объем известны уже при трансляции и не могут быть изменены при выполнении программы.
Но при написании многих программ заранее неизвестна размерность обрабатываемых данных. При использовании обычных переменных в таких случаях возможен единственный выход - определять размерность «по максимуму». В ситуации, когда требуется обработать данные еще большей размерности, необходимо внести изменения в текст программы и перетранслировать ее. Для таких целей используется команда препроцессора #define с тем, чтобы не менять значение одной и той же константы в нескольких местах программы.
//-------------------------------------------------------------------------------
// Модель стека в массиве ограниченной размерности
#define SZ 1000
int A[SZ],sp = -1;
int PUSH(int vv) {
if (sp == SZ) return 0;
A[++sp] = vv;
return 1;
}Динамические переменные
Назначение и механизм реализации динамических переменных нужно воспринимать в свете только что сформулированного малоутешительного вывода: программа не может превысить лимит памяти, запланированный при трансляции. В противном случае ей потребуется дополнительная память, выделяемая во время выполнения программы.
С этой целью на уровне библиотек в Си создан механизм порождения и уничтожения переменных самой работающей программой. Такие переменные называются динамическими, а область памяти, в которой они создаются – динамической памятью или «кучей». Куча организуется в одном или нескольких дополнительных сегментах памяти, выделяется программе операционной системой. Все в целом называется также системой динамического распределения памяти (ДРП). Перечислим основные свойства динамических переменных:
динамические переменные создаются и уничтожаются работающей программой путем выполнения специальных операторов или вызовов функций;
количество и размерность динамических переменных (массивов) может меняться в процессе работы программы. Это определяется числом вызовов соответствующих функций их параметрами;
динамическая переменная не имеет имени, доступ к ней возможен только через указатель;
функция создания динамической переменной ищет в «куче» свободную память необходимого размера и возвращает указатель на нее (адрес);
функция уничтожения динамической переменной получает указатель на уничтожаемую переменную.
Наиболее важным свойством динамической переменной является ее «безымянность» и доступность по указателю. Кстати, это хорошо согласуется с одним из названий операции * - разыменование указателя. Таким образом, динамическая переменная не может быть доступна «сама по себе», а только опосредованно через другие переменные или обычные именованные указатели. Динамическая переменная может, в свою очередь, содержать один или несколько указателей на другие динамические переменные. В этом случае мы получаем динамические структуры данных, в которых количество переменных и связи между ними могут меняться в процессе работы программы (списки, деревья);
Работа с динамическими переменными и системой ДРП имеет ряд особенностей и сложностей. Они усугубляются еще и тем, что в Си в соответствии с требованиями эффективности программного кода, функции библиотеки минимально защищены от ошибок программирования:
если динамическая переменная создана, а указатель на нее «потерян» программой, то такая переменная представляет собой «вещь в себе» -существует, но недоступна для использования. Тем не менее, занимаемая ею память остается за программой;
ошибки в процессе создания, уничтожения и работы с динамическими переменными (повторная попытка уничтожения динамической переменной, попытка уничтожения переменной, не являющейся динамической и т.д.), приводят к непредсказуемым последствиям в работе программы. Причем программа «валится» иногда не в том месте, где производятся ошибочные действия, при последующих вывовах функций работы с библиотекой.
Операторы управления динамической памятью. Операторы new и delete используются для создания и уничтожения динамических переменных. При создании динамической переменной в операторе new указывается тип создаваемой переменной, оператор имеет тип результата – указатель на создаваемый тип, и значение – адрес (указатель) созданной переменной. Оператор delete получает указатель на уничтожаемую переменную.
double *pd;
pd = new double; // Обычная динамическая переменная
if (pd !=NULL) {
*pd = 5;
delete pd;
} Функции управления динамической памятью низкого уровня. Работать с памятью на Си можно и на «низком» уровне, рассматривая переменные как области памяти известной размерности, используя операции sizeof для получения размерности переменных и преобразование типа указателя для изменения «точки зрения» на содержимое памяти (см. 10.2). Функции распределения памяти низкого уровня «не вникают» в содержание создаваемых переменных, единственно важным для них является их размерность, выраженная естественным для Си способом в байтах (при помощи операции sizeof). Адрес выделенной области памяти также возвращается в виде указателя типа void* - абстрактный адрес памяти без определения адресуемого типа данных.
void *malloc(int size); // выделить область памяти размером
// в size байтов и возвратить адрес
void free(void *p); // освободить область памяти,
// выделенную по адресу p
// расширить выделенную область памяти
// до размера size, при изменении адреса
// переписать старое содержимое блока
void *realloc(void *p, int size);
#include <alloc.h> // библиотека функций управления памятью
double *pd; // Обычная динамическая переменная
pd = (double*)malloc(sizeof(double));
if (pd != NULL) {
*pd = 5;
free(pd);
}Обратите внимание, что оператор delete, функции free и realloc не содержат размерности возвращаемой области памяти. Очевидно, что библиотека, управляющая динамической памятью, должна сохранять информацию о размерности выделенных блоков. Обычно размерность выделенной памяти размещается в первом слове блока, а программа получает адрес памяти «вслед за ним» (см.10.2).
В заключение следует сказать, что динамическим переменным «не повезло»: несмотря на свое исключительное значение в деле представления данных переменной размерности, они синтаксически поддерживаются библиотекой, а не транслятором, то есть по большому счету «не входят в язык».
Динамические массивы
Адресная арифметика указателей и операторы выделения динамической памяти позволяют создавать массивы динамических переменных, или динамические массивы (ДМ), синтаксически не отличимые от обычных:
любой указатель в Си по определению адресует массив элементов указуемого типа неограниченной размерности, при работе с ним можно использовать стандартную операцию индексации [] для работы с памятью как с массивом;
функция malloc и оператор new могут выделять память под массивы переменных. Размерность массива задается значением в квадратных скобках оператора new. В функции malloc объем требуемой памяти указывается как произведение размерности элемента на их количество;
указанные действия происходят во время работы программы и, следовательно, размерность массива может меняться от одного выполнения программы к другому.
#include <malloc.h> // Библиотека функций управления памятью
double *pd1,*pd2; // Массивы динамических переменных
pd1=new double[n1]; // Выделение памяти под ДМ
pd2 = (double*)malloc(n2*sizeof(double));
if (pd1 == NULL || pd2 == NULL) return;
for (i=0; i<n1; i++) pd1[i]=0; // Работа с ДМ
for (i=0; i<n2; i++) pd2[i]=i;
delete []pd1; // Освобождение памяти
free(pd2);Замечание: функции динамического распределения памяти malloc/free/realloc и соответствующие операции new/delete являются механизмами разных уровней и не сводятся один к другому. Функции malloc/free/realloc представляют собой библиотеку «классического» Си и транслятором не контролируются. С их помощью можно работать с обычными переменными и их массивами, но никак не с объектами. Операции new/delete используют собственную систему контроля данных в динамической памяти, к тому же при работе с объектами необходимо использовать исключительно их. Отсюда рекомендации:
не применять для динамической переменной или динамического массива одновременно функции и операции управления динамической памятью;
при работе с объектами использовать только операции new/delete;
при освобождении памяти из-под динамического массива «подсказывать» транслятору, что указатель ссылается именно на массив, записывая перед указателем пустые скобки: delete [] pd1.
Массивы, создаваемые в динамической памяти, называются динамическими. Свойства указателей позволяют одинаковым образом обращаться как с динамическими, так и с обычными массивами. Во многих языках интерпретирующего типа (например, Бейсик) подобный механизм скрыт в самом трансляторе, поэтому массивы там «по своей природе» могут быть переменной размерности.
На самом деле возможность получить массив заданной размерности проблемы не решает. Программа не всегда знает, сколько какой объем данных она получит для обработки. Как можно поступить в таком случае? Есть несколько вариантов:
самый неэффективный: под каждый вид данных резервировать память заранее «по максимуму». Применительно к массиву это означает, что мы заранее выбираем такую размерность, которая никогда не будет превышена. Тем не менее, такое «никогда» рано или поздно может случиться, поэтому процесс заполнения массива лучше контролировать;
приемлемый вариант может быть реализован, если в какой-то момент времени выполнения программа «узнает», какова в этот раз будет размерность обрабатываемых данных. Тогда она может создать динамический массив такой размерности и работать с ним. К сожалению, такое «знание» не всегда возможно;
идеальный вариант заключается в создании такой структуры данных, которая автоматически увеличивает свою размерность при ее заполнении. К сожалению, в случае с массивом ни язык, ни библиотека здесь не помогут – его можно реализовать только программно.
Как известно, функция не может возвратить в качестве результата массив, но она может создать динамический массив во время работы и возвратить указатель на него.
//------------------------------------------------------56-01.cpp
// Строка как динамический массив - объединение строк
char *twoToOne(char *p1, char *p2){
char *out; int n1,n2;
for (n1=0; p1[n1]!='\0'; n1++); // Длина первой строки
for (n2=0; p2[n2]!='\0'; n2++); // Длина второй строки
if ((out = new char [n1+n2+1]) == NULL)
return NULL; // Выделить память под результат
for (n1=0; *p1!='\0';) out[n1++] = *p1++;
while(*p2!=0) out[n1++] = *p2++; // Копировать строки
out[n1] = '\0';
return out; }В данном примере размерность выходной строки определяется элементарно как сумма длин строк. Иногда для этого приходится два раза выполнять одно и тор же действие. Например, при возвращении множителей числа в первый раз разложение требуется провести для определения количества множителей, а после выделения памяти во второй раз – для его заполнения.
//------------------------------------------------------56-01.cpp
//------ Динамический массив простых множителей числа
// Размерность массива определяется двойным вычислением
int *mnog(long vv){
long nn=vv;
for (int sz=0; vv!=1; sz++){ // Цикл определения количества
for (int i=2; vv%i!=0; i++); // Определить очередной множитель
vv = vv / i; }
int *p=new int[sz+1]; // Создать динамический массив
for (int k=0; nn!=1; k++){ // Повторный цикл заполнения
for (int i=2; nn%i!=0; i++); // Определить очередной множитель
p[k]=i; // Сохранить множитель в массиве
nn = nn / i; }
p[k]=0; return p;} // Вернуть указатель на ДМНо наиболее универсальным и распространенным случаем является перераспределение памяти при переполнении массива: создается новый массив большей размерности, в который переписывается содержимое старого. После чего старый уничтожается, а указатель на старый массив устанавливается на новый (новый считается за старый). Все указанные действия можно выполнить единственной функцией нижнего уровня realloc.
«Кофе в постель могу себе позволить, но сначала нужно встать, одеться, сварить, а потом раздеться, лечь и выпить». М.Жванецкий.
//------------------------------------------------------56-01.cpp
// Загрузка динамического массива целых из файла
int *loadInt(char nm[],int &n){
FILE *fd=fopen(nm,"r");
int sz=10,*p=new int[sz]; n=0;
//----------------- или p=(int*)malloc(sz*sizeof(int));
while(fscanf(fd,"%d",&p[n])==1){ // пока есть числа в файле
n++;
if (n==sz){ // массив заполнен
sz*=2; // удвоить размерность
int *q=new int[sz]; // создать новый
for (int i=0;i<n;i++) // копировать старый в новый
q[i]=p[i];
delete p; // уничтожить старый
p=q; // считать новый за старый
//--------------- или p=(int*)realloc(p,sz*sizeof(int));
}} return p;}Отдельного обсуждения заслуживает вопрос, на сколько следует увеличивать размерность нового массива. В нашем примере она удваивается, что приводит к геометрической прогрессии или экспоненциальному росту sz=sz0 2N. На это есть свои причины. При заранее неизвестной размерности программа должна достигать этой размерности достаточно быстро (иначе возникнет эффект «вычерпывания бочки чайной ложкой»). К тому же операция перераспределения тоже является довольно затратной. Можно еще оценить и эффективность использования памяти. Занятыми окажутся от 50% до 100% ячеек последнего выделенного массива (т.е. в среднем 75%). Суммарный объем ранее выделенных массивов будет примерно равен размерности последнего (sz0(1+2+4+…2N-1)=sz0*(2N-1)). Если они не будут использованы другими динамическими структурами, то эффективность снизится до 37.5%.
Более изящно это перераспределение можно сделать с помощью функции низкого уровня realloc, которая резервирует память новой размерности и переписывает в нее содержимое старой области памяти (либо расширяет существующую):
p = (int*) realloc(p,sizeof(int)*(i+1+N));
Вопросы без ответов
Определите содержательный смысл функции, назначение и способ формирования динамического массива.
//------------------------------------------------------56-02.cpp
//----------------------------------------------------- 1
char *F1(char *s)
{ char *p,*q; int n;
for (n=0; s[n] !='\0'; n++);
p = new char[n+1];
for (q=p; n >=0; n--) *q++ = *s++;
return p; }
//------------------------------------------------------- 2
int *F2()
{ int n,i,*p;
scanf("%d",&n);
p=new int[n+1];
for (p[0]=n, i=0; i<n; i++) scanf("&d",&p[i+1]);
return p; }
//------------------------------------------------------- 3
int *F3()
{ int n,i,*p;
scanf("%d",&n);
p=new int[n+1];
for (i=0; i<n; i++)
{ scanf("&d",&p[i]); if (p[i]<0) break; }
p[i]=-1;
return p; }
//------------------------------------------------------- 4
char *F4(char *p, char *q)
{ int n1, n2;
for (n1=0; p[n1]!=0; n1++);
for (n2=0; p[n2]!=0; n2++);
char *s,*v;
s=v=new char[n1+n2+1];
while(*p!=0) *s++ = *p++;
while(*q!=0) *s++ = *q++;
*s=0;
return v; }
//------------------------------------------------------- 5
double *F5(int n, double v[]){
double *p=new double[n+1];
p[0]=n;
for (int i=0; i<n; i++) p[i+1]=v[i];
return p; }
//------------------------------------------------------- 6
int *F6()
{ int *p, n=10,i;
p=(int*)malloc(n*sizeof(int));
for (i=0;;i++){
if (i==n) { n=n*2; p=(int*)realloc(p,sizeof(int)*n); }
scanf("&d",&p[i]);
if (p[i]==0) break;}
return p;}
//------------------------------------------------------- 7
void *F7(void *p, int n)
{ char *pp, *qq, *ss;
qq = ss = new char [n];
for (pp= (char*)p; n!=0; n--) *pp++ = *qq++;
return ss;}
//------------------------------------------------------- 8
int *F8(int n)
{ int s,i,m,k,*p;
s = 10; (int*)malloc(s*sizeof(int));
for (i=2, m=0; i<n; i++) {
for (k=0; k<m; k++)
if (i % p[k]==0) break;
if (k==m)
{ p[m++] = i;
if (m==s){
s=s*2;
p= (int*) realloc( (void*) p,sizeof(int)*s);
}}}
return p; }