Многомерные динамические массивы

Автор: manager Понедельник, Март 24th, 2008 Нет комментариев

Рубрика: C++. Бархатный путь

Многомерный массив в C++ по своей сути одномерен. Операции new[] и delete[] позволяют создавать и удалять динамические массивы, поддерживая при этом иллюзию произвольной размерности. Деятельность по организации динамического массива требует дополнительного внимания, которое окупается важным преимуществом: характеристики массива (операнды операции new) могут не быть константными выражениями. Это позволяет создавать многомерные динамические массивы произвольной конфигурации. Следующий пример иллюстрирует работу с динамическими массивами.

#include
int fdArr(int **, int, int);
int fdArr(int ***, int, int, int);
// Одноимённые функции. Различаются списками списками параметров.
// Это так называемые перегруженные функции. О них позже.
void main()
{
int i, j;
/* Переменные (!) для описания характеристик массивов.*/
int dim1 = 5, dim2 = 5, dim3 = 10, wDim = dim2;
/*
Организация двумерного динамического массива производится в два этапа.
Сначала создаётся одномерный массив указателей, а затем каждому элементу
этого массива присваивается адрес одномерного массива. Для характеристик
размеров массивов не требуется константных выражений.
*/
int **pArr = new int*[dim1];
for (i = 0; i < dim1; i++) pArr[i] = new int[dim2];
pArr[3][3] = 100;
cout << pArr[3][3] << endl;
fdArr(pArr,3,3);
/*
Последовательное уничтожение двумерного массива┘
*/
for (i = 0; i < dim1; i++) delete[]pArr[i];
delete[]pArr;
/*
Организация двумерного "треугольного" динамического массива. Сначала
создаётся одномерный массив указателей, а затем каждому элементу этого
массива присваивается адрес одномерного массива. При этом размер
(количество элементов) каждого нового массива на единицу меньше
размера предыдущего. Заключённая в квадратные скобки переменная в
описателе массива, которая, в данном контексте, является операндом
операции new, позволяет легко сделать это.
*/
int **pXArr = new int*[dim1];
for (i = 0; i < dim1; i++, wDim—) pXArr[i] = new int[wDim];
pXArr[3][3] = 100;
cout << pArr[3][3] << endl;
fdArr(pXArr,3,3);
/*
Последовательное уничтожение двумерного массива треугольной конфигурации┘
*/
for (i = 0; i < dim1; i++) delete[]pXArr[i];
delete[]pXArr;
/*
Создание и уничтожение трёхмерного массива требует дополнительной итерации.
Однако здесь также нет ничего принципиально нового.
*/
int ***ppArr;
ppArr = new int**[dim1];
for (i = 0; i < dim1; i++) ppArr[i] = new int*[dim2];
for (i = 0; i < dim1; i++)
{
for (j = 0; j < dim2; j++) ppArr[i][j] = new int[dim3];
}
ppArr[1][2][3] = 750; cout << ppArr[1][2][3] << endl; fdArr(ppArr,1,2,3);
for (i = 0; i < dim1; i++)
{
for (j = 0; j < dim2; j++) delete[]ppArr[i][j];
}
for (i = 0; i < dim1; i++) delete[]ppArr[i];
delete[] ppArr;
}
int fdArr(int **pKey, int index1, int index2)
{
cout << pKey[index1][index2] << endl;
}
int fdArr(int ***pKey, int index1, int index2, int index3)
{
cout << pKey[index1][index2][index3] << endl;
}
Функции с изменяемым списком параметров

Для решения задачи передачи неопределённого количества параметров C++ располагает также средствами объявления переменных списков параметров.

Вспомним несколько форм Бэкуса-Наура, определяющих синтаксис списка параметров в определении и прототипе функции.

СписокОбъявленийПараметров ::= [СписокОбъявленийПарам] [...]
::= СписокОбъявленийПарам, …
СписокОбъявленийПарам ::= ОбъявлениеПараметра
::= [СписокОбъявленийПарам,] ОбъявлениеПараметра

