Improving equal_range and erase(key) in tree containers

[Paolo Carlini]

Ion Gaztañaga wrote:

> Regarding erase(const key &x) in tree containers, at least in the v7
> branch, also uses std::distance() after equal_range to know the number
> of erased elements:
>
> size erase(const _Key& __x)
> {
>   pair<iterator,iterator> __p = equal_range(__x);
>   size_type __n = std::distance(__p.first, __p.second);
>   erase(__p.first, __p.second);
>   return __n;
> }
>
> Both distance and erase(iterator, iterator) traverse the sequence so
> we are traversing the sequence to be erased more than necessary. we
> can implement erase(iterator, iterator) if a private function that
> returns the number of erased elements, so we can save some cycles if
> we want to erase many nodes with the same key. Another way is to get
> the size of the tree before calling erase and to substract the size
> after calling erase.

This bit seem sufficiently straightforward to go in immediately with 
proper acknowledgement. I'm finishing testing the below.

Paolo.

/////////////////
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: CL_ion_1
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20061006/92f0cb2f/attachment.ksh>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: patch_ion_1
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20061006/92f0cb2f/attachment-0001.ksh>