На этом шаге мы рассмотрим соглашения именования шаблонов.
Бессчетное количество имен классов в библиотеке поначалу может показаться ошеломляющим, и поскольку одни классы выводятся из других, то часто приходится читать информацию о нескольких классах для того, чтобы разобраться, что делает дин из них. Например, в классе TStackAsVector определен только конструктор. В предке класса TMStackAsVector определяются другие функции, подобные Push(), Pop() и Тор(). Вам придется разобраться в обоих классах, чтобы понять, как работает TStackAsVector.
Замечание. В классах с именами начинающимися на ТМ, обеспечивается управление памятью для контейнера. Эти классы следует использовать только в том случае, если вы собираетесь реализовать свое собственное управление памятью, о чем речь пойдет позже.
Хорошее знание имен контейнерных классов поможет вам преодолеть дебри библиотечной документации. Еще более важно свободно владеть соглашениями именования классов. Имена контейнерных классов характеризуют их возможности и взаимосвязи. Сперва имена контейнерных классов могут показаться вам непонятными, однако разложите имя каждого класса на составные части и вы обнаружите, что все они составлены по единому плану.
В целом имена контейнерных классов имеют следующий вид:
Т [префикс] [АТД] [AsФСД] [суффикс]
Все имена классов начинаются с буквы Т (тип). Необязательный префикс указывает на способ запоминания данных - например, сортируются ли объекты (S) или же запоминаются косвенно в виде указателей (I). Затем следует такой АТД, как массив (Array) или стек (Stack). Если за ним следует слово As, значит контейнер реализован на основе заданной ФСД, которая может быть, к примеру, списком (List), двусвязным списком (DoubleList) или другим фундаментальным типом данных. Наконец, необязательный параметр "суффикс" ссылается на тип сопутствующего класса. Некоторые классы, к примеру, заканчиваются словом Iterator, означающим, что этот класс выполняет итерационные действия над данными в контейнере.
Однако не все классы в библиотеке твердо придерживаются этих соглашений именования. Некоторые классы даже не являются контейнерными - они могут быть, к примеру, фундаментальными структурами, использующимися для реализации контейнеров. Другие классы играют просто вспомогательную роль. Вы также не найдете абсолютно всех возможных комбинаций АТД и ФСД. Например, не существует класса TStackAsHashTable, поскольку бессмысленно реализовать стек (тип данных с последовательным доступом) с помощью хэш-таблицы (структура данных с произвольным доступом).
В таблице 1 перечислены библиотечные абстрактные типы данных и соответствующие им заголовочные файлы, а также фундаментальные структуры данных, используемые для реализации каждого контейнера. Например, Deque (дек) может реализоваться как DoubleList (двухсвязный список) или Vector (вектор). Исходя из таблицы, можно предположить существование контейнерных классов с именами TDequeAsDoubleList и TDequeAsVector. Можно также заключить, что класса TDequeAsHashTable не существует. Ни один контейнер не использует структуру BinarySearchTree (бинарное дерево поиска).
| АТД | Заголовочный файл | Дерево двоичного поиска | Двусвязный список | Хэш-таблица | Список | Вектор |
|---|---|---|---|---|---|---|
| Array (Массив) | ARRAYS. H | х | ||||
| Bag (Мультимножество) | BAGS.H | х | ||||
| Deque (Дек - очередь с двусторонним доступом) | DEQUES. H | х | х | |||
| Dictionary (Словарь) | DICT.H | х | ||||
| Queue (Очередь) | QUEUES.H | х | х | |||
| Set (Множество) | SETS.H | х | ||||
| Stack (Стек) | STACKS.H | х | х |
В таблице 2 приводится та же информация, что и в таблице 1, с той лишь разницей, что в ней перечислены фундаментальные структуры данных и их заголовочные файлы. Например, в таблице 2 указывается, что только контейнер Stack (стек) может использовать List (список), следовательно, можно предположить существование в библиотеке класса с именем TStackList. Таблица также свидетельствует о том, что Vector - самая часто используемая фундаментальная структура, задействованная в шести различных типах контейнеров.
| ФСД | Заголовочный файл | Array (Массив) | Bag (Мультимножество) | Deque (Дек) | Dictionary (Словарь) | Queue (Очередь) | Set (Множество) | Stack (Стек) |
|---|---|---|---|---|---|---|---|---|
| Дерево двоичного поиска | BINIMP.H | |||||||
| Двусвязный список | DLISTIMP.H | х | х | |||||
| Хэш-таблица | HASHIMP.H | х | ||||||
| Список | LISTIMP.H | |||||||
| Вектор | VECTIMP.H | х | х | х | х | х | х |
В таблице З имена АДТ и ФСД, приведенные в таблицах 1 и 2, дополняются несколькими модификаторами способа хранения. Модификаторы задаются сразу после лидирующей буквы Т в имени класса. Например, класс TIStackVector означает косвенный контейнерный класс стека, реализованный с помощью вектора. Косвенные контейнеры хранят указатели на объекты. Без модификатора I (например, в TStackVector) контейнер запоминает непосредственно объекты данных. Добавочное S означает автоматическую сортировку. Например, класс TSArrayAsVector - отсортированный массив объектов, реализованный с помощью вектора; класс TISArrayAsVector - отсортированный массив указателей на объекты, реализованный с помощью вектора.
| Модификатор | Свойство |
|---|---|
| C | С подсчетом числа объектов |
| I | С запоминанием указателей (без I запоминаются сами объекты) |
| IS | С сортировкой и запоминанием указателей |
| M | С управлением памятью |
| MC | С управлением памятью и подсчетом числа объектов |
| MI | С управлением памятью и запоминанием указателей |
| MIC | С управлением памятью, запоминанием указателей и подсчетом числа объектов |
| MIS | С управлением памятью, запоминанием указателей и сортировкой |
| MS | С управлением памятью и сортировкой |
| S | С сортировкой |
В классах с модификатором М обеспечивается управление памятью для классов со схожими именами. Например, в классе ТМQueueAsVector обеспечивается управление памятью для класса TQueueAsVector. Единственная причина использования контейнера класса М - замена стандартного управления памятью вашим собственным. Большинство программистов крайне редко занимаются подобными вещами.
Контейнеры класса М используют класс выделения памяти по умолчанию TStandardAllocator, определенный в заголовочном файле ALLOCSTR.H. Этот класс пользуется базовыми операторами new, new[], delete и delete[], которые в Borland C++ вызывают стандартные функции языка С malloc() и free().
Замечание. Контейнеры с сортировкой должны иметь возможность сравнивать свои объекты. Контейнеры с хранением непосредственно объектов должны быть способны их копировать. Это означает, что вы должны снабдить класс конструктором копии и перегруженными операторами == и <.
После беглого ознакомления с библиотекой контейнеров рассмотрим несколько дополнительных классов, завершающихся одним из трех возможных суффиксов (назовем их модификаторами типа класса, однако стандартного термина для них не существует). Классы, имена которых заканчиваются словом Element, обеспечивают "списочные оболочки" объектов. Существует только два таких класса - TMDoubleListElement и TMListElement. Они дают возможность создавать списки объектов, не имеющих полей-указателей. Вы не можете использовать классы Element в контейнерах абстрактных типов данных. Они используются только фундаментальными структурами данных.
Другой модификатор типа класса, Imp, означает реализацию. В общем, классы, имена которых заканчиваются на Imp, - это фундаментальные структуры данных, используемые для реализации абстрактных контейнеров. Например, класс TDoubleListImp реализует двусвязный список. Вы можете использовать классы Imp для создания своих собственных контейнеров, однако для этого необходимо хорошо разбираться во внутренностях классов. В большинстве случаев лучше пользоваться абстрактным контейнером, подобным TDequeAsDoubleList, чем реализацией TDoubleListImp, на которой основывается абстрактный контейнер.
Третий и последний тип модификатора, Iterator, означает, что класс снабжает средствами итерации фундаментальную структуру или контейнер с похожим именем. Итератор обеспечивает доступ ко всем объектам, содержащимся в контейнере. Например, класс TDequeAsVectorIterator - итератор для объектов, хранящихся в контейнере TDequeAsVector. Классы итераторов, заканчивающиеся на Imp, снабжают средствами итерации фундаментальные структуры. Например, класс TDoubleListIteratorImp - реализация итератора для объектов, хранящихся в структуре TDoubleListImp.
Наконец, существует еще один класс, TShouldDelete, "плавающий"; под своим флагом. Как можно заключить из его имени, этот специальный класс сообщает, должен ли контейнер удалять объекты, которые он хранит, или следует переложить эту обязанность на вас.
На следующем шаге мы рассмотрим способы запоминания объектов в контейнерах.
