This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Question about complexity of map constructor


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.

When a tree has N nodes, in worst case _Rb_tree_insert_and_rebalance's
complexity is O(log(N)).
So the complexity is O(log(1)+log(2)+...log(N)) = O(log(N!)) and it is
nearly equal to O(N*log(N)).

I overlook anything? or it is sure that the map constructor's
complexity is O(N*log(N))?

Thanks.
-- 
Taro Sekiyama


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]