306 Глава

и понятная подсистема. Если вы будете следовать нескольким правилам, то легко избежите ошибок, создавая собственный контейнер.

Предлагаемый в этой главе пользовательский контейнер реализует динамический массив с настраиваемым диапазоном индексов (range-selectable dynamic array), называемый RangeArray. При использовании такого массива можно задавать начальное и конечное значения индекса. Например, тип RangeArray позволяет создать массив, номера элементов которого меняются в диапазоне от -10 до 10.

Краткий обзор библиотеки STL

о стандартной библиотеке шаблонов можно рассказывать долго, а для ее подробного описания потребовались бы сотни страниц книги, что не входит в задачу автора. Поэтому при изложении материала в данной главе предполагается, что у вас есть базовые практические знания библиотеки STL. Тем не менее далее приводится краткий обзор основных терминов и компонентов библиотеки для того, чтобы все читатели оказались в равном положении.

Три основные составляюшие стандартной библиотеки шаблонов: контейнеры, итераторы и алгоритмы. Как уже отмечалось, контейнеры - это объекты, содержащие другие объекты. Итераторы - это объекты-указатели, позволяющие обрабатывать в цикле содержимое контейнера подобно тому, как вы обрабатываете в цикле массив с помошью указателя. Алгоритмы воздействуют на контейнеры, модифицируя, копируя элементы контейнеров или любым другим способом манипулируя ими.

Помимо контейнеров, алгоритмов и итераторов, в библиотеке используются следующие стандартные вспомогательные компоненты: pacnpedeiiumejiu памяти (allocators), адаптеры (adaptors), предикаты (predicates) и объекты-функции (function objects). В следующих разделах подробно описаны основные составляющие стандартной библиотеки шаблонов.

Примечание

Для подробного изучения библиотеки STL я рекомендую книгу STL Programming from the Ground Up ( STL-программирование, начиная с азов ) издательства McGraw-Hill/Osborne.

Контейнеры

в стандартной библиотеке шаблонов определены два типа контейнеров: по-ofiedoeamejibHbie (sequence container) и ассоциативные (associative container)-STL предоставляет несколько встроенных последовательных, контейнеров, включая вектор (vector), определяющий динамический массив, дек (deque), создающий двустороннюю очередь, и список (list), реализующий связанный

список. Ассоциативные контейнеры хранят пары ключ/значение. Таким образом, ассоциативные контейнеры позволяют эффективно извлекать значения, основываясь на ключах. Например, отображение (тар) обеспечивает доступ к значениям с помощью уникальных ключей. Таким образом, отображение хранит пару ключ/значение и позволяет извлекать значение, задавая его ключ.

В классе каждого контейнера определяется набор функций, которые могут применяться в контейнере. Например, контейнер list включает функции вставки, удаления и объединения элементов. В контейнере stack содержатся функции помещения (или проталкивания) данных в стек и извлечения (или выталкивания) данных из стека.

Алгоритмы

Алгоритмы воздействуют на контейнеры. Они обеспечивают средства, с помощью которых вы манипулируете содержимым контейнеров. К ним относятся инициализация, сортировка, поиск и преобразования содержимого. Многие алгоритмы обрабатывают ряд элементов в контейнере, а не весь контейнер целиком. Примерами алгоритмов могут служить соруО, removeo, replace о И find().

Итераторы

Итераторы - это объекты, подобные указателям. К ним применимы операции инкремента и декремента, а также операция *. Итераторы объявляются с типом iterator, определенным в различных контейнерах.

Библиотека STL поддерживает обратные (reverse iterator) итераторы. Такие итераторы перемещаются по последовательности объектов в обратном направлении. Следовательно, если обратный итератор указывает на конец последовательности, увеличение его на единицу с помощью операции инкремента приведет к ссылке итератора на предпоследний элемент последовательности.

Другие компоненты библиотеки STL

Помимо контейнеров, итераторов и алгоритмов, в стандартной библиотеке шаблонов содержится ряд других элементов, ифаюших важную роль, к ним относятся распределители памяти, объекты-функции, адаптеры, предикаты, связыватели (binders) и отрицатели (или инверторы) Xnegators). V каждого контейнера есть определенный для него распределитель, который Управляет распределением памяти для контейнера. Установленный по умолчанию распределитель памяти - это объект класса allocator, но можно определить собственный распределитель, если он необходим для специали-

зированного приложения. В большинстве случаев достаточно распределителя памяти, заданного по умолчанию.

Объекты-функции - это классы, в которых определена перегрузка оператора вызова с помощью operator (). Есть несколько определенных заранее объектов-функций, таких как lessO, greaterO, plus О , minus О , multiplies {) ц divides {). Возможно, наиболее часто используется объект-функция less () определяющая, меньше ли один объект другого. Объекты-функции могут применяться на месте указателей на функции в алгоритмах STL.

В самом общем смысле адаптер преобразует один элемент в другой. Существуют адаптеры контейнера, адаптеры итератора и адаптеры функции. Например, к контейнерным относится адаптер queue, который приспосабливает контейнер типа deque для использования его как стандартной очереди. Адаптеры упрощают обработку ряда сложных ситуаций.

Некоторые из алгоритмов и контейнеров используют специальный тип функции, именуемый предикатом. Есть две разновидности предикатов: унарные и бинарные. Унарный предикат принимает один аргумент, а бинарный - два аргумента. Эти функции возвращают результат true/false, но условия, при которых они возвращают true или false, определяются вами. Некоторые алгоритмы применяют специальный тип бинарного предиката, который сравнивает два элемента. Эти функции сравнения возвращают true, если их первый аргумент меньше второго.

Два других элемента, используемых в библиотеке STL, - связыватели и отрицатели. Связыватель связывает аргумент с объектом-функцией. В библиотеке STL определены два связывателя: bind2nd() и bindisto. Отрицатель возвращает дополнение предиката. Существуют два отрицателя: notio и not2 (). Как связыватели, так и отрицатели увеличивают гибкость и универсальность библиотеки STL.

Требования

к пользовательскому контейнеру

Прежде чем начать разрабатывать собственный контейнер, необходимо точно знать, что он должен делать. В соответствии со стандартом С++, все контейнеры должны поддерживать предписанный набор типов, операций и функции-членов. Помимо этих общих элементов, как последовательные, так и ассоциативные контейнеры должны удовлетворять специфическим требованиям Если строго следовать всем правилам, ваш собственный контейнер сможет воспользоваться любыми другими элементами, определенными в библиотеке STL, включая распределители памяти, объекты-функции, предикаты и связыватели-Таким образом, ваш собственный контейнер составит единое целое с STL-В следующих разделах перечислены требования к контейнеру.