Скотт Мейерс - Эффективное использование STL

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

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

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

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

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

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

class Widget {

public:

…

private:

TimeStamp lastAccessed;

};

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

bool operator==(const Widgets lhs, const Widgets rhs) {

// Поле lastAccessed игнорируется

}

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

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