The template constructor of associative containers with range [first,last) should have linear complexity if the range is sorted. libstdc++ fails to comply.
This is quite evident when looking at the include file bits/stl_tree.h, more precisely the functions insert_unique and insert_equal taking ranges. To be sure I made some runtime tests. The complexity is really O(n log n), where n=distance(first,last). It is not evident with the default allocator, but one can see the trend. I also tested with a self-made single-threaded pool allocator and the results were very clear. I can submit the source if need be. Regards, Vladimir Marko -- Summary: assoc. containers: ctor taking range is O(n log n) even if the range is sorted Product: gcc Version: 3.4.3 Status: UNCONFIRMED Severity: normal Priority: P2 Component: c++ AssignedTo: unassigned at gcc dot gnu dot org ReportedBy: SWElef at post dot sk CC: gcc-bugs at gcc dot gnu dot org http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19422