Armin Schleu_inger wrote:
>
> Hi,
>
> I have some problems with the sorting order of the
> priority_queue when there are some objects with
> equal priority. B. Stroustrup mentioned in his book,
> that equal priority objects should be handled like a FIFO.

I just looked at the standard, and found nothing indicating the ordering
of a priority_queue<>. A priority_queue is required to have a Compare
object, but the standard nowhere states even that the Compare object is
actually used, much less how it is used. Priority_queue is not listed as
one of the associative containers. Of course, a lot is implied by the
name of the template, butI think the description needs to be more
specific.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Hi,

I have some problems with the sorting order of the
priority_queue when there are some objects with
equal priority. B. Stroustrup mentioned in his book,
that equal priority objects should be handled like a FIFO.
But the simple program listed below produces the
following output:

Object: priority 2 separate 1
Object: priority 2 separate 2
Object: priority 2 separate 4        <---
Object: priority 2 separate 3        <---
Object: priority 1 separate 0

The expected output should be:

Object: priority 2 separate 1
Object: priority 2 separate 2
Object: priority 2 separate 3
Object: priority 2 separate 4
Object: priority 1 separate 0

I'm using gcc 2.8.1 (djgpp version). I would be glad, if someone
could help me.

Armin

//Program listing ***************************************
#include <queue>

struct Message
{
 int priority;
 int separate;

 bool operator < (const Message& x) const
      { return priority < x.priority; }

 friend ostream& operator << (ostream& os, const Message& msg);
};

ostream& operator << (ostream& os, const Message& msg)
{
 os << "Object: priority " << msg.priority << " separate " <<
msg.separate << endl;
 return os;
}

int main()
{
 Message a,b,c,d,e;
 a.priority=1;
 a.separate=0;
 b.priority=c.priority=d.priority=e.priority=2;
 b.separate=1;
 c.separate=2;
 d.separate=3;
 e.separate=4;

 priority_queue<Message> pq;
 pq.push(a);
 pq.push(b);
 pq.push(c);
 pq.push(d);
 pq.push(e);
 while(!pq.empty())
 {
  cout << pq.top();
  pq.pop();
 }
 cout << endl;
}
// End of listing *******************************

--
_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/

Dipl.-Ing. Armin Schleussinger     _/     _/_/_/ _/_/_/_/
Universitaet Erlangen-Nuernberg   _/     _/  _/    _/
Lehrstuhl fuer Regelungstechnik  _/     _/_/      _/
Cauerstrasse 7                  _/     _/  _/    _/
D - 91058 Erlangen             _/_/_/ _/   _/   _/

Phone :  +49 (0)9131 / 85-7132
Fax   :  +49 (0)9131 / 85-8715
E-mail:  schleus@rt.e-technik.uni-erlangen.de

_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper <kuyper@wizard.net> wrote:

> Armin Schleu_inger wrote:
> >
> > Hi,
> >
> > I have some problems with the sorting order of the
> > priority_queue when there are some objects with
> > equal priority. B. Stroustrup mentioned in his book,
> > that equal priority objects should be handled like a FIFO.
>
> I just looked at the standard, and found nothing indicating the ordering
> of a priority_queue<>. A priority_queue is required to have a Compare
> object, but the standard nowhere states even that the Compare object is
> actually used, much less how it is used. Priority_queue is not listed as
> one of the associative containers. Of course, a lot is implied by the
> name of the template, butI think the description needs to be more
> specific.
> ---

First, priority queue is not an associative container. Despite the name,
it is usually implemented as a heap based on an array-like container of
objects of some class, T. Second, the natural ordering mechanism for the
class T is used if you don't designate the ordering you want. The
'smallest' entries end up at the root of the heap. For example, the
following defines the event queue in a program I'm writing:

priority_queue< event, vector<event>, greater<event> > elist;

