Re: Question about complexity of map constructor

[Jonathan Wakely <jwakely dot gcc at gmail dot com>]

On 4 June 2011 18:07, Taro Sekiyama <ryukilon@gmail.com> wrote:
> Hi
>
> I have a question about complexity of map constructor:
>
> template <class InputIterator>
> map ( InputIterator first, InputIterator last,
> ? ? ? ? const Compare& comp = Compare(), const Allocator& = Allocator() );
>
> The constructor's complexity is linear in N if the range [first,last)
> is already sorted where N is last - first
> ?according to ISO/IEC 14882, C++ specification. However if iterators
> (first and last) satisfy the condition,
> it looks like the implementation calls _Rb_tree::_M_insert_, that is
> _Rb_tree_insert_and_rebalance, N times.

It calls this function:

  template<typename _Key, typename _Val, typename _KoV,
           typename _Cmp, typename _Alloc>
    template<class _II>
      void
      _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
      _M_insert_unique(_II __first, _II __last)
      {
        for (; __first != __last; ++__first)
          _M_insert_unique_(end(), *__first);
      }

That uses end() as the hint for where to insert the next element, so
for a sorted range where each element should be inserted at the end
that hint is correct and avoids searching for the insertion point.