This is the mail archive of the
gcc-bugs@gcc.gnu.org
mailing list for the GCC project.
[Bug libstdc++/19422] assoc. containers: ctor taking range is O(n log n) even if the range is sorted
- From: "SWElef at post dot sk" <gcc-bugzilla at gcc dot gnu dot org>
- To: gcc-bugs at gcc dot gnu dot org
- Date: 14 Jan 2005 13:33:13 -0000
- Subject: [Bug libstdc++/19422] assoc. containers: ctor taking range is O(n log n) even if the range is sorted
- References: <20050113120525.19422.SWElef@post.sk>
- Reply-to: gcc-bugzilla at gcc dot gnu dot org
------- Additional Comments From SWElef at post dot sk 2005-01-14 13:33 -------
It took me quite a long time to realise that the best performance tests are
those where we count the elementary operations. The best way to expose the
O(n log n) complexity in non-fixed case is to supply the container with
a comparator object that counts the invocations of operator() in some global
variable. For an experimental proof that the fixed version is really linear
one also needs to count the node manipulations by, say, replacing _Base_ptr
with a "smart pointer" that acts as a plain pointer and counts every action
(ctor, dtor, copy, dereference).
Regards,
Vladimir Marko
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19422