--
Harry Erwin, herwin@gmu.edu
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Harry Erwin wrote:
>
> James Kuyper <kuyper@wizard.net> wrote:
>
> > Armin Schleu_inger wrote:
> > >
> > > Hi,
> > >
> > > I have some problems with the sorting order of the
> > > priority_queue when there are some objects with
> > > equal priority. B. Stroustrup mentioned in his book,
> > > that equal priority objects should be handled like a FIFO.
> >
> > I just looked at the standard, and found nothing indicating the ordering
> > of a priority_queue<>. A priority_queue is required to have a Compare
> > object, but the standard nowhere states even that the Compare object is
> > actually used, much less how it is used. Priority_queue is not listed as
> > one of the associative containers. Of course, a lot is implied by the
> > name of the template, butI think the description needs to be more
> > specific.
> > ---
>
> First, priority queue is not an associative container. Despite the name,

I know that; I mentioned associative containers because they, unlike
priority_queue<>,  have statements about the access order of their
members.

> it is usually implemented as a heap based on an array-like container of
> objects of some class, T. Second, the natural ordering mechanism for the
> class T is used if you don't designate the ordering you want. The

I presume that by 'natural ordering' you mean less<T>. I expect that you
are right, and I believe that you are right; so why doesn't the standard
say so?

> 'smallest' entries end up at the root of the heap. For example, the
> following defines the event queue in a program I'm writing:
>
> priority_queue< event, vector<event>, greater<event> > elist;

Which still leaves open the original question of what happens to entries
that have the same priority?


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper wrote:
>
> Armin Schleu_inger wrote:
> >
> > Hi,
> >
> > I have some problems with the sorting order of the
> > priority_queue when there are some objects with
> > equal priority. B. Stroustrup mentioned in his book,
> > that equal priority objects should be handled like a FIFO.
>
> I just looked at the standard, and found nothing indicating the ordering
> of a priority_queue<>. A priority_queue is required to have a Compare
> object, but the standard nowhere states even that the Compare object is
> actually used, much less how it is used.

My apologies; I'd just spent the three days fighting defective hardware
when I read that message, took an overly quick look at the standard, and
made my reply. In fact, the standard specifies exactly what
priority_queue<> does, in terms of the make_heap(), push_heap() and
pop_heap() algorithms. Precisely what those functions are is probably
clearer to CS majors than to me. Much of their implementation is implied
by their time constraints, rather than explicitly stated, and I don't
understand the implications. If I'd never heard of binary trees, I might
have had an equally hard time figuring out the implementation implied by
the time constraints on  map<>.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper <kuyper@wizard.net> wrote:

> Harry Erwin wrote:
> >
> > James Kuyper <kuyper@wizard.net> wrote:
> >
> > > Armin Schleu_inger wrote:
> > > >
...
>
> Which still leaves open the original question of what happens to entries
> that have the same priority?

To have O(log n) access and update time (which priority queues generally
provide), you have to give up preservation of the order of insertion. If
you insert two entries with the same priority, they may emerge from the
priority queue in either order. Consider a heap implementation of a
priority queue. Assume left is chosen over right when the entries are
equal. Start with an empty data structure and insert 0 four times,
labeling each insertion with the order of insertion. So you insert 0'1',
then 0'2', next 0'3', and finally 0'4'. The structure looks like this:
        0'1'
    0'2'   0'3'
0'4'

When you read the entries, you get 0'1', 0'2', 0'4'(!), and 0'3'.

--
Harry Erwin, herwin@gmu.edu
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Harry Erwin wrote in message
<1d9n0yx.lr44qr1dnnynqN@pool-207-205-219-250.pbgh.grid.net>...

>To have O(log n) access and update time (which priority queues generally
>provide), you have to give up preservation of the order of insertion.

Or make other tradeoffs (such as using extra space to hold tie-breaking
information).

A multiset that always did inserts at the end of an equal range can be used
as a priority queue which preserves order with almost the same big-O
behavior.  It takes longer to create (O(N log N) vs. O(N)) but can be
emptied faster (O(N) vs O(N log N)).  Multiset obviously takes more space,
and the constants for most operations are significantly larger.



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Harry Erwin wrote:
>
> James Kuyper <kuyper@wizard.net> wrote:
>
> > Which still leaves open the original question of what happens to entries
> > that have the same priority?
>
> To have O(log n) access and update time (which priority queues generally
> provide), you have to give up preservation of the order of insertion.

Do you have a proof of that or are you guessing ?

It seems to me that a tree would meet the requirements.

