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

["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.