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

Мейерс Скотт

Обновление реализовано весьма прямолинейно. С созданием дело обстоит поинтереснее, поскольку в нем используется «рекомендательная» форма

insert

. Конструкция

m.insert(lb.MVT(k, v))

«рекомендует»

lb

как правильную точку вставки для нового элемента с ключом, эквивалентным

k

, а Стандарт гарантирует, что в случае правильности рекомендации вставка будет выполнена за постоянное время (вместо логарифмического). В

efficentAddOrUpdate

мы знаем, что

lb

определяет правильную позицию вставки, поэтому

insert

всегда выполняется с постоянным временем.

У данной

реализации есть одна интересная особенность —

KeyArgType

и

ValueArgType

не обязаны быть типами, хранящимися в контейнере, а всего лишь должны приводитьсяк этим типам. Существует и другое возможное решение — удалить параметры-типы

KeyArgType/ValueArgType

и заменить их на

МарТуре::key_type

и

МарТуре::mapped_type

. Но в этом случае вызов может сопровождаться лишними преобразованиями типов. Возьмем определение контейнера

map

, встречавшееся в примерах:

map<int, Widget> m; // См. ранее

Также вспомним, что Widget допускает присваивание значений типа

double

:

class Widget { // См. ранее

public:

 Widget& operator=(double weight);

};

Теперь рассмотрим следующий вызов

efficientAddOrUpdate

:

effcientAddOrUpdate(m, 10, 15);

Допустим, выполняется операция обновления, то есть

m

уже содержит элемент с ключом 10. В этом случае приведенный ранее шаблон заключает, что

ValueArgType

является

double

, и в теле функции число 1.5 в формате

double

напрямую присваивается объекту

Widget

, ассоциированному с ключом 10. Присваивание осуществляется вызовом

Widget::operator=(double)

. Если бы третий параметр

efficientAddOrUpdate

относился к типу

МарТуре::mapped_type

, то число 1.5 в момент вызова было бы преобразовано в

Widget

, что привело бы к лишним затратам на конструирование (и последующее уничтожение) объекта

Widget

.

Сколь бы интересными не были тонкости реализации

efficientAddOrUpdate

, не будем отклоняться от главной темы этого совета — от необходимости тщательного выбора между

map::operator[]

и

map::insert

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

map

рекомендуется использовать оператор

[]

, но при создании нового элемента предпочтение отдается

insert

.

Совет 25. Изучите нестандартные хэшированные контейнеры

После первого знакомства с STL у большинства программистов неизбежно возникает вопрос: «Векторы, списки, множества… хорошо, но где же хэш-таблицы?» Действительно, хэш-таблицы не входят в стандартную библиотеку C++. Все сходятся на том, что это досадное упущение, но Комитет по стандартизации C++ решил, что усилия, затраченные на их поддержку, привели бы к чрезмерной задержке в работе над стандартом. По всей вероятности, хэш-таблицы появятся в следующей версии Стандарта, но в настоящий момент хеширование не поддерживается в STL.

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

hash_set

,

hash_multiset

,

hash_map

и

hash_multimap

.

Реализации, скрытые за похожими именами… мягко говоря, не похожи друг на друга. Различается все: интерфейсы, возможности, структуры данных и относительная эффективность поддерживаемых операций, Можно написать более или менее переносимый код, использующий хэш-таблицы, но стандартизация хэшированных контейнеров значительно упростила бы эту задачу (теперь понятно, почему стандарты так важны),

Из всех существующих реализаций хэшированных контейнеров наибольшее распространение получили две: от SGI (совет 50) и от Dinkumware (приложение Б), поэтому дальнейшее описание ограничивается устройством хешированных контейнеров от этих разработчиков. STLport (совет 50) также содержит хэшированные контейнеры, но они базируются на реализации SGI. В контексте настоящего примера все сказанное о хэшированных контейнерах SGI относится и к хэшированным контейнерам STLport.

Хэшированные контейнеры относятся к категории ассоциативных, поэтому им, как и всем остальным ассоциативным контейнерам, при объявлении следует задать тип объектов, хранящихся в контейнере, функцию сравнения для этих объектов и распределитель памяти. Кроме того, для работы хэшированному контейнеру необходима хэш-функция. Естественно предположить, что объявление хэшированного контейнера должно выглядеть примерно так:

template<typename T, typename HashFunction, typename CompareFunction,

 typename Allocator = allocator<T> >

class hash_контейнер;

Полученное объявление весьма близко к объявлению хэшированных контейнеров в реализации SGI. Главное различие между ними заключается в том, что в реализации SGI для типов

HashFunction

и

CompareFunction

предусмотрены значения по умолчанию. Объявление

hash_set

в реализации SGI выглядит следующим образом (слегка исправлено для удобства чтения):

template<typename T,

 typename HashFunction = hash<T>,

 typename CompareFunction = equal_to<T>,

 typename Allocator = allocator<T> >

class hash_set;

В реализации SGI следует обратить внимание на использование

equal_to

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

less

. Смысл этого изменения не сводится к простой замене функции. Хэшированные контейнеры SGI сравнивают два объекта, проверяя их равенство, а неэквивалентность (см. совет 19), Для хэшированных контейнеров такое решение вполне разумно, поскольку в хэшированных ассоциативных контейнерах, в отличие от их стандартных аналогов (обычно построенных на базе деревьев), элементы не хранятся в отсортированном порядке.

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

hash_compare

, который передается по умолчанию в параметре

HashingInfo

шаблона контейнера.

Например, объявление

hash_set

(также отформатированное для наглядности) в реализации Dinkumware выглядит следующим образом:

template<typename T, typename CompareFunction>