Глав4. Библиотека стандартные онов 423

У каждого контейнера имеется определенный для него распределитель памяти (allocator), который управляет процессом выделения памяти для контейнера. По умолчанию распределителем памяти является объект класса allocator, но вы можете определить собственный распределитель памяти,

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

В некоторых алгоритмах и контейнерах используется функция особого типа,

называемая предикатом (predicate). Предикат может быть бинарным или унарным. У унарного предиката один аргумент, а у бинарного - два. Возвращаемым значением этих функций жляется значения истина либо ложь. Точные условия получения того или иного значения определяются программистом. Все унарные предикаты, которые будут упомянуты в этой главе, имеют тип UnPred, а все бинарные - BinPrcd. Аргументы бинарного предиката всегда расположены по порядку: первый, второй. Тип аргументов как унарного, так и бинарного предиката соответствует типу хранящихся в

контейнере объектов.

В некоторых алгоритмах и классах используется специальный тип бинарного предиката, предназначенный для сравнения двух элементов. Такой предикат называется функцией сравнения (comparison function). Функция сравнения возвращает истину, если ее первый аргумент меньше второго. Типом функции сравнения является тип Сотр.

Помимо заголовков для разнообразных классов-контейнеров, входящих в библиотеку стандартных шаблонов, стандартная библиотека С++ включает также заголовка i[ity> и <functional>, предназначенные для поддержки классов-шаблонов. Например, заголовочный файл <utility> содержит определение класса-шаблона pair (пара), в котором могут храниться пары значений. Позднее в этой главе мы еще воспользуемся шаблоном pair.

Шаблоны из заголовочного файл Mtional> помогают создавать объекты, определяющие кцию operator(). Эти объекты называются объектами-функциями (function objects) и во многих случаях могут использоваться вместо указателей на функцию. В заголовочном файле <functionaI> обь-явлено несколько встроенных объектов-функций, некоторые из которых перечислены ниже:

plus minus multiplies divides modulus

negate equal to not equal to greater greater equal

less less equal iogical and logica1 or logicaLnot

Вероятно, чаще других применяется объект-функция less (меньше), которая позволяет определить, является ли значение одного объекта меньше, чем значение другого. В описываемых далее алгоритмах библиотеки стандартных шаблонов можно заменять указатели на реальные

функции. Если использовать объекты-функции вместо указателей на функцию, библиотека стандартных шаблонов будет генерировать более эффек-

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

1. Что представляют собо йнеры, алгоритмы и итераторы, входящие в

библиотеку стандартных шаблонов?

2. Какие вы знаете два типа предикатов? - ;

3. Какие существуют пять типов итераторов?

14.2. Классы-контейнеры

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

Таблица Контейнеры, определенные в библиотеке стандартных шаблонов

Таблица 1 (продолжение)

Поскольку имена типов элементов, входящих в объявление класса-шаблона, могут быть самыми разными, в классах-контейнерах с помощью ключевого слова typedef объявжются некоторые согласованные версии этих типов. Эта операция позволяет конкретизировать имена типов. Ниже представлены имена типов, конкретизированные с помощью ключевого слова typedef, которые можно встретить чаще других:

Согласованное имя типа Описание

size type reference const reference iterator

const lterator reversejterator const reverse lterator value.type

allocator type key type key compare value compare

Интегральный тип, эквивалентный типу size t Ссылка на элемент Постоянная ссылка на элемент Итератор

Постоянный итератор , -<

Обратный итератор Постоянный обратный итератор и.

Тип хранящегося в контейнере значения Тип распределителя памяти

Тип ключа

Тип функции, которая сравнивает два ключа Тип функции, которая сравнивает два значения

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

14.3. Векторы

Вероятно, самым популярным контейнером является вектор. В классе vector поддерживаются динамические массивы. Динамическим массивом называется массив, размеры которого могут увеличиваться по мере необходимости. Как известно, в C++ в процессе компиляции размеры массива фиксируют-