What is the use of emplace_hint on a map?

Question

I understand that map :: emplace_hint is used to place a pair of keys, values ​​at a specified location on the map, but in the end the map is sorted so what is its placement point at a specific location? 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; } 

he 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 card only if the key is not already specified. Of course, you can just call insert , but suppose the operation is expensive or irreversible (for example, moving from an object that cannot be copied).

In this situation, you need to separate the search from the insert. Where the hint appears, combined 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 an iterator where the key would be if it were on the map, regardless of whether it is really there. The time complexity of the intended insert is constant if the prompt is correct.

It makes no sense to use the intended insert with the wrong iterator (i.e. the one that was not obtained as the lower bound for the given key).

Note that the intended insertion only works for ordered associative containers. Unordered containers also offer these overloads, but they do not work, since there is no way to get useful advice for unordered containers.

Answer 2

I understand that map :: emplace_hint is used to place a pair of keys, values ​​in a specific place on the map

No, it is not.

As you say, you cannot independently control the position of the elements. The map decides that.

This hint should tell the compiler where, in your opinion, the card decides to place it, so the card does not need to spend so much time to understand what is for itself.

For example, if you already know (because it is your program!) That some new element will definitely end with the "start" of the card, you can transfer this knowledge to the container. Then you just need to verify that you are right, instead of scanning the entire tree, in order to ultimately come to this conclusion.

If your hint is incorrect, it does not change anything when the item ends, but you give the map more work.