Скотт Мейерс - Эффективное использование STL

m[k] = v; // Значение, ассоциируемое

// с ключом k, заменяется на v при помощи оператора []

m.insert(intWidgetMap::value_type(k, v)).first->second = v; // Значение, ассоциируемое

// с ключом k, заменяется

// на v при помощи insert

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

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

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

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

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

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

// pair(k, v) в m; в противном случае

// выполнить эффективное обновление

// значения, ассоциированного с ключом k.

// Функция возвращает итератор

// для добавленной или измененной пары

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

template

typename KeyArgType, // Причины для передачи параметров-типов

typename ValueArgType> // KeyArgType и ValueArgType

// приведены ниже

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, встречавшееся в примерах: