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

будут вызваны конструктор и деструктор 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, встречавшееся в примерах:
map m; // См. ранее
Также вспомним, что Widget допускает присваивание значений типа double:
class Widget { // См. ранее
public:
 Widget& operator=(double weight);
};
Теперь рассмотрим следующий вызов efficientAddOrUpdate:
effcientAddOrUpdate(m, 10, 15);
Допустим, выполняется операция обновления, то есть m уже содержит элемент с ключом 10. В этом случае приведенный ранее шаблон заключает, что ValueArgType является double, и в теле функции число 1.5 в формате double напрямую присваивается объекту Widget, ассоциированному с ключом 10. Присваивание осуществляется вызовом Widget::operator=(double). Если бы третий параметр efficientAddOrUpdate относился к типу МарТуре::mapped_type, то число 1.5 в момент вызова было бы преобразовано в Widget, что привело бы к лишним затратам на конструирование (и последующее уничтожение) объекта Widget.
Сколь бы интересными не были тонкости реализации