ми ПОЛЯМИ существует принципиальное различие. Создать указатель на реальное число bool можно, но указатели на отдельные биты запрещены.

Ссылки на отдельные биты тоже запрещены, что представляет определенную проблему для дизайна интерфейса vector<bool>, поскольку функция vector<T>:: operator[] должна возвращать значение типаТ&. Если бы контейнер vector<bool> действительно содержал bool, этой проблемы не существовало бы, но вследствие особенностей внутреннего представления функция vector<T>: :operator[] должна вернуть несуществующую ссылку на отдельный бит.

Чтобы справиться с этим затруднением, функция vector<T>: :operator[] возвращает объект, который имитирует ссылку на отдельный бит - так называемый промежуточный объект. Для использования STL не обязательно понимать, как работают промежуточные объекты, но вообще это весьма полезная идиома С++. Дополнительная информация о промежуточных объектах приведена в совете 30 Моге Effective С++ , а также в разделе Паттерн Ргоху книги Приемы объектно-ориентированного проектирования [6]. На простейшем уровне vector<bool> выглядит примерно так:

template <typenanie Allocator> vector<bool.Allocator> { public:

class reference {...}: Класс, генерирующий проме)Куточные

объекты для ссылок на отдельные биты

reference operator[](size type n); operator[] возвращает

промежуточный объект

Теперь понятно, почему следующий фрагмент не компилируется: vector<bool> v;

bool *pb=&v[0]; Ошибка! Выражение в правой части относится к типу vector<bool>::reference*, а не bool*

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

Спрашивается, почему же vector<bool> присутствует в Стандарте, если это не контейнер? Отчасти это связано с одним благородным, но неудачным экспериментом, но позвольте мне ненадолго отложить эту тему и заняться более насущным вопросом. Итак, от vector<bool> следует держаться подальше, потому что это не контейнер - но что же делать, когда вам действительно понадобится вектор логических величин?

В стандартную библиотеку входят два альтернативных решения, которые подходят практически для любых ситуаций. Первое решение - deque<bool>. Контейнер deque обладает практически всеми возможностями vector (за исключением разве

что reserve и capacity), но при этом deque<bool> является полноценным контейнером STL, содержащим настоящие значения bool. Конечно, внутренняя память deque не образует непрерывный блок, поэтому данные deque<bool> не удастся передать функции С, получающей массив bool (см. совет 16), но это не удалось бы сделать и с vector<bool> из-за отсзггствия переносимого способа ползения данных vector<bool>. (Прием, продемонстрированный для vector в совете 16, не компилируется для vector<bool>, поскольку он зависит от возможности ползения на тип элемента, хранящегося в векторе, - как упоминалось выше, vector<bool> не содержит bool.)

Второй альтернативой для vector<bool> является bitset. Вообще говоря, bitset не является стандартным контейнером STL, но входит в стандартную библиотеку С++. В отличие от контейнеров STL, размер bitset (количество элементов) фиксируется на стадии компиляции, поэтому операции вставки-удаления элементов не поддерживаются. Более того, поскольку bitset не является контейнером STL, в нем отсутствует поддержка итераторов. Тем не менее bitset, как и vector<bool>, использует компактное представление каждого элемента одним битом, поддерживает функцию flip контейнера vector<bool> и ряд других специальных функций, имеющих смысл в контексте битовых множеств. Если вы переживете без итераторов и динамического изменения размеров, вероятно, bitset хорошо подойдет для ваших целей.

А теперь вернемся к благородному, но неудачному эксперименту, из-за которого появился псевдоконтейнер vector<bool>. Я уже упоминал о том, что промежуточные объекты часто используются при программировании на С++. Члены Комитета по стандартизации С++ знали об этом, поэтому они решили создать vector<bool> как наглядный пример контейнера, доступ к элементам которого производится через промежуточные объекты. Предполагалось, что при наличии такого примера в Стандарте у программистов появится готовый образец для построения собственных аналогов.

В итоге выяснилось, что создать контейнер с промежуточными объектами, удовлетворяющий всем требованиям к контейнеру STL, невозможно. Так или иначе, следы этой неудачной попытки сохранились в Стандарте. Можно долго гадать, почему vector<bool > был сохранен, но с практической точки зрения это несущественно. Главное - помните, что vector<bool> не удовлетворяет требованиям к контейнерам STL, что им лзше не пользоваться и что существуют альтернативные структуры данных deque<bool> и bitset, почти всегда способные заменить vector<bool>.

Ассоциативные контейнеры ч\;.е1

Ассоциативные контейнеры по некоторым характеристикам схожи с последовательными контейнерами, однако между этими категориями существует ряд принципиальных различий. Так, содержимое ассоциативных контейнеров автоматически сортируется; анализ содержимого производится по критерию эквивалентности, а не равенства; контейнеры set и тар не могут содержать дубликатов, а контейнеры тар и mul timap обычно игнорируют половину данных в каждом из содержащихся в них объектов. Да, ассоциативные контейнеры являются контейнерами, но они определенно выделяются в самостоятельную категорию.

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

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

Совет 19. Помните о различиях между равенством и эквивалентностью

Задача сравнения объектов возникает в STL очень часто. Например, если функция f i nd ищет в интервале первый объект с заданным значением, она должна уметь сравнивать два объекта и узнавать, совпадают ли их значения. При попытке включения нового элемента в множество функция set:: insert должна проверить, не существует ли данное значение в контейнере.