Таким образом, список объявлений параметров может завершаться многоточием, отделённым запятой от списка объявлений параметров, этого многоточия в списке параметров может не быть, а возможно также, что кроме многоточия в списке параметров вовсе ничего нет.

Так вот это многоточие предупреждает транслятор о том, что определяемая или объявляемая функция может вызываться с произвольным списком параметров.

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

Рассмотрим прототип и определение функции с переменным количеством параметров.
int PP(┘);
int PP(┘)
{
return 100;
}

Трансляция этого фрагмента кода не вызывает у транслятора никаких возражений. Многоточием в списке параметров он предупреждён о возможных неожиданностях.

Следующий фрагмент кода демонстрирует варианты выражений вызова функции PP().
int retVal;
retVal = PP();
retVal = PP(1,2 + retVal,3,4,5,25*2);
PP('z',25,17);

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

в стековом сегменте выделяется запись активации. Теперь размер записи активации зависит от количества и типа параметров в выражении вызова, (а не прототипа). Так что сначала нужно определить и запомнить общее количество и тип выражений, которые образуют список параметров в выражении вызова функции. Как и раньше, вычисление значений производится в процессе выполнения программы. Как и раньше, значение параметра может быть представлено любыми выражениями;

на основе анализа прототипов вызываемой функции, расположенных в области видимости вызывающей функции, определяются начальные значения параметров (если они имеются), которые и записываются в соответствующие области записи активации. Как мы увидим дальше, в функциях с переменным количеством параметров слева от многоточия всё же может находиться хотя бы один явным образом определённый параметр. В противном случае просто не будет возможности воспользоваться значениями параметров;

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

элементам записи активации присваиваются вычисленные значения. При этом возможно, часть параметров, которым были присвоены значения умолчания (это всегда ближайшие к многоточию параметры), получит новые значения. В этом процессе не допускается неопределённых ситуаций. Либо элемент записи активации получает значение умолчания, либо ему присваивается значение при вызове. Нарушение порядка означивания, как и раньше, выявляется ещё на стадии трансляции программы;

в вызываемой функции всем параметрам, которые были указаны в списке параметров, присваиваются значения из записи активации. Для остальных (непостоянных и, естественно, безымянных) параметров выделяется дополнительная память. Эти параметры также получают свои значения из записи активации;

управление передаётся первому оператору функции. Означенные параметры используются как переменные с определёнными значениями. Доступ к безымянным параметрам, в силу того, что к ним невозможно обращение по имени, обеспечивается специальными алгоритмами.

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

Если же параметр был определён как параметр без имени, то существует единственный способ доступа к таким параметрам — доступ с помощью указателей.

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

С точки зрения реализации всё очень просто. Если бы не одно обстоятельство, которое заметно ограничивает свободу применения подобных функций.

Дело в том, что всякий раз при создании функций с неопределённым количеством параметров, мы вынуждены разрабатывать алгоритм доступа к списку этих самых параметров. А для этого необходимо, по крайней мере, представлять закономерность расположения параметров в списке. Так что список необъявленных параметров не может состоять из подобранных случайным образом элементов, поскольку не существует универсальных средств распознавания элементов этого списка. На практике дело обычно ограничивается несколькими тривиальными вариантами.

