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
|
The ti(priority_queue) class implements a i(priority queue data structure).
Before using a tt(priority_queue) container the tthi(queue) header file must
have been included.
A priority queue is identical to a tt(queue), but allows the entry of data
elements according to emi(priority rules). A real-life priority queue is
found, e.g., at airport check-in terminals. At a terminal the passengers
normally stand in line to wait for their turn to check in, but late passengers
are usually allowed to jump the queue: they receive a higher priority than
other passengers.
The priority queue uses tt(operator<) of the data type stored in the
priority queue to decide about the priority of the data elements. The
em(smaller) the value, the em(lower) the priority. So, the priority queue
em(could) be used to sort values while they arrive. A simple example of such
a priority queue application is the following program: it reads words from
tt(cin) and writes a sorted list of words to tt(cout):
verbinclude(-a examples/prioritywords1.cc)
Unfortunately, the words are listed in reversed order: because of the
underlying tt(<)-operator the words appearing later in the i(ASCII)-sequence
appear first in the priority queue. A solution to that problem is to define a
em(wrapper class) around the tt(string) datatype, reversing tt(string)'s
tt(operator<). Here is the modified program:
verbinclude(-a examples/prioritywords2.cc)
Other possibilities to achieve the same exist. One would be to store the
content of the priority queue in, e.g., a vector, from which the elements can
be read in reversed order.
The following constructors, operators, and member functions are available
for the tt(priority_queue) container:
itemization(
it() hi(priority_queue) Constructors:
itemization(
it() The copy and move constructors are available;
it() A tt(priority_queue) may be constructed empty:
verb(priority_queue<string> object;)
)
it() The tt(priority_queue) only supports the basic operators of
containers.
it() The following i(member functions) are available for priority queues:
itemization(
ithtq(empty)(bool empty())(returns tt(true) if the
priority queue contains no elements.)
ithtq(pop)(void pop())(removes the element at the top of the priority
queue. Note that the element is em(not) returned by this member. As with the
tt(queue) avoid calling this member on an empty priority queue (cf. section
ref(QUEUE).))
ithtq(push)(void push(value))(inserts tt(value) at the
appropriate position in the priority queue.)
ithtq(size)(size_t size())(returns the number of elements
in the priority queue.)
ithtq(top)(Type &top())(returns a reference to the first
element of the priority queue. It is the
responsibility of the programmer to use the member only if the priority
queue is not empty.)
)
)
Note that the priority queue does not support iterators or an index
operator. The only element that can be accessed is its top element. A
priority queue can be emptied by:
itemization(
it() repeatedly removing its top element;
it() assigning an empty queue using the same data type to it;
it() having its destructor called.
)
|
