Контейнерные адаптеры

Помимо основных контейнерных классов стандартная библиотека C++ содержит специальные контейнерные адаптеры, предназначенные для особых целей. В их реализации применяются основные контейнерные классы. Ниже перечислены стандартные контейнерные адаптеры, определенные в библиотеке.

Стеки — контейнеры, элементы которых обрабатываются по принципу LIFO (последним прибыл, первым обслужен);

Очереди — контейнеры, элементы которых обрабатываются по принципу FIFO (первым прибыл, первым обслужен). Иначе говоря, очередь представляет собой обычный буфер.

Приоритетные очереди — контейнеры, элементам которых назначаются приоритеты. Приоритет определяется на основании критерия сортировки, переданного программистом (по умолчанию используется оператор <). В сущности, приоритетная очередь представляет собой буфер, следующий элемент которого всегда обладает максимальным приоритетом в очереди. Если максимальный приоритет назначен сразу нескольким элементам, порядок следования элементов не определен.

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

Итераторы

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

* — получение элемента в текущей позиции итератора. Если элемент состоит из отдельных членов, для обращения к ним непосредственно через итератор используется оператор -> .

++ — перемещение итератора к следующему элементу. Многие итераторы также поддерживают перемещение в обратном направлении, для чего используется оператор --.

= = и != — проверка совпадений позиций, представленных двумя итераторами.

= — присваивание итератора (позиции элемента, на которую он ссылается).

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

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

begin( ) — возвращает итератор, установленный в начало последовательности элементов контейнера. Началом считается позиция первого элемента (если он есть).

end( ) — возвращает итератор, установленный в конец последовательности элементов контейнера. Концом считается позиция за последним элементом.

Итак, функции begin( ) и end( ) определяют полуоткрытый интервал, который содержит первый элемент, но выходит за пределы последнего элемента (рис. 5.3). Полуоткрытый интервал обладает двумя достоинствами:

- появляется простое условие завершения перебора в контейнере: цикл продолжается до тех пор, пока не будет достигнута позиция end( );

- предотвращается специальная обработка пустых интервалов, поскольку в пустом интервале begin( ) совпадает с end( ).

Рис. 9.3. Функции begin( ) и end( )

Следующий пример демонстрирует применение итераторов. В нем выводятся значения всех элементов списка.

#include "stdafx.h"

#include <iostream>

#include <list>

using namespace std;

int main()

{

list<char> coll; // Список с символьными элементами

// Присоединение элементов от ‘a’ до 'z'

for (char с = 'a'; с <='z'; ++с) coll.push_back(с);

/* Вывод содержимого списка

* - перебор всех элементов.*/

list<char>::const_iterator pos;

for (pos = coll.begin(); pos != coll.end(); ++pos) cout<<*pos<<' ';

cout<<endl;

}

После того как список создан и заполнен символами от «а» до «z», все элементы выводятся в цикле for:

list<char>::const_iterator pos;

for (pos = coll.begin(); pos != coll.end(); ++pos) cout<<*pos<<' ';

Итератор pos объявляется непосредственно перед началом цикла. В объявлении выбирается тип итератора для обращения к элементам контейнерного класса без возможности модификации: list<char>::const_iterator pos;

В каждом контейнере определены два типа итераторов:

· контейнер::iterator — используется для перебора элементов в режиме чтения/записи;

· контейнер::const_iterator — используется для перебора элементов в режиме чтения.

Скажем, в классе list эти определения выглядят примерно так:

namespace std {

template <class T>

class list {

public:

typedef ... iterator;

typedef ... const_iterator;

...

}

}

Конкретный тип итераторов iterator и const_iterator зависит от реализации.

В теле цикла for итератор pos инициализируется позицией первого элемента: pos = coll.begin( );

Цикл продолжается до тех пор, пока pos не выйдет за пределы интервала контейнерных элементов: pos != coll.end( );

В этом условии итератор pos сравнивается c конечным итератором. Оператор ++pos в заголовке цикла перемещает итератор pos к следующему элементу.

В итоге итератор pos перебирает все элементы, начиная с первого, пока не дойдет до конца (рис. 54), Если контейнер не содержит ни одного элемента, тело цикла не выполняется, потому что значение coli.begin( ) будет равным значению coil.end( ).

Рис. 9.4. Итератор pos при переборе элементов списка

В теле цикла текущий элемент представляется выражением *pos. Модификация текущего элемента невозможна, потому что итератор был объявлен с типом const_iterator, а значит, с точки зрения итератора элементы являются константными. Но если объявить неконстантный итератор для перебора неконстантных элементов, значения можно будет изменить. Пример:

// Приведение всех символов в списке к верхнему регистру

list<char>::iterator pos;

for(pos = coll.begin(); pos != coll.end(); ++pos) *pos = toupper(*pos);

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

for (pos = coll.begin(); pos != coll.end(); pos++) {

// Работает.

// но медленнее

…

}

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