On 09 Jul 98 11:31:02 GMT, enrightm@acm.org (Mike Enright) wrote:

>What I'm here for is to speak for the value of good names for things.
>If you give a component a name, and the name denotes characteristics,
>and you leave those characteristics out of the component, people are
>going to ask questions. If they happen to use a badly-named component
>first, they'll question every name they see after that. Realistically,
>some will even prefer to build their own component instead of
>cross-examining an unknown component from the Library. This is as
>close to a lost sale as a standard can get.

While I'd be the first to agree with you about the value of
appropriate naming (I'm one of the biggest "name-nazis" around here),
I can't agree about priority-queue. Priority queues have been known in
the literature for decades, and the term agrees with the standard
library definition. Knuth's Volume III, p. 150 (copyright 1973) says:

"...we want a ``smallest in, first out'' list, where every deletion
removes the item having the smallest key. Such a list may be called a
_priority_ _queue_, since the key of each item reflects its relative
ability to get out of the list quickly".

Knuth goes on to suggest implementation using a heap, and in fact
notes that

"When using a heap or leftist tree we cannot predict very easily what
will happen to two items with equal keys; it is impossible to
guarantee that items with equal keys will be treated in a
last-in-first-out or first-in-first-out manner, unless the key is
extended to include an additional ``serial number of insertion'' field
so that no equal keys are actually present."

He also discusses the possibility of using balanced trees to get FIFO
behavior, but clearly intends the term "priority-queue" to cover the
heap implementation. I'm sure he didn't invent the term; it probably
goes back even farther.

=Dave
---
[ 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              ]

ncm@nospam.cantrip.org (Nathan Myers) wrote:

>P.J. Plauger<pjp@dinkumware.com> wrote:
>>Mike Enright wrote:
>>>[snip]
>>[snip]
>
>So give [a properly-working priority queue] a different name, or put
>it in a different namespace --
>just don't pretend your variant is part of the standard library,
>and there is no problem.  Meanwhile, users know what to expect
>from the standard std::priority_queue.  They can look up what
>to expect from a Bill_knows_better::priority_queue, if you actually
>do care to specify it (the remark above suggests not).

What I'm here for is to speak for the value of good names for things.
If you give a component a name, and the name denotes characteristics,
and you leave those characteristics out of the component, people are
going to ask questions. If they happen to use a badly-named component
first, they'll question every name they see after that. Realistically,
some will even prefer to build their own component instead of
cross-examining an unknown component from the Library. This is as
close to a lost sale as a standard can get.

>[stuff about the Library]
>
>It's not hard to construct a stable priority queue from an unstable
>one. Requiring a stable queue would imply an unavoidable overhead where
>FIFO behavior isn't needed -- generally a bad thing in a low-level
>component.

If it's so bad that the obvious meaning of the words just should not
be carried out, then it is wise to do something else instead. It is
not so wise to retain an incorrect name.

>
>[stuff about how you can build stuff using the Library]

And the Library's components ought to have meaningful names so people
know what they are buying.


--
Mike Enright
enrightm@acm.org (Email replies cheerfully ignored, use the news group)
http://www.users.cts.com/sd/m/menright/
Cardiff-by-the-Sea, California, USA
---
[ 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              ]

Mike Enright <enrightm@acm.org> wrote in article <359eda4e.403551944@news>...
> Maybe I'm missing something-- why do you think it should be well known
> that a queue container would not preserve FIFO order?

Maybe ``a careful reading of the draft'' makes it clear. Hmmph. The sad
thing is that the C++ Standard is overspecified. It *requires* that a
priority queue be kept in sort by using a heap-sort discipline, which is
not stable. We vendors can't provide a stable priority_queue (by that
name) even if we want to.

> The point is, "queue" connotes FIFO in most usage. (Try going against
> it at a cinema).

And a priority queue at a cinema connotes someone is pulling rank. Try
explaining FIFO to a fellow VIP who's throwing his weight around. Weak
analogy, even though your basic point is a good one.

>                      FIFO is a useful property for queues. So is priority.
> They could have been combined. The best name for a container that did
> both would be "priority_queue".

Agreed. Too late now.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com



[ 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              ]

