[Bug c++/19422] New: assoc. containers: ctor taking range is O(n log n) even if the range is sorted

["SWElef at post dot sk" <gcc-bugzilla at gcc dot gnu dot org>]

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