Эффективное использование 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>.

Ассоциативные контейнеры

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

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

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

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

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

Алгоритм find и функция set::insert являются типичными представителями семейства функций, проверяющих совпадение двух величин, однако делают это они по-разному. Для find совпадением считается равенство двух величин, проверяемое оператором =. Функция set:: insert проверяет отношение эквивалентности, обычно основанное на операторе < Таким образом, по одному определению два объекта могут иметь одинаковые значения, тогда как по другому определению они будут различаться. Отсюда следует, что для эффективного использования STL необходимо понимать различия между равенством и эквивалентностью.

Формальное определение равенства основано на использовании оператора =. Если результат выражения х=у равен true, значит, х и у имеют одинаковые значения, а если false — разные. В целом определение весьма прямолинейное, хотя следует помнить о том, что из равенства значений не следует равенство всех полей данных. Предположим, класс Widget хранит внутренние данные о времени последнего обращения:

class Widget {
public:
private:
	TimeStamp lastAccessed;
};

Для класса Widget можно определить оператор ==, игнорирующий значение этого поля:

bool operator=(const Widgets Ihs, const Widgets rhs) {
// Поле lastAccessed игнорируется
}

В этом случае два объекта Widget будут считаться равными даже в том случае, если их поля lastAccessed содержат разные значения.

Эквивалентность основана на относительном порядке значений объектов в отсортированном интервале. Проще всего рассматривать ее в контексте порядка сортировки, являющегося частью любого стандартного ассоциативного контейнера (то есть set, multiset, map и multimap). Два объекта х и у считаются эквивалентными по отношению к порядку сортировки, используемому ассоциативным контейнером с, если ни один из них не предшествует другому в порядке сортировки с. На первый взгляд такая формулировка кажется запутанной, но на практике все просто. Возьмем контейнер set<Widget> s. Два объекта Widget, w1 и w2, имеют эквивалентные значения по отношению к s, если ни один из них не предшествует другому в порядке сортировки s. Стандартная функция сравнения для set<Widget> — less<Widget> — по умолчанию просто вызывает operator< для объектов Widget, поэтому wl и w2 будут иметь значения, эквивалентные по отношению к operator< если истинно следующее выражение:

!(w1<w2)	// Условие w1 < w2 ложно
&&	// и
!(w2<w1)// Условие w2 < w1 ложно

Все вполне логично: два значения эквивалентны (по отношению к некоторому критерию упорядочения), если ни одно из них не предшествует другому в соответствии с данным критерием.

В общем случае функцией сравнения для ассоциативного контейнера является не оператор < или даже less, а пользовательский предикат (см. совет 39). Каждый стандартный ассоциативный контейнер предоставляет свой предикат сортировки через функцию key_comp, поэтому два объекта х и у имеют эквивалентные значения по отношению к критерию сортировки ассоциативного контейнера с, если выполняется следующее условие:

!c.key_comp()(x.y) && !c.key_comp()(y,x) // х не предшествует у
// в порядке сортировки с,
// а у не предшествует х

Выражение !c.key_comp()(x,y) выглядит устрашающе, но стоит понять, что c.key_comp() возвращает функцию (или объект функции), как все затруднения исчезают. Перед нами простой вызов функции (или объекта функции), возвращаемой key_comp, которой передаются аргументы х и у. Затем вычисляется логическое отрицание результата. Функция с.keycomp ()(х, у) возвращает true лишь в том случае, если х предшествует у в порядке сортировки, поэтому выражение !с.key_comp()(х, у) истинно только в том случае, если х не предшествует у в порядке сортировки с.

Чтобы вы лучше осознали принципиальный характер различий между равенством и эквивалентностью, рассмотрим пример — контейнер set<string> без учета регистра символов, то есть контейнер set<string>, в котором функция сравнения игнорирует регистр символов в строках. С точки зрения такой функции строки «STL» и «stL» эквивалентны. Пример реализации функции ciStringCompare, игнорирующей регистр символов, приведен в совете 35, однако set требуется тип функции сравнения, а не сама функция. Чтобы заполнить этот пробел, мы пишем класс функтора с оператором (), вызывающим ciStringCompare:

struct CiStringCompare:// Класс сравнения строк
public// без учета регистра символов;
binary_function<string,string,bool>{ // описание базового класса
// приведено в совете 40
bool operator() (const string& lhs,
const string& rhs) const