Совет 24. Тщательно выбирайте между map::operator[] и map::insert
Допустим, у нас имеется класс Widget с конструктором по умолчанию, а также конструктором и оператором присваивания с операндом типа double:
class Widget {
public:
Widget();
Widget(double weight);
Widget& operator=(double weight);
};
Предположим, мы хотим создать контейнер map, ассоциирующий int с Widget, и инициализировать созданное множество конкретными значениями. Все выглядит очень просто:
map m;
m[1]=1.50;
m[2]=3.67;
m[3]=10.5;
m[4]=45.8;
m[5]=0.0003;
Настолько просто, что легко упустить, что же здесь, собственно, происходит. А это очень плохо, потому что в действительности происходящее может заметно ухудшить быстродействие программы.
Функция operator[] контейнеров map никак не связана с функциями operator[] контейнеров vector, deque и string, а также со встроенным оператором [ ], работающим с массивами. Функция
map::operator[]
упрощает операции «обновления с возможным созданием». Иначе говоря, при наличии объявления map m команда m[k]=v; проверяет, присутствует и ключ к в контейнере. Если ключ отсутствует, он добавляется вместе с ассоциированным значением v. Если ключ уже присутствует, ассоциированное с ним значение заменяется на v.Для этого operator [] возвращает ссылку на объект значения, ассоциированного с ключом к, после чего v присваивается объекту, к которому относится эта ссылка. При обновлении значения, ассоциированного с существующим ключом, никаких затруднений не возникает — в контейнере уже имеется объект, ссылка на который возвращается функцией operator[]. Но при отсутствии ключа к готового объекта, на который можно было бы вернуть ссылку, не существует. В этом случае объект создается конструктором по умолчанию, после чего operator [] возвращает ссылку на созданный объект.
Вернемся к началу исходного примера:
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. В результате проверки эквивалентности мы узнаем, какая операция выполняется — создание или обновление.