This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: Question about complexity of map constructor
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