Question about complexity of map constructor

[Axel Freyn]

On Sun, Jun 05, 2011 at 02:33:06AM +0900, Taro Sekiyama wrote:
> On Sun, Jun 5, 2011 at 2:11 AM, Jonathan Wakely <jwakely.gcc@gmail.com> wrote:
> > 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.
> >
> 
> Searching is avoided, but in _M_insert_unique_, _M_insert_ is called, isn't it?
> 
> if (__position._M_node == _M_end())
> {
>  if (size() > 0
>      && _M_impl._M_key_compare(_S_key(_M_rightmost()),
>      _KeyOfValue()(__v)))
>    return _M_insert_(0, _M_rightmost(), _GLIBCXX_FORWARD(_Arg, __v));
>  else
>    return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first;
>  }
> }
> 
> Then, tree is rebalanced by _Rb_tree_insert_and_rebalance and
> rebalance complexity should be O(log(N)).
No -- worst case rebalancing is O(log(N)). But if you insert the
elements already in sorted order, you won't have the worst case
situation after each insert. So, if the rebalancing is written
efficiently, you will arrive at O(N) for inserting N sorted elements.
(I haven't checked the implementation right now, but I'm quite confident
it is efficiently implemented... :-) )


Axel