При этом либо известен тип и количество передаваемых параметров, и процедура доступа к параметрам сводится к примитивному алгоритму, который воспроизводится в следующем примере:
#include
long PP(int n, …);
void main (void)
{
long RR;
RR = PP(5, 1, 2, 3, 4, 5 );
/*
Вызвали функцию с 6 параметрами. Единственный обязательный параметр
определяет количество передаваемых параметров.
*/
cout << RR << endl;
}
long PP(int n …)
{
int *pPointer = &n;
// Настроились на область памяти с параметрами…
int Sum = 0;
for ( ; n; n—) Sum += *(++pPointer);
return Sum;
}
Либо известен тип элементов списка и признак завершения списка передаваемых параметров. Процедура доступа к параметрам также проста, как и в первом случае:
#include
long PP(int par1 …);
void main (void)
{
long RR;
RR = PP( 1, 2, 0, 4, 0 );
/*
Вызвали функцию с 5 параметрами. Единственный обязательный параметр -
первый параметр в списке параметров.
*/
cout << RRR << endl;
}
long PP(int par1 …)
{
int *pPointer = &par1;
/*
Настроились на область памяти с параметрами. Признак конца списка -
параметр с нулевым значением.
*/
int Sum = 0;
for ( ; *pPointer != 0; pPointer++) Sum += *pPointer;
// Что-то здесь не так┘ Мы так и не обработали до конца весь список.
return Sum;
}
Преобразование основных типов

Вычисление значений выражений в операторах C++ обеспечивается выполнением операций и вызовом функций. Операции используют операнды, функции требуют параметров. Операнды и параметры характеризуются типом. В C++ не существует операций, которые, например, обеспечивали бы сложение или умножение операндов различных типов. Выражения вызова функций также требуют соответствия типа параметров типу параметров определения и прототипа.
Однако не всегда в программе удаётся легко согласовать типы операндов и параметров. И здесь проблем, связанных с согласованием типов операндов и параметров транслятор берёт на себя. Фактически это означает введение ещё одной системы правил, которая называется правилами стандартного преобразования типов.
В общем случае, при определении значения выражения могут возникать следующие ситуации:

1.Присвоение "большему типу" значения "меньшего типа". Безопасное присвоение, гарантирует сохранение значения.
unsigned int UnsignedIntVal;
unsigned char UnsignedCharVal;
UnsignedIntVal = UnsignedCharVal;

2.Присвоение "меньшему типу" значения "большего типа". Потенциально опасное присвоение, грозит потерей информации.
int IntVal;
char CharVal;
CharVal = IntVal;

3.Преобразование значения из "меньшего типа" в "больший тип". Называется расширением типа.
(unsigned int)UnsignedCharVal;

4.Преобразование значения из "большего типа" в "меньший тип". Называется сужением типа. Является опасным преобразованием.
(char)IntVal;

Корректное выполнение действий со значениями различных типов в безопасных случаях и в ряде опасных случаев обеспечивается благодаря реализованной в C++ системе преобразования типов.

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

Присваивание значения объекту преобразует это значение к типу объекта.
unsigned int MyIntU;
MyIntU = 3.14159;
Эквивалентно
MyIntU = (unsigned int)3.14159;

Передача значения при вызове функции преобразует это значение в тип параметра функции. Он становится известен благодаря прототипу вызываемой функции.
void ff(int); // Прототип функции.
:::::
ff(3.14159);
Эквивалентно ff((int)3.14159);

При этом на стадии трансляции возможно появление предупреждения о сужении типа.
В арифметическом выражении тип результата выражения определяется самым "широким" типом среди всех образующих выражение операндов. Этот тип называют результирующим типом выражения. К этому типу преобразуются все остальные операнды.
unsigned int MyIntU = 5;
┘(MyIntU + 3.14159)┘

Результирующим типом выражения здесь оказывается тип double, представленный в выражении литералом 3.14159. В процессе вычисления выражения значение переменной MyIntU преобразуется в 5.0, к которому прибавляется 3.14159.

Преобразование типа при вычислениях арифметических выражений применяется к копиям значений образующих выражение подвыражений. В процессе преобразования типов результаты преобразований подвыражениям не присваиваются.
unsigned int MyIntU = 5;
MyIntU = MyIntU + 3.14159;

Здесь имеют место два последовательных преобразования:
По ходу вычисления выражения значение переменной MyIntU расширяется до double и к расширенной копии значения 5.0 прибавляется 3.14159. После этого результирующее значение 8.14159, в соответствии с первым правилом, сужается до типа unsigned int. В результате чего получается значение 8, которое и присваивается переменной MyIntU.

