Re: libstdc++/8195: n-th algorithm (STL) doesn`t work properly

Re: libstdc++/8195: n-th algorithm (STL) doesn`t work properly

[paolo]

Synopsis: n-th algorithm (STL) doesn`t work properly

State-Changed-From-To: open->closed
State-Changed-By: paolo
State-Changed-When: Fri Oct 11 16:12:33 2002
State-Changed-Why:
    Not a bug.

http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&pr=8195

Re: libstdc++/8195: n-th algorithm (STL) doesn`t work properly

[Wolfgang Bangerth]

The following reply was made to PR libstdc++/8195; it has been noted by GNATS.

From: Wolfgang Bangerth <bangerth@ticam.utexas.edu>
To: "Belov, Eugeny" <Eugeny_Belov@stl.sarov.ru>
Cc: gcc-bugs@gcc.gnu.org, <gcc-gnats@gcc.gnu.org>
Subject: Re: libstdc++/8195: n-th algorithm (STL) doesn`t work properly
Date: Fri, 11 Oct 2002 10:50:51 -0500 (CDT)

 >   I am understanding that the principle of this algorithm (in simple 
 > terms) is to divide the sequence into 2 parts like this:
 > smaller elements , n-th element, bigger elements,  and in the general 
 > case both parts can be unsorted.
 
 Correct.
 
 >   But the real problem in this case is that smaller elements comes after 
 > n-th ("n-th" is the integer with value 12 - the biggiest of all other 
 > elements), i.e. the sequence after using the nth_element() is "4 4 5 6 6 
 > 6 9 _12_ 8 10" and in this case I think the n-th algorithm 
 > implementation make a mistake.
 
 Why? The signature of the function is
   void nth_element(RandomAccessIterator first, 
                    RandomAccessIterator nth,
                    RandomAccessIterator last);
 and you call it like
   nth_element(a, a+2, a+10);
 so the result is that elements 0 and 1 will be smaller than the one at 
 position 2, and that elements 3 through 9 will be larger. This is what 
 happens in your output.
 
 Regards
   Wolfgang
 
 PS-1: Note that a+2 points to "9" in your example, not "12" as you claim, 
 since indices are zero-based.
 
 PS-2: The algorithm sorts such that the values before and after the 
 _pointer_ are smaller and larger, respectively, not those elements that 
 are smaller and larger than the _element pointed to_! I think this is the 
 basic misunderstanding on your behalf. The standard on this reads
 
   After nth_element the element in the position pointed to by nth is the
   element that would be in that position if the whole range were sorted.
   Also  for  any iterator i in the range [first, nth) and any iterator j
   in the range [nth, last) it holds that: !(*i > *j) or comp(*j, *i)  ==
   false.
 
 -------------------------------------------------------------------------
 Wolfgang Bangerth              email:           bangerth@ticam.utexas.edu
                                www: http://www.ticam.utexas.edu/~bangerth
 
 

Re: libstdc++/8195: n-th algorithm (STL) doesn`t work properly

[Belov, Eugeny]

The following reply was made to PR libstdc++/8195; it has been noted by GNATS.

