Обратите внимание на формулировку примерно так . Значения max size() и capacityO зависят от реализации. Например, в данном случае видно, что если вектор не помещается в зарезервированной памяти, реализация удваивает его емкость.

Класс vector<bool>

Для векторов, содержащих элементы логического тина, в стандартной библиотеке C-f-+ определена специализированная разновидность класса vector. Это было сделано для того, чтобы оптимизированная версия занимала меньше места, чем стандартная реализация vector для тина bool. В стандартной реализации для каждого элемента резервируется минимум 1 байт. Во внутреннем представлении специализированной реализации vector<bool> каждый элемент обычно представляется одним битом, поэтому она занимает в восемь раз меньше памяти. Впрочем, оптимизация не дается даром: в С-ь+ минимальное адресуемое значение должно иметь размер минимум 1 байт. Следовательно, специализированная версия требует специальной обработки ссылок и итераторов.

В результате vector<bool> не удовлетворяет всем требованиям других векторов (в частности, значение vector<bool>::reference не является полноценным 1-значением, а итератор vector<bool>::iterator не является итератором произвольного доступа). Следовательно, код шаблона работает с векторами любого тигш, за исключением bool. Вдобавок класс vector<bool> может уступать обычным реализациям но скорости работы, потому что операции с элементами приходится преобразовывать в операции с битами. Впрочем, внутреннее устройство vector<bool> зависит от реализации, поэтому эффективность (как скорость работы, так и затраты памяти) может быть разной.

Учтите, что класс vector<bool> представляет собой нечто большее, чем специализацию класса vectoro для bool. В него также включена поддержка специальных операций, упрощающих работу с флагами и наборами битов.

Размер контейнера vector<bool> изменяется динамически, поэтому его можно рассматривать как битовое ноле с динамическим размером. Иначе говоря, вы можете добавлять и удалять биты. Если вы работаете с битовым полем, имеющим статический размер, вместо класса vector<bool> лучше использовать bitset. Класс bitset рассматривается на с. 444.

Дополнительные операции контейнера vector<bool> перечислены в табл. 6.8. Операция flip(), производящая логическую иьшерсию, может применяться как ко всем битам, так и к отдельному биту вектора.

Таблица 6.8. Специальные операции vector<boo1> Операция Описание

c.ftipO Инвертирует все логические элементы

m[idx].flip() Инвертирует логический элемент с заданным индексом

m[idx] = val Присваивает значение логическому элементу с индексом idx

(присваивание одного бита)

m[idxl] = nfi[ldx2] Присваивает значение элемента с индексом idx2 элементу с индексом idxl

Обратите внимание на возможность вызова 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 fllpO:

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

- возвращается тип 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>.