[PATCH] Basic_string::_M_replace clean up

[Nathan Myers]

On Sun, Dec 09, 2001 at 01:19:47AM +0100, Paolo Carlini wrote:
> Nathan Myers wrote:
> > The point of having the two is that for the forward_iterator_tag version
> > you can count the number of elements to insert, allocate the space once,
> > and then copy them into place.  An input iterator cannot be re-read,
> > so there's no better way than to allocate as you go.  Therefore, it is
> > necessary to keep the distinction.
> 
> I agree, in principle.
> 
> > In fact, it would call the second.  The second form would not work
> > correctly on a real input iterator.  I don't see the loss of efficiency.
> > If it were inefficient, the correct approach would be to add a version
> > that takes a random_access_iterator_tag.
> 
> In my opinion it is inefficient in that 
> inside _M_replace(forward_iterator_tag)
> there is *another* copy into a temporary (I put it there some time 
> ago ;-) which is needed for the other uses of it, when overlapping 
> ranges are concerned.

I see what you mean now.  Of course, we can have code actually check
if the ranges are overlapping, when the iterators are ordinary string
iterators or pointers.  That doesn't help if they happen to be (e.g.)
reverse iterators; then we have to be paranoid and do the safe thing.

We can also check if the range being replaced is empty.  Since 
everything else ends up calling replace, there are lots of 
productive opportunities for optimization of extremely common
special cases.

Nathan Myers
ncm at cantrip dot org