Обновление реализовано весьма прямолинейно. С созданием дело обстоит поинтереснее, поскольку в нем используется «рекомендательная» форма insert. Конструкция m.insert(lb.MVT(k, v)) «рекомендует» lb как правильную точку вставки для нового элемента с ключом, эквивалентным к, а Стандарт гарантирует, что в случае правильности рекомендации вставка будет выполнена за постоянное время (вместо логарифмического). В efficentAddOrUpdate мы знаем, что lb определяет правильную позицию вставки, поэтому insert всегда выполняется с постоянным временем.
У данной реализации есть одна интересная особенность — KeyArgType и ValueArgType не обязаны быть типами, хранящимися в контейнере, а всего лишь должны приводиться к этим типам. Существует и другое возможное решение — удалить параметры-типы KeyArgType/ValueArgType и заменить их на
МарТуре::key_type
и МарТуре::mapped_type
. Но в этом случае вызов может сопровождаться лишними преобразованиями типов. Возьмем определение контейнера map, встречавшееся в примерах:map m;// См. ранее
Также вспомним, что Widget допускает присваивание значений типа double:
class Widget {//См. ранее
public:
Widget& operator=(double weight);
};
Теперь рассмотрим следующий вызов efficientAddOrllpdate:
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 у большинства программистов неизбежно возникает вопрос: «Векторы, списки, множества... хорошо, но где же хэш-таблицы?» Действительно, хэш-таблицы не входят в стандартную библиотеку С++. Все сходятся на том, что это досадное упущение, но Комитет по стандартизации С++ решил, что усилия, затраченные на их поддержку, привели бы к чрезмерной задержке в работе над стандартом. По всей вероятности, хэш-таблицы появятся в следующей версии Стандарта, но в настоящий момент хеширование не поддерживается в STL.
Программисты, не печальтесь! Вам не придется обходиться без хэш-таблиц или создавать собственные реализации. Существует немало готовых STL-совместимых хэшированных ассоциативных контейнеров с вполне стандартными именами: hash_set, hash_multiset, hash_map и hash_multimap.
Реализации, скрытые за похожими именами... мягко говоря, не похожи друг на друга. Различается все: интерфейсы, возможности, структуры данных и относительная эффективность поддерживаемых операций, Можно написать более или менее переносимый код, использующий хэш-таблицы, но стандартизация хэшированных контейнеров значительно упростила бы эту задачу (теперь понятно, почему стандарты так важны),
Из всех существующих реализаций хэшированных контейнеров наибольшее распространение получили две: от SGI (совет 50) и от Dinkumware (приложение Б), поэтому дальнейшее описание ограничивается устройством хешированных контейнеров от этих разработчиков. STLport (совет 50) также содержит хэшированные контейнеры, но они базируются на реализации SGI. В контексте настоящего примера все сказанное о хэшированных контейнерах SGI относится и к хэшированным контейнерам STLport.
Хэшированные контейнеры относятся к категории ассоциативных, поэтому им, как и всем остальным ассоциативным контейнерам, при объявлении следует задать тип объектов, хранящихся в контейнере, функцию сравнения для этих объектов и распределитель памяти. Кроме того, для работы хэшированному контейнеру необходима хэш-функция. Естественно предположить, что объявление хэшированного контейнера должно выглядеть примерно так:
template
typename HashFunction,
typename CompareFunction,
typename Allocator = allocator>
class hash_контейнер;
Полученное объявление весьма близко к объявлению хэшированных контейнеров в реализации SGI. Главное различие между ними заключается в том, что в реализации SGI для типов HashFunction и CompareFunction предусмотрены значения по умолчанию. Объявление hash_set в реализации SGI выглядит следующим образом (слегка исправлено для удобства чтения):
template
typename HashFunction = hash,
typename CompareFunction = equal_to,
typename Allocator = allocator>
class hash_set;
В реализации SGI следует обратить внимание на использование equal_to в качестве функции сравнения по умолчанию. В этом она отличается от стандартных ассоциативных контейнеров, где по умолчанию используется функция сравнения less. Смысл этого изменения не сводится к простой замене функции. Хэшированные контейнеры SGI сравнивают два объекта, проверяя их равенство, а неэквивалентность (см. совет 19), Для хэшированных контейнеров такое решение вполне разумно, поскольку в хэшированных ассоциативных контейнерах, в отличие от их стандартных аналогов (обычно построенных на базе деревьев), элементы не хранятся в отсортированном порядке.
В реализации Dinkumware принят несколько иной подход. Она также позволяет задать тип объектов, хэш-функцию, функцию сравнения и распределитель, но хэш-функция и функция сравнения по умолчанию перемещены в отдельный класс hash_compare, который передается по умолчанию в параметре HashingInfo шаблона контейнера.
Например, объявление hash_set (также отформатированное для наглядности) в реализации Dinkumware выглядит следующим образом:
template
class hash_compare;
template
typename Hashinglnfo = hash_compare>,
typename Allocator = allocator>
class hash_set;
В этом интерфейсе внимание стоит обратить на использование параметра HashingInfo, содержащего функции хэширования и сравнения, а также перечисляемые типы, управляющие минимальным количеством гнезд в таблице и максимальным допустимым отношением числа элементов контейнера к числу гнезд. В случае превышения пороговой величины количество гнезд в таблице увеличивается, а некоторые элементы в таблице хэшируются заново (в реализации SGI предусмотрены функции, обеспечивающие аналогичные возможности управления количеством гнезд в таблице).
После небольшого форматирования объявление hash_compare (значение по умолчанию для HashingInfo) выглядит примерно так:
template>
class hash_compare{
public:
enum{
bucket_size = 4. // Максимальное отношение числа элементов к числу гнезд
min_buckets = 8 // Минимальное количество гнезд
}
size_t operator()(const Т&) const; // Хэш-функция
bool operator() (const T&,
const T&) const;
// Некоторые подробности опущены,
// включая использование CompareFunction
};
Перегрузка operator() (в данном случае для реализации функций хэширования и сравнения) используется гораздо чаще, чем можно представить. Другое применение этой концепции продемонстрировано в совете 23.
Реализация Dinkumware позволяет программисту написать собственный касс-аналог hash_compare (возможно, объявленный производным от hash_compare). Если этот класс будет определять bucket_size, min_buckets, две функции operator() (с одним и с двумя аргументами) и еще несколько мелочей, не упомянутых выше, он может использоваться для управления конфигурацией и поведением контейнеров Dinkumware hash_set и hash_multiset. Управление конфигурацией hash_mnap и hash_ multimap осуществляется аналогичным образом.