Эффективное использование STL

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

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

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

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

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

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

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

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