[Patch] Fix libstdc++/11480

[Paolo Carlini]

Hi,

this took me some time... A little bit of history will help
understanding why I'm now confident that, besides fixing the bug,
I haven't broken anything ;)

Let us consider, for simplicity, the first of the two unique:

    __first = std::adjacent_find(__first, __last);
    return std::unique_copy(__first, __last, __first);

The bug is that, after adjacent_find, *__first == *++__first and
unique_copy does one redundant, non conforming, comparison.

Therefore, I envisaged fixing the bug like this:

    __first = std::adjacent_find(__first, __last);
    if (__first == __last)
      return __last;
    _ForwardIterator __dest = __first;
    return std::unique_copy(++__first, __last, __dest);

This does the trick, indeed, but now we are doing one unnecessary
copy right at the beginning of unique_copy.

However, we are almost there: it suffices to inspect __unique_copy
(the forward_iterator_tag version, of course) to discover that:

    *__result = *__first;    <<<<<<<<<<<<<<<<<<<
    while (++__first != __last)
      if (!(*__result == *__first))
        *++__result = *__first;
    return ++__result;

The unnecessary copy is easily identified! At this point, I have
just copied over the code, removed the first line, renamed a
variable and... that's it.

The same reasoning applies straightforwardly to the binary predicate
version of unique too.

To be safe, I have also added some missing tests to testsuite.

Tested x86-linux, will wait a day or two for comments.

Paolo.

///////////
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: CL_11480
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20031014/a5e53e42/attachment.ksh>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: patch_11480
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20031014/a5e53e42/attachment-0001.ksh>