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: "pcarlini at suse dot de" <gcc-bugzilla at gcc dot gnu dot org>
- To: gcc-bugs at gcc dot gnu dot org
- Date: 13 Jan 2005 17:20:25 -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 pcarlini at suse dot de 2005-01-13 17:20 -------
> This is my test program.
Thanks.
> After giving it some thought I believe that calling the
> insert_unique/insert_equal function is wrong. I don't think that any hint
> (position) can help to make the running time linear in distance(first,last).
> A special function should be writen for this purpose.
Why? Are you aware of the fact that insert with hint has amortized *constant*
complexity if t is inserted after p? (Table 69)
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19422