Bug 36333 - stable_sort calling merge; problems when _GLIBCXX_DEBUG is switched on
Summary: stable_sort calling merge; problems when _GLIBCXX_DEBUG is switched on
Status: VERIFIED INVALID
Alias: None
Product: gcc
Classification: Unclassified
Component: libstdc++ (show other bugs)
Version: 4.3.0
: P3 normal
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2008-05-26 12:56 UTC by dominik.strasser
Modified: 2009-05-20 14:59 UTC (History)
2 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed:


Attachments
Source code illustrating the problem (497 bytes, text/plain)
2008-05-26 12:57 UTC, dominik.strasser
Details

Note You need to log in before you can comment on or make changes to this bug.
Description dominik.strasser 2008-05-26 12:56:39 UTC
I have an application calling stable_sort with a comparison operator.

stable_sort internally calls
__stable_sort_adaptive
__merge_sort_with_buffer
__merge_sort_loop
_GLIBCXX_STD_P::merge
The last function (if called directly) requires the parameters to be sorted.
It seems to me that this is not necessarily the case here.
Comment 1 dominik.strasser 2008-05-26 12:57:28 UTC
Created attachment 15685 [details]
Source code illustrating the problem
Comment 2 Paolo Carlini 2008-05-26 15:10:01 UTC
Will investigate ASAP, note this is not a regression, already fails at least with 4.1.3...
Comment 3 Chris Jefferson 2008-05-26 15:51:01 UTC
Out of interest, how did you come across this comparison operator?

You comparison operator fails to be an ordering, in particular it is required that:

comp(a,b) && comp(b,c) implies comp(a,c)

comp(0x8ac6a30, 0x8ac69e4) and comp(0x8ac69e4, 0x8ac6ac8) are both true, but
comp(0x8ac6a30, 0x8ac6ac8) is false.
Comment 4 Paolo Carlini 2008-05-26 20:42:12 UTC
It's *extremely* unlikely that stable_sort, unchanged for many years, is misusing merge. Therefore, before any further investigation, please provide a testcase involving a well-formed comparison operator.
Comment 5 dominik.strasser 2008-06-06 07:07:45 UTC
Bug was on my side, the comparison operator didn't form a total order.
Sorry for the noise.
Comment 6 dominik.strasser 2009-05-20 14:59:28 UTC
Works fine