Массивы со статической и динамической размерностью. STL Часть 1




Массивы со статической и динамической размерностью, контейнеры STL C++ , Standard Template LibraryПрежде, чем приступать к обзору контейнерных типов библиотеки STL, разумно освежить в памяти информацию об организации массивов C и C++. Потому что контейнеры STL — это некоторые альтернативные формы организации коллекций данных, свободные от ограничений массивов.

Массивы — одна из самых используемых форм организаций данных, и исторически одна из самых первых форм, появившихся в языках программирования (языки конца 50-х годов XX века). Массив — это представление набора последовательных однотипных элементов. Принципиально важным в таком определении являются 2 момента, которые для массива должны выполняться обязательно:

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

  2. Все элементы массива должны обязательно быть однотипными. Всем знакомы и понятны простейшие определения, например, целочисленных массивов: int array[100] . Но это вовсе не означает, что в массивы могут организовываться только простейшие встроенные типы языка C++. В массив могут организовываться объекты-переменные любого составного типа (класса, структуры) и степени сложности. Единственным ограничением является то, что все элементы одного массива должны быть одного типа. Например, так может описываться студенческая группа:

Массивы со статической и динамической размерностью, контейнеры STL C++ , Standard Template Library

К этому крайне важному обстоятельству — типы элементов массива — мы ещё вернёмся в дальнейшем.

Ещё со времён самых ранних языков программирования (FORTRAN и др.), на массивы накладывалось сильное ограничение: размер массива должен определяться только целочисленной константой, значение которой должно быть определено на момент компиляции кода. То же самое ограничение сохранилось и в языке C, который стал прародителем C++. Например:

Массивы со статической и динамической размерностью, контейнеры STL C++ , Standard Template Library

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

Массивы со статической и динамической размерностью, контейнеры STL C++ , Standard Template LibraryВо всех таких случаях, после определения массива размер его фиксируется и мы никак не сможем увеличить его размер (если, например, в ходе вычислений окажется, что нам не хватает этого размера). Так определенные массивы называются массивами со статически объявленным (в момент написания кода) размером.

Примечание: Из-за того, что все элементы массива располагаются последовательно (1-е правило из названных выше), для вычисления размера массива (в области его видимости) можно использовать показанный в примере трюк: размер массива равен длине всего массива, делённой на длину любого его элемента (поскольку все они одинаковые по типу).

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

Массивы со статической и динамической размерностью, контейнеры STL C++ , Standard Template Library

Но это не так! Просто здесь константное значение размера объявляемого массива извлекается из списка значений, и равно, в показанном примере 5.

Единственным способом создать массив, в классических C и C++, размером в N элементов, вычисляемым в момент создания массива (на этапе выполнения) — это был способ динамического размещения массива. Которое в C и C++ делается, соответственно:

Например, так:

Массивы со статической и динамической размерностью, контейнеры STL C++ , Standard Template Library

Самые поздние стандарты (C99, C++11) внесли расширения, которые допускают создание локальных массивов в функциях с размерами, вычисляемыми при входе в функцию. При таких условиях массив будет выделен в стеке функции. Это уже весьма существенно, когда мы не можем знать наперед размер обрабатываемых данных. В качестве примера посмотрим задачу нахождения всех простых чисел, не превосходящих N (решето Эратосфена), где N задаётся при запуске программы.

Этот код мы уже обязаны компилировать с указанием стандарта C++ 2011 года (опциями или компилятора, или свойствами собираемого проекта):Массивы со статической и динамической размерностью, контейнеры STL C++ , Standard Template Library

Но даже после всех расширений, простейший массив, как форма организации набора объектов, оказывается недостаточно гибким. Главные из ограничивающих факторов:

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

  • По правилам C/C++ при вызове функций вместо массива в качестве параметра вместо массива передаётся указатель на его начало (адрес 1-го элемента). Это позволяет сильно повысить эффективность многих вычислительных алгоритмов, но при этом теряется информация о размере массива, и её необходимо передавать отдельным параметром. Например, если бы мы хотели формировать решето Эратосфена не в функции main(), а в отдельной функции, то мы должны были бы формировать её вызов как erastof ( a, n ).

  • Многие интуитивно простейшие операции над массивами вызывают сложности. Например: в 15-ти элементном массиве элемент под номером 10 надо вставить между элементами 2 и 3. При этом а). все элементы с 3 по 9 нужно копировать на одну позицию вправо, б). делать это можно только в нисходящем порядке от 9 к 3 и в). за всеми индексами этих операций необходимо следить в ручном режиме.

Потребности практики требовали большего, что и породило контейнеры STL (Standard Template Library).

Рассылка новых уроков по программированию:

Массивы со статической и динамической размерностью. STL Часть 1
Оцени эту статью

Olej

Об авторе Olej

Стаж практических программных разработок около 40 лет. Преподаватель международной софтверной компании Global Logic. Постоянный автор публикаций IBM Developer Works. Научный редактор книжного издательства компьютерной литературы "Символ-Плюс", Санкт-Петербург.

Массивы со статической и динамической размерностью. STL Часть 1: 2 комментария

  1. В C и C++ существует правило: вместо массивов при вызове функций передаётся указатель на начало массива (это сложилось лет 40-50 назад из-за соображений эффективности тех компьютеров). Поэтому при передаче массива в функцию информация о его размере теряется.
    Традиционно массивы передаются в функцию как 2 параметра: указатель начала массива + число его элементов. Например: void func( double arr[], int size ) или void func( double *arr, int size ).

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *