6

On cppreference about map::emplace_hint():

template <class... Args>
iterator emplace_hint( const_iterator hint, Args&&... args );

Inserts a new element to the container, using hint as a suggestion where the element should go.

So if it is a suggestion does that mean that the implementation doesn't have to place the element there? What exactly is a hint?

5
  • 1
    Doesn't matter, every implementation I know of ignores it 100% Oct 28, 2014 at 23:32
  • @MooingDuck I know libstdc++ checks the positions before hand and if it can it uses it. Otherwise it just does a regular insert.
    – Rapptz
    Oct 29, 2014 at 0:03
  • @MooingDuck: libc++ does the same thing as libstdc++.
    – rici
    Oct 29, 2014 at 0:16
  • Oh, maybe I was thinking of allocate. Oct 29, 2014 at 0:25
  • Suppose you wan't to insert a list of sorted elements to the map. You can use the position of the previously inserted element to hint the container where the next element would be instead of searching again from the root
    – balki
    Dec 4, 2014 at 6:52

3 Answers 3

11

cppreference is not accurate about map::emplace_hint(). However it should be excused for being so, as at one point prior to C++11, the draft explicitly granted permission for the implementation to ignore the hint:

From N3225, Table 102:

... Implementations are permitted to ignore the hint.

Fortunately this was corrected by LWG 1253 and in C++11 and forward reads:

... The element is inserted as close as possible to the position just prior to p.

logarithmic in general, but amortized constant if the element is inserted right before p

So the "hint" has teeth now. It shall be respected. Though note, these comments only apply to the associative containers (map, multimap, set, multiset).

In C++98/03 the "hint" was improperly used for insert. But that was corrected by N1780, and that wording was subsequently adopted for emplace_hint.

Implementations continue to be permitted to ignore the hint for the unordered containers. And this is for good reason. There is no good implementation strategy for taking advantage of the hint for the unordered containers. The hint is there just to provide compatibility with the associative containers in container-generic code.

Update

Somewhere over the years cppreference has updated its documentation and is now correct:

Inserts a new element to the container as close as possible to the position just before hint.

0
10

Normally, insertions into a tree-based map (like std::map) requires a O(log n) lookup to find the correct insertion point. If the correct insertion point is adjacent to your provided hint, you can save the O(log n) lookup and the operation is O(1) instead.

The usual use case for this is for inserting an item when no existing item for the given key exists. Then, rather than using .find() (which returns .end() if the item is not found), you use .lower_bound() to find the existing key (which returns an iterator to the insertion point, if the key isn't found). Then if the key doesn't exist, you use that iterator for hinted insertion.

3
  • Can you please explain how this could be done in amortized O(1) time (as indicated in cppreference)? Doesn't it need to check whether the hint is the correct insertion point and such check would cost O(lg n)?
    – Jason L
    Oct 29, 2014 at 3:14
  • @JasonL No, remember that these iterators are bidirectional. So you simply check the iterator's previous spot, and see if it is suitable (as regards the key ordering) for inserting the entry. If the hint is incorrect, then you fall back to the O(log n) unhinted insertion. Oct 29, 2014 at 3:22
  • I don't understand the usual case. std::map::emplace will insert only if the key doesn't exist. There is no need to call find() or lower_bound()
    – balki
    Dec 4, 2014 at 6:46
1

std::map is an associative container that keeps its key-value pairs sorted with respect to key. Insertion is of O(logN) complexity, because of costs associated with lookup. But by providing an hint, an iterator where to start to search - insertion can occur in amortized constant time instead of logarithmic time.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.