Обновление реализовано весьма прямолинейно. С созданием дело обстоит поинтереснее, поскольку в нем используется «рекомендательная» форма
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.
Хэшированные контейнеры относятся к категории ассоциативных, поэтому им, как и всем остальным ассоциативным контейнерам, при объявлении следует задать тип объектов, хранящихся в контейнере, функцию сравнения для этих объектов и распределитель памяти. Кроме того, для работы хэшированному контейнеру необходима хэш-функция. Естественно предположить, что объявление хэшированного контейнера должно выглядеть примерно так:
Полученное объявление весьма близко к объявлению хэшированных контейнеров в реализации 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 выглядит следующим образом: