Efficiency of the map::insert(iterator position, const value& k)
can be dramatically improved by providing the appropriate value in parameter position.
If I use integer numbers as the key, and every insertion is done with a number larger than all previously inserted keys, can I speed up the ::insert
operation when giving the ::end()
iterator of the map?
Something like:
myMap.insert( myMap.end() , make_pair( next_number , myValue ) );
where myMap
is of type map<uint64_t,MyType>
and next_number
is an every incrementing large integer.
Edit:
The answer to this question might differ depending on whether the data stored in the map
is dense or not (see discussion below). So, lets ask the question in both ways: Once it's dense once it's not. Still curious. Perhaps measuring will answer it.
To directly answer the question asked, the C++ specs say that:
a.insert(p,t)
must be amortized constant complexity (rather than logarithmic) if t
is inserted right after p
. a.insert(p,t)
must be amortized constant complexity if t
is inserted right before p
.and in neither case does p
need to be dereferenceable. Therefore, in your case, a.end()
is likely to be the best hint in C++11, but not in C++03.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With