Указатель на любой не являющийся константой тип можно присваивать указателю типа void*. Этот указатель способен адресовать объекты любого типа данных. Он используется всякий раз, когда неизвестен тип объекта.
int iVal;
int *p_iVal = 0;
char *p_chVal = 0;
void *p_Val;
const int *pc_iVal = &iVal;
p_Val = p_iVal;
p_Val = p_chVal;
// ПРАВИЛО 5 выполняется…
p_Val = pc_iVal;
//Ошибка: pc_iVal — указатель на константу.
const void *pcVal = pc_iVal;
/*
А здесь всё хорошо! Указателю на константу присвоен указатель на константу.
*/

Перед операцией разыменования указатель типа void* нужно явно преобразовать в указатель на конкретный тип, поскольку в этом случае отсутствует информация о типе, подсказывающая транслятору способ интерпретации битовой последовательности, представляемой указателем:
char *p_chValName = "Marina";
p_Val = p_chValName;
p_chVal = (char*)p_Val; /*Явное приведение.*/

Механизм неявных преобразований может быть отключён посредством явного указания в тексте программы требуемого преобразования типов.

Так, модификация ранее рассмотренного примера
MyIntU = MyIntU + (int)3.14159;
отключает механизм неявных преобразований и при вычислении значения переменной производится лишь одно преобразование типа, которое заключается в сужении типа значения литерала 3.14159.
typedef-объявление

На стадии компиляции производится полная идентификация типов всех входящих в программу выражений. Даже отсутствие имени типа в объявлении как, например,
unsigned long MMM;

// Вместо имени типа — комбинация модификаторов unsigned long.
восстанавливается транслятором в соответствии с принятыми в C++ правилами умолчания.
Помимо явного объявления типа в C++ предусмотрены дополнительные средства описания имён типов. Таким средством является typedef-объявление. С его помощью в программу можно ввести новые имена, которые затем используются для обозначения производных и основных типов.

typedef-объявление — это инструмент объявления. Средство ввода новых имён в программу, средство замены громоздких последовательностей имён в объявлениях (но не определениях!) новыми именами.
Синтаксис typedef-объявления как подмножества объявления представляется внушительным списком форм Бэкуса-Наура. Но при известной степени концентрации это нагромождение БНФ всё же можно разобрать:

Объявление ::= [СписокСпецификаторовОбъявления][СписокОписателей];
СписокСпецификаторовОбъявления ::=
СпецификаторОбъявления [СписокСпецификаторовОбъявления]
СпецификаторОбъявления ::= typedef
::= *****
СписокОписателей ::=
[СписокОписателей,] ОписательИнициализатор
ОписательИнициализатор ::= Описатель [Инициализатор]
Описатель ::= dИмя
::= *****
dИмя ::= Имя
::= ОписанноеИмяТипа
::= *****
ОписанноеИмяТипа ::= Идентификатор
СписокСпецификаторовТипа ::=
СпецификаторТипа [СписокСпецификаторовТипа]
СпецификаторТипа ::= ИмяПростогоТипа
::= СпецификаторКласса
::= *****

Таким образом, typedef-объявление является объявлением, которое начинается спецификатором typedef и состоит из последовательностей разнообразных спецификаторов объявления и описателей. Список описателей (элементы списка разделяются запятыми) может содержать языковые конструкции разнообразной конфигурации. В него могут входить описатели (в конце концов, это всего лишь разнообразные имена) с символами ptrОпераций (* и &), описатели, заключённые в круглые скобки, описатели в сопровождении заключённых в скобки списков объявлений параметров, описателей const и volatile, а также заключённых в квадратные скобки константных выражений (последние, надо полагать, предназначены для спецификации массивов).

В качестве примера рассмотрим, следующее typedef-объявление:
typedef int Step, *pInteger;

