Эффективное использование STL

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 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. Изучите нестандартные хэшированные контейнеры