Question about complexity of map constructor

[Taro Sekiyama]

On Sun, Jun 5, 2011 at 2:46 AM, Axel Freyn <axel-freyn@gmx.de> wrote:
> 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
>

It sounds great! I will understand the mechanism.
Thank you very much for answers, Wakely and Freyn.

-- 
Taro Sekiyama