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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
|
// -*- mode: c++; mode: visual-line; mode: flyspell; fill-column: 100000 -*-
/***************************************************************************
* doc/tutorial_pqueue.dox
*
* Usage Tutorial for STXXL
*
* Part of the STXXL. See http://stxxl.sourceforge.net
*
* Copyright (C) 2013 Timo Bingmann <tb@panthema.net>
*
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
**************************************************************************/
namespace stxxl {
/** \page tutorial_pqueue STXXL Priority Queue
This page introduces into the stxxl::priority_queue container (to learn more about the structure of stxxl::priority_queue, see section \ref design_pqueue).
Basically, the priority queue provides insertion of new elements as well as access and deletion of the element on top.
The invariant guarantees that the top element is the largest (or smallest if desired) of all inserted elements identified by comparison realized by the customizable comparator class.
### Creating a STXXL priority queue
To manage the configuration of the priority queue type, we use the generator template stxxl::PRIORITY_QUEUE_GENERATOR. This generator template expects a value type (which is an integer in our example),
a class which we name Comparator(a,b) to compare two given elements a and b, a internal memory limit in bytes and the number of elements to be stored (in 1024 units). See section \ref design_pqueue_generator for additional configuration parameters and information.
Thus the definition may look as follows:
\code
// template parameter <value_type, CompareType, internal_memory_limit, number_of_elements>
typedef stxxl::PRIORITY_QUEUE_GENERATOR<int, ComparatorGreater, 64*1024*1024, 1024*1024>::result pqueue_type;
\endcode
The ComparatorGreater(a,b) class is needed to compare two given elements a and b and has to be defined by hand (and before the priority queue definition above):
\code
struct ComparatorGreater
{
bool operator () (const int &a, const int &b) const
{ return (a > b); }
int min_value() const
{ return std::numeric_limits<int>::max(); }
};
\endcode
The compare-operator () of two elements a and b returns true, if a is larger than b, otherwise false. Consequently, this priority queue serves it's <b> smallest element on top </b>. The additional min_value() function ensures that Comparator(min_value(),x) is true for each and every x.
iLikewise the minimum-on-top Comparator, we can easily define a <b> largest element on top </b> Comparator which stores the the largest contained integer on top as well:
\code
struct ComparatorLess
{
bool operator () (const int & a, const int & b) const
{ return a<b; }
int min_value() const
{ return std::numeric_limits<int>::min(); }
};
\endcode
Note that CompareType must define a strict weak ordering. These and some other details are available in the Notes part of \ref design_pqueue_generator
To create a STXXL priority queue instance, a resizable buffered writing and prefetched reading pool (to overlap I/O and computation) is needed:
\code
typedef pqueue_type::block_type block_type;
const unsigned int mem_for_pools = 16 * 1024 * 1024; // restricts memory consumption of the pools
stxxl::read_write_pool<block_type> pool((mem_for_pools / 2) / block_type::raw_size, (mem_for_pools / 2) / block_type::raw_size);
pqueue_type my_pqueue(pool); // creates priority queue object with read-write-pool
\endcode
### Insert / Access / Delete elements
To insert a new element into the priority queue, call push():
\code
my_pqueue.push(5);
\endcode
The priority queue only allows to access the top element, which is the smallest or largest element (depending on the used comparator class) of all inserted elements.
Calling top() on an instance returns this element:
\code
int x;
x = my_pqueue.top();
\endcode
Erasing elements is only possible on the top of the priority queue by calling pop().
Note that after removing the element on top, the priority queue still holds the above mentioned property.
\code
my_pqueue.pop();
\endcode
### Determine size / Check whether the priority queue is empty
To determine the size (i.e. the number of elements) of an instance, call size():
\code
std::cout << "priority queue stores: " << my_pqueue.size() << " elements" << std::endl;
\endcode
To check if the priority queue is empty, call empty() which returns true in case:
\code
std::cout << "empty priority queue? " << my_pqueue.empty() << std::endl;
\endcode
### A minimal working example of STXXL's priority queue
(See \ref examples/containers/pqueue1.cpp for the sourcecode of the following example).
\snippet examples/containers/pqueue1.cpp example
See \ref examples/containers/pqueue2.cpp for the sourcecode of another small example.
\example examples/containers/pqueue1.cpp
This example code is explained in the \ref tutorial_pqueue section
\example examples/containers/pqueue2.cpp
This example code is explained in the \ref tutorial_pqueue section
*/
} // namespace stxxl
|
