НИЯ этих функций СО стороны пользователя. Такие изменения всегда нежелательны и нарушают общую стройность программы, которая использует, например, библиотечные классы, построенные по приведенной в данном параграфе схеме.

Шаблоны здесь применяются для того, чтобы обеспечить возможность использования различных типов в нашей иерархической структуре, представленной базовыми и производным классами. Это позволяет существенно расширить область применения соответствующих программ.

6.7. Контейнеры

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

Вернемся к примеру из § 6.1 (с. 227). Стек - это типовая структура, показанная на рис. 6.3. Можно рассматривать класс STACK (стек) целочисленных объектов и строить объекты это-

Данные, которые уже помещены в стек

ПАМЯТЬ

Увеличение значения sp

Размер стека

СТЕК

. Вершина стека (Юр)

- Указатель стека (sp)

1. Запись (push)

1.1, Запись объекта

1.2. Увеличение значения spna единицу

2. Чтение (pop)

2.1. Уменьшение значения spna единицу

2.2, Чтение объекта

Рис. 6.3. Структура стека. Контейнер стеков - это множество стеков, для которого тип хранимых в стеке объектов задается в виде параметра

Длинные имена классов, функций, переменных и констант, которые перенесены с одной строки на другую с использованием знака переноса (-), следует читать как одно слово,

ГО класса, которые будут отличаться, например, размером size стека. Однако любой объект - это стек целых чисел размером size. Предположим, необходимо построить стек объектов типа Т размером size. Здесь уже необходим контейнер классов, т. е. множество классов, в которые тип Т поставляется в виде параметра. Таким образом, контейнер - это множество классов, содержащих типовую структуру, например, стек, и типовые операции, например, push - затолкнуть в стек и pop - вытолкнуть из стека (см. рис. 6.3). Множество таких классов (т. е. контейнер классов) обычно строится с помоп1ью шаблона (template).

Использование контейнеров рассмотрим на примере библиотеки Borland С++ [7], которая содержит контейнеры двух типов: фундаментальные структуры данных (ФСД) и абстрактные типы данных (АТД). Первые из них являются контейнерами низкого уровня и включают: бинарные деревья, кэш-таблицы, связанные списки и векторы. Вторые являются контейнерами высокого уровня и включают: массивы, очереди, словари, множества и стеки. Каждый АТД основывается на ФСД и включает операции, являющиеся специфичными для соответствующего типа (например, push и pop для стека). Так, стек можно представить в виде вектора (один тип ФСД) и в виде списка (другой тип ФСД). Соответственно можно рассмотреть такие объявления:

TStackAsVector<char> ch stackV( 150);

TStackAsList<char> ch stackL(150); Здесь TStackAsVector и TStackAsList - имена классов, для которых заданы шаблоны в библиотеке, char - тип данных, передаваемых в объекты ch stackV и ch stackL в виде параметра, 150 - размер стека, равный 150 символам.

Выбор того или иного типа стека определяется предъявляемыми к нему требованиями. Так, если необходим быстрый стек с заранее известным числом элементов, то надо использовать ФСД-вектор. Если скорость записи-чтения данных не является определяющей и заранее не известен размер стека, то надо использовать ФСД-список.

При построении имен контейнеров, например*, TStackAsVector, использованы следующие соглашения:

префикс Т используется во всех классах библиотеки Borland;

буква I (например, TIStackAsVector) говорит о том, что контейнер хранит указатели на объекты, а не сами объекты;

буква S (например, TSArray As Vector) свидетельствует о том, что данные в контейнере будут сортироваться;

буква М (например, TMStackAsVector) говорит о том, что пользователь будет применять свои собственные функции для управления памятью (эти вопросы частично рассмотрены в § 6.6 и в [1, с. 282-283]);

буква С применяется довольно редко (например, TCVec-torlmp) и говорит о том, что класс использует счетные структзфы.

Разрешается комбинировать несколько букв в имени одного класса (например, TISArrayAsVector), однако не все комбинации являются допустимыми (соответствующую информацию можно найти в руководствах по использованию библиотек фирмы Borland).

Каждый контейнер имеет соответствующий ему повторитель, или итератор. Как и контейнер, итератор задается с помощью шаблона. Например, класс TArrayAsVector имеет класс-итератор TArrayAsVectorlterator, который отличается наличием суффикса Iterator.

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

Первый пример демонстрирует построение про-стейщего массива объектов типа double.

#include <iostream.h>

#include <classlib\arrays.h> файл заголовка /

для данного контейнера

void main(void)

{ TSArrayAsVector<double> а(10); а - контейнер