[Bug c++/31155] New: priority_queue sorts wrong with std::less

[Bug c++/31155] New: priority_queue sorts wrong with std::less

[rmecklenburg at s5w dot com]

#define protected public
#include <iostream>
#include <queue>

typedef std::vector<int> int_collection;
typedef std::priority_queue<int, int_collection, std::greater<int> > int_queue;

void
print(int_queue & q)
{
    for (int_collection::iterator iter(q.c.begin()); iter != q.c.end(); ++iter)
        std::cout << *iter << " ";
    std::cout << std::endl;
}

int
main()
{
    int_queue q;
    q.push(9); print(q);
    q.push(8); print(q);
    q.push(7); print(q);
    q.push(6); print(q);
    q.push(5); print(q);
    q.push(4); print(q);
    q.push(3); print(q);
    q.push(2); print(q);
    q.push(1); print(q);
}

// $ g++ --version -o priority_queue_test priority_queue_test.cpp;
./priority_queue_test
// g++ (GCC) 4.1.2 20060928 (prerelease) (Ubuntu 4.1.1-13ubuntu5)
// Copyright (C) 2006 Free Software Foundation, Inc.
// This is free software; see the source for copying conditions.  There is NO
// warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
//
// 9
// 8 9
// 7 9 8
// 6 7 8 9
// 5 6 8 9 7
// 4 6 5 9 7 8
// 3 6 4 9 7 8 5
// 2 3 4 6 7 8 5 9
// 1 2 4 3 7 8 5 9 6

I have a cpp expanded version with configuration parameters, but I couldn't
figure out how to submit them from the web page.


-- 
           Summary: priority_queue sorts wrong with std::less
           Product: gcc
           Version: 4.1.2
            Status: UNCONFIRMED
          Severity: major
          Priority: P3
         Component: c++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: rmecklenburg at s5w dot com


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

[Bug c++/31155] priority_queue sorts wrong with std::less

[rmecklenburg at s5w dot com]

------- Comment #1 from rmecklenburg at s5w dot com  2007-03-12 19:51 -------
Created an attachment (id=13197)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=13197&action=view)
gcc -v -E version of the test program


-- 


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

[Bug c++/31155] priority_queue sorts wrong with std::greater

[pcarlini at suse dot de]

------- Comment #2 from pcarlini at suse dot de  2007-03-12 20:05 -------
This is how priority_queue works: it makes an "heap" (in the exact computer
science meaning), therefore, in particular, there is no guarantee that the
contents are all fully sorted, only that the smallest is the first one (the
largest with the default predicate).


-- 

pcarlini at suse dot de changed:

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


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