From: "Belov, Eugeny" <Eugeny_Belov@stl.sarov.ru>
To: Wolfgang Bangerth <bangerth@ticam.utexas.edu>
Cc: gcc-bugs@gcc.gnu.org, gcc-gnats@gcc.gnu.org
Subject: Re: libstdc++/8195: n-th algorithm (STL) doesn`t work properly
Date: Fri, 11 Oct 2002 19:42:01 +0400

     Hello Wolfgang
 
   I am understanding that the principle of this algorithm (in simple 
 terms) is to divide the sequence into 2 parts like this:
 smaller elements , n-th element, bigger elements,  and in the general 
 case both parts can be unsorted.
   But the real problem in this case is that smaller elements comes after 
 n-th ("n-th" is the integer with value 12 - the biggiest of all other 
 elements), i.e. the sequence after using the nth_element() is "4 4 5 6 6 
 6 9 _12_ 8 10" and in this case I think the n-th algorithm 
 implementation make a mistake.
 
 With best regards.
 Eugeny.
 
 
 Wolfgang Bangerth wrote:
 
 >This is not a bug, so may be closed.
 >
 >nth_element does not sort the _entire_ array, it only makes sure that the 
 >elements before the nth-pointer are smaller, and the ones behind that are 
 >larger than the element pointed to by nth (the second argument). It makes 
 >no guarantees that each of these two parts of the entire range is sorted 
 >itself.
 >
 >Regards
 >  Wolfgang
 >
 >-------------------------------------------------------------------------
 >Wolfgang Bangerth              email:           bangerth@ticam.utexas.edu
 >                               www: http://www.ticam.utexas.edu/~bangerth
 >
 

Re: libstdc++/8195: n-th algorithm (STL) doesn`t work properly

[Wolfgang Bangerth]

The following reply was made to PR libstdc++/8195; it has been noted by GNATS.

From: Wolfgang Bangerth <bangerth@ticam.utexas.edu>
To: johnb@stl.sarov.ru, <gcc-bugs@gcc.gnu.org>, <gcc-gnats@gcc.gnu.org>
Cc:  
Subject: Re: libstdc++/8195: n-th algorithm (STL) doesn`t work properly
Date: Fri, 11 Oct 2002 09:42:48 -0500 (CDT)

 This is not a bug, so may be closed.
 
 nth_element does not sort the _entire_ array, it only makes sure that the 
 elements before the nth-pointer are smaller, and the ones behind that are 
 larger than the element pointed to by nth (the second argument). It makes 
 no guarantees that each of these two parts of the entire range is sorted 
 itself.
 
 Regards
   Wolfgang
 
 -------------------------------------------------------------------------
 Wolfgang Bangerth              email:           bangerth@ticam.utexas.edu
                                www: http://www.ticam.utexas.edu/~bangerth
 
 

libstdc++/8195: n-th algorithm (STL) doesn`t work properly

[johnb]

>Number:         8195
>Category:       libstdc++
>Synopsis:       n-th algorithm (STL) doesn`t work properly
>Confidential:   no
>Severity:       serious
>Priority:       medium
>Responsible:    unassigned
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Fri Oct 11 04:16:01 PDT 2002
>Closed-Date:
>Last-Modified:
>Originator:     johnb@stl.sarov.ru (Eugeny Belov)
>Release:        g++ v3.2
>Organization:
>Environment:
Red Hat Linux release 8.0
>Description:
The simple testcase using nth_element() doesn`t work properly. Compiled by g++ (v.3.2, 3.1, 2.96) it gives the "4 4 5 6 6 6 9 12 8 10", but expected output is "4 4 5 6 6 6 8 9 10 12" (sorted sequence). See the testcase.
>How-To-Repeat:
Compile the testcase by g++ and run it, compare output. The correct result is the sorted integers sequence.
>Fix:

>Release-Note:
>Audit-Trail:
>Unformatted:
----gnatsweb-attachment----
Content-Type: application/octet-stream; name="nth-elem.cpp"
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="nth-elem.cpp"

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8aXRlcmF0
b3I+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1haW4oKQp7ICAKICAgaW50IGFbMTBdID0g
ezQsIDEyLCA5LCA1LCA2LCA2LCA2LCA0LCA4LCAxMH07CiAgIAogICAgbnRoX2VsZW1lbnQoYSwg
YSsyLCBhKzEwKTsKICAgIGNvcHkoYSwgYSsxMCwgb3N0cmVhbV9pdGVyYXRvcjxpbnQ+KGNvdXQs
ICIgIikpOwogICAgY291dCA8PCBlbmRsOwoKICAgcmV0dXJuIDA7Cn0K