Hi,
In article <B5B95B44.7913%nospam@nospam.com>,
  Chip Jarred <nospam@nospam.com> wrote:
> Of course, the other option is to implement your own priority queue.

A variation on this is to get the priority queues from
<http://www.boost.org/>: There are several different classes allowing
changes in the priority. I think they are pretty fast. They use data
structures specifically designed for this purpose. The best ones are
Fibonacci heaps and a variation on d-heaps where elements can be
located efficiently by keeping an array with their current positions
around.
--
<mailto:dietmar_kuehl@yahoo.com>
<http://www.dietmar-kuehl.de/>


Sent via Deja.com http://www.deja.com/
Before you buy.

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

I have another possible solution that I think should work for any situation
where you'd put object pointers (as opposed to objects themselves) in the
queue.  It's a bit of a kludge, but better than popping elements off until
you get to the one you want to change.

What I might suggest is rather than stuffing raw pointers into the
priority_queue, wrap the pointer in an object which allows you to mark the
pointer as active or not.  To reprioritize a given item, you disable it via
the wrapper class, which doesn't change the queue, and then add a new,
enabled wrapper object.  When you pop a disabled object from the queue, just
ignore it.  Of course, this doesn't solve the problem of finding the nth
element, but assuming you have a reference to the object you want to change,
this technique would let you change the priority without breaking the
priority queue.  Obviously if you do a lot of priority changing relative to
the rate at which you pop elements out of the queue, then this will use an
increasing amount of memory and might not be acceptable, but if the changing
priority is relatively rare, this should be an adequate solution.

Of course, the other option is to implement your own priority queue.  The
easiest would be to have a vector which you sort every time you add an
element, or change a priority.

Actually another possibility would be to use a set instead of a
priority_queue.  I'll defer to those more knowledgeable than I, but I think
that sets guarantee that removing objects will remove them in an order
according to their key, which would effectively be a priority queue, but you
can also remove an arbitrary member from the set, change it's key (ie. it's
priority) and then re-add it.

Chip Jarred

in article 399264F3.F07492FA@elektron.its.tudelft.nl, Arjen van Rhijn at
arjen@elektron.its.tudelft.nl wrote on 8/10/00 11:31 AM:

>
> James Kuyper wrote:
>
>> Arjen van Rhijn wrote:
>>>
>>> Hi,
>>>
>>> If I use the priority queue of STL to hold a pair<int, object*>, is it
>>> possible to change the priority of an element if I have it's object*?
>>> That is, say we've got 8 elements in the queue, is it possible to change
>>> the priority of say the 5th element, so that the queue resorts? I could
>>> not find anything about it in the documentation I have.
>>
>> The behavior of std::priority_queue is defined entirely in terms of
>> make_heap(), push_heap() and pop_heap(). make_heap converts and iterator
>> range into a heap. The other two require that the iterator range they
>> work on is currently a valid heap, and they leave it as a heap
>> afterward. Therefore, you can't safely do anything to a
>> std::priority_queue's controlled sequence, or the objects it contains,
>> that would render it no longer a valid heap.
>> In particular, you can't change the priority of any element in the
>> std::priority_queue, since that's virtually guaranteed to make it no
>> longer a valid heap.
>>
>
> that's why I want it to re-sort.
>
>>
>> Thus, the only safe way you can change the priority of a heap element is
>> to pop() elements until you find the one you want to change, push() the
>> rest of them back on, change the one you want to change, and then push()
>> it back on too.
>>
>
> And wait forever for my program to finish? That's probably the worst way to
> solve this problem. I'm better of using my own priority queue class that does
> support changing priorities. I like STL, but I'm not gonna use it if there is
> a much faster way.
>
>>
>> Tricky alternative
>> ==================
>> Section 23.2.3.2p1 says that priority_queue<Container> has the following
>> member:
>>
>> protected:
>> Container c;
>>
>> and all operations are defined in terms of 'c'. If 'c' were declared
>> 'private', I would simple consider this as merely an example. However,
>> since it's declared as 'protected', I think that there's a deliberate
>> intent to allow derivation from std::priority_queue, and that derived
>> classes can count on the contained sequence as having the name 'c'.
>>
>> If so, a class derived from std::priority_queue could have a member
>> function which locates a specified element in 'c', change it's order,
>> then calls make_heap(c.begin(), c.end(), comp). That should do exactly
>> what you want.
>
> I'm not too sure about that one, maybe it's possible. I'll look into it.
>
> Arjen
>
>
> ---
> [ 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              ]
>

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

