public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug libstdc++/11480] New: std::unique calls predicate too many times
@ 2003-07-09 16:57 vince dot delvecchio at analog dot com
2003-07-09 16:58 ` [Bug libstdc++/11480] " vince dot delvecchio at analog dot com
` (4 more replies)
0 siblings, 5 replies; 6+ messages in thread
From: vince dot delvecchio at analog dot com @ 2003-07-09 16:57 UTC (permalink / raw)
To: gcc-bugs
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------------------------------
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug libstdc++/11480] std::unique calls predicate too many times
2003-07-09 16:57 [Bug libstdc++/11480] New: std::unique calls predicate too many times vince dot delvecchio at analog dot com
@ 2003-07-09 16:58 ` vince dot delvecchio at analog dot com
2003-07-10 19:39 ` paolo at gcc dot gnu dot org
` (3 subsequent siblings)
4 siblings, 0 replies; 6+ messages in thread
From: vince dot delvecchio at analog dot com @ 2003-07-09 16:58 UTC (permalink / raw)
To: gcc-bugs
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
------- Additional Comments From vince dot delvecchio at analog dot com 2003-07-09 16:58 -------
Created an attachment (id=4371)
--> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=4371&action=view)
preprocessed source
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug libstdc++/11480] std::unique calls predicate too many times
2003-07-09 16:57 [Bug libstdc++/11480] New: std::unique calls predicate too many times vince dot delvecchio at analog dot com
2003-07-09 16:58 ` [Bug libstdc++/11480] " vince dot delvecchio at analog dot com
@ 2003-07-10 19:39 ` paolo at gcc dot gnu dot org
2003-10-14 17:12 ` cvs-commit at gcc dot gnu dot org
` (2 subsequent siblings)
4 siblings, 0 replies; 6+ messages in thread
From: paolo at gcc dot gnu dot org @ 2003-07-10 19:39 UTC (permalink / raw)
To: gcc-bugs
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
paolo at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
AssignedTo|unassigned at gcc dot gnu |paolo at gcc dot gnu dot org
|dot org |
Status|UNCONFIRMED |ASSIGNED
Ever Confirmed| |1
Last reconfirmed|0000-00-00 00:00:00 |2003-07-10 19:39:27
date| |
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug libstdc++/11480] std::unique calls predicate too many times
2003-07-09 16:57 [Bug libstdc++/11480] New: std::unique calls predicate too many times vince dot delvecchio at analog dot com
2003-07-09 16:58 ` [Bug libstdc++/11480] " vince dot delvecchio at analog dot com
2003-07-10 19:39 ` paolo at gcc dot gnu dot org
@ 2003-10-14 17:12 ` cvs-commit at gcc dot gnu dot org
2003-10-14 17:15 ` cvs-commit at gcc dot gnu dot org
2003-10-14 17:18 ` paolo at gcc dot gnu dot org
4 siblings, 0 replies; 6+ messages in thread
From: cvs-commit at gcc dot gnu dot org @ 2003-10-14 17:12 UTC (permalink / raw)
To: gcc-bugs
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
------- Additional Comments From cvs-commit at gcc dot gnu dot org 2003-10-14 17:12 -------
Subject: Bug 11480
CVSROOT: /cvs/gcc
Module name: gcc
Changes by: paolo@gcc.gnu.org 2003-10-14 17:11:54
Modified files:
libstdc++-v3 : ChangeLog
libstdc++-v3/include/bits: stl_algo.h
Added files:
libstdc++-v3/testsuite/25_algorithms/unique: 1.cc 11480.cc 2.cc
Log message:
2003-10-14 Paolo Carlini <pcarlini@unitus.it>
PR libstdc++/11480
* include/bits/stl_algo.h (unique): Fix.
* testsuite/25_algorithms/unique.cc: Move to unique/1.cc.
* testsuite/25_algorithms/unique/11480.cc: New, from the PR.
* testsuite/25_algorithms/unique/2.cc: New.
Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc++-v3/ChangeLog.diff?cvsroot=gcc&r1=1.2012&r2=1.2013
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc++-v3/include/bits/stl_algo.h.diff?cvsroot=gcc&r1=1.40&r2=1.41
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc++-v3/testsuite/25_algorithms/unique/1.cc.diff?cvsroot=gcc&r1=NONE&r2=1.1
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc++-v3/testsuite/25_algorithms/unique/11480.cc.diff?cvsroot=gcc&r1=NONE&r2=1.1
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc++-v3/testsuite/25_algorithms/unique/2.cc.diff?cvsroot=gcc&r1=NONE&r2=1.1
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug libstdc++/11480] std::unique calls predicate too many times
2003-07-09 16:57 [Bug libstdc++/11480] New: std::unique calls predicate too many times vince dot delvecchio at analog dot com
` (2 preceding siblings ...)
2003-10-14 17:12 ` cvs-commit at gcc dot gnu dot org
@ 2003-10-14 17:15 ` cvs-commit at gcc dot gnu dot org
2003-10-14 17:18 ` paolo at gcc dot gnu dot org
4 siblings, 0 replies; 6+ messages in thread
From: cvs-commit at gcc dot gnu dot org @ 2003-10-14 17:15 UTC (permalink / raw)
To: gcc-bugs
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
------- Additional Comments From cvs-commit at gcc dot gnu dot org 2003-10-14 17:15 -------
Subject: Bug 11480
CVSROOT: /cvs/gcc
Module name: gcc
Changes by: paolo@gcc.gnu.org 2003-10-14 17:15:27
Removed files:
libstdc++-v3/testsuite/25_algorithms: unique.cc
Log message:
2003-10-14 Paolo Carlini <pcarlini@unitus.it>
PR libstdc++/11480
* include/bits/stl_algo.h (unique): Fix.
* testsuite/25_algorithms/unique.cc: Move to unique/1.cc.
* testsuite/25_algorithms/unique/11480.cc: New, from the PR.
* testsuite/25_algorithms/unique/2.cc: New.
Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc++-v3/testsuite/25_algorithms/unique.cc.diff?cvsroot=gcc&r1=1.1&r2=NONE
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Bug libstdc++/11480] std::unique calls predicate too many times
2003-07-09 16:57 [Bug libstdc++/11480] New: std::unique calls predicate too many times vince dot delvecchio at analog dot com
` (3 preceding siblings ...)
2003-10-14 17:15 ` cvs-commit at gcc dot gnu dot org
@ 2003-10-14 17:18 ` paolo at gcc dot gnu dot org
4 siblings, 0 replies; 6+ messages in thread
From: paolo at gcc dot gnu dot org @ 2003-10-14 17:18 UTC (permalink / raw)
To: gcc-bugs
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
paolo at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|ASSIGNED |RESOLVED
Resolution| |FIXED
------- Additional Comments From paolo at gcc dot gnu dot org 2003-10-14 17:18 -------
Fixed for 3.4
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2003-10-14 17:18 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2003-07-09 16:57 [Bug libstdc++/11480] New: std::unique calls predicate too many times vince dot delvecchio at analog dot com
2003-07-09 16:58 ` [Bug libstdc++/11480] " vince dot delvecchio at analog dot com
2003-07-10 19:39 ` paolo at gcc dot gnu dot org
2003-10-14 17:12 ` cvs-commit at gcc dot gnu dot org
2003-10-14 17:15 ` cvs-commit at gcc dot gnu dot org
2003-10-14 17:18 ` paolo at gcc dot gnu dot org
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).