Вернемся в классу iStack
У класса iStack, разработанного нами в разделе 4.15, два недостатка:
- он поддерживает только тип int. Мы хотим обеспечить поддержку любых типов. Это можно сделать, преобразовав наш класс в шаблон класса Stack;
- он имеет фиксированную длину. Это неудобно в двух отношениях: заполненный стек становится бесполезным, а в попытке избежать этого мы окажемся перед необходимостью отвести ему изначально слишком много памяти. Разумным выходом будет разрешить динамический рост стека. Это можно сделать, пользуясь тем, что лежащий в основе стека вектор способен динамически расти.
Напомним определение нашего класса iStack:
#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() и 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 <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;
};
Для обеспечения совместимости с программами, использующими наш прежний класс 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(). Поскольку программисту не приходится запоминать много разных имен для одной и той же операции, пользоваться ими становится проще. Компилятор сам подставляет нужное в зависимости от типов фактических аргументов. В главе 9 объясняется, как объявлять и использовать перегруженные функции и как компилятор выбирает подходящую из набора перегруженных.
Вторым средством, облегчающим использование функций, является механизм шаблонов. Шаблон – это обобщенное определение, которое используется для конкретизации –
автоматической генерации потенциально бесконечного множества функций, различающихся только типами входных данных, но не действиями над ними. Этот механизм описывается в главе 10.
Функции обмениваются информацией с помощью значений, которые они получают при вызове (параметров), и значений, которые они возвращают. Однако этот механизм может оказаться недостаточным при возникновении непредвиденной ситуации в работе программы. Такие ситуации называются исключениями, и, поскольку они требуют немедленной реакции, необходимо иметь возможность послать сообщение вызывающей программе. Язык С++ предлагает механизм обработки исключений, который позволяет функциям общаться между собой в таких условиях. Этот механизм рассматривается в главе 11.
Наконец, стандартная библиотека предоставляет нам обширный набор часто используемых функций – обобщенных алгоритмов. В главе 12 описываются эти алгоритмы и способы их использования с контейнерными типами из главы 6 и со встроенными массивами.
