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

["pcarlini at suse dot de" <gcc-bugzilla at gcc dot gnu dot org>]

------- Additional Comments From pcarlini at suse dot de  2005-01-14 11:50 -------
> I was a little in a hurry, so I'll add a comment on the test programm now.
> The "reference time" of std::list ctor taking range must be linear. Thus it
> makes sence to have a look at the quotient of the second and third collumn
> in the output. And that's where you can see the logarithmic behaviour.
> It is visible even for std::allocator but the pool allocator makes it shine.

Thanks for the clarification. I will definitely adapt your test program for
our performance testsuite.

> ... With the access to the rightmost node in constant time the insertions
> at the end could actualy be in "amortized" constant time ("amortized" wrt.
> consecutive insertions at the end). This is just a feeling and needs to be
> proved.

Indeed, it works: on my home machine (P4-2400) currently the quotient above
grows from about 2.8 to 3.5 during the test. The trivial patch that I'm
finishing testing leads to a constant value (~2.4), as expected. This is
with the standard allocator, more suited for our testsuite.

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19422