> Arjen van Rhijn wrote:
> >
> > Hi,
> >
> > If I use the priority queue of STL to hold a pair<int, object*>, is it
> > possible to change the priority of an element if I have it's object*?
> > That is, say we've got 8 elements in the queue, is it possible to change
> > the priority of say the 5th element, so that the queue resorts? I could
> > not find anything about it in the documentation I have.
>
> The behavior of std::priority_queue is defined entirely in terms of
> make_heap(), push_heap() and pop_heap(). make_heap converts and iterator
> range into a heap. The other two require that the iterator range they
> work on is currently a valid heap, and they leave it as a heap
> afterward. Therefore, you can't safely do anything to a
> std::priority_queue's controlled sequence, or the objects it contains,
> that would render it no longer a valid heap.
> In particular, you can't change the priority of any element in the
> std::priority_queue, since that's virtually guaranteed to make it no
> longer a valid heap.
>

that's why I want it to re-sort.

>
> Thus, the only safe way you can change the priority of a heap element is
> to pop() elements until you find the one you want to change, push() the
> rest of them back on, change the one you want to change, and then push()
> it back on too.
>

And wait forever for my program to finish? That's probably the worst way to
solve this problem. I'm better of using my own priority queue class that does
support changing priorities. I like STL, but I'm not gonna use it if there is
a much faster way.

>
> Tricky alternative
> ==================
> Section 23.2.3.2p1 says that priority_queue<Container> has the following
> member:
>
>         protected:
>                 Container c;
>
> and all operations are defined in terms of 'c'. If 'c' were declared
> 'private', I would simple consider this as merely an example. However,
> since it's declared as 'protected', I think that there's a deliberate
> intent to allow derivation from std::priority_queue, and that derived
> classes can count on the contained sequence as having the name 'c'.
>
> If so, a class derived from std::priority_queue could have a member
> function which locates a specified element in 'c', change it's order,
> then calls make_heap(c.begin(), c.end(), comp). That should do exactly
> what you want.

I'm not too sure about that one, maybe it's possible. I'll look into it.

Arjen


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

If I use the priority queue of STL to hold a pair<int, object*>, is it
possible to change the priority of an element if I have it's object*?
That is, say we've got 8 elements in the queue, is it possible to change
the priority of say the 5th element, so that the queue resorts? I could
not find anything about it in the documentation I have.

Thanks in advance,

Arjen


---
[ 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 Tue,  8 Aug 2000 17:11:03 GMT, Arjen van Rhijn
<arjen@elektron.its.tudelft.nl> wrote:

>Hi,
>
>If I use the priority queue of STL to hold a pair<int, object*>, is it
>possible to change the priority of an element if I have it's object*?
>That is, say we've got 8 elements in the queue, is it possible to change
>the priority of say the 5th element, so that the queue resorts? I could
>not find anything about it in the documentation I have.

Not with the standard library priority queue- it is not modifiable,
but there is a good implementation of a Fibonacci heap in the boost
library that has a change( ) member function. (see www.boost.org).

,Brian Parker
(brianp@research.canon.com.au)

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

Arjen van Rhijn wrote:
>
> Hi,
>
> If I use the priority queue of STL to hold a pair<int, object*>, is it
> possible to change the priority of an element if I have it's object*?
> That is, say we've got 8 elements in the queue, is it possible to change
> the priority of say the 5th element, so that the queue resorts? I could
> not find anything about it in the documentation I have.

The behavior of std::priority_queue is defined entirely in terms of
make_heap(), push_heap() and pop_heap(). make_heap converts and iterator
range into a heap. The other two require that the iterator range they
work on is currently a valid heap, and they leave it as a heap
afterward. Therefore, you can't safely do anything to a
std::priority_queue's controlled sequence, or the objects it contains,
that would render it no longer a valid heap.
In particular, you can't change the priority of any element in the
std::priority_queue, since that's virtually guaranteed to make it no
longer a valid heap.

Thus, the only safe way you can change the priority of a heap element is
to pop() elements until you find the one you want to change, push() the
rest of them back on, change the one you want to change, and then push()
it back on too.

Tricky alternative
==================
Section 23.2.3.2p1 says that priority_queue<Container> has the following
member:

 protected:
  Container c;

and all operations are defined in terms of 'c'. If 'c' were declared
'private', I would simple consider this as merely an example. However,
since it's declared as 'protected', I think that there's a deliberate
intent to allow derivation from std::priority_queue, and that derived
classes can count on the contained sequence as having the name 'c'.

If so, a class derived from std::priority_queue could have a member
function which locates a specified element in 'c', change it's order,
then calls make_heap(c.begin(), c.end(), comp). That should do exactly
what you want.

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