Теперь понятно, почему такой подход ухудшает быстродействие программы. Сначала мы конструируем объект Widget, а затем немедленно присваиваем ему новое значение. Конечно, правильнее было бы сразу сконструировать Widget с нужными данными вместо того, чтобы конструировать Widget по умолчанию и затем выполнять присваивание. Следовательно, вызов operator[] было бы правильнее заменить прямолинейным вызовом insert:

rn.insertCintWidgetMap: :value type(1.1.50)):

С функциональной точки зрения эта конструкция эквивалентна фрагменту, приведенному выше, но она позволяет сэкономить три вызова функций: создание временного объекта Widget конструктором по умолчанию, уничтожение этого временного объекта и оператор присваивания Widget. Чем дороже обходятся эти вызовы, тем большую экономию обеспечивает применение тар:: insert вместо тар::operator[].

В приведенном выше фрагменте используется определение типа value type, предоставляемое всеми стандартными контейнерами. Помните, что для тар и multimap (а также для нестандартных контейнеров hash map и hashmul timap - совет 25) тип элемента всегда представляет собой некую разновидность pair.

Я уже упоминал о том, что operator[] упрощает операции обновления с возможным созданием . Теперь мы знаем, что при создании insert работает эффективнее, чем operator []. При обновлении, то есть при наличии эквивалентного ключа (см. совет 19) в контейнере тар, ситуация полностью меняется. Чтобы понять, почему это происходит, рассмотрим потенциальные варианты обновления:

П1[к] = V: Значение, ассоциируемое

с ключом к.заменяется на V при помощи оператора []

m.insertCintWidgetMap::value type(k,v)).first->second = v: Значение, ассоциируемое

сключом к. заменяется на V при помощи insert

Вероятно, один внешний вид этих команд заставит вас выбрать operator [], но в данном случае речь идет об эффективности, поэтому фактор наглядности не учитывается.

При вызове insert передается аргумент типа intWidgetMap: :value type (то есть pair<int.Widget>), поэтому при вызове insert необходимо сконструировать и уничтожить объект данного типа. Следовательно, при вызове insert будут вызваны конструктор и деструктор pair, что в свою очередь приведет к вызову конструктора и деструктора Widget, поскольку pair<int,Widget> содержит объект Widget. При вызове operator[] объект pair не используется, что позволяет избежать затрат на конструирование и уничтожение pair и Widget.

Следовательно, при вставке элемента в тар по соображениям эффективности желательно использовать insert вместо operator[], а при обновлении существующих элементов предпочтение отдается operator[], что объясняется как эффективностью, так и эстетическими соображениями.

Конечно, нам хотелось бы видеть в STL функцию, которая бы автоматически выбирала оптимальное решение в синтаксически привлекательном виде. Интерфейс вызова мог бы выглядеть следующим образом:

iterator affectedPair = Если ключ к отсутствует в контейнере т,

efficientAddOrUpdate(m.k.v); выполнить эффективное добавление

pairCk.v) в m: в противном случае выполнить эффективное обновление значения, ассоциированного с ключом к. Функция возвращает итератор для добавленной или измененной пары

В STL такая функция отсутствует, но как видно из следующего фрагмента, ее нетрудно написать самостоятельно. В комментариях даются краткие пояснения, а дополнительная информация приведена после листинга.

tempiate<typename МарТуре, Тип контейнера

typename КеуАгдТуре. Причины для передачи параметров-типов typename ValueArgType> КеуАгдТуре и ValueArgType приведены ниже

typename МарТуре::iterator efficientAddOrUpdate(MapType& m.

const KeyArgTypeS к.

const ValueArgTypeS 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.insertdb.MVTCk.v)); Включить pair(k,v) в m и вернуть

итератор для нового элемента

Для эффективного выполнения операций создания и обновления необходимо узнать, присутствует ли ключ к в контейнере; если присутствует - где он находится, а если нет - где он должен находиться. Задача идеально подходит для функции lower bound (совет 45). Чтобы определить, обнаружила ли функция lower bound элемент с нужным ключом, мы проверяем вторую половину условия эквивалентности (см. совет 19). При этом сравнение должно производиться функцией, полученной при вызове тар: :кеусотр. В результате проверки эквивалентности мы узнаем, какая операция выполняется - создание или обновление.

Обновление реализовано весьма прямолинейно. С созданием дело обстоит поинтереснее, поскольку в нем используется рекомендательная форма insert. Конструкция m.inserdb.MVTCk, V)) рекомендует lb как правильную точку вставки для нового элемента с ключом, эквивалентным к, а Стандарт гарантирует, что в случае правильности рекомендации вставка будет выполнена за постоянное время (вместо логарифмического). В efficientAddOrUpdate мы знаем, что lb определяет правильную позицию вставки, поэтому i nsert всегда выполняется с постоянным временем.

У данной реализации есть одна интересная особенность - КеуАгдТуре и Val ueArgType не обязаны быть типами, хранящимися в контейнере, а всего лишь должны приводиться к этим типам. Существует и другое возможное решение - удалить параметры-типы KeyArgType/Val ueArgType и заменить их на МарТуре:: keytype и МарТуре:: mappecl type. Но в этом случае вызов может сопровождаться лишними преобразованиями типов. Возьмем определение контейнера тар, встречавшееся в примерах:

map<int,Widget> m; См. ранее

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

class Widget { См. ранее

public:

Widgets operator=(double weight): }:

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

efficientAddOrUpdate(m.l0.15):

Допустим, выполняется операция обновления, то есть m уже содержит элемент с ключом 10. В этом случае приведенный ранее шаблон заключает, что Val ueArgType является doubl е, и в теле функции число 1.5 в формате doubl е напрямую присваивается объекту Widget, ассоциированному с ключом 10. Присваивание осуществляется вызовом Widget: :operator=(double). Если бы третий параметр efficientAddOrUpdate относился к типу МарТуре::mapped type, то число 1.5 в момент вызова было бы преобразовано в Widget, что привело бы к лишним затратам на конструирование (и последующее уничтожение) объекта Widget.

Сколь бы интересными не были тонкости реализации efficientAddOrUpdate, не будем отклоняться от главной темы этого совета - от необходимости тщательного выбора между тар: :operator[] и тар::insert в тех случаях, когда важна эффективность выполняемых операций. При обновлении существующего элемента тар рекомендуется использовать оператор [ ], но при создании нового элемента предпочтение отдается insert.

Совет 25. Изучите нестандартные хэшированные контейнеры

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

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