--

Valentin Bonnard                mailto:bonnardv@pratique.fr
info about C++/a propos du C++: http://pages.pratique.fr/~bonnardv/


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Harry Erwin <herwin@gmu.edu> wrote:

> James Kuyper <kuyper@wizard.net> wrote:
>
> > Harry Erwin wrote:
> > >
> > > James Kuyper <kuyper@wizard.net> wrote:
> > >
> > > > Armin Schleu_inger wrote:
> > > > >
> ...
> >
> > Which still leaves open the original question of what happens to entries
> > that have the same priority?
>
> To have O(log n) access and update time (which priority queues generally
> provide), you have to give up preservation of the order of insertion. If
> you insert two entries with the same priority, they may emerge from the
> priority queue in either order. Consider a heap implementation of a
> priority queue. Assume left is chosen over right when the entries are
> equal. Start with an empty data structure and insert 0 four times,
> labeling each insertion with the order of insertion. So you insert 0'1',
> then 0'2', next 0'3', and finally 0'4'. The structure looks like this:
>         0'1'
>     0'2'   0'3'
> 0'4'
>
> When you read the entries, you get 0'1', 0'2', 0'4'(!), and 0'3'.

The example I gave here was incorrect. I forgot to reheapify upon each
pop. I love this stuff, but I have to review it carefully every semester
to get all the details right. It's a side-effect of being over 50. 8(

The order you actually get is 0'1', 0'4' (!), 0'3', 0'2'. You can get
other orders if you interleave the insert_back() and pop() calls.

Valentin Bonnard asked if there was a proof. That got me to thinking. If
you keep track of the order of calls to insert_back, either using a
serial number or a time stamp, you can use that to break ties and
recover the order of insertion. It does slow the algorithm in a number
of ways, in particular because it guarantees that the candidate item you
move to the root as part of the resorting after a pop() will settle down
through the maximum possible number of levels.

--
Harry Erwin, herwin@gmu.edu
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Hi,

I have some problems with the sorting order of the
priority_queue when there are some objects with
equal priority. B. Stroustrup mentioned in his book,
that equal priority objects should be handled like a FIFO.
But the simple program listed below produces the
following output:

Object: priority 2 separate 1
Object: priority 2 separate 2
Object: priority 2 separate 4        <---
Object: priority 2 separate 3        <---
Object: priority 1 separate 0

The expected output should be:

Object: priority 2 separate 1
Object: priority 2 separate 2
Object: priority 2 separate 3
Object: priority 2 separate 4
Object: priority 1 separate 0

I'm using gcc 2.8.1 (djgpp version). I would be glad, if someone
could help me.

Armin

//Program listing ***************************************
#include <queue>

struct Message
{
 int priority;
 int separate;

 bool operator < (const Message& x) const
      { return priority < x.priority; }

 friend ostream& operator << (ostream& os, const Message& msg);
};

ostream& operator << (ostream& os, const Message& msg)
{
 os << "Object: priority " << msg.priority << " separate " <<
msg.separate << endl;
 return os;
}

int main()
{
 Message a,b,c,d,e;
 a.priority=1;
 a.separate=0;
 b.priority=c.priority=d.priority=e.priority=2;
 b.separate=1;
 c.separate=2;
 d.separate=3;
 e.separate=4;

 priority_queue<Message> pq;
 pq.push(a);
 pq.push(b);
 pq.push(c);
 pq.push(d);
 pq.push(e);
 while(!pq.empty())
 {
  cout << pq.top();
  pq.pop();
 }
 cout << endl;
}
// End of listing *******************************

--
_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/

Dipl.-Ing. Armin Schleussinger     _/     _/_/_/ _/_/_/_/
Universitaet Erlangen-Nuernberg   _/     _/  _/    _/
Lehrstuhl fuer Regelungstechnik  _/     _/_/      _/
Cauerstrasse 7                  _/     _/  _/    _/
D - 91058 Erlangen             _/_/_/ _/   _/   _/

Phone :  +49 (0)9131 / 85-7132
Fax   :  +49 (0)9131 / 85-8715
E-mail:  schleus@rt.e-technik.uni-erlangen.de

_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/




[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]