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

Вернемся к началу исходного примера:

map m;

m[1]=1.50;

Выражение m[1] представляет собой сокращенную запись для m.operator[](1), поэтому во второй строке присутствует вызов map:: operator[]. Функция должна вернуть ссылку на ассоциированный объект Widget. В данном примере m еще не содержит ни одного элемента, поэтому элемент с ключом 1 не существует. Конструктор по умолчанию создает объект Widget, ассоциируемый с ключом 1, и возвращает ссылку на этот объект. Наконец, созданному объекту Widget присваивается значение 1.50.

Иначе говоря, команда

m[1]=1.50:

функционально эквивалентна следующему фрагменту:

typedef map intWidgetMap: // Вспомогательное определение типа

pair result =//'Создание нового

m.insert(intWidgetMap::value_type(1,Widget())); // элемента с ключом 1

// и ассоциированным объектом, созданным

// конструктором по умолчанию; комментарии

// по поводу value_type // приведены далее

result.first->second = 1.50;// Присваивание значения

// созданному объекту

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

m.insert(intWidgetMap::value_type(1,1.50));

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

В приведенном выше фрагменте используется определение типа value_type, предоставляемое всеми стандартными контейнерами. Помните, что для map и multimap (а также для нестандартных контейнеров hash_map и hash_multimap — совет 25) тип элемента всегда представляет собой некую разновидность pair.

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

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

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

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

// с ключом к, заменяется на 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: в противном случае

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

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

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

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

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

template

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