 |
Тема 5.4 Представление массивов в статической памяти, динамической памяти и в стеке. Обработка одномерных массивов.
|
|
|
|
1. Общие положения
Массив является простейшим агрегатным типом. Он моделирует набор однотипных элементов, расположенных подряд в непрерывном отрезке памяти. Массивы в той или иной форме поддерживаются практически всеми языками программирования и неудивительно, что они появились в первых версиях C и затем стали частью C++.
1. 1. Объявление массивов
Если T некоторый тип, N константа или выражение, вычисляемое во время компиляции, то инструкция
T a[N];
объявляет переменную a типа «массив из N элементов типа T» (array of N elements of the type T). Тип N должен иметь неявное приведение к типу std:: size_t, а его значение, называемое размером массива, должно быть больше нуля. Массив располагается в непрерывном отрезке памяти, под каждый элемент массива выделяется sizeof(T) байт, соответственно размер памяти, необходимой для размещения всего массива, равен N*sizeof(T) байт. Эта величина ограничена сверху платформой и компилятором. Тип массива обозначается как T[N], то есть он включает тип элементов и размер массива. Таким образом, массивы, имеющие одинаковый тип элементов, но разный размер, будут иметь разный тип.
Такие массивы еще называют встроенными массивами (regular arrays), чтобы подчеркнуть отличие от других вариантов массивов, термин «массив» используется в программировании и в том числе в C++ достаточно широко.
Вот примеры правильных объявлений массивов:
const int N = 8;
constexpr int Square ( int n) { return n * n; }
int a1[1];
int a2[N];
int a3['Q'];
int a4[Square(2)];
А вот примеры некорректных объявлений массивов:
int n;
int b1[0]; // нулевой размер
int b2[n]; // размер нельзя определить во время компиляции
int b3[" Q" ]; // размер нельзя привести к size_t
|
|
|
Доступ к элементам массива осуществляется через индексатор, значения индекса от 0 до N-1. Вот пример:
int a[4];
a[0] = 42;
int t = a[3];
Выход за границы массива не контролируется, ошибка может привести к неопределенному поведению.
В одной инструкции можно объявить несколько массивов, но размер должен быть указан для каждого.
int a[4], b[8];
Для типов массивов можно вводить псевдонимы. Можно использовать традиционный вариант с ключевым словом typedef:
typedef int I4[4];
или более современный (C++11) с ключевым словом using:
using I4 = int [4];
После этого массивы объявляются как простые переменные:
I4 a, b;
Это будет то же самое, что
int a[4], b[4];
1. 2. Операторы и стандартные функции для работы с массивами
Для работы с массивами можно использовать оператор sizeof и несколько стандартных функций и макросов.
Оператор sizeof возвращает полный размер массива в байтах, то есть размер элемента умноженный на размер массива.
Макрос _countof() (в MSVS заголовочный файл < cstdlib> ) возвращает размер массива, то есть количество элементов. В С++17 появился стандартный шаблон функции std:: size(), которая делает то же самое (а еще имеет перегруженную версию, которая определяет размер стандартного контейнера).
int a[4];
std:: cout < < sizeof (a) < < ' ' < < std:: size(a) < < '\n';
Вывод:
16 4
В C++11 в стандартной библиотеке появились свободные (не члены) шаблоны функций std:: begin() и std:: end(). Вызванная для массива std:: begin() возвращает указатель на первый элемент массива, std:: end() на past-the-last элемент. (Есть также константные версии: std:: cbegin(), std:: cend(). ) Это позволяет использовать массивы в диапазонном for.
int a[4]{ 4, 3, 2, 1 };
for ( auto t: a)
{
std:: cout < < t < < ' ';
}
А также в стандартных алгоритмах:
std:: sort(std:: begin(a), std:: end(a));
1. 3. Размещение в памяти
|
|
|
Если массив объявлен статически, то есть в глобальной области видимости, в области видимости пространства имен или в качестве статического члена класса, то он размещается в статической памяти. Массивам, объявленным локально, память выделяется на стеке. (Естественно, надо учитывать ограниченный размер стека при выборе размера локальных массивов. ) Нестатические члены класса размещаются в границах экземпляра класса. Динамические массивы (см. раздел 6) размещаются в динамической памяти.
1. 4. Ограничения на типы элементов массивов
Нельзя объявить массив, элементы которого имеют тип void.
Нельзя объявить массив ссылок.
int u, v;
int & rr[2] = { u, v }; // ошибка
Вместо этого можно использовать массив константных указателей.
int * const rr[2] = { & u, & v };
(Синтаксис инициализации массивов будет обсуждаться в разделе 3. 2. )
В C++11 появился шаблон std:: reference_wrapper< >. Он эмулирует интерфейс ссылки, но экземпляры конкретизации можно хранить в контейнерах и встроенных массивах. Но все же эмуляция интерфейса ссылки не совсем полная, иногда приходится использовать функцию-член get(). Вот пример.
int u = 42, v = 5;
std:: reference_wrapper< int > rr[2] = { u, v };
std:: cout < < rr[0] < < ' ' < < rr[1] < < '\n'; // вывод: 42 5
++rr[0];
rr[1]. get() = 125; // get() необходим
std:: cout < < u < < ' ' < < v < < '\n'; // вывод: 43 125
Нельзя объявить массив функций.
int ff[2]( double ); // ошибка
Вместо этого можно использовать массив указателей на функцию.
int (*ff[2])( double );
Шаблон std:: reference_wrapper< > можно конкретизировать типом функции, но преимуществ перед указателем практически нет — функцию и так можно вызвать через указатель без разыменования, а инициализировать указатель именем функции без оператора &. Есть еще вариант эмулирования массива функций — это использование шаблона std:: function< >, но этот шаблон является темой отдельного разговора.
Массив нельзя объявить с помощью ключевого слова auto.
auto x[2] = {1, 2} // ошибка
Квалификатор const не применим к типу массива, а только к типам его элементов.
using I4 = int [4];
const I4 ci; // то же, что и const int ci[4];
50. Обработка многомерных массивов. Массивы Айлиффа.
|
|
|
На рис. 3. 4 приведена физическая структура трёхмерного массива В[4.. 5, -1.. 1, 0.. 1], представленная по методу Айлиффа. Из этого рисунка видно, что метод Айлиффа, увеличивая скорость доступа к элементам массива, приводит в то же время к увеличению суммарного объёма памяти, требуемого для представления массива. В этом заключается основной недостаток представления массивов с помощью векторов Айлиффа.
Рис. 3. 4. Представление массивов с помощью векторов Айлиффа
Специальные массивы
На практике встречаются массивы, которые в силу определенных причин могут записываться в память не полностью, а частично. Это особенно актуально для массивов настолько больших размеров, что для их хранения в полном объеме памяти может быть недостаточно. К таким массивам относятся симметричные и разреженные массивы.
СИММЕТРИЧНЫЕ МАССИВЫ. Двумерный массив, в котором количество строк равно количеству столбцов, называется квадратной матрицей.
Квадратная матрица, у которой элементы, расположенные симметрично относительно главной диагонали, попарно равны друг другу, называется симметричной. Если матрица порядка n симметрична, то в ее физической структуре достаточно отобразить не n2, а лишь n*(n+1)/2 её элементов. Иными словами, в памяти необходимо представить только верхний (включая и диагональ) треугольник квадратной логической структуры. Доступ к треугольному массиву организуется таким образом, чтобы можно было обращаться к любому элементу исходной логической структуры, в том числе и к элементам, значения которых хотя и не представлены в памяти, но могут быть определены на основе значений симметричных им элементов.
|
|
|
