Priority Queues in Visual Studio 6.0

[Der Andere]

Are priority queues implemented in the STL in Visual Studio 6? If no, which
is the easiest way to simulate them? Multisets?
BTW: The container contains pointers to instances of a class. The ordering
of the elements must follow the value of the class-instances not the value
of the pointers. Furthermore, elements are inserted throughout execution of
the program so I need a insert function which keeps the elements sorted; a
sort function which sorts the whole container after every insertion is not
sufficient (and surely not efficient).

Regards,
Matthias

[P.J. Plauger]

"Der Andere" <ma**************@gmx.net> wrote in message
news:c9*************@news.t-online.com...

Are priority queues implemented in the STL in Visual Studio 6? If no, which is the easiest way to simulate them? Multisets?
BTW: The container contains pointers to instances of a class. The ordering
of the elements must follow the value of the class-instances not the value
of the pointers. Furthermore, elements are inserted throughout execution of the program so I need a insert function which keeps the elements sorted; a
sort function which sorts the whole container after every insertion is not
sufficient (and surely not efficient).

See template class priority_queue in the header <queue>. You'll
have to supply an ordering predicate that takes two pointers
and returns true when one of the designated objects is ordered
before the other, but that shouldn't be hard. The queue stores
the pointers in a random-access container, which it maintains
as a heap. Pushing new items on the heap and popping the highest
priority items off the heap each take log(N) percolations, where
N is the total size of the heap (queue). Hard to do better.

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

[Der Andere]

> > Are priority queues implemented in the STL in Visual Studio 6? If no,

which

is the easiest way to simulate them? Multisets?
BTW: The container contains pointers to instances of a class. The ordering of the elements must follow the value of the class-instances not the value of the pointers. Furthermore, elements are inserted throughout execution

of

the program so I need a insert function which keeps the elements sorted; a sort function which sorts the whole container after every insertion is not sufficient (and surely not efficient).

See template class priority_queue in the header <queue>. You'll
have to supply an ordering predicate that takes two pointers
and returns true when one of the designated objects is ordered
before the other, but that shouldn't be hard. The queue stores
the pointers in a random-access container, which it maintains
as a heap. Pushing new items on the heap and popping the highest
priority items off the heap each take log(N) percolations, where
N is the total size of the heap (queue). Hard to do better.

Written by you. Nice to have people around who know quite well what they are
talking about ;-)))

Cheers,
Matthias

[Dietmar Kuehl]

Der Andere wrote:

Written by you. Nice to have people around who know quite well what they
are talking about ;-)))

Well, a d-heap is not that hard to write anyway... It is more interesting
to write heaps with modifiable priority. Although a d-heap operators quite
good there, too, the theoretical best implementation is a Fibonacci-heap
which is a little bit harder to implement.
--
<mailto:di***********@yahoo.com> <http://www.dietmar-kuehl.de/>
<http://www.contendix.com> - Software Development & Consulting

[Der Andere]

> > Are priority queues implemented in the STL in Visual Studio 6? If no,

which

is the easiest way to simulate them? Multisets?
BTW: The container contains pointers to instances of a class. The ordering of the elements must follow the value of the class-instances not the value of the pointers. Furthermore, elements are inserted throughout execution of

the program so I need a insert function which keeps the elements sorted; a sort function which sorts the whole container after every insertion is not sufficient (and surely not efficient).

See template class priority_queue in the header <queue>. You'll
have to supply an ordering predicate that takes two pointers
and returns true when one of the designated objects is ordered
before the other, but that shouldn't be hard.

The following sample program does not compile but I have no idea what to do
about it. Might be a beginner's fault. If I substitute pv(comp()) with
pv(std::less<Vertex*>()) the compiler gives no error, but I strongly suppose
less() would order the elements according to the address value of the
pointer.

#include <queue>

struct Vertex
{
int a;
};

bool comp (Vertex* v1, Vertex* v2)
{
return v1->a < v2->a;
}

int main()
{
std::priority_queue<Vertex*> pv(comp());
return 0;
}
Regards,
Matthias

the pointers in a random-access container, which it maintains
as a heap. Pushing new items on the heap and popping the highest
priority items off the heap each take log(N) percolations, where
N is the total size of the heap (queue). Hard to do better.

[Der Andere]

> > Written by you. Nice to have people around who know quite well what they

are talking about ;-)))

Well, a d-heap is not that hard to write anyway... It is more interesting
to write heaps with modifiable priority. Although a d-heap operators quite
good there, too, the theoretical best implementation is a Fibonacci-heap
which is a little bit harder to implement.

Yes, had a look on Fibonacci-heaps and decided not to take another before
next year ;-)

Regards,
Matthias

[Dietmar Kuehl]

Der Andere wrote:

bool comp (Vertex* v1, Vertex* v2)
{
return v1->a < v2->a;
}

int main()
{
std::priority_queue<Vertex*> pv(comp());

There are two things which are wrong with the above code:
- The type of the comparator is part of the priority queue's type.
That is, the type in the above line would read something like
this:

std::priority_queue<Vertex*, std::vector<Vertex*>,
bool(*)(Vertex*, Vertex*)>

- 'comp' is a function, not a type. To pass 'comp' to a function
like the constructor you just use 'comp':

pv(comp)

Of course, 'std::less<Vertex*>' would indeed compare the pointer
values.

Since you apparently want to use your priority queue with a graph,
you might want to use a priority queue allowing changing a nodes
priority. 'std::priority_queue' does not allow this. I have a
made a collection of priority queues publically available, some of
which allow this (e.g. the Fibonacci-heap and a specialized d-heap
implementation). These can be downloaded from
<http://www.dietmar-kuehl.de/heaps.tar.gz>.
--
<mailto:di***********@yahoo.com> <http://www.dietmar-kuehl.de/>
<http://www.contendix.com> - Software Development & Consulting