jp******@web.de wrote:
I know there is a method "insert with hint" int std::set. But there
isn't anything similar for find and erase.
Does somebody know why?
First question should be, why insert with hint?
It's because the (in practice) standard implementation (red-black tree) allows
an optimisation that makes it at best constant time rather than log time
to find the place to insert.
Again, why provide it rather than just plain insert(key)?
I guess because insertion is so often done in batches, and keys to be inserted
are so often pre-sorted (roughly or completely, eg in a file),
so it makes general sense to use the iterator returned from last insert as hint.
Why not find with hint then? The more common use of searches is probably
that they are one-off operations with random input (eg user-provided keys).
There could probably be valid use cases where find with hint would be good
to have, eg to look up a list of two-letter words in a full OED dictionary.
In this case the range you get from lower_bound(firstKey), upper_bound(lastKey)
would not be of much help. But if the batch of keys to find is so small,
the sum of find operations is not so expensive...
So, it may have been deemed that it's not common enough to warrant the extra effort.
Again I'm guessing the reasoning of standard committee without looking at facts.
If you really want to know, Stroustrup's "Design and Evolution of C++" may
provide answers, and is anyway certainly a good read (near top of my reading list)
Hope it helps more than confuses
homsan
(privatdozent of speculative statistics)