std::map insert or std::map find?

Question

Assuming a map where you want to preserve existing entries. 20% of the time, the entry you are inserting is new data. Is there an advantage to doing std::map::find then std::map::insert using that returned iterator? Or is it quicker to attempt the insert and then act based on whether or not the iterator indicates the record was or was not inserted?

Answer 1

There will be barely any difference in speed between the 2, find will return an iterator, insert does the same and will search the map anyway to determine if the entry already exists.

So.. its down to personal preference. I always try insert and then update if necessary, but some people don't like handling the pair that is returned.

Answer 2

If you are concerned about efficiency, you may want to check out hash_map<>.

Typically map<> is implemented as a binary tree. Depending on your needs, a hash_map may be more efficient.

Answer 3

I don't seem to have enough points to leave a comment, but the ticked answer seems to be long winded to me - when you consider that insert returns the iterator anyway, why go searching lower_bound, when you can just use the iterator returned. Strange.