emplace_hint performance when hint is wrong

  • A+
Category:Languages

I am trying to determine if emplace_hint should be used to insert a key into a multimap (as opposed to regular emplace). I have already calculated the range of the key in an earlier operation (on the same key):

range = multimap.equal_range(key);  

Should I use range.first, range.second, or nothing as a hint to insert the key, value pair? What if the range is empty?

 


Should I use range.first, range.second, or nothing as a hint to insert the key, value pair?

As std::multimap::emplace_hint() states:

Inserts a new element into the container as close as possible to the position just before hint.

(emphasis is mine) you should use second iterator from range and it should make insertion more efficient:

Complexity

Logarithmic in the size of the container in general, but amortized constant if the new element is inserted just before hint.

as for empty range, it is still fine to use second iterator as it should always point to greater than element or behind the last if not such one exists.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: