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

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

на обложку

Мейерс Скотт

Шрифт:

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; // Значение, ассоциируемое

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

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

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

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

Вероятно, один внешний вид этих команд заставит вас выбрать

operator[]

, но в данном случае речь идет об эффективности, поэтому фактор наглядности не учитывается.

При вызове

insert

передается аргумент типа

inWidgetMap::value_type

(то есть

pair<int, Widget>

), потому при вызове

insert

необходимо сконструировать и уничтожить объект данного типа. Следовательно, при вызове

insert

будут вызваны конструктор и деструктор

pair

, что в свою очередь приведет к вызову конструктора и деструктора

Widget

, поскольку

pair<int, Widget>

содержит объект

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 МарТуре, // Тип контейнера

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

. В результате проверки эквивалентности мы узнаем, какая операция выполняется — создание или обновление.