[Bug libstdc++/11480] New: std::unique calls predicate too many times

[vince dot delvecchio at analog dot com]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

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

           Summary: std::unique calls predicate too many times
           Product: gcc
           Version: 3.2
            Status: UNCONFIRMED
          Severity: minor
          Priority: P2
         Component: libstdc++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: vince dot delvecchio at analog dot com
                CC: gcc-bugs at gcc dot gnu dot org
 GCC build triplet: sparc-sun-solaris2.7
  GCC host triplet: sparc-sun-solaris2.7
GCC target triplet: sparc-sun-solaris2.7

Section 25.2.8 [lib.alg.unique] of the C++ standard says, with
regard to the std::unique function template:

  Complexity:  If the range ( last - first) is not empty, exactly
  ( last - first) - 1 applications of the corresponding predicate,
  otherwise no applications of the predicate.

But, as attached example demonstrates, the g++ implementation invokes
the predicate once more than that if there are any duplicates.
The example prints out "10".  It should print "9".

The culprit is the definition of unique() in stl_algo.h, which first
invokes adjacent_find in an effort to skip over any already-unique
items at the start of the sequence.  When unique_copy is called,
it invokes the predicate again on two items that have already been
compared.

This was tested with gcc 3.2 but the 3.3 sources seem to
still have the bug.

------------------------------cut here------------------------------
#include <algorithm>
#include <iostream>

int a[10] = { 1, 2, 3, 3, 4, 5, 5, 6, 7, 9 };

static int compare_count = 0;

bool compare(int a, int b)
{
  compare_count++;
  return a == b;
}

int main()
{
  std::unique(a, a+10, compare);
  std::cout << compare_count << std::endl;
  return 0;
}
------------------------------cut here------------------------------
Compiled with
  gcc -v x.cpp -lstdc++

Reading specs from /cpd/gnu/modules/gcc3.2/lib/gcc-lib/sparc-sun-
solaris2.7/3.2/specs
Configured with: ../configure --prefix=/cpd/gnu/modules/gcc3.2 --enable-shared -
-with-as=/cpd/gnu/modules/gcc3.2/bin/as --with-ld=/cpd/gnu/modules/gcc3.2/bin/ld
Thread model: posix
gcc version 3.2
 /cpd/gnu/modules/gcc3.2/lib/gcc-lib/sparc-sun-solaris2.7/3.2/cc1plus -v -
D__GNUC__=3 -D__GNUC_MINOR__=2 -D__GNUC_PATCHLEVEL__=0 -D__GXX_ABI_VERSION=102 -
Dsparc -Dsun -Dunix -D__svr4__ -D__SVR4 -D__PRAGMA_REDEFINE_EXTNAME -
D__sparc__ -D__sun__ -D__unix__ -D__svr4__ -D__SVR4 -
D__PRAGMA_REDEFINE_EXTNAME -D__sparc -D__sun -D__unix -Asystem=unix -
Asystem=svr4 -D__NO_INLINE__ -D__STDC_HOSTED__=1 -D_XOPEN_SOURCE=500 -
D_LARGEFILE_SOURCE=1 -D_LARGEFILE64_SOURCE=1 -D__EXTENSIONS__ -
D__SIZE_TYPE__=unsigned int -D__PTRDIFF_TYPE__=int -D__WCHAR_TYPE__=long int -
D__WINT_TYPE__=long int -D__GCC_NEW_VARARGS__ -Acpu=sparc -Amachine=sparc 
x.cpp -D__GNUG__=3 -D__DEPRECATED -D__EXCEPTIONS -quiet -dumpbase x.cpp -
version -o /var/tmp//cczeWeOb.s
GNU CPP version 3.2 (cpplib) (sparc ELF)
GNU C++ version 3.2 (sparc-sun-solaris2.7)
	compiled by GNU C version 3.2.
ignoring nonexistent directory "/cpd/gnu/modules/gcc3.2/sparc-sun-
solaris2.7/include"
#include "..." search starts here:
#include <...> search starts here:
 /cpd/gnu/modules/gcc3.2/include/c++/3.2
 /cpd/gnu/modules/gcc3.2/include/c++/3.2/sparc-sun-solaris2.7
 /cpd/gnu/modules/gcc3.2/include/c++/3.2/backward
 /usr/local/include
 /cpd/gnu/modules/gcc3.2/include
 /cpd/gnu/modules/gcc3.2/lib/gcc-lib/sparc-sun-solaris2.7/3.2/include
 /usr/include
End of search list.
 /cpd/gnu/modules/gcc3.2/bin/as -V -Qy -s -
o /var/tmp//cc92lqXh.o /var/tmp//cczeWeOb.s
GNU assembler version 2.12 (sparc-sun-solaris2.7) using BFD version 2.12
 /cpd/gnu/modules/gcc3.2/lib/gcc-lib/sparc-sun-solaris2.7/3.2/collect2 -V -Y 
P,/usr/ccs/lib:/usr/lib -Qy /cpd/gnu/modules/gcc3.2/lib/gcc-lib/sparc-sun-
solaris2.7/3.2/crt1.o /cpd/gnu/modules/gcc3.2/lib/gcc-lib/sparc-sun-
solaris2.7/3.2/crti.o /usr/ccs/lib/values-Xa.o /cpd/gnu/modules/gcc3.2/lib/gcc-
lib/sparc-sun-solaris2.7/3.2/crtbegin.o -L/cpd/gnu/modules/gcc3.2/lib/gcc-
lib/sparc-sun-solaris2.7/3.2 -L/cpd/gnu/modules/gcc3.2/lib/gcc-lib/sparc-sun-
solaris2.7/3.2/../../../../sparc-sun-solaris2.7/lib -L/usr/ccs/bin -
L/usr/ccs/lib -L/cpd/gnu/modules/gcc3.2/lib/gcc-lib/sparc-sun-
solaris2.7/3.2/../../.. /var/tmp//cc92lqXh.o -lstdc++ -lgcc -lgcc_eh -lc -lgcc -
lgcc_eh -lc /cpd/gnu/modules/gcc3.2/lib/gcc-lib/sparc-sun-
solaris2.7/3.2/crtend.o /cpd/gnu/modules/gcc3.2/lib/gcc-lib/sparc-sun-
solaris2.7/3.2/crtn.o
GNU ld version 2.12
  Supported emulations:
   elf32_sparc
   elf64_sparc
------------------------------cut here------------------------------