James Kuyper <kuyper@wizard.net> wrote:
: James Kuyper wrote:
:> Don Montgomery wrote:
:> > On 3 Jul 1998, Don Montgomery wrote:
:> > !Hi, does anyone know the (a) good way to do a linear
:> > !(or, for that matter, a random access) search on PQs
:> > !in STL?

:> > Let me re-phrase: is it possible/how do you do it: get an
:> > iterator returned from a
:> >
:> > priority-queue<vector<user-defined-type> >?
:> >
:> > (Purpose: to check for non-key flag fields in an event list,
:> > with the possibility of User-defined-type deletion from the
:> > priority-queue, or perhaps just setting an `invalid flag.')
:>
[snip]
: is, it can't be a reverse-sorted list. I conclude that it is
: unambiguously unsafe to remove arbitrary elements from 'c'. Flagging bad
: elements should still work, however.

I was actually thinking of an operation `wipe-it()' which would (a) remove
the `bad' element from the heap (in O(n) time for vector, O(1) time for
deque), and (b) do make_heap on what was left to restore heap properties
(in O(n) time). This would not be too bad, if wipe-it() was called
infrequently. I'm staring at it to try to discover where the trade-off is
between (1) doing that, (2) keeping a flag list (i.e., not even doing any
search, just doing a condition check for each event that is popped), and
(3) searching out events, but not deleting them, just marking them to be
discarded as encountered. I guess I need to get further into
implementation (and cases!) to get a feeling for what's best (in my
case!).

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              ]

On 3 Jul 1998, Don Montgomery wrote:
!Hi, does anyone know the (a) good way to do a linear
!(or, for that matter, a random access) search on PQs
!in STL?
!

Let me re-phrase: is it possible/how do you do it: get an
iterator returned from a

priority-queue<vector<user-defined-type> >?

(Purpose: to check for non-key flag fields in an event list,
with the possibility of User-defined-type deletion from the
priority-queue, or perhaps just setting an `invalid flag.')

Thanks,

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              ]

Don Montgomery <montgo@utdallas.edu> wrote in article <Pine.GSO.3.96.980706105514.25685C-100000@apache.utdallas.edu>...
> On 3 Jul 1998, Don Montgomery wrote:
> !Hi, does anyone know the (a) good way to do a linear
> !(or, for that matter, a random access) search on PQs
> !in STL?
>
> Let me re-phrase: is it possible/how do you do it: get an
> iterator returned from a
>
> priority-queue<vector<user-defined-type> >?
>
> (Purpose: to check for non-key flag fields in an event list,
> with the possibility of User-defined-type deletion from the
> priority-queue, or perhaps just setting an `invalid flag.')

You can't get an iterator that lets you walk through a priority_queue.
By design, it is a container adapter with a limited repertory of
operations defined, to protect the abstraction.

Sounds like what you want may be a map. It's kept in order,
and you can walk the sequence with iterators, erasing as your
heart desires.

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              ]

Don Montgomery <montgo@utdallas.edu> wrote:
>On 3 Jul 1998, Don Montgomery wrote:
>!Hi, does anyone know the (a) good way to do a linear
>!(or, for that matter, a random access) search on PQs
>!in STL?

All the code for std::priority_queue fits on a page.  If it's not
exactly what you want, why not implement exactly what you want?
std::priority_queue is just an example of a container adapter.

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

James Kuyper wrote:
>
> Don Montgomery wrote:
> >
> > On 3 Jul 1998, Don Montgomery wrote:
> > !Hi, does anyone know the (a) good way to do a linear
> > !(or, for that matter, a random access) search on PQs
> > !in STL?
> > !
> >
> > Let me re-phrase: is it possible/how do you do it: get an
> > iterator returned from a
> >
> > priority-queue<vector<user-defined-type> >?
> >
> > (Purpose: to check for non-key flag fields in an event list,
> > with the possibility of User-defined-type deletion from the
> > priority-queue, or perhaps just setting an `invalid flag.')
>
> priority-queue<T, Container> doesn't provide a publicly accessible way
> to get an iterator to its contents. However, the standard does specify
> that is has a protected member 'c' of type 'Container', which presumably
> contains the elements of the queue. However, the standard gives no
> details about 'c'; it may even be intended merely as an example of a
> typical implementation detail.

I was asleep yesterday; I publicly admitted to it :-{ I'm awake this
morning, and I see that the Effects portions of the priority_queue
members' descriptions specify exactly how 'c' is used, in terms of
make_heap(), push_heap(), and pop_heap(). What those heap functions do
is described only in a fairly elliptical fashion; the details are
implied by the complexity requirements.

> To get access to 'c', you'd have to derive from priority-queue<>, and
> add functions to give public access to the iterator members of 'c'. Is
> that feasible for your application?
> I wouldn't recommend direct deletion of elements of 'c'; you know
> nothing about how it is used by priority_queue<>.

'c' is required to be a heap. One of the requirements for a heap is that
its first element is always the largest element in the heap. If you
remove the first n elements, that property will remain true only if 'c'
is a reverse-sorted list. However, the second property of a heap is that
pop_heap() must be able to remove the first element in O(log N) time.
There's no way to do this with a reverse-sorted list, so whatever a heap
is, it can't be a reverse-sorted list. I conclude that it is
unambiguously unsafe to remove arbitrary elements from 'c'. Flagging bad
elements should still work, however.


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

Thanks, P.J. and James. I like both suggestions, but for now I am inclined
toward the map option. As time permits (god, that sounds feeble!) I will
explore inheritance and extension of priority_queue for conditional-event
lists. If I can still remember by then, I'll post an offer to send source
for the new creature.

Thanks again,

Don


[ 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, does anyone know the (a) good way to do a linear
(or, for that matter, a random access) search on PQs
in STL?

Thanks,

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