You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@stdcxx.apache.org by "Martin Sebor (JIRA)" <ji...@apache.org> on 2006/06/28 21:53:29 UTC
[jira] Created: (STDCXX-238) std::unique() violates 25.2.8, p3
std::unique() violates 25.2.8, p3
---------------------------------
Key: STDCXX-238
URL: http://issues.apache.org/jira/browse/STDCXX-238
Project: C++ Standard Library
Type: Bug
Components: 25. Algorithms
Reporter: Martin Sebor
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 <gr...@roguewave.com>
To: sebor@roguewave.com, yoder@roguewave.com
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 <ar...@research.att.com>
Date: Wed, 26 Apr 2000 08:49:08 -0400
Forwarded-by: Frank Griswold <gr...@roguewave.com>
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
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see:
http://www.atlassian.com/software/jira
[jira] Closed: (STDCXX-238) std::unique() violates 25.2.8, p3
Posted by "Martin Sebor (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/STDCXX-238?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Martin Sebor closed STDCXX-238.
-------------------------------
Resolution: Fixed
Fix Version/s: 4.2
When compiled with the latest trunk the test case produces the output below, indicating that the predicate is invoked exactly 8 times, i.e., in accordance with the requirements. Our test for the algorithm, algorithms/25.unique.cpp which exercises the complexity guarantees, passes all assertions.
1:1
1:1
2:1
2:2
2:3
3:3
3:3
3:4
> std::unique() violates 25.2.8, p3
> ---------------------------------
>
> Key: STDCXX-238
> URL: https://issues.apache.org/jira/browse/STDCXX-238
> Project: C++ Standard Library
> Issue Type: Bug
> Components: 25. Algorithms
> Reporter: Martin Sebor
> Assignee: Martin Sebor
> Fix For: 4.2
>
>
> 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 <gr...@roguewave.com>
> To: sebor@roguewave.com, yoder@roguewave.com
> 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 <ar...@research.att.com>
> Date: Wed, 26 Apr 2000 08:49:08 -0400
> Forwarded-by: Frank Griswold <gr...@roguewave.com>
> 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
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Assigned: (STDCXX-238) std::unique() violates 25.2.8, p3
Posted by "Martin Sebor (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/STDCXX-238?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Martin Sebor reassigned STDCXX-238:
-----------------------------------
Assignee: Martin Sebor
> std::unique() violates 25.2.8, p3
> ---------------------------------
>
> Key: STDCXX-238
> URL: https://issues.apache.org/jira/browse/STDCXX-238
> Project: C++ Standard Library
> Issue Type: Bug
> Components: 25. Algorithms
> Reporter: Martin Sebor
> Assignee: Martin Sebor
>
> 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 <gr...@roguewave.com>
> To: sebor@roguewave.com, yoder@roguewave.com
> 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 <ar...@research.att.com>
> Date: Wed, 26 Apr 2000 08:49:08 -0400
> Forwarded-by: Frank Griswold <gr...@roguewave.com>
> 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
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.