<< Пред.           стр. 31 (из 121)           След. >>

Список литературы по разделу

 #include
 #include
 int main()
 {
 const int ia_size = 10;
 int ia[ia_size ]={0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
 // заполним стек
 int ix = 0;
 stack< int > intStack;
 for ( ; ix < ia_size; ++ix )
  intStack.push( ia[ ix ] );
 
 int error_cnt = 0;
 if ( intStack.size() != ia_size ) {
  cerr << "Ошибка! неверный размер IntStack: "
  << intStack.size()
  << "\t ожидается: " << ia_size << endl,
  ++error_cnt;
 }
 
 int value;
 while ( intStack.empty() == false )
 {
  // считаем элемент с вершины
  value = intStack.top();
  if ( value != --ix ) {
  cerr << "Ошибка! ожидается " << ix
  << " получено " << value << endl;
  ++error_cnt;
  }
 
  // удалим элемент
  intStack.pop();
 }
 
 cout << "В результате запуска программы получено "
 << error_cnt << " ошибок" << endl;
 }
 Объявление
 stack< int > intStack;
 определяет intStack как пустой стек, предназначенный для хранения элементов типа int. Стек является надстройкой над некоторым контейнерным типом, поскольку реализуется с помощью того или иного контейнера. По умолчанию это deque, поскольку именно эта структура обеспечивает эффективную вставку и удаление первого элемента, а vector эти операции не поддерживает. Однако мы можем явно указать другой тип контейнера, задав его как второй параметр:
 stack< int, list > intStack;
 Элементы, добавляемые в стек, копируются в реализующий его контейнер. Это может приводить к потере эффективности для больших или сложных объектов, особенно если мы только читаем элементы. В таком случае удобнее определить стек указателей на объекты. Например:
 #include
 class NurbSurface { /* mumble */ };
 stack< NurbSurface* > surf_Stack;
 К двум стекам одного типа можно применять операции сравнения: равенство, неравенство, меньше, больше, меньше или равно, больше или равно, если они определены над элементами стека. Элементы сопоставляются попарно. Первая пара несовпадающих элементов определяет результат операции сравнения в целом.
 Стек будет использован в нашей программе текстового поиска в разделе 17.7 для поддержки сложных запросов типа
 
 Civil && ( War || Rights )
 
 6.17. Очередь и очередь с приоритетами
 Абстракция очереди реализует метод доступа FIFO (first in, first out – “первым вошел, первым вышел”): объекты добавляются в конец очереди, а извлекаются из начала. Стандартная библиотека предоставляет две разновидности этого метода: очередь FIFO, или простая очередь, и очередь с приоритетами, которая позволяет сопоставлять элементы с их приоритетами. Текущий элемент помещается не в конец такой очереди, а перед элементами с более низким приоритетом. Программист, определяющий такую структуру, задает способ вычисления приоритетов. В реальной жизни подобное можно увидеть, скажем, при регистрации багажа в аэропорту. Как правило, пассажиры, чей рейс через 15 минут, передвигаются в начало очереди, чтобы не опоздать на самолет. Примером из практики программирования служит планировщик операционной системы, определяющий последовательность выполнения процессов.
 Для использования queue и priority_queue необходимо включить заголовочный файл:
 #include
 Полный набор операций с контейнерами queue и priority_queue приведен в таблице 6.6.
 
 Таблица 6.6. Операции с queue и priority_queue
 
 Операция Действие
 empty() Возвращает true, если очередь пуста, и false в противном случае
 size() Возвращает количество элементов в очереди
 pop() Удаляет первый элемент очереди, но не возвращает его значения. Для очереди с приоритетом первым является элемент с наивысшим приоритетом
 front() Возвращает значение первого элемента очереди, но не удаляет его. Применимо только к простой очереди
 back() Возвращает значение последнего элемента очереди, но не удаляет его. Применимо только к простой очереди
 top() Возвращает значение элемента с наивысшим приоритетом, но не удаляет его. Применимо только к очереди с приоритетом
 push(item) Помещает новый элемент в конец очереди. Для очереди с приоритетом позиция элемента определяется его приоритетом.
 
 Элементы priority_queue отсортированы в порядке убывания приоритетов. По умолчанию упорядочение основывается на операции “меньше”, определенной над парами элементов. Конечно, можно явно задать указатель на функцию или объект-функцию, которая будет использоваться для сортировки. (В разделе 12.3 можно найти более подробное объяснение и иллюстрации использования такой очереди.)
 6.18. Вернемся в классу iStack
 У класса iStack, разработанного нами в разделе 4.15, два недостатка:
 он поддерживает только тип int. Мы хотим обеспечить поддержку любых типов. Это можно сделать, преобразовав наш класс в шаблон класса Stack;
 он имеет фиксированную длину. Это неудобно в двух отношениях: заполненный стек становится бесполезным, а в попытке избежать этого мы окажемся перед необходимостью отвести ему изначально слишком много памяти. Разумным выходом будет разрешить динамический рост стека. Это можно сделать, пользуясь тем, что лежащий в основе стека вектор способен динамически расти.
 Напомним определение нашего класса iStack:
 #include
 
 class iStack {
 public:
  iStack( int capacity )
  : _stack( capacity ), _top( 0 ) {};
 
  bool pop( int &value );
  bool push( int value );
 
  bool full();
  bool empty();
  void display();
 
  int size();
 
 private:
  int _top;
  vector< int > _stack;
 };
 Сначала реализуем динамическое выделение памяти. Тогда вместо использования индекса при вставке и удалении элемента нам нужно будет применять соответствующие функции-члены. Член _top больше не нужен: функции push_back() и pop_back() автоматически работают в конце массива. Вот модифицированный текст функций pop() и push():
 bool iStack::pop( int &top_value )
 {
  if ( empty() )
  return false;
  top_value = _stack.back(); _stack.pop_back();
  return true;
 }
 
 bool iStack::push( int value )
 {
  if ( full() )
  return false;
  _stack.push_back( value );
  return true;
 }
 Функции-члены empty(), size() и full() также нуждаются в изменении: в этой версии они теснее связаны с лежащим в основе стека вектором.
 inline bool iStack::empty(){ return _stack.empty(); }
 inline bool iStack::size() { return _stack.size(); }
 inline bool iStack::full() {
  return _stack.max_size() == _stack.size(); }
 Надо немного изменить функцию-член display(), чтобы _top больше не фигурировал в качестве граничного условия цикла.
 void iStack::display()
 {
  cout << "( " << size() << " )( bot: ";
  for ( int ix=0; ix < size(); ++ix )
  cout << _stack[ ix ] << " ";
  cout << " stop )\n";
 }
 Наиболее существенным изменениям подвергнется конструктор iStack. Никаких действий от него теперь не требуется. Можно было бы определить пустой конструктор:
 inline iStack::iStack() {}
 Однако это не совсем приемлемо для пользователей нашего класса. До сих пор мы строго сохраняли интерфейс класса iStack, и если мы хотим сохранить его до конца, необходимо оставить для конструктора один необязательный параметр. Вот как будет выглядеть объявление конструктора с таким параметром типа int:
 class iStack {
 public:
  iStack( int capacity = 0 );
  // ...
 };
 Что делать с аргументом, если он задан? Используем его для указания емкости вектора:
 inline iStack::iStack( int capacity )
 {
  if ( capacity )
  _stack.reserve( capacity );
 }
 Превращение класса в шаблон еще проще, в частности потому, что лежащий в основе вектор сам является шаблоном. Вот модифицированное объявление:
 #include
 
 template
 class Stack {
 public:
  Stack( int capacity=0 );
  bool pop( elemType &value );
  bool push( elemType value );
 
  bool full();
  bool empty();
  void display();
 
  int size();
 private:
  vector< elemType > _stack;
 };
 Для обеспечения совместимости с программами, использующими наш прежний класс iStack, определим следующий typedef:
 typedef Stack iStack;
 Модификацию операторов класса мы оставим читателю для упражнения.
 Упражнение 6.29
 Модифицируйте функцию peek() (упражнение 4.23 из раздела 4.15) для шаблона класса Stack.
 Упражнение 6.30
 Модифицируйте операторы для шаблона класса Stack. Запустите тестовую программу из раздела 4.15 для новой реализации
 Упражнение 6.31
 По аналогии с классом List из раздела 5.11.1 инкапсулируйте наш шаблон класса Stack в пространство имен Primer_Third_Edition
 Часть III
 Процедурно-ориентированное программирование
 В части II были представлены базовые компоненты языка С++: встроенные типы данных (int и double), типы классов (string и vector) и операции, которые можно совершать над данными. В части III мы увидим, как из этих компонентов строятся функции, служащие для реализации алгоритмов.
 В каждой программе на С++ должна присутствовать функция main(), которая получает управление при запуске программы. Все остальные функции, необходимые для решения задачи, вызываются из main(). Они обмениваются информацией при помощи параметров, которые получают при вызове, и возвращаемых значений. В главе 7 представлен соответствующие механизмы С++.
 Функции используются для того, чтобы организовать программу в виде совокупности небольших и не зависящих друг от друга частей. Она инкапсулирует алгоритм или набор алгоритмов, применяемых к некоторому набору данных. Объекты и типы можно определить так, что они будут использоваться в течение всего времени работы программы. Однако, если некоторые объекты или типы применяются только в части программы, предпочтительнее ограничить область их использования именно этой частью и объявить внутри той функции, где они нужны. Понятие видимости предоставляет в распоряжение программиста механизм, позволяющий ограничивать область применения объектов. Различные области видимости, поддерживаемые языком С++, мы рассмотрим в главе 8.
 Для облегчения использования функций С++ предлагает множество средств, рассматриваемых нами в части III. Первым из них является перегрузка. Функции, которые выполняют семантически одну и ту же операцию, но работают с разными типами данных и потому имеют несколько отличающиеся реализации, могут иметь общее имя. Например, все функции для печати значений разных типов, таких, как int, string и т.д., называются print(). Поскольку программисту не приходится запоминать много разных имен для одной и той же операции, пользоваться ими становится проще. Компилятор сам подставляет нужное в зависимости от типов фактических аргументов. В главе 9 объясняется, как объявлять и использовать перегруженные функции и как компилятор выбирает подходящую из набора перегруженных.
 Вторым средством, облегчающим использование функций, является механизм шаблонов. Шаблон – это обобщенное определение, которое используется для конкретизации – автоматической генерации потенциально бесконечного множества функций, различающихся только типами входных данных, но не действиями над ними. Этот механизм описывается в главе 10.
 Функции обмениваются информацией с помощью значений, которые они получают при вызове (параметров), и значений, которые они возвращают. Однако этот механизм может оказаться недостаточным при возникновении непредвиденной ситуации в работе программы. Такие ситуации называются исключениями, и, поскольку они требуют немедленной реакции, необходимо иметь возможность послать сообщение вызывающей программе. Язык С++ предлагает механизм обработки исключений, который позволяет функциям общаться между собой в таких условиях. Этот механизм рассматривается в главе 11.
 Наконец, стандартная библиотека предоставляет нам обширный набор часто используемых функций – обобщенных алгоритмов. В главе 12 описываются эти алгоритмы и способы их использования с контейнерными типами из главы 6 и со встроенными массивами.
 7. Функции
 Мы рассмотрели, как объявлять переменные (глава 3), как писать выражения (глава 4) и инструкции (глава 5). Здесь мы покажем, как группировать эти компоненты в определения функций, чтобы облегчить их многократное использование внутри программы. Мы увидим, как объявлять и определять функции и как вызывать их, рассмотрим различные виды передаваемых параметров и обсудим особенности использования каждого вида. Мы расскажем также о различных видах значений, которые может вернуть функция. Будут представлены четыре специальных случая применения функций: встроенные (inline), рекурсивные, написанные на других языках и объявленные директивами связывания, а также функция main(). В завершение главы мы разберем более сложное понятие – указатель на функцию.
 7.1. Введение
 Функцию можно рассматривать как операцию, определенную пользователем. В общем случае она задается своим именем. Операнды функции, или формальные параметры, задаются в списке параметров, через запятую. Такой список заключается в круглые скобки. Результатом функции может быть значение, которое называют возвращаемым. Об отсутствии возвращаемого значения сообщают ключевым словом void. Действия, которые производит функция, составляют ее тело; оно заключено в фигурные скобки. Тип возвращаемого значения, ее имя, список параметров и тело составляют определение функции. Вот несколько примеров:
 inline int abs( int obj )
 {
  // возвращает абсолютное значение iobj
  return( iobj < 0 ? -iobj : iobj );
 }
 inline int min( int p1, int p2 )
 {
  // возвращает меньшую из двух величин
  return( pi < p2 ? pi : p2 );
 }
 
 int gcd( int vl, int v2 )
 {
  // возвращает наибольший общий делитель
  while ( v2 )
  {
  int temp = v2;
  v2 = vl % v2;
  vl = temp;
  }
  return vl;
 }
 Выполнение функции происходит тогда, когда в тексте программы встречается оператор вызова. Если функция принимает параметры, при ее вызове должны быть указаны фактические параметры, аргументы. Их перечисляют внутри скобок, через запятую. В следующем примере main() дважды вызывает abs() и по одному разу min() и gcd(). Функция main() определяется в файле main.C.
 #include
 
 int main()
 {
  // прочитать значения из стандартного ввода
  cout << "Введите первое значение: ";
  int i;
  cin >> i;
  if ( !cin ) {
  cerr << "!? Ошибка ввода - аварийный выход!\n";
  return -1;
  }
 
  cout << "Введите второе значение: ";
  int j;
  cin >> j;
  if ( !cin ) {
  cerr << "!? Ошибка ввода - аварийный выход!\n";
  return -2;
  }
 
  cout << "\nmin: " << min( i, j ) << endl;
  i = abs( i );
  j = abs( j );
  cout << "НОД: " << gcd( i, j ) << endl;
  return 0;
 }
 Вызов функции может обрабатываться двумя разными способами. Если она объявлена встроенной (inline), то компилятор подставляет в точку вызова ее тело. Во всех остальных случаях происходит нормальный вызов, который приводит к передаче управления ей, а активный в этот момент процесс на время приостанавливается. По завершении работы выполнение программы продолжается с точки, непосредственно следующей за точкой вызова. Работа функции завершается выполнением последней инструкции ее тела или специальной инструкции return.
 Функция должна быть объявлена до момента ее вызова, попытка использовать необъявленное имя приводит к ошибке компиляции. Определение функции может служить ее объявлением, но ему разрешено появиться в программе только один раз. Поэтому обычно его помещают в отдельный исходный файл. Иногда в одном файле находятся определения нескольких функций, логически связанных друг с другом. Чтобы использовать их в другом исходном файле, необходим механизм, позволяющий объявить ее, не определяя.
 Объявление функции состоит из типа возвращаемого значения, имени и списка параметров. Вместе эти три элемента составляют прототип. Объявление может появиться в файле несколько раз.
 В нашем примере файл main.C не содержит определений abs(), min() и gcd(), поэтому вызов любой из них приводит к ошибке компиляции. Чтобы компиляция была успешной, их необязательно определять, достаточно только объявить:
 int abs( int );
 int min( int, int );
 int gcd( int, int );
 (В таком объявлении можно не указывать имя параметра, ограничиваясь названием типа.)
 Объявления (а равно определения встроенных функций) лучше всего помещать в заголовочные файлы, которые могут включаться всюду, где необходимо вызвать функцию. Таким образом, все файлы используют одно общее объявление. Если его необходимо модифицировать, изменения будут локализованы. Вот так выглядит заголовочный файл для нашего примера. Назовем его localMath.h:
 // определение функции находится в файле gcd.С
 int gcd( int, int );
 
 inline int abs(int i) {
  return( i<0 ? -i : i );
 }
 inline int min(int vl.int v2) {
  return( vl  }
 В объявлении функции описывается ее интерфейс. Он содержит все данные о том, какую информацию должна получать функция (список параметров) и какую информацию она возвращает. Для пользователей важны только эти данные, поскольку лишь они фигурируют в точке вызова. Интерфейс помещается в заголовочный файл, как мы поступили с функциями min(), abs() и gcd().
 При выполнении наша программа main.C, получив от пользователя значения:
 
 Введите первое значение: 15
 Введите второе значение: 123
 
 выдаст следующий результат:
 
 mm: 15
 НОД: 3
 
 7.2. Прототип функции
 Прототип функции описывает ее интерфейс и состоит из типа возвращаемого функцией значения, имени и списка параметров. В данном разделе мы детально рассмотрим эти характеристики.
 7.2.1. Тип возвращаемого функцией значения
 Тип возвращаемого функцией значения бывает встроенным, как int или double, составным, как int& или double*, или определенным пользователем – перечислением или классом. Можно также использовать специальное ключевое слово void, которое говорит о том, что функция не возвращает никакого значения:
 #include
 #include class Date { /* определение */ };
 
 bool look_up( int *, int );
 double calc( double );
 int count( const string &, char );
 Date& calendar( const char );
 void sum( vector&, int );
 Однако функция или встроенный массив не могут быть типом возвращаемого значения. Следующий пример ошибочен:
 // массив не может быть типом возвращаемого значения
 int[10] foo_bar();
 Но можно вернуть указатель на первый элемент массива:
 // правильно: указатель на первый элемент массива
 int *foo_bar();
 (Размер массива должен быть известен вызывающей программе.)
 Функция может возвращать типы классов, в частности контейнеры. Например:
 // правильно: возвращается список символов
 list foo_bar();
 (Этот подход не очень эффективен. Обсуждение типа возвращаемого значения см. в разделе 7.4.)
 Тип возвращаемого функцией значения должен быть явно указан. Приведенный ниже код вызывает ошибку компиляции:
 // ошибка: пропущен тип возвращаемого значения
 const is_equa1( vector vl, vector v2 );
 В предыдущих версиях С++ в подобных случаях считалось, что функция возвращает значение типа int. Стандарт С++ отменил это соглашение. Правильное объявление is_equal() выглядит так:
 // правильно: тип возвращаемого значения указан
 const bool is_equa1( vector vl, vector v2 );
 7.2.2. Список параметров функции
 Список параметров не может быть опущен. Функция, которая не требует параметров, должна иметь пустой список либо список, состоящий из одного ключевого слова void. Например, следующие объявления эквивалентны:
 int fork();
 int fork( void );
 Такой список состоит из названий типов, разделенных запятыми. После имени типа может находиться имя параметра, хотя это и необязательно. В списке параметров не разрешается использовать сокращенную запись, соотнося одно имя типа с несколькими параметрами:
 int manip( int vl, v2 ); // ошибка
 int manip( int vl, int v2 ); // правильно
 Имена параметров не могут повторяться. Имена, фигурирующие в определении функции, можно и даже нужно использовать в ее теле. В объявлении же функции они не обязательны и служат средством документирования ее интерфейса. Например:
 void print( int *array, int size );
 Имена параметров в объявлении и в определении одной и той же функции не обязаны совпадать. Однако употребление разных имен может запутать пользователя.
 С++ допускает сосуществование двух или более функций, имеющих одно и то же имя, но разные списки параметров. Такие функции называются перегруженными. О списке параметров в этом случае говорят как о сигнатуре функции, поскольку именно он используется различения разных версий одноименных функций. Имя и сигнатура однозначно идентифицируют версию. (Перегруженные функции подробно обсуждаются в главе 9.)
 7.2.3. Проверка типов формальных параметров
 Функция gcd() объявлена следующим образом:
 int gcd( int, int );
 Объявление говорит о том, что имеется два параметра типа int. Список формальных параметров предоставляет компилятору информацию, с помощью которой тот может проверить типы передаваемых функции фактических аргументов.

<< Пред.           стр. 31 (из 121)           След. >>

Список литературы по разделу