STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
stxxl::addressable_priority_queue< KeyType, PriorityType, Cmp > Class Template Reference

Detailed Description

template<typename KeyType, typename PriorityType, class Cmp = std::less<PriorityType>>
class stxxl::addressable_priority_queue< KeyType, PriorityType, Cmp >

An internal priority queue that allows removing elements addressed with (a copy of) themselves.

Template Parameters
KeyTypeType of contained elements.
PriorityTypeType of Priority.

Definition at line 112 of file addressable_queues.h.

+ Inheritance diagram for stxxl::addressable_priority_queue< KeyType, PriorityType, Cmp >:

Classes

struct  cmp
 

Public Types

typedef meta_iterator handle
 Type of handle to an entry. For use with insert and remove. More...
 

Public Member Functions

 addressable_priority_queue ()
 Create an empty queue. More...
 
 ~addressable_priority_queue ()
 
bool empty () const
 Check if queue is empty. More...
 
bool erase (const KeyType &e)
 Erase element from the queue. More...
 
void erase (handle i)
 Erase element from the queue. More...
 
std::pair< handle, bool > insert (const KeyType &e, const PriorityType o)
 Insert new element. If the element is already in, it's priority is updated. More...
 
KeyType pop ()
 Remove top (= min) element from the queue. More...
 
const KeyType & top () const
 Access top (= min) element in the queue. More...
 

Private Types

typedef container_type::iterator container_iterator
 
typedef std::set< std::pair
< PriorityType, KeyType >, cmp
container_type
 
typedef meta_type::iterator meta_iterator
 
typedef std::map< KeyType,
container_iterator
meta_type
 

Private Attributes

meta_type meta
 
container_type vals
 

Member Typedef Documentation

template<typename KeyType, typename PriorityType, class Cmp = std::less<PriorityType>>
typedef container_type::iterator stxxl::addressable_priority_queue< KeyType, PriorityType, Cmp >::container_iterator
private

Definition at line 126 of file addressable_queues.h.

template<typename KeyType, typename PriorityType, class Cmp = std::less<PriorityType>>
typedef std::set<std::pair<PriorityType, KeyType>, cmp> stxxl::addressable_priority_queue< KeyType, PriorityType, Cmp >::container_type
private

Definition at line 125 of file addressable_queues.h.

template<typename KeyType, typename PriorityType, class Cmp = std::less<PriorityType>>
typedef meta_iterator stxxl::addressable_priority_queue< KeyType, PriorityType, Cmp >::handle

Type of handle to an entry. For use with insert and remove.

Definition at line 135 of file addressable_queues.h.

template<typename KeyType, typename PriorityType, class Cmp = std::less<PriorityType>>
typedef meta_type::iterator stxxl::addressable_priority_queue< KeyType, PriorityType, Cmp >::meta_iterator
private

Definition at line 128 of file addressable_queues.h.

template<typename KeyType, typename PriorityType, class Cmp = std::less<PriorityType>>
typedef std::map<KeyType, container_iterator> stxxl::addressable_priority_queue< KeyType, PriorityType, Cmp >::meta_type
private

Definition at line 127 of file addressable_queues.h.

Constructor & Destructor Documentation

template<typename KeyType, typename PriorityType, class Cmp = std::less<PriorityType>>
stxxl::addressable_priority_queue< KeyType, PriorityType, Cmp >::addressable_priority_queue ( )
inline

Create an empty queue.

Definition at line 138 of file addressable_queues.h.

template<typename KeyType, typename PriorityType, class Cmp = std::less<PriorityType>>
stxxl::addressable_priority_queue< KeyType, PriorityType, Cmp >::~addressable_priority_queue ( )
inline

Definition at line 139 of file addressable_queues.h.

Member Function Documentation

template<typename KeyType, typename PriorityType, class Cmp = std::less<PriorityType>>
bool stxxl::addressable_priority_queue< KeyType, PriorityType, Cmp >::empty ( ) const
inline

Check if queue is empty.

Returns
If queue is empty.

Definition at line 143 of file addressable_queues.h.

template<typename KeyType, typename PriorityType, class Cmp = std::less<PriorityType>>
bool stxxl::addressable_priority_queue< KeyType, PriorityType, Cmp >::erase ( const KeyType &  e)
inline

Erase element from the queue.

Parameters
eElement to remove.
Returns
If element was in.

Definition at line 166 of file addressable_queues.h.

template<typename KeyType, typename PriorityType, class Cmp = std::less<PriorityType>>
void stxxl::addressable_priority_queue< KeyType, PriorityType, Cmp >::erase ( handle  i)
inline

Erase element from the queue.

Parameters
iIterator to element to remove.

Definition at line 178 of file addressable_queues.h.

template<typename KeyType, typename PriorityType, class Cmp = std::less<PriorityType>>
std::pair<handle, bool> stxxl::addressable_priority_queue< KeyType, PriorityType, Cmp >::insert ( const KeyType &  e,
const PriorityType  o 
)
inline

Insert new element. If the element is already in, it's priority is updated.

Parameters
eElement to insert.
oPriority of element.
Returns
pair<handle, bool> Iterator to element; if element was newly inserted.

Definition at line 150 of file addressable_queues.h.

template<typename KeyType, typename PriorityType, class Cmp = std::less<PriorityType>>
KeyType stxxl::addressable_priority_queue< KeyType, PriorityType, Cmp >::pop ( )
inline

Remove top (= min) element from the queue.

Returns
Top element.

Definition at line 191 of file addressable_queues.h.

template<typename KeyType, typename PriorityType, class Cmp = std::less<PriorityType>>
const KeyType& stxxl::addressable_priority_queue< KeyType, PriorityType, Cmp >::top ( ) const
inline

Access top (= min) element in the queue.

Returns
Const reference to top element.

Definition at line 186 of file addressable_queues.h.

Member Data Documentation

template<typename KeyType, typename PriorityType, class Cmp = std::less<PriorityType>>
meta_type stxxl::addressable_priority_queue< KeyType, PriorityType, Cmp >::meta
private

Definition at line 131 of file addressable_queues.h.

template<typename KeyType, typename PriorityType, class Cmp = std::less<PriorityType>>
container_type stxxl::addressable_priority_queue< KeyType, PriorityType, Cmp >::vals
private

Definition at line 130 of file addressable_queues.h.


The documentation for this class was generated from the following file: