Многомерные массивы, массивы указателей, динамические массивы

Многомерный массив в соответствии с синтаксисом языка - массив массивов, т.е. массив, элементами которого служат массивы. Определение многомерного массива в общем случае должно содержать сведение о типе, размерности и количествах элементов каждой размерности:

type имя_массива[K1][K2]… [KN];

type – допустимый тип (основной или производный); имя_массива – идентификатор; N – размерность массива, К – количество в массиве элементов размерности К -1 каждый. Например: long Array[4][3][6];

Трехмерный массив Array состоит из четырех элементов, каждый из которых – двухмерный массив с размерами 3х6. Язык Си++ гарантирует, что в памяти компьютера элементы массива будут размещаться последовательно друг за другом в порядке возрастания самого правого индекса, т. е. самый младший адрес имеет элемент Array[0][0][0], затем идёт Array[0][0][1], Array[0][0][2], …, Array[0][0][5] далее

Array[0][1][0], Array[0][1][1], …, Array[0][1][5], далее Array[0][2][0], …, Array[0][2][5] заканчивается первый и далее начинается второй элемент двухмерного массива с размерами 3х6 Array[1][0][0], Array[1][0][1] и т. д.

С учётом порядка расположения в памяти элементов многомерного массива нужно размещать начальные значения его элементов в списке инициализации.

Так long Array[4][3][6] = {0,1,2,3,4,5,6,7,8,9}; такая запись означает, что начальные значения получат первые десять элементов массива Array, т.е.

Array[0][0][0] = = 0, Array[0][0][1] = =1, Array[0][0][2]= = 2, Array[0][0][3] = =3, Array[0][0][4] = = 4, Array[0][0][5] = = 5, Array[0][1][0] = = 6, Array[0][1][1] = = 7, Array[0][1][2] = = 8, Array[0][1][3] = = 9. Остальные элементы массива Array остались не инициализированными.

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

long A[4][5][6] = { {{0}},

{ {100}, {110, 111} },

{ {200}, {210}, {220, 221, 222}} };

так задаётся только некоторое значения его элементов:

А[0][0][0] = = 0

А[1][0][0]== 100, А[1][1][0] == 110, А[1][1][1] == 111

А[2][0][0] = = 200, А[2][1][0] = = 210,

А[2][2][0]== 220, А[2][2][1] == 221, А[2][2][2] == 222

Остальные элементы массива явно не инициализируются.

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

float matrix [][5] = { {1}, (2}, {3} };

формирует массив matrix с размерами 3х5, но не определяет явно начальных значений всех его элементов. Оператор

cout « "\n sizeof(matrix) = "«sizeof(matrix); /*выведет на экран: sizeof(matrix)=60*/

Начальные значения получают только

matrix[0][0] = 1

matrix[1][0] = 2

matrix[2][0] = 3

Как и в случае одномерных массивов, доступ к элементам многомерных массивов возможен с помощью индексированных переменных и с помощью указателей. Возможно объединение обоих способов в одном выражении. Чтобы не допускать ошибок при обращении к элементам многомерных массивов с помощью указателей, нужно помнить, что при добавлении целой величины к указателю его внутреннее значение изменяется на "длину" элемента соответствующего типа. Имя массива всегда константа-указатель. Для массива, определенного как type ar [N] [M] [L], ar - указатель, поставленный в соответствие элементам типа type [M] [L]. Добавление 1 к указателю ar приводит к изменению значения адреса на величину sizeof(type) * M * L.

Именно поэтому выражение * (ar + 1) есть адрес элемента ar[l], т.е. указатель на массив меньшей размерности, отстоящий от начала массива (&ar[0]), на размер одного элемента type[M] [L]. Сказанное иллюстрирует следующая программа:

//Программа 5.5

#include "stdafx.h"

#include <iostream>

void main(){

int b[3][2][4] = {0, 1, 2, 3,

10, 11, 12, 13,

100, 101, 102, 103,

110, 111, 112, 113,

200, 201, 202, 203,

210, 211, 212, 213,

};

// Адрес массива b[][][]

std::cout << "\nb = " << b;

// Адрес массива b[0][][]

std::cout << "\n*b = " << *b;

// Адрес массива b[0][0][]

std::cout << "\n**b = " << **b;

// Элемент b[0][0][0]

std::cout << "\n***b ="<< ***b;

// Адрес массива b[1][][]

std::cout << "\n*(b + 1) = " << *(b + 1);

// Адрес массива b[2][][]

std::cout << "\n*(b +2) = " << *(b + 2);

// Адрес массива b[0][1][]:

std::cout << "\n*(*b + 1) = " << *(*b + 1);

std::cout << "\n*(*(*(b + 1) + 1) + 1) = " <<*(*(*(b + 1) + 1) + 1);

std::cout << "\n*(b[l][l]+ 1) = " << *(b[1][1] + 1);

//Элемент b[2][0] [0];

std::cout<< "\n*(b[l] + 1)[1] = " << *(b[1] + 1)[1];

getchar();

}

Результаты выполнения программы:

b = 0x8d880fd0

*b = 0x8d880fd0

**b = 0x8d880fd0

***b = 0

*(b + 1) = 0x8d880fe0

*(b + 2) = 0x8d880ff0

*(*b + 1) = 0x8d880fd8

*(*(*(b + 1) + 1) + 1) = 111

*(b[1][1] + 1) = 111

*(b[1] + 1) [1] = 200

В программе доступ к элементам многомерного массива осуществляется с помощью операций с указателями. В общем случае для трехмерного массива индексированный элемент b[i] [j] [k] соответствует выражению *(*(* (b + i) + j) + k). В нашем примере:

*(*<*(b + 1) + 1) + 1) == b[1][1][1] ==111

Допустимо в одном выражении комбинировать обе формы доступа к элементам многомерного массива:

*(b[1][1] + 1) == 111

Как бы ни был указан путь доступа к элементу многомерного массива, внутренняя адресная арифметика, используемая компилятором, всегда предусматривает действия с конкретными числовыми значениями адресов. Компилятор всегда реализует доступ к элементам массива с помощью указателей и операции разыменования. Если в программе использована, например, такая индексированная переменная: ar[i][j][k], принадлежащая массиву type ar[N][M][L], где N, M, L - целые положительные константы, то последовательность действий компилятора такова:

· выбирается адрес начала массива, т.е. целочисленное значение указателя ar, равное (unsigned long)ar;

· добавляется смещение i * (М * L) * sizeof(type) для вычисления начального адреса i-го массива с размерами M на L, входящего в исходный трехмерный массив;

· добавляется смещение для вычисления начального адреса j-й строки (одномерный массив), включающей L элементов. Теперь смещение равно (i * (М * L) + j * L) * sizeof (type);

· добавляется смещение для получения адреса k-го элемента в строке, т.е. получается адрес (unsigned long) (i * (M * L) + j * L + k) * sizeof(type);

· применяется разыменование, т.е. обеспечивается доступ к содержимому элемента по его адресу: * ((unsigned long) (i * (м * l) + j * l + k)).

Массивы указателей. Синтаксис языка Си++ в отношении указателей непротиворечив, но весьма далек от ясности. Для понимания, что же определено с помощью набора звездочек, скобок и имен типов, приходится аккуратно применять синтаксические правила, учитывающие последовательность выполнения операций. Например, следующее определение

int *array[6];/*вводит массив указателей на объекты типа int. Имя массива array, он состоит из шести элементов, тип каждого int* . Определение*/

int (*ptr)[6]; /*вводит указатель ptr на массив из шести элементов, каждый из которых имеет тип int. Таким образом, выражение (array + 1) соответствует перемещению в памяти на sizeof (int ) байтов от начала массива (т.е. на длину указателя типа int ). Если прибавить 1 к ptr, то адрес изменится на величину sizeof (int[6]), т.е. на 12 байт при двухбайтовом представлении данных типа int.*/

int *ptr2; ptr2+1

Эта возможность создавать массивы* указателей порождает интересные следствия, которые удобно рассмотреть в контексте многомерных массивов.

По определению массива, его элементы должны быть однотипными и одного "размера". Предположим, что мы хотим определить массив для представления списка фамилий (учеников класса, сотрудников фирмы и т.п.). Если определять его как двухмерный массив элементов типа char, то в определении для элементов массива необходимо задать предельные размеры каждого из двух индексов. Таким образом, "прямолинейное" определение массива для хранения списка фамилий может быть таким:

char spisok[25][20];

Для примера здесь предполагается, что количество фамилий в списке не более 25 и что длина каждой фамилии не превышает 19 сим­волов (букв). После такого определения или с помощью инициализа­ции в самом определении в элементы spisok[0], spisok[l], ... можно занести конкретные фамилии, представленные в виде строк. Размеры так определенного массива всегда фиксированы.

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

char spisok[][20] = { "Иванов", "Петров", "Сидоров" };

Теперь в массиве spisok только 3 элемента, каждый из них длиной 20 элементов типа char (рис. 5.2).

Рис. 5.2. Двухмерный массив char spisok[3][20] и одномерный массив указателей char *pointer[3], инициализированные одинаковыми строками

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

В противоположность этому при определении и инициализации теми же символьными строками одномерного массива указателей типа char* память распределяется гораздо рациональнее:

char *pointer [] = {"Иванов", "Петров", "Сидоров"};

Для указателей массива pointer, в котором при таком определении 3 элемента и каждый является указателем-переменной типа char *, выделяется всего 3*sizeof (char *) байтов. Кроме того, компилятор размещает в памяти три строковые константы "Иванов" (7 байт), "Петров" (7 байт), "Сидоров" (8 байт), а их адреса становятся значениями элементов pointer[0], pointer[1], pointer[2]. Сказанное иллюстрирует рис. 5.2.

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

//Программа 5.6

#include "stdafx.h"

#include <iostream>

void main (){

char *pointer []={"Ivanov", "Petrov", "Cidorov", "Antonov"};

int i, j;

char* temp;

int iNumberOfElement = 4;

for(i = 0; i < iNumberOfElement; i++) std::cout<<"\n\n"<< pointer [i];/*Печать исходного массива*/

//Сортировка по алвавиту

for(i = 0; i < iNumberOfElement -1; i++)

for(j = iNumberOfElement-1; j>i;j--){

if(strcmp(pointer [j], pointer [j-1]) >0){

temp = pointer [j]; // Меняем местами указатели

pointer [j] = pointer [j-1];

pointer [j-1] = temp;

}

}

std::cout<<"\n\n\n";/*Печать отсортированного массива */

for(i = 0; i < iNumberOfElement; i++) std::cout<<"\n "<< pointer [i];

getchar();

}

int strcmp(char* str1, char*str2);

Накладными расходами при этой "косвенной" сортировке списков объектов является требование к памяти, необходимой для массива указателей. Выигрыш - существенное ускорение сортировки.

void* malloc(unsigned int size);

void free(void* p)

type* new type;

delete type*;

type* new type[выражение];

delete [] type*;

Массивы динамической памяти. В соответствии с синтаксисом операция new при использовании с массивами имеет следующий формат:

new тип_массива

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

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

long (*1р)[2][4]; // Определили указатель

1р = new long[3][2][4]; // Выделили память для массива

В данном примере использован указатель на объекты в виде двухмерных массивов, каждый из которых имеет фиксированные размеры 2х4 и содержит элементы типа long. В определении указателя следует обратить внимание на круглые скобки, без которых обойтись нельзя. После выполнения приведенных операторов указатель 1р становится средством доступа к участку динамической памяти с размерами 3 ´ 2 ´ 4 ´ sizeof (long) байтов. В отличие от имени массива (имени у этого массива из примера нет) указатель 1р есть переменная, что позволяет изменять его значение и тем самым, например, перемещаться по элементам массива.