Это объявление начинается спецификатором typedef, содержит спецификатор объявления int и список описателей, в который входит два элемента: имя Step и имя pInteger, перед которым стоит символ ptrОперации *.
Объявление эквивалентно паре typedef-объявлений следующего вида:
typedef int Step;
typedef int *pInteger;

В соответствии с typedef-объявлениями, транслятор производит серию подстановок, суть которых становится понятной из анализа примера, в котором пара операторов объявления
Step StepVal;
extern pInteger pVal;
заменяется следующими объявлениями:
int StepVal;
extern int * pVal;

На основе этого примера можно попытаться воспроизвести алгоритм подстановки:

после возможного этапа декомпозиции списка описателей typedef-объявления, в результате которого может появиться новая серия typedef-объявлений, транслятор переходит к анализу операторов объявлений;
в очередном операторе объявления выделяется идентификатор, стоящий на месте спецификатора объявления;
среди typedef-объявлений производится поиск соответствующего объявления, содержащего вхождение этого идентификатора в список описателей. Таким образом, транслятор находит соответствующий контекст для подстановки. Мы будем называть этот контекст контекстом замены. Контекст замены оказывается в поле зрения транслятора вместе с оператором объявления, в котором транслятор различает спецификатор объявления и описатель;

оператор объявления заменяется контекстом замены, в котором совпадающий со спецификатором объявления идентификатор заменяется соответствующим описателем.
Если в программе присутствует typedef-объявление
typedef char* (*PPFF) (int,int,int*,float);
то компактное объявление функции
PPFF ReturnerF(int, int);
преобразуется при трансляции в сложное, но как мы далее увидим, абсолютно корректное объявление:
char* (*ReturnerF(int, int))(int,int,int*,float);
При этом по идентификатору PPFF в прототипе функции находится контекст замены char* (*PPFF) (int,int,int*,float), в котором замещаемый описатель PPFF заменяется замещающим описателем ReturnerF(int, int).

Цель достигнута. Простое становится сложным. И как хорошо, что всё это происходит без нашего участия! Перед нами очередное средство для "облегчения" труда программиста.
Заметим, что подстановка возможна и в том случае, когда замещаемый описатель заменяется пустым замещающим описателем.

То же самое typedef-объявление позволяет построить следующее объявление функции:
void MyFun (int, int, int*, float, PPFF);
Рассмотрим ещё один пример.
typedef long double NewType;
/*
Используем спецификатор для ввода в программу нового имени типа.
*/
:::::
NewType MyFloatVal;
Новое имя для обозначения типа введено┘

Новое имя ранее уже поименованного типа называют ОПИСАННЫМ ИМЕНЕМ ТИПА. Именно таким образом и назывался (так выглядел) соответствующий нетерминальный символ во множестве БНФ, связанных с typedef-объявлением.
Описанное имя типа может заменять прежнее имя типа везде, где это возможно, поскольку объявления с описанным именем при трансляции заменяется первоначальным объявлением:
long double MyFloatVal;

В ряде случаев описанное имя типа может оказаться единственным именем для обозначения безымянного типа (об этом позже).

В области действия объявления имени типа (typedef-объявления), идентификатор NewType (он является спецификатором типа) становится синонимом другого спецификатора типа — конструкции long double. Иногда подобным образом вводимый синоним называют замещающим идентификатором.

Использование спецификатора typedef подчиняется следующим правилам (ничто не даётся даром):

1. Спецификатор typedef может переопределять имя как имя типа, даже если это имя само уже было ранее введено typedef спецификатором:
typedef int I;
typedef I I;

2. Спецификатор typedef не может переопределять имя типа, объявленное в одной и той же области действия, и замещающее имя другого типа.
typedef int I;
typedef float I; // Ошибка: повторное описание┘

3. На имена, введённые в программу с помощью спецификатора typedef, распространяются правила области действия, за исключением разрешения на многократное использование имени (правило 1.).

Оставить комментарий

Чтобы оставлять комментарии Вы должны быть авторизованы.

Похожие посты