Скотт Мейерс - Эффективное использование STL
Конечно, нам хотелось бы видеть в STL функцию, которая бы автоматически выбирала оптимальное решение в синтаксически привлекательном виде. Интерфейс вызова мог бы выглядеть следующим образом:
iterator affectedPair =// Если ключ к отсутствует в контейнере m.
efficentAddOrUpdate(m,k,v); // выполнить эффективное добавление
// pair(k.v) в m: в противном случае
// выполнить эффективное обновление
// значения, ассоциированного с ключом к.
// Функция возвращает итератор
// для добавленной или измененной пары
В STL такая функция отсутствует, но как видно из следующего фрагмента, ее нетрудно написать самостоятельно. В комментариях даются краткие пояснения, а дополнительная информация приведена после листинга.
template<typename МарТуре,// Тип контейнера
typename KeyArgType, // Причины для передачи параметров-типов typename ValueArgType> // KeyArgType и ValueArgType
// приведены ниже
typename МарТуре::iterator
efficientAddOrUpdate(MapType& m.
const KeyArgType& k.
const ValueArgType& v)
{
typename МарТуре:iterator lb = // Определить, где находится
// или должен находиться ключ к.
m.lower_bound(k);// Ключевое слово typename
// рассматривается на с. 20
if (lb!=m.end())&& !(m.key_comp()(k.lb->first))){ // Если lb ссылается на пару.
// ключ которой эквивалентен к
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::кеуcomp. В результате проверки эквивалентности мы узнаем, какая операция выполняется — создание или обновление.
Обновление реализовано весьма прямолинейно. С созданием дело обстоит поинтереснее, поскольку в нем используется «рекомендательная» форма insert. Конструкция m.insert(lb.MVT(k, v)) «рекомендует» lb как правильную точку вставки для нового элемента с ключом, эквивалентным к, а Стандарт гарантирует, что в случае правильности рекомендации вставка будет выполнена за постоянное время (вместо логарифмического). В 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);
};
Теперь рассмотрим следующий вызов 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 Т,
typename HashFunction,
typename CompareFunction,
typename Allocator = allocator<T> >
class hash_контейнер;
Полученное объявление весьма близко к объявлению хэшированных контейнеров в реализации SGI. Главное различие между ними заключается в том, что в реализации SGI для типов HashFunction и CompareFunction предусмотрены значения по умолчанию. Объявление hash_set в реализации SGI выглядит следующим образом (слегка исправлено для удобства чтения):
template<typename Т,
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 Т,typename CompareFunction>
class hash_compare;
template<typename T,
typename Hashinglnfo = hash_compare<T,less<T>>,
typename Allocator = allocator<T>>
class hash_set;
В этом интерфейсе внимание стоит обратить на использование параметра HashingInfo, содержащего функции хэширования и сравнения, а также перечисляемые типы, управляющие минимальным количеством гнезд в таблице и максимальным допустимым отношением числа элементов контейнера к числу гнезд. В случае превышения пороговой величины количество гнезд в таблице увеличивается, а некоторые элементы в таблице хэшируются заново (в реализации SGI предусмотрены функции, обеспечивающие аналогичные возможности управления количеством гнезд в таблице).
