Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

STL map insertion efficiency: [] vs. insert

There are two ways of map insertion:

m[key] = val;

Or

m.insert(make_pair(key, val));

My question is, which operation is faster? People usually say the first one is slower, because the STL Standard at first 'insert' a default element if 'key' is not existing in map and then assign 'val' to the default element.

But I don't see the second way is better because of 'make_pair'. make_pair actually is a convenient way to make 'pair' compared to pair<T1, T2>(key, val). Anyway, both of them do two assignments, one is assigning 'key' to 'pair.first' and two is assigning 'val' to 'pair.second'. After pair is made, map inserts the element initialized by 'pair.second'.

So the first way is 1. 'default construct of typeof(val)' 2. assignment the second way is 1. assignment 2. 'copy construct of typeof(val)'

like image 592
DerekFOol Avatar asked Apr 17 '11 07:04

DerekFOol


People also ask

What does insert map mean?

An inset map is a smaller map inset within a larger map. Inset maps serve multiple purposes, including to: Provide an overview of the main map. Inset maps can show the location of the main map in the context of a larger area. Show more detail of a portion of the main map.

What does std::map insert return?

std::map::insert succeeds when it inserts the new element, otherwise it returns an iterator to an already existing element.

How do you assign a value to a map in C++?

map insert() in C++ STL. The map::insert() is a built-in function in C++ STL which is used to insert elements with a particular key in the map container. Parameters: The function accepts a pair that consists of a key and element which is to be inserted into the map container.


1 Answers

Both accomplish different things.

m[key] = val;

Will insert a new key-value pair if the key doesn't exist already, or it will overwrite the old value mapped to the key if it already exists.

m.insert(make_pair(key, val));

Will only insert the pair if key doesn't exist yet, it will never overwrite the old value. So, choose accordingly to what you want to accomplish.
For the question what is more efficient: profile. :P Probably the first way I'd say though. The assignment (aka copy) is the case for both ways, so the only difference lies in construction. As we all know and should implement, a default construction should basically be a no-op, and thus be very efficient. A copy is exactly that - a copy. So in way one we get a "no-op" and a copy, and in way two we get two copies.
Edit: In the end, trust what your profiling tells you. My analysis was off like @Matthieu mentions in his comment, but that was my guessing. :)


Then, we have C++0x coming, and the double-copy on the second way will be naught, as the pair can simply be moved now. So in the end, I think it falls back on my first point: Use the right way to accomplish the thing you want to do.

like image 136
Xeo Avatar answered Sep 19 '22 07:09

Xeo