This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Question about complexity of map constructor
- From: Taro Sekiyama <ryukilon at gmail dot com>
- To: libstdc++ at gcc dot gnu dot org
- Date: Sun, 5 Jun 2011 02:07:10 +0900
- Subject: 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