Fast insertion of values into a map with an increasing integer as the key?
c++, dictionary
Solution
To directly answer the question asked, the C++ specs say that:
- In C++03, insertion into a map with `a.insert(p,t)` must be amortized constant complexity (rather than logarithmic) if `t` is inserted right after `p`.
- In C++11, insertion into a map with `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.
Problem
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.