c++ - Fast insertion of values into a map with an increasing integer as the key? -

efficiency of map::insert(iterator position, const value& k) can dramatically improved providing appropriate value in parameter position.

if use integer numbers key, , every insertion done number larger inserted keys, can speed ::insert operation when giving ::end() iterator of map?

something like:

mymap.insert( mymap.end() , make_pair( next_number , myvalue ) ); 

where mymap of type map<uint64_t,mytype> , next_number every incrementing large integer.

edit:

the answer question might differ depending on whether data stored in map dense or not (see discussion below). so, lets ask question in both ways: once it's dense once it's not. still curious. perhaps measuring answer it.

to directly answer question asked, c++ specs that:

• in c++03, insertion map a.insert(p,t) must amortized constant complexity (rather logarithmic) if t inserted right after p.
• in c++11, insertion map a.insert(p,t) must amortized constant complexity if t inserted right before p.

and in neither case p need dereferenceable. therefore, in case, a.end() best hint in c++11, not in c++03.