[Bug libstdc++/19422] 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>]

------- Additional Comments From SWElef at post dot sk  2005-01-14 08:24 -------
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.

> > 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)

As stated in some thread on std.comp.c++ recently, "amortized" is allways
"with respect to something" and that part is missing from the standard.
The usual interpretation in this case is that if you take an assoc. container
in a given state and take the average time of the insertion with hint at every
position, it should be a constant (i.e. also independent of size()). It is far
from guaranteed to be constant if you make a lot of insertions at the end.

The position==end() is special-cased in the insert_unique/insert_equal
function with hint and a member function _M_rightmost() is used. [When I tried
to make an own version of map I decided not to have the information about
the rightmost node and I was able to satisfy all complexity requirements
anyway (except those deffective). This influenced my previously expressed
opinion.] 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.

Regards,
Vladimir Marko


-- 


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