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

(совет 45). Чтобы определить, обнаружила ли функция элемент с нужным ключом, мы проверяем вторую половину условия эквивалентности (см. совет 19). При этом сравнение должно производиться функцией, полученной при вызове . В результате проверки эквивалентности мы узнаем, какая операция выполняется — создание или обновление.

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

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

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

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

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

:

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

:

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

уже содержит элемент с ключом 10. В этом случае приведенный ранее шаблон заключает, что является , и в теле функции число 1.5 в формате напрямую присваивается объекту , ассоциированному с ключом 10. Присваивание осуществляется вызовом . Если бы третий параметр относился к типу , то число 1.5 в момент вызова было бы преобразовано в , что привело бы к лишним затратам на конструирование (и последующее уничтожение) объекта .

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

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

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

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

, , и .

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