Topic: Defect Report: 25.3.6 [lib.alg.heap.operations] - incorrect description


Author: "Markus Mauhart" <mmauhart@ping.at>
Date: 1999/09/28
Raw View
Dave Abrahams <abrahams@mediaone.net> wrote:
> In article <7sleo1$j0v$1@fleetstreet.Austria.EU.net> , "Markus Mauhart"
> <mmauhart@ping.at> wrote:
>
> > Is this a commonly
> > agreed term (outside the c++ standard !) ? If yes, does it have the same
> > semantics as defined in the c++ standard ?
>
> Yes and yes. I refer you to Knuth.

Short an exact information, thanks :-)
Then my previous complaints about std::priority_queue's choosen behaviour
(or the name choosen for that behaviour) were inappropriate; but I still
think that a more explicit description of priority_queue's
[not-]intended behaviour would be worth the effort.




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






Author: "Markus Mauhart" <mmauhart@ping.at>
Date: 1999/09/29
Raw View
John Potter <jpotter@falcon.lhup.edu> wrote:
>=20
> This is a nit-pick, but if changed, you have a good version.

I dont know the german translation of 'nit-pick', but it sounds very
appropriate for a thing not worth a DR (but IMHO worth 5 minutes work
when actually typesetting a new release of the standard).

Concerning respecting of insertion order for heap and priority_queue,
as their standard-defined behaviour follows the classic entities with
same name, this choosen behaviour and naming is one of the many topics
where the standard is perfect, especially my assumption that mentioning
insertion order was forgotten by accident was incorrect which makes
that part of my DR a NAD.

// some discussions of the problem to implement a generally useful
// priority_queue respecting insert order.

Having considered some of that problems, when I read the name
"priority_queue" in the standard I immediately praised the people
who seemed to have solved these problems for me. Then I realized that
they seemed to have forgotten to mention 'respecting insert order' in
the description ..

> sensitive.  The CS knowledge that heap based priority queue, heap =
sort,
> and quick sort are unstable is needed here.  Whether the standard

Knowledge of instability was not enough for me. I noticed the "not =
stable"
in std::heap's description (and assumed this to be 'true', cause it's
unlikely to warn for unstability by accident), but as long as one does
not expose the whole container via the interface (and heap and prio_q..
only provide its top), its exposed 'top' could respect the order.

Btw, I'd consider a standard with an explicit note concerning the
probably unexpected behaviour of priority_queue a better standard.
---
[ 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              ]





Author: jpotter@falcon.lhup.edu (John Potter)
Date: 1999/09/27
Raw View
On 26 Sep 1999 17:10:36 GMT, "Markus Mauhart" <mmauhart@ping.at> wrote:

First, my apologies for the tone and lack of facts in that reply.  My
thanks to you for your polite reply.  Let's see if I can do better.

: John Potter <jpotter@falcon.lhup.edu> wrote ..
: >
: >On 24 Sep 1999 16:21:01 GMT, "Markus Mauhart" <mmauhart@ping.at> wrote:
: >
: >: 25.3.6 [lib.alg.heap.operations] states two key properties of a heap [a,b),
: >: the first of them ..
: >: "(1) *a is the largest element"
: >:
: >: I think this is incorrect and should be
: >: (1) *a is part of the heaps largest equivalence-class,

This is a nit-pick, but if changed, you have a good version.

: Given that I stay with my original proposal:

:  (1) *a is part of the heaps largest equivalence-class,

Agreed.

:
: >: 2-Take 'an oldest' from that equivalence class, otherwise the heap functions
: >:  could not be used for a priorityqueue as explained in 23.2.3.2.2
: >:  [lib.priqueue.members] (where I assume that a "priority queue" respects
: >:  priority AND time).

The problem with 25.3.6 is that these are heap algorithms that operate
on some random access iterator range.  There is no heap container in
which to place time information.  There is a statement that the heap
properties make it possible to use these algorithms to implement a
priority queue.  There is also a statement at the end that sort_heap
is not stable.  25.3.6/2 says that the properties make heaps useful
as priority queues.  That seems like a note rather than the normative
text which it is.  The DR might attack that paragraph by adding "when
the priorities are unique".  There is not much else that can be done
with 25.3.6.

The next attempt would be to attack 23.2.3.2 priority queue which is
a container.  Making it time sensitive would require another container
of time stamps and a modified compare object to use the time stamps in
breaking ties.  This may be possible, but it would not be nice.  The
time stamps would need to be swapped along with the data items and the
compare object would need access to the time stamps for tie breaking.
I don't think that everyone would want that overhead when they do not
need it.  Also note the comments in clc++m that time stamps are not
usable in all cases.  It seems that the best that could be done would
be to add a note stating that the priority queue assumes unique
priorities.

The workarounds are to place time stamps in the data items if this will
solve the problem or to use one of the stable_priority_queues mentioned
in the clc++m thread.

I agree that common expectation of a priority queue is that it be time
sensitive.  The CS knowledge that heap based priority queue, heap sort,
and quick sort are unstable is needed here.  Whether the standard
should have notes about that seems debatable since it does say that
for heap sort but not for quick sort (sort).

I hope this makes more sense than my prior tirade.

John


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






Author: Valentin Bonnard <Bonnard.V@wanadoo.fr>
Date: 1999/09/27
Raw View
Markus Mauhart wrote:

> But IF "priority queue" is NOT a commonly agreed term outside standard c++
> with semantic as outlined in standard c++, then I would consider the
> current description of "priotity_queue" in the standard as a defect

s/description/name/

If the name is inadequate, change the name, not the
semantic.

Anyway you are coming a bit late for changing names of
standard components (which would break code).

NAD, definitely

[ moderator's note: "NAD" means Not A Defect". -sdc ]

--

Valentin Bonnard


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






Author: Valentin Bonnard <Bonnard.V@wanadoo.fr>
Date: 1999/09/27
Raw View
Markus Mauhart wrote:

> 25.3.6 [lib.alg.heap.operations] states two key properties of a heap [a,b),
> the first of them ..
> "(1) *a is the largest element"
>
> I think this is incorrect and should be
> (1) *a is part of the heaps largest equivalence-class, and no other
>   element in that class is 'older' than *a (X is older than *a, if *a
>   was added to the heap while X was yet part of the heap)
>
> Actually there are two independent changes:
> 1-"part of largest equivalence class" instead of "largest", cause 25.3
>   [lib.alg.sorting] asserts "strict weak ordering" for all its sub clauses.

I am happy w/ largest. Maybe larger or equal would be better.

IMHO ``part of largest equivalence class'' is overkill and
unclear (or is it because I am French ?): to me it means that
2 2 3 is a heap because {3, 3} has more elements (2 exactly)
than {2} (which has 1).

> 2-Take 'an oldest' from that equivalence class, otherwise the heap functions
>   could not be used for a priorityqueue as explained in 23.2.3.2.2
>   [lib.priqueue.members] (where I assume that a "priority queue" respects
>   priority AND time).

No. This is a request for new feature, not a DR.

--

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





Author: "Dave Abrahams" <abrahams@mediaone.net>
Date: 1999/09/27
Raw View
In article <7sleo1$j0v$1@fleetstreet.Austria.EU.net> , "Markus Mauhart"
<mmauhart@ping.at> wrote:

> Is this a commonly
> agreed term (outside the c++ standard !) ? If yes, does it have the same
> semantics as defined in the c++ standard ?

Yes and yes. I refer you to Knuth.

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





Author: "Dave Abrahams" <abrahams@mediaone.net>
Date: 1999/09/25
Raw View
In article <7seop1$ji7$1@fleetstreet.Austria.EU.net> , "Markus Mauhart"
<mmauhart@ping.at> wrote:

> Actually there are two independent changes:
> 1-"part of largest equivalence class" instead of "largest", cause 25.3
>   [lib.alg.sorting] asserts "strict weak ordering" for all its sub clauses.

This change makes sense, and is more precise than the wording in the
standard.

> 2-Take 'an oldest' from that equivalence class, otherwise the heap functions
>   could not be used for a priorityqueue as explained in 23.2.3.2.2
>   [lib.priqueue.members] (where I assume that a "priority queue" respects
>   priority AND time).

A priority queue doesn't "respect time", just priority. If you want you can
include time in your notion of priority; then you'll get the behavior you're
looking for.


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






Author: jpotter@falcon.lhup.edu (John Potter)
Date: 1999/09/25
Raw View
On 24 Sep 1999 16:21:01 GMT, "Markus Mauhart" <mmauhart@ping.at> wrote:

: [ moderator's note: forwarded to the C++ committee for handling. -sdc ]

Data Structures 101: A heap is a partially ordered complete binary tree.
---------------------------------^^^^^^^^^

: 25.3.6 [lib.alg.heap.operations] states two key properties of a heap [a,b),
: the first of them ..
: "(1) *a is the largest element"
:
: I think this is incorrect and should be
: (1) *a is part of the heaps largest equivalence-class,

Then it is one of the largest elements; thus, an example of the
largest element, and as good as any other.

: and no other
:   element in that class is 'older' than *a (X is older than *a, if *a
:   was added to the heap while X was yet part of the heap)

Sorry, a heap is not a chronologically ordered collection.

: Actually there are two independent changes:
: 1-"part of largest equivalence class" instead of "largest", cause 25.3
:   [lib.alg.sorting] asserts "strict weak ordering" for all its sub clauses.

Therefor, any one of them is as good as any other.  It is largest.

: 2-Take 'an oldest' from that equivalence class, otherwise the heap functions
:   could not be used for a priorityqueue as explained in 23.2.3.2.2
:   [lib.priqueue.members] (where I assume that a "priority queue" respects
:   priority AND time).

Your assumptions on priority are correct.  Your assumptions on time
are absurd.

I refer you to comp.lamg.c++.moderated for ways to make the standard
priority queue time sensitive.  If you wish to make a heap based
priority queue time sensitive, you must make your data time sensitive
and provide the appropriate comparison operator.  There are
alternatives to a heap based priority queue.  The thread is labeled
priority-queue.

I have no comprension of why one would consider a heap improper
when it did not respect time.  Time is simply not a compatable
factor in the partial ordering of a heap.  Period!

Any attempt to change the properties of a heap would make it
something other than a heap and lose all of the advantages of
that data structure.

IMO, this DR is a total absurdity.

John


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






Author: "Markus Mauhart" <mmauhart@ping.at>
Date: 1999/09/24
Raw View

[ moderator's note: forwarded to the C++ committee for handling. -sdc ]

25.3.6 [lib.alg.heap.operations] states two key properties of a heap [a,b),
the first of them ..
"(1) *a is the largest element"

I think this is incorrect and should be
(1) *a is part of the heaps largest equivalence-class, and no other
  element in that class is 'older' than *a (X is older than *a, if *a
  was added to the heap while X was yet part of the heap)

Actually there are two independent changes:
1-"part of largest equivalence class" instead of "largest", cause 25.3
  [lib.alg.sorting] asserts "strict weak ordering" for all its sub clauses.
2-Take 'an oldest' from that equivalence class, otherwise the heap functions
  could not be used for a priorityqueue as explained in 23.2.3.2.2
  [lib.priqueue.members] (where I assume that a "priority queue" respects
  priority AND time).



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