[Cs3] hints and insert iterators

[Mikhail Nesterenko]

This is from last lecture's discussion.

So, for associative containers there is an insert with a hint

mymap.insert(iterator_hint, value);

The insert() attempts to insert as close to the place as iterator_hint
as possible. If the hint is "right", the insertion is (amortized)
constant time. If it is "wrong" it is O(longN). That is, it does not
hurt to provide incorrect hints, but it helps if, for example, the
elements are inserted in squence. Then each insert is inserted in
constant time, rather than O(log(N)).

Now, in case of insert iterator, the signature is as follows

  template<typename Container>
  std::insert_iterator<Container>
  inserter(Container& c, typename Container::iterator position);


That is, the inserter _must_ provide a hint. That is, in case the hint
is there, things are good. However, it is when the hint is not there,
then something silly, like mymap.end() is provided as a hint.

Here is a blog entry that explains it a provides a programmatic fix.

   https://www.fluentcpp.com/2017/03/17/smart-iterators-for-inserting-into-sorted-container/

Thanks,
-- 
Mikhail