к массиву с помощью выражения a[i] требует небольшого количества машинных команд.

Простой пример использования массива демонстрируется в профамме 3.5, которая распечатывает все простые числа, меньшие 10000. Используемый метод восходит к третьему столетию до н.э. и называется решетом Эратосфена (см. рис. 3.1). Это типичный алгоритм, где используется возможность быстрого доступа к любому элементу массива по его индексу. Реализовано четыре цикла, из которых три выполняют последовательный доступ к массиву от первого до последнего элемента. В четвертом цикле перебирается весь массив, по i элементов за один раз. В некоторых случаях предпочтительна последовательная обработка, в других - используется последовательное упорядочение, поскольку оно не хуже других методов. Например, можно первый цикл программы 3.5 изменить следующим образом:

for (i = N-l; i > 1, i--) a[i] = 1;

что никак не отразится на вычислениях. Подобным же образом можно изменить порядок обхода во внутреннем цикле, либо изменить последний цикл, чтобы печатать простые числа в порядке убывания. Однако нельзя изменить порядок обхода во внешнем цикле основных вычислений, поскольку в нем обрабатываются все целые числа, меньшие i, перед проверкой элемента a[i] на соответствие простому числу.

Мы не будем подробно анализировать время выполнения программы 3.5, дабы не углубляться в теорию чисел. Однако очевидно, что время выполнения пропорционально

N+ N/2 + N/3 + Л75 + N/7 + ЛуП + ...

что меньше

N+ N/2 + N/3 + 7V/4 + ... = NH ~ N InN.

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

РИСУНОК 3.1 РЕШЕТО ЭРАТОСФЕНА

Для вычисления простых чисел, меньших 32, все элементы массива инициализируются с присвоением значения 1 (второй столбец). Это указывает, что пока не обнаружено ни одно число, которое не является простым (элементы а[0] и а[1] не используются и не показаны). Затем присваивается значение О тем элементам массива, индексы которых являются произведениями чисел 2, 3 и 5, поскольку эти произведения не являются простыми числами. Индексы элементов массива, у которых сохранилось значение 1, являются простыми числами (крайний правый столбец).

*р, на второй - *(р+1), на третий - *(р+2) и т.д. Другими словами, записи *(a+i) и a[i] в языке С++ эквивалентны.

Это создает альтернативный механизм доступа к объектам массивов, который иногда оказывается удобнее индексации. Он чаще всего используется для массивов символов (строк). Мы вернемся к этому вопросу в разделе 3.6.

Программа 3.5 Решето Эратосфена

Цель программы заключается в присвоении элементам a[i] значения 1, если i простое число, и значения О в противном случае. Сначала значение 1 присваивается всем элементам массива. Затем присваивается значение О элементам, индексы которых не являются простыми числами (представляют собой произведения известных простых чисел). Если после этого некоторый элемент a[i] сохраняет значение 1, его индекс является простым числом.

Поскольку массив состоит из элементов простейшего типа, принимающих значения О или 1, для экономии пространства имеет смысл явно описать массив бит вместо массива целых чисел. Кроме того, в некоторых средах программирования требуется, чтобы массив был глобальным, если значение N велико, либо можно выделять пространство для массива динамически (см. программу 3.6).

finclude <iostreani.h> static const int N = 1000; int mainO { int i, a[N]; for (i = 2; i < N; i++) a[i] = 1; for (i = 2; i < N; i++) if (a[i])

for (int j = i; j*i < N; j++) a[i*j] = 0; for (i = 2; i < N; i++)

if (a[i]) cout i; cout endl;

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

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

В программе 3.5 предполагается, что размер массива должен быть известен заранее. Чтобы выполнить программу для другого значения N, следует изменить константу N и повторно скомпилировать программу. В программе 3.6 показано альтернативное решение: пользователь может ввести значение N, после чего будут выводиться простые числа, меньшие этой величины. Применены два основных механизма С++. В обоих осуществляется передача функциям массивов в качестве аргументов. Первый механизм обеспечивает передачу аргументов командной строки главным программам в массиве argv с размером argc. Массив argv является составным и включает объекты, которые сами представляют собой массивы (строки). Обзор массивов отложим до раздела 3.7, а пока примем на веру, что переменная N принимает значение, вводимое пользователем при выполнении программы.

Второй базовый механизм - оператор new[], распределяющий область памяти, необходимый для массива во время выполнения. В нашем особом случае он возвращает указатель на массив. В некоторых языках программирования динамическое выделение памяти массивам затруднено либо вообще невозможно. В других языках этот процесс выполняется автоматически. Динамическое распределение памяти служит важной функцией программ, управляющих несколькими массивами, отдельные из которых могут иметь большой размер. В данном случае необходимо без выделения памяти предварительно объявить массив с размером, не меньшим любого значения, которое допускается при вводе. В сложной программе, где может использоваться много массивов, выполнять эти действия для каждого из них затруднительно. Обычно используется код, подобный коду программы 3.6, по причине его гибкости. Однако в определенных приложениях, где размер массива известен, вполне применимы простые решения, такие как в программе 3.5.

Программа 3.6 Динамическое выделение памяти массиву

Для изменения максимального значения простого числа, вычисляемого в программе 3.5, необходима повторная компиляция программы. Вместо этого можно принимать максимальное значение из командной строки и использовать его для выделения памяти массиву во время выполнения с помощью оператора С++ new[]. Например, если,скомпилировать программу и ввести в командной строке 1000000, будут получены все целые числа, меньшие миллиона (если компьютер достаточно мощный для таких вычислений). Для отладки программы достаточно значения 100 (что позволит сэкономить время и пространство памяти). Этот подход в дальнейшем используется часто, хотя для краткости проверка на перерасход памяти будет опускаться.

int main(int argc, char *argv[]) { int i, N = atoi (argv[l]) ; int *a = new int[N] ; if (a == 0)

{ cout out of memory endl; return 0; }

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

Стандартная библиотека С++ содержит класс Vector - абстрактный объект, который можно индексировать подобно массиву (с необязательной автоматической проверкой соответствия диапазону). Однако он также способен к расширению и усечению. Это позволяет воспользоваться преимуществами массивов, но возлагать задачи проверки допустимости индексов и управления памятью на систему. Поскольку в этой книге много внимания уделяется быстродействию, будем избегать скрытых недостатков, связанных с использованием массивов, указывая, что в коде могут быть применены также векторы (см. упражнение 3.14).

Программа 3.7 служит примером эмуляции, использующей массивы. Моделируется последовательность попыток Бернулли (Bernoulli trials) - известная абстрактная концепция теории вероятностей. Если подбросить монету ТУраз, вероятность выпадения к решек составляет