P.J. Plauger<pjp@dinkumware.com> wrote:
>Mike Enright <enrightm@acm.org> wrote:
>> Maybe I'm missing something-- why do you think it should be well known
>> that a queue container would not preserve FIFO order?
>
>Maybe ``a careful reading of the draft'' makes it clear. Hmmph. The sad
>thing is that the C++ Standard is overspecified. It *requires* that a
>priority queue be kept in sort by using a heap-sort discipline, which is
>not stable. We vendors can't provide a stable priority_queue (by that
>name) even if we want to.

So give it a different name, or put it in a different namespace --
just don't pretend your variant is part of the standard library,
and there is no problem.  Meanwhile, users know what to expect
from the standard std::priority_queue.  They can look up what
to expect from a Bill_knows_better::priority_queue, if you actually
do care to specify it (the remark above suggests not).

The standard library leaves endless niches for library vendors who
have something else to offer, and there's no need to pretend
that only "standard" facilities are useful.  The standard library
was fully intended to work alongside (indeed, to help enable) a
thriving marketplace in "other" libraries.

>>                      FIFO is a useful property for queues.
>> So is priority.  They could have been combined. The best name
>> for a container that did both would be "priority_queue".

Or "stable_priority_queue".  I notice nobody is complaining that
std::sort() is not stable (or that the standard library is too small).

It's not hard to construct a stable priority queue from an unstable
one. Requiring a stable queue would imply an unavoidable overhead where
FIFO behavior isn't needed -- generally a bad thing in a low-level
component.

The STL is a framework.  In a very real sense, just about every actual
template in it is just an example.  Anything not there is easily added;
anything that's not exactly what you want is easily replaced.

--
Nathan Myers
ncm@nospam.cantrip.org  http://www.cantrip.org/



[ 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              ]

If I insert pointer of objects (allocated on the heap) with the same
priority into a priority_queue and pop them out again, the element order is
not preserved. Is there a bug in the implementation of the priority_queue
of the STL in Visual C++ 5.0 Service Pack 3?

Thank you very much for help.

Oliver Trampenau


// An object of the class CSequenceElement can store a sequence number. All
objects of this class have the same priority.
class CSequenceElement {
public:
 typedef unsigned int sequenceNumber;
 CSequenceElement(sequenceNumber S) : m_SequenceNumber(S) { }
 sequenceNumber SequenceNumber() const { return m_SequenceNumber; }
 bool operator<(const CSequenceElement& Element) const
  { return false; } // All elements have the same priority
 class CComparePriority {
 public:
  bool operator()(const CSequenceElement& _X, const CSequenceElement& _Y)
const
   { return false; } // All elements have the same priority
  bool operator()(const CSequenceElement* _X, const CSequenceElement* _Y)
const
   { return false; } // All elements have the same priority
 };
private:
 sequenceNumber m_SequenceNumber;
};

/////////////////////////////////////////////
// Test order of priority_queue

typedef CSequenceElement::sequenceNumber sequenceNumber;
typedef priority_queue<CSequenceElement*, vector<CSequenceElement*>,
 CSequenceElement::CComparePriority> sequenceQueue;

sequenceQueue Queue;
const sequenceNumber FirstSequenceNumber = 1;
const sequenceNumber LastSequenceNumber = 2000;

// Insert elements into the priority queue. The elements have an ascending
sequence number
for(sequenceNumber i = FirstSequenceNumber; i <= LastSequenceNumber; i++)
 Queue.push(new CSequenceElement(i));

// Retrieve elements from the priority queue
sequenceNumber Check = FirstSequenceNumber;
while(!Queue.empty())
{
 CSequenceElement& Element = *Queue.top();
 sequenceNumber i = Element.SequenceNumber();
 if(i != Check++)
  OutputDebugString("Invalid element order\n");
 Queue.pop();
 delete &Element;
}
if(Check != LastSequenceNumber + 1)
 OutputDebugString("Wrong number of elements");
---
[ 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              ]

Oliver Trampenau <otrampenau@kaba.com> wrote:
: If I insert pointer of objects (allocated on the heap) with the same
: priority into a priority_queue and pop them out again, the element order is
: not preserved. Is there a bug in the implementation of the priority_queue
: of the STL in Visual C++ 5.0 Service Pack 3?

Maybe I'm missing something---why did you think order
should be preserved? the spec only calls for items
of lesser (greater, depending on the comparison function
you pass in) comparative value to reach the `top of the
heap' first for popping. This way there is no constraint
on implementation that might slow down operation.


Don

Don Montgomery
Advanced Communications Technology (ACT) Laboratory
University of Texas at Dallas
montgo@utdallas.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              ]