STL insert with hint

[Mark P]

Is an insert with hint (in say std::set) only beneficial if the
insertion occurs immediately before the pointed to location of the hint?
Suppose the insertion occurs right after the hint location? Or
suppose the insertion is near to the hint location but not adjacent? Is
there a performance penalty for an approximate hint, a partial gain, or
no gain?

Thanks,
Mark

[Bart van Ingen Schenau]

Mark P wrote:

Is an insert with hint (in say std::set) only beneficial if the
insertion occurs immediately before the pointed to location of the
hint?
No, the hint is most beneficial if the insertion takes place immediately
_after_ the hint.
Suppose the insertion occurs right after the hint location? Or
suppose the insertion is near to the hint location but not adjacent?
Is there a performance penalty for an approximate hint, a partial
gain, or no gain?
It depends on the implementation of std::set<> on your system, but an
insertion with hint should not be less efficient than insertion without
a hint.
Depending on the implementation and how close the hint is to the actual
insertion point, insertion with a hint may or may not be noticeably
more efficient.

Thanks,
Mark

Bart v Ingen Schenau
--
a.c.l.l.c-c++ FAQ: http://www.comeaucomputing.com/learn/faq
c.l.c FAQ: http://www.eskimo.com/~scs/C-faq/top.html
c.l.c++ FAQ: http://www.parashift.com/c++-faq-lite/