С.Б. Липпман, Ж. Лажойе - Язык программирования С++ Вводный курс (1114944), страница 51
Текст из файла (страница 51)
Это можетприводить к потере эффективности для больших или сложных объектов, особенно еслимы только читаем элементы. В таком случае удобнее определить стек указателей на#include <stack>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>Полный набор операций с контейнерами queue и priority_queue приведен в таблице6.6.Таблица 6.6. Операции с queue и priority_queueОперацияДействиеempty()Возвращает true, если очередь пуста, иfalse в противном случаеС++ для начинающих310size()Возвращает количество элементов в очередиpop()Удаляет первый элемент очереди, но невозвращает его значения.
Для очереди сприоритетом первым является элемент снаивысшим приоритетомfront()Возвращает значение первого элементаочереди, но не удаляет его. Применимотолько к простой очередиback()Возвращает значение последнего элементаочереди, но не удаляет его. Применимотолько к простой очередиtop()Возвращаетзначениеэлементаснаивысшим приоритетом, но не удаляет его.Применимо только к очереди с приоритетомpush(item)Помещает новый элемент в конец очереди.Для очереди с приоритетом позицияэлемента определяется его приоритетом.Элементы priority_queue отсортированы в порядке убывания приоритетов. Поумолчанию упорядочение основывается на операции “меньше”, определенной над парамиэлементов. Конечно, можно явно задать указатель на функцию или объект-функцию,которая будет использоваться для сортировки.
(В разделе 12.3 можно найти болееподробное объяснение и иллюстрации использования такой очереди.)6.18. Вернемся в классу iStackУ класса iStack, разработанного нами в разделе 4.15, два недостатка:•он поддерживает только тип int. Мы хотим обеспечить поддержку любыхтипов. Это можно сделать, преобразовав наш класс в шаблон класса Stack;•он имеет фиксированную длину. Это неудобно в двух отношениях:заполненный стек становится бесполезным, а в попытке избежать этого мыокажемся перед необходимостью отвести ему изначально слишком много памяти.Разумным выходом будет разрешить динамический рост стека.
Это можно сделать,пользуясь тем, что лежащий в основе стека вектор способен динамически расти.Напомним определение нашего класса iStack:С++ для начинающих311#include <vector>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()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;и push():}Функции-члены 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, и если мы хотим сохранить его до конца,необходимо оставить для конструктора один необязательный параметр. Вот как будетclass iStack {public:iStack( int capacity = 0 );// ...выглядеть объявление конструктора с таким параметром типа int:};inline iStack::iStack( int capacity ){if ( capacity )_stack.reserve( capacity );Что делать с аргументом, если он задан? Используем его для указания емкости вектора:}Превращение класса в шаблон еще проще, в частности потому, что лежащий в основе#include <vector>template <class elemType>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;вектор сам является шаблоном.
Вот модифицированное объявление:312С++ для начинающих313};Для обеспечения совместимости с программами, использующими наш прежний классiStack, определим следующий typedef:typedef Stack<int> 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(). Поскольку программисту не приходится запоминать многоС++ для начинающих314разных имен для одной и той же операции, пользоваться ими становится проще.Компилятор сам подставляет нужное в зависимости от типов фактических аргументов. Вглаве 9 объясняется, как объявлять и использовать перегруженные функции и каккомпилятор выбирает подходящую из набора перегруженных.Вторым средством, облегчающим использование функций, является механизм шаблонов.Шаблон – это обобщенное определение, которое используется для конкретизации –автоматической генерации потенциально бесконечного множества функций,различающихся только типами входных данных, но не действиями над ними.
Этотмеханизм описывается в главе 10.Функции обмениваются информацией с помощью значений, которые они получают привызове (параметров), и значений, которые они возвращают. Однако этот механизм можетоказаться недостаточным при возникновении непредвиденной ситуации в работепрограммы. Такие ситуации называются исключениями, и, поскольку они требуютнемедленной реакции, необходимо иметь возможность послать сообщение вызывающейпрограмме. Язык С++ предлагает механизм обработки исключений, который позволяетфункциям общаться между собой в таких условиях.
Этот механизм рассматривается вглаве 11.Наконец, стандартная библиотека предоставляет нам обширный набор частоиспользуемых функций – обобщенных алгоритмов. В главе 12 описываются этиалгоритмы и способы их использования с контейнерными типами из главы 6 и совстроенными массивами.7. ФункцииМы рассмотрели, как объявлять переменные (глава 3), как писать выражения(глава 4) и инструкции (глава 5). Здесь мы покажем, как группировать этикомпоненты в определения функций, чтобы облегчить их многократноеиспользование внутри программы. Мы увидим, как объявлять и определятьфункции и как вызывать их, рассмотрим различные виды передаваемыхпараметров и обсудим особенности использования каждого вида.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
