Re: [PATCH] Basic_string::_M_replace clean up

[Paolo Carlini <pcarlini at unitus dot it>]

Nathan Myers wrote:

> On Sat, Dec 08, 2001 at 10:14:08PM +0100, Paolo Carlini wrote:
> > Currently, we have the following helper
> >
> >   basic_string::_M_replace(iterator __i1, iterator __i2, _InputIter __k1,
> >                            _InputIter __k2, input_iterator_tag)
> > in addition to
> >
> >   basic_string::_M_replace(iterator __i1, iterator __i2, _ForwardIter __k1,
> >                            _ForwardIter __k2, forward_iterator_tag)
> >
> > What I propose is getting rid of the first, changing the signature of
> > the second to:
> >
> >   basic_string::_M_replace(iterator __i1, iterator __i2, _InputIter __k1,
> >                                _InputIter __k2, input_iterator_tag)
>
> 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.

> >       template<class _InputIterator>
> >         basic_string&
> >         replace(iterator __i1, iterator __i2, _InputIterator __k1,
> > _InputIterator __k2)
> >         {
> >           return _M_replace(__i1, __i2, __k1, __k2,
> >               typename iterator_traits<_InputIterator>::iterator_category());
> >         }
> >
> > replace in principle could either call _M_replace(input_iterator_tag), thus
> > leading to infinite recursion, or _M_replace(forward_iterator_tag), with a
> > definite loss of efficiency.
>
> 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.

> If the first is not called in the test suite, that is an omission from
> the test suite that should be fixed.  You can use a stringstream and
> a pair of istreambuf_iterators or istream_iterators.

I will try to cook up something, I see your point, thanks.

So perhaps what we can do is the following.

Now _M_replace(forward_iterator_tag) also has a temporary (which I added to deal
with the "pathological" cases of overlapping source and destination ranges). This
means that if _M_replace(input_iterator_tag) always ends up calling
_M_replace(forward_iterator_tag) (can you confirm this?) then in this
implementations its temporary is *not* needed (in principle it needs it since
deals with input-iterators).

In fact, the very reason why I had to put the temporary inside
_M_replace(forward_iterator_tag) is that when overlapping ranges are concerned,
the forward_iterator is not so forward but conceptually similar to an
input_iterator!!

Do you agree?

Thanks for your feedback,
Paolo.