Обратите внимание на возможность вызова flip() для одного логического элемента. На первый взгляд это выглядит странно, потому что оператор индексирования возвращает зпачение типа bool, а вызов flip() для этого базового типа невозможен. В данном случае класс vector<bool> использует стандартную методику, основанную на применении так называемых заместителей, для vector<bool> возвращаемое значение оператора индексирования (и других операторов, возвращающих элементы) оформлено в виде вспомогательного класса. Если вы хотите, чтобы возвращаемое значение интерпретировалось как значение типа bool, используется автоматическое преобразование типа. Для других операций определяются функции класса. Соответствующая часть объявления vector<bool> выглядит так:

namespace std { *

class vector<bool> { public:

Вспомогательный тип для оператора индексирования class reference {

public:

Автоматическое преобразование типа к bool operator boolО const:

Присваивание

references operator= (const bool): references operator= (const references):

Инверсия бита void flipO:

Операции обращения к элементам

- возвращается тип reference вместо bool

reference operator[](size type n):

reference at(size type n);

reference front();

reference backO;

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

c.frontO.flipO; Инверсия первого логического элемента

c,at(5) = cbackO: Присвоить последний элемент элементу с индексом 5

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

Внутренний тин reference используется только для неконстантных контейнеров тина vector<bool>. Константные функции обращения к элементам возвращают обычные значения тина bool.

Деки

Дек очень похож на вектор. Он тоже работает с элементами, o(lJopмлeнными в динамический массив, поддерживает произвольный доступ и обладает практически тем же интерфейсом. Различие заключается в том, что динамический массив дека открыт с обоих концов. По этой причине дек быстро выполняет операции вставки и удаления как с конца, так и с начала (рис. 6.2).

Рис. 6.2. Логическая структура дека

Дек обычно реализуется в виде набора блоков; первый и последний блоки наращиваются в противоположных направлениях (рис. 6.3).

Рис. 6.3. Внутренняя структура дека

Чтобы исно.тьзовать дек в программе, необходимо включить в нее заголовочный файл <deque>:

finclude <deque>

Тип дека определяется как шаблон класса в пространстве имен std:

namespace std {

template <class Т.

class Allocator = allocator<T> > class deque;

В исходной версии STL дек определялся в заголовочном файле <deque.h>.

Как и в случае с вектором, тип элементов дека передается в первом параметре шаблона. Допускается любой тип, поддерживающий присваивание и копирование. Необязательный второй параметр шаблона определяет модель памяти, ло умолчанию используется модель allocator (см. главу 15)

Возможности деков

По споим возможностям деки во многом отличаются от векторов.

О Вставка и удаление выполняются быстро как в начале, так и в конце (для векторов эти операции выполняются быстро только в конце). Операции выполняются с амортизированным постоянным временем.

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

О Итераторы должны быть умными указателями особого типа. Обычные указатели не подходят из-за необходимости перехода между блоками.

О В системах с ограниченными размерами блоков памяти (например, в некоторых системах PC) дек может содержать больше элементов, поскольку он не ограничивается одним блоком памяти. Следовательно, функция max size() может возвращать для деков большую величину.

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

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

Следующие особенности векторов характерны также и для деков.

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

О Итераторы являются итераторами произвольного доступа.

Подведем итог. Выбирайте дек, если выполняются следующие условия:

О вставка элементов выполняется с обоих концов (классический пример очереди);

О в программе не используются ссылки на элементы контейнера;

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

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