What is a "hint"?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.