typename МарТуре::iterator efficientAddOrUpdate(MapType& m,
const KeyArgType& k, const ValueArgType& v) {
typename МарТуре:iterator lb = // Определить, где находится
// или должен находиться ключ k.
m.lower_bound(k); // Ключевое слово typename
// рассматривается на с. 20
if (lb != m.end)&& !(m.key_comp(k.lb->first))){ // Если lb ссылается на пару,
// ключ которой эквивалентен k,
lb->second = v; // …обновить
ассоциируемое значение
return lb; // и вернуть итератор для найденной пары
} else {
typedef typename МарТуре::value_type MVT;
return m.insert(lb.MVT(k, v)); // Включить pair(k, v) в m и вернуть
// итератор для нового элемента
}
}
Для эффективного выполнения операций создания и обновления необходимо узнать, присутствует ли ключ к в контейнере; если присутствует — где он находится, а если нет — где он должен находиться. Задача идеально подходит для функции
lower_bound
(совет 45). Чтобы определить, обнаружила ли функция
lower_bound
элемент с нужным ключом, мы проверяем вторую половину условия эквивалентности (см. совет 19). При этом сравнение должно производиться функцией, полученной при вызове
map::keycomp
. В результате проверки эквивалентности мы узнаем, какая операция выполняется — создание или обновление.
Обновление реализовано весьма прямолинейно. С созданием дело обстоит поинтереснее, поскольку в нем используется «рекомендательная» форма
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 выглядит следующим образом (слегка исправлено для удобства чтения):