C++: базовый курс

Алгоритмы обрабатывают содержимое контейнеров.

Алгоритмы обрабатывают содержимое контейнеров. Их возможности включают средства инициализации, сортировки, поиска и преобразования содержимого контейнеров. Многие алгоритмы работают с заданным диапазоном элементов контейнера.

Итераторы подобны указателям.

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

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

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

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

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

STL опирается не только на контейнеры, алгоритмы и итераторы, но и на другие стандартные компоненты. Основными из них являются распределители памяти, предикаты и функции сравнения.

Распределитель памяти управляет выделением памяти для контейнера.

Каждый контейнер имеет свой распределитель памяти (allocator). Распределители управляют выделением памяти для контейнера. Стандартный распределитель — это объект класса allocator, но при необходимости (в специализированных приложениях) можно определять собственные распределители. В большинстве случаев стандартного распределителя вполне достаточно.

Предикат возвращает в качестве результата значение ИСТИНА/ЛОЖЬ.

Некоторые алгоритмы и контейнеры используют специальный тип функции, называемый предикатом (predicate). Существует два варианта предикатов: унарный и бинарный. Унарный предикат принимает один аргумент, а бинарный — два. Эти функции возвращают значения ИСТИНА/ЛОЖЬ, но точные условия, которые заставят их вернуть истинное или ложное значение, определяются программистом. В остальной части этой главы, когда потребуется унарная функция-предикат, на это будет указано с помощью типа UnPred. При необходимости использования бинарного предиката будет применяться тип BinPred. В бинарном предикате аргументы всегда расположены в порядке первый, второй относительно функции, которая вызывает этот предикат. Как для унарного, так и для бинарного предикатов аргументы должны содержать значения, тип которых совпадает с типом объектов, хранимых данным контейнером.

Функции сравнения сравнивают два элемента последовательности.

Некоторые алгоритмы и классы используют специальный тип бинарного предиката, который сравнивает два элемента. Функции сравнения возвращают значение true, если их первый аргумент меньше второго. Функции сравнения идентифицируются с помощью типа Comp.

Помимо заголовков, требуемых различными классами STL, стандартная библиотека C++ включает заголовки и , которые обеспечивают поддержку STL. Например, в заголовке определяется шаблонный класс pair, который может хранить пару значений. Мы будем использовать класс pair ниже в этой главе.

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

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

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

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