How do I create an inserter iterator for unhinted insertion into std::map? -- Raymond Chen

The C++ standard library provides various inserters like back_inserter, front_inserter, and inserter, but for associative containers like std::map, only inserter is available, requiring a hint. However, if elements arrive in an unpredictable order, providing a hint could be inefficient, so a custom inserter that performs unhinted insertion can be a useful alternative.

How do I create an inserter iterator that does unhinted insertion into an associative container like std::map? 

by Raymond Chen

From the article:

The C++ standard library contains various types of inserters:

• back_inserter(c) which uses c.push_back(v).
• front_inserter(c) which uses c.push_front(v).
• inserter(c, it) which uses c.insert(it, v).

C++ standard library associative containers do not have push_back or push_front methods; your only option is to use the inserter. But we also learned that the hinted insertion can speed up the operation if the hint is correct, or slow it down if the hint is wrong. (Or it might not have any effect at all.)

What if you know that the items are arriving in an unpredictable order? You don’t want to provide a hint, because that’s a pessimization. The inserter requires you to pass a hint. What do you do if you don’t want to provide a hint?

View the full article