Изменять значение указателя на динамический массив нужно с осторожностью, чтобы не "забыть", где же находится начало массива, так как указатель, значение которого определяется при выделении памяти для динамического массива, используется затем для освобождения памяти с помощью операции delete. Например, оператор;

delete [] 1р;

освободит целиком всю память, выделенную для определенного выше трехмерного массива, если 1р адресует его начало. Следующая программа иллюстрирует сказанное:

Выделение и освобождение памяти для массива

//Программа 5.7

#include "stdafx.h"

#include <iostream>

void main(){

long (*lp) [2][4];

lp = new long [3][2][4];

std::cout<< "\n";

for (int i = 0; i < 3; i++) {

std::cout << "\n";

for (int j = 0; j < 2; j++)

for (int k = 0; k < 4; k++) {

lp[i][j][k] = i + j + k;

std::cout<<'\t'<< lp[i][j][k];

}

}

getchar();

delete [] lp;

}

Результаты выполнения программы:

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

new long[] // Ошибка, размер неизвестен

new long[][2][4] // Ошибка, размер неизвестен

new long[3][][4] // Ошибка, размер неизвестен

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

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

Единичная диагональная матрица с изменяемым порядком

//Программа 5.8

#include "stdafx.h"

#include <iostream> // Для ввода-вывода

void main(){

int n; // Порядок матрицы

std::cout<< "\nInput order of matrix: ";

std::cin>> n; // Определяются размеры массива

float **matr; // Указатель для массива указателей

matr = new float *[n]; // Массив указателей float *

if (matr == NULL){

std::cout<< "He создан динамический массив!";

return; // Завершение программы

}

for (int i = 0; i < n; i++){

// Строка-массив значений типа float:

matr[i] = new float[n];

if (matr[i] == NULL){

std::cout<< "He создан динамический массив!";

return; // Завершение программы

}

for (int j = 0; j < n; j++) // Заполнение матрицы

// Формирование нулевых элементов

if (i != j)

matr[i][j] = 0;

else // Формирование единичной диагонали:

matr[i][j] = 1;

}

for (int i = 0; i < n; i++){

std::cout<< "\n row" << (i + 1) << ":";// Цикл печати элементов строки:

for (int j = 0; j < n; j++)std::cout<< "\t" << matr[i][j];

}

for (int i = 0; i < n; i++)

delete[] matr[i];

delete[]matr;

getchar();

}

Результаты выполнения:

Введите размер матрицы: 5 <Enter>

Строка 1: 10000

Строка 2: 01000

Строка 3: 00100

Строка 4: 00010

Строка 5: 00001

На рис. 5.3 изображена схема взаимосвязи (n - 1) - одномерных массивов, из n элементов каждый. Эти (n - 1) массивов совместно имитируют квадратную матрицу с изменяемыми размерами, формируемую в программе.

Рис. 5.3. Схема имитации двухмерного динамического массива с помощью массива указателей и набора одномерных массивов

Ссылки

В общем случе lvalue-ссылка это ещё одно имя для уже существующего объекта, так, во всяком случае, было до выхода 11-го стандарта языка Си++. В 11-ой версии стандарта было введено понятия rvalue-ссылки. Это было сделано в первую очередь, для того чтобы поднять скорость выполнения программ, написанных на языке Си++. Основная идея заключалась в том, чтобы использовать ресурсы временных объектов, которые появляются в выражениях и должны быть уничтожены, для порождения не с нуля новых временных объектов. Например, предположим, что у нас есть строки кода:

Matr A, B;

A = 2*A +B;

При умножении матрицы А на 2 появлятся временный объект (матрица1), который должен быть просуммирован с матрицей В, в результате чего получится новый временный объект (матрица2), а матрица1 в принципе уже не нужна и может быть уничтожена. При создании матрицы1 было выполнено много операций (выделения памяти, копирования и т.д.). Вопрос заключается в том, можно ли не создавать матрицу2 с нуля, а воспользоваться ресурсами уже не нужной матрицы1. После выхода 11-ого стандарта языка и введения rvalue ссылок это стало возможным.

