[STDCXX-238] std::unique() violates 25.2.8, p3

• Type: Bug
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 4.2.0
• Component/s: 25. Algorithms
• Assignee: Martin Sebor
• Reporter: Martin Sebor
• Created: 29/Jun/06 02:52
• Updated: 30/May/07 00:33
• Resolved: 30/May/07 00:33

Description

Moved from the Rogue Wave bug tracking database:

***Created By: sebor @ Apr 26, 2000 11:30:28 AM***
Subject: we have this bug
Date: Wed, 26 Apr 2000 09:53:24 PDT
From: Frank Griswold <[e-mail]>
To: [e-mail], [e-mail]

At least on //stdlib2/ia64/LATEST (as of my last pull a couple of days
ago). We apparently compare a temporary against the first element:
There are 4 comparisons with "1" on the left, 2 with "2" and 3 with "3".

------- Forwarded Message

Subject: a brand new comment about unique()
From: Andrew Koenig <[e-mail]>
Date: Wed, 26 Apr 2000 08:49:08 -0400
Forwarded-by: Frank Griswold <[e-mail]>

To: C++ libraries mailing list
Message c++std-lib-7563

The following comment is derived from a remark by Howard Hinnant.

Until now, I have been under the impression that if we were to impose
the requirement that the predicate given to unique() be an equivalence
relation, that would be enough to allow existing implementations, and
their documentation to conform to the standard without changing either.

Well, it isn't so. The reason is that the standard explicitly says
that applying unique() to an n-element sequence calls the predicate
exactly n-1 times, and both of the implementations that I tested call
the predicate n times, at least in some circumstances.

Here is a test program that you may wish to try on your system:

#include <iostream>
#include <algorithm>

bool pred(int a, int b)

{ std::cout << a << ":" << b << std::endl; return a == b; }

int main()
{
int x[] =

{ 1, 1, 1, 2, 2, 3, 3, 3, 4 }

;
std::unique(x, x + 9, pred);
return 0;
}

Here, x has 9 elements, so the predicate should be called 8 times. I
would be interested to know how many implementations call it 9 times,
and if there are any that do actually call it only 8 times.

The point is that if we do nothing, or if we impose the requirement
that the predicate be an equivalence relation, every implementation
that calls the predicate n times must still change its code. Even if
we remove or change the requirement in the standard to call the
predicate exactly n-1 times, any implementation whose documentation
claims that unique() calls the predicate n-1 times must still change
its documentation.

------- End of Forwarded Message

***Modified By: sebor @ May 30, 2000 11:59:39 AM***
We're not testing complexity requirements of any algorithms in the lib. Test cases should be created.

***Modified By: sebor @ May 09, 2002 10:22:24 AM***
tests/algorithms/unique.cpp is supposed to exercise this functionality. The test is passing at 100%, so there's either a problem with the test or with the logic above. Need to analyze. The ouptut of the program above with the latest libstd 3.0 sources is:

1:1
1:1
1:1
1:2
2:2
2:3
3:3
3:3
3:4