[Bug libstdc++/36333] New: stable_sort calling merge; problems when _GLIBCXX_DEBUG is switched on

[Bug libstdc++/36333] New: stable_sort calling merge; problems when _GLIBCXX_DEBUG is switched on

[dominik dot strasser at onespin-solutions dot com]

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.


-- 
           Summary: stable_sort calling merge; problems when _GLIBCXX_DEBUG
                    is switched on
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: dominik dot strasser at onespin-solutions dot com


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36333

[Bug libstdc++/36333] stable_sort calling merge; problems when _GLIBCXX_DEBUG is switched on

[dominik dot strasser at onespin-solutions dot com]

------- Comment #1 from dominik dot strasser at onespin-solutions dot com  2008-05-26 12:57 -------
Created an attachment (id=15685)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=15685&action=view)
Source code illustrating the problem


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36333

[Bug libstdc++/36333] stable_sort calling merge; problems when _GLIBCXX_DEBUG is switched on

[paolo dot carlini at oracle dot com]

------- Comment #2 from paolo dot carlini at oracle dot com  2008-05-26 15:10 -------
Will investigate ASAP, note this is not a regression, already fails at least
with 4.1.3...


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36333

[Bug libstdc++/36333] stable_sort calling merge; problems when _GLIBCXX_DEBUG is switched on

[chris at bubblescope dot net]

------- Comment #3 from chris at bubblescope dot net  2008-05-26 15:51 -------
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.


-- 

chris at bubblescope dot net changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |chris at bubblescope dot net


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36333

[Bug libstdc++/36333] stable_sort calling merge; problems when _GLIBCXX_DEBUG is switched on

[paolo dot carlini at oracle dot com]

------- Comment #4 from paolo dot carlini at oracle dot com  2008-05-26 20:42 -------
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.


-- 

paolo dot carlini at oracle dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |WAITING


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36333

[Bug libstdc++/36333] stable_sort calling merge; problems when _GLIBCXX_DEBUG is switched on

[dominik dot strasser at onespin-solutions dot com]

------- Comment #5 from dominik dot strasser at onespin-solutions dot com  2008-06-06 07:07 -------
Bug was on my side, the comparison operator didn't form a total order.
Sorry for the noise.


-- 

dominik dot strasser at onespin-solutions dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |RESOLVED
         Resolution|                            |INVALID


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36333

[Bug libstdc++/36333] stable_sort calling merge; problems when _GLIBCXX_DEBUG is switched on

[dominik dot strasser at onespin-solutions dot com]

------- Comment #6 from dominik dot strasser at onespin-solutions dot com  2009-05-20 14:59 -------
Works fine


-- 

dominik dot strasser at onespin-solutions dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |VERIFIED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36333