1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
|
<HTML><HEAD>
<!!---------------------------------------------------------------------->
<!! Copyright (C) 1999 Dietmar Kuehl, Claas Solutions GmbH >
<!!>
<!! Permission to use, copy, modify, distribute and sell this >
<!! software for any purpose is hereby granted without fee, provided >
<!! that the above copyright notice appears in all copies and that >
<!! both that copyright notice and this permission notice appear in >
<!! supporting documentation. Dietmar Kuehl and Claas Solutions make no >
<!! representations about the suitability of this software for any >
<!! purpose. It is provided "as is" without express or implied warranty. >
<!!---------------------------------------------------------------------->
<TITLE>mfd/p_queue.3</TITLE>
</HEAD>
<BODY BGCOLOR=white LINK="0000FF" VLINK="800080">
<IMG SRC=../../c++boost.gif ALIGN=TOP WIDTH=277 HEIGHT=86><BR>
<TABLE BORDER=0 CELLSPACING=0 CELLPADDING=0 COLS=2>
<TR><TD WIDTH=109 VALIGN=TOP><IMG SRC=sidebar.jpg WIDTH=109 HEIGHT=494>
</TD><TD>
<SPACER TYPE=VERTICAL SIZE=40>
<H1>Template Class <nobr><tt>priority_queue<T, Cont, Comp></tt></nobr></H1>
<A NAME="Synopsis"><H1>Synopsis</H1></A>
<TABLE BORDER=0 CELLSPACING=0 CELLPADDING=0 COLS=2>
<TR><TD WIDTH=30 VALIGN=TOP></TD><TD>
<PRE>
#include "boost/p_queue.hpp"
template <class T,
class Cont = std::vector<T>,
class Comp = std::less<typename Cont::value_type> >
class boost::priority_queue
{
public:
typedef typename Cont::value_type <A HREF="heap-common.html#value_type">value_type</A>;
typedef typename Cont::size_type <A HREF="heap-common.html#size_type">size_type</A>;
typedef Cont container_type;
typedef typename Cont::reference reference;
typedef typename Cont::const_reference <A HREF="heap-common.html#const_reference">const_reference</A>;
typedef typename Cont::iterator iterator;
typedef typename Cont::const_iterator <A HREF="heap-common.html#const_iterator">const_iterator</A>;
explicit <A HREF="heap-common.html#default-ctor">priority_queue</A>(Comp const& comp = Comp());
bool <A HREF="heap-common.html#empty">empty</A>() const;
size_type <A HREF="heap-common.html#size">size</A>() const;
const_reference <A HREF="heap-common.html#top">top</A>() const;
void <A HREF="heap-common.html#push">push</A>(const_reference val);
void <A HREF="heap-common.html#pop">pop</A>();
void <A HREF="heap-common.html#change_top">change_top</A>(const_reference val);
const_iterator <A HREF="heap-common.html#begin">begin</A>() const;
const_iterator <A HREF="heap-common.html#end">end</A>() const;
};
</PRE></TD></TABLE>
<A NAME="Description"><H1>Description</H1></A>
The template class <nobr><tt>priority_queue</tt></nobr> is a replacement for the standard template
class <nobr><tt>std::priority_queue</tt></nobr>. It has a slightly extended interface, namely the
methods <nobr><tt><A HREF="heap-common.html#begin">begin</A>()</tt></nobr> and
<nobr><tt><A HREF="heap-common.html#begin">end</A>()</tt></nobr> to get access to all elements
currently
stored in the priority queue and the method
<nobr><tt><A HREF="heap-common.html#begin">change_top</A>()</tt></nobr> which is used for efficient
modification of the largest element's priority.
<P>
The basic method to maintain the internal data structure is identical to that
of <A HREF="d_heap.html">d-heaps</A> but for <nobr><tt>priority_queue</tt></nobr> the elements
inserted into the priority queue are kept in the array. Thus, these are
swapped. However, this removes the need to maintain a mapping between the
elements in the heap and their position resulting a huge performance boost.
On the other hand, this remove the possibility to change the priority of
an arbitrary element because the elements cannot be found efficiently in the
priority queue. If you never need to change the priority of an
element except for the largest element this class is probably suitable.
If you need only the methods also present for <nobr><tt>std::priority_queue</tt></nobr>
you should probably stick to the standard class...
<P>
For a description of the methods of <nobr><tt>priority_queue<T, Cont, Comp></tt></nobr> see the
description of <A HREF="heap-common.html">common methods</A>.
<A NAME="See Also"><H1>See Also</H1></A>
<A HREF="heap.html">heap(3)</A>,
<A HREF="heap-common.html">heap-common(3)</A>
<HR>
Copyright © 1999 <A HREF=http://www.claas-solutions.de/kuehl>Dietmar Kühl</A> (<A HREF="mailto:dietmar.kuehl@claas-solutions.de">dietmar.kuehl@claas-solutions.de</A>)<BR>
<a href="http://www.claas-solutions.de/">Claas Solutions GmbH</a>
</TD></TR></TABLE>
</BODY></HTML>
|