В соответствии с 11-ым стандартом на каждом этапе вычисления выражения (например 2*A +B) компилятор может получить временный объект обладаюий свойствами (lvalue, xvalue, rvalue), где lvalue – это объект, который не будет уничтожен (обычно это именнованный объект); rvalue – это временный неименнованный объект, который будет уничтожен при завершении вычисления выражения; xvalue – объект который находится в конце своего жизненного цикла, но ещё не удалён.

Например, рассмотрим функции:

int&& xvalue_func(){ //Эта функция возвращает в точку вызова xvalue объект

return 5;

}

int& lvalue_func(){ // Эта функция возвращает в точку вызова lvalue объект

static int i = 0;

return i;

}

int rvalue_func(){// Эта функция возвращает в точку вызова prvalue объект

return 5;

},

вызов которых можно рассматривать как результат вычисления выражения.

Функция xvalue_func() это пример, который никогда не надо повторять в реальной программе, так как в точку вызова будет возвращена xvalue-ссылка на локальную константу (неименованный объект), которая в этот момент уже может быть уничтожена. Следовательно, использование этой ссылки в программе может привести к ошибкам времени выполнения.

Функция lvalue_func() возвращает в точку вызова lvalue-ссылку на статическую локльную переменную i, которая будет существовать напротяжении всего времени выполнения программы. Использовать эту ссылку можно без всяких ограничений.

Функция rvalue_func() возвращает в точку вызова неименнованный временный объект, который появится в точке вызова функции и будет уничтожен после выполнения всех операций, такой объект и называют rvalue-ссылкой.

Первый вопрос заключается в том, можем ли мы сделать так, чтобы этот временный объект не был уничтожен. Оказывается да, если мы запишем строчку кода вида:

const int& rvalue = rvalue_func();

int&& rvalue2 = rvalue_func();

const int&& const_rvalue2 = rvalue_func();

Объект, возвращаемый rvalue_func() все еще является временным, но согласно 11-ому стандарту Си++, время жизни временного объекта продлевается и становится таким же, как и время жизни ссылки, которая указывает на этот объект. Мало того, поскольку rvalue2 это не констанная ссылка, то её можно использовать, чтобы изменить значение объекта, например, так rvalue2 = 4.

Кроме того, старое правило о том, что нельзя настраивать (теперь только неконстантную) ссылку на временный объект, продолжает действовать. Т.е. строка вида int& rvalue = rvalue_func(); будет вызывать ошибку во время компиляции, а со строкой int& lvalue = lvalue_func(); никаких проблем не будет, так как lvalue_func() возвращает lvalue-ссылку.

Если кратко записать все правила инициализации ссылок в 11-ом стандарте, то ссылки:

Type& //может ссылаться на любое не константное lvalue.

const Type& //может ссылаться на любое выражение.

Type&& //может ссылаться на не константные xvalue и rvalue.

const Type&& //может ссылаться на любое выражение, кроме lvalue.

Для нашего примера без ошибок компиляции будут скомпилированы строки:

int& lvalue = lvalue_func();

const int& const_lvalue1 = lvalue_func();

const int& const_lvalue2 = rvalue_func();

const int& const_lvalue3 = xvalue_func();

int&& rvalue2 = rvalue_func();

int&& rvalue3 = xvalue_func();

const int&& const_rvalue2 = rvalue_func();

const int&& const_rvalue3 = xvalue_func();

Несмотря на безошибочную компиляцию, ссылки: const_lvalue3, rvalue3, const_rvalue3, которые получили своё значение от xvalue_func() буду обращаться к фрагменту памяти, значение которого может быть произвольным. Это может произойти, так как локальный объект, на который указывает ссылка, находится в стадии уничтожения, т.е. его память в любой момент может быть использована для размещения другого объекта.