public inbox for gcc-prs@sourceware.org
help / color / mirror / Atom feed
* Re: libstdc++/8195: n-th algorithm (STL) doesn`t work properly
@ 2002-10-11 16:12 paolo
0 siblings, 0 replies; 5+ messages in thread
From: paolo @ 2002-10-11 16:12 UTC (permalink / raw)
To: gcc-bugs, gcc-prs, johnb, nobody
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
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: libstdc++/8195: n-th algorithm (STL) doesn`t work properly
@ 2002-10-11 8:56 Wolfgang Bangerth
0 siblings, 0 replies; 5+ messages in thread
From: Wolfgang Bangerth @ 2002-10-11 8:56 UTC (permalink / raw)
To: nobody; +Cc: gcc-prs
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
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: libstdc++/8195: n-th algorithm (STL) doesn`t work properly
@ 2002-10-11 8:46 Belov, Eugeny
0 siblings, 0 replies; 5+ messages in thread
From: Belov, Eugeny @ 2002-10-11 8:46 UTC (permalink / raw)
To: nobody; +Cc: gcc-prs
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
>
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: libstdc++/8195: n-th algorithm (STL) doesn`t work properly
@ 2002-10-11 7:46 Wolfgang Bangerth
0 siblings, 0 replies; 5+ messages in thread
From: Wolfgang Bangerth @ 2002-10-11 7:46 UTC (permalink / raw)
To: nobody; +Cc: gcc-prs
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
^ permalink raw reply [flat|nested] 5+ messages in thread
* libstdc++/8195: n-th algorithm (STL) doesn`t work properly
@ 2002-10-11 4:16 johnb
0 siblings, 0 replies; 5+ messages in thread
From: johnb @ 2002-10-11 4:16 UTC (permalink / raw)
To: gcc-gnats
>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
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2002-10-11 23:12 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2002-10-11 16:12 libstdc++/8195: n-th algorithm (STL) doesn`t work properly paolo
-- strict thread matches above, loose matches on Subject: below --
2002-10-11 8:56 Wolfgang Bangerth
2002-10-11 8:46 Belov, Eugeny
2002-10-11 7:46 Wolfgang Bangerth
2002-10-11 4:16 johnb
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).