What is the use of emplace_hint in map?

Question

I understand that map::emplace_hint is used to place a key,value pair at a specified place in the map but in the end the map gets sorted so what is the point of placing it in a certain place? for example, when i ran this code :

#include <iostream> #include <map> #include <unordered_map>  int main() {     std::map<char, int> mymap;     auto it = mymap.end();     std::unordered_map<char, int> mymap2;       it = mymap.emplace_hint(it, 'b', 10);     mymap.emplace_hint(it, 'z', 12);     mymap.emplace_hint(mymap.end(), 'a', 14);     mymap.emplace_hint(mymap.end(), 'c', 10);      auto it2 = mymap2.end();     it2 = mymap2.emplace_hint(it2, 'b', 10);     mymap2.emplace_hint(it2, 'z', 12);     mymap2.emplace_hint(mymap2.end(), 'a', 14);     mymap2.emplace_hint(mymap2.end(), 'c', 10);       std::cout << "mymap contains:";     for (auto& x : mymap)         std::cout << " [" << x.first << ':' << x.second << ']';     std::cout << '\n';      for(auto& y :mymap2)         std::cout << " [" << y.first << ':' << y.second << ']';     char c;     std::cin >> c;     return 0; } 

it gave me this o/p :

mymap contains: [a:14] [b:10] [c:10] [z:12]  [z:12] [b:10] [a:14] [c:10] 

Answer 1

Suppose you want to insert an element into a map only if the key isn't present yet. You could of course just call insert, but suppose further that the operation is expensive or irreversible (e.g. moving from a non-copyable object).

In that situation, you need to separate the lookup from the insertion. That's where the hint comes in, in conjunction with lower_bound:

auto it = m.lower_bound(key);  if (it != m.end() && it->first == key) {   // key already exists } else {   m.insert(it, std::make_pair(key, compute_expensively()));   // or:   m.emplace_hint(it, key, compute_expensively()); } 

The trick is that lower_bound returns the iterator where the key would be if it were in the map, regardless of whether it actually is there. The time complexity of the hinted insertion is constant if the hint is correct.

There's no point using the hinted insertion with an incorrect iterator (i.e. one that wasn't obtained as the lower bound for the given key).

Note that hinted insertion only works for ordered associative containers. The unordered containers also offer those overloads, but they have no effect, since there is no way to obtain a useful hint for unordered containers.