stxxl::priority_queue_local::internal_priority_queue< ValueType, ContainerType, CompareType > Class Template Reference

Detailed Description

template<typename ValueType, typename ContainerType = std::vector<ValueType>, typename CompareType = std::less<ValueType>>
class stxxl::priority_queue_local::internal_priority_queue< ValueType, ContainerType, CompareType >

Similar to std::priority_queue, with the following differences:

• Maximum size is fixed at construction time, so an array can be used.
• Provides access to underlying heap, so (parallel) sorting in place is possible.
• Can be cleared "at once", without reallocation.

Definition at line 92 of file pq_helpers.h.

Inheritance diagram for stxxl::priority_queue_local::internal_priority_queue< ValueType, ContainerType, CompareType >:

Public Types
typedef CompareType	compare_type
typedef container_type::const_reference	const_reference
typedef ContainerType	container_type
typedef container_type::reference	reference
typedef container_type::size_type	size_type
typedef ValueType	value_type

Public Member Functions
	internal_priority_queue (size_type capacity)
	Default constructor creates no elements. More...
void	clear ()
	Remove all contained elements. More...
bool	empty () const
	Returns true if the queue is empty. More...
void	pop ()
	Removes first element. More...
void	push (const value_type &x)
	Add data to the queue. More...
size_type	size () const
	Returns the number of elements in the queue. More...
void	sort_to (value_type *target)
	Sort all contained elements, write result to target. More...
const_reference	top () const
	Returns a read-only (constant) reference to the data at the first element of the queue. More...

Protected Attributes
CompareType	comp
size_type	current_size
container_type	heap

Member Typedef Documentation

template<typename ValueType, typename ContainerType = std::vector<ValueType>, typename CompareType = std::less<ValueType>>

typedef CompareType stxxl::priority_queue_local::internal_priority_queue< ValueType, ContainerType, CompareType >::compare_type

Definition at line 97 of file pq_helpers.h.

template<typename ValueType, typename ContainerType = std::vector<ValueType>, typename CompareType = std::less<ValueType>>

typedef container_type::const_reference stxxl::priority_queue_local::internal_priority_queue< ValueType, ContainerType, CompareType >::const_reference

Definition at line 99 of file pq_helpers.h.

template<typename ValueType, typename ContainerType = std::vector<ValueType>, typename CompareType = std::less<ValueType>>

typedef ContainerType stxxl::priority_queue_local::internal_priority_queue< ValueType, ContainerType, CompareType >::container_type

Definition at line 96 of file pq_helpers.h.

template<typename ValueType, typename ContainerType = std::vector<ValueType>, typename CompareType = std::less<ValueType>>

typedef container_type::reference stxxl::priority_queue_local::internal_priority_queue< ValueType, ContainerType, CompareType >::reference

Definition at line 98 of file pq_helpers.h.

template<typename ValueType, typename ContainerType = std::vector<ValueType>, typename CompareType = std::less<ValueType>>

typedef container_type::size_type stxxl::priority_queue_local::internal_priority_queue< ValueType, ContainerType, CompareType >::size_type

Definition at line 100 of file pq_helpers.h.

template<typename ValueType, typename ContainerType = std::vector<ValueType>, typename CompareType = std::less<ValueType>>

typedef ValueType stxxl::priority_queue_local::internal_priority_queue< ValueType, ContainerType, CompareType >::value_type

Definition at line 95 of file pq_helpers.h.

Constructor & Destructor Documentation

template<typename ValueType, typename ContainerType = std::vector<ValueType>, typename CompareType = std::less<ValueType>>

stxxl::priority_queue_local::internal_priority_queue< ValueType, ContainerType, CompareType >::internal_priority_queue ( size_type  capacity )

inlineexplicit

Default constructor creates no elements.

Definition at line 111 of file pq_helpers.h.

Member Function Documentation

template<typename ValueType, typename ContainerType = std::vector<ValueType>, typename CompareType = std::less<ValueType>>

void stxxl::priority_queue_local::internal_priority_queue< ValueType, ContainerType, CompareType >::clear ( )

inline

Remove all contained elements.

Definition at line 179 of file pq_helpers.h.

template<typename ValueType, typename ContainerType = std::vector<ValueType>, typename CompareType = std::less<ValueType>>

bool stxxl::priority_queue_local::internal_priority_queue< ValueType, ContainerType, CompareType >::empty ( ) const

inline

Returns true if the queue is empty.

Definition at line 117 of file pq_helpers.h.

template<typename ValueType, typename ContainerType = std::vector<ValueType>, typename CompareType = std::less<ValueType>>

void stxxl::priority_queue_local::internal_priority_queue< ValueType, ContainerType, CompareType >::pop ( )

inline

Removes first element.

This is a typical queue operation. It shrinks the queue by one. The time complexity of the operation depends on the underlying container.

Note that no data is returned, and if the first element's data is needed, it should be retrieved before pop() is called.

Definition at line 163 of file pq_helpers.h.

template<typename ValueType, typename ContainerType = std::vector<ValueType>, typename CompareType = std::less<ValueType>>

void stxxl::priority_queue_local::internal_priority_queue< ValueType, ContainerType, CompareType >::push ( const value_type &  x )

inline

Add data to the queue.

Parameters

x	Data to be added.

This is a typical queue operation. The time complexity of the operation depends on the underlying container.

Definition at line 144 of file pq_helpers.h.

template<typename ValueType, typename ContainerType = std::vector<ValueType>, typename CompareType = std::less<ValueType>>

size_type stxxl::priority_queue_local::internal_priority_queue< ValueType, ContainerType, CompareType >::size ( ) const

inline

Returns the number of elements in the queue.

Definition at line 122 of file pq_helpers.h.

template<typename ValueType, typename ContainerType = std::vector<ValueType>, typename CompareType = std::less<ValueType>>

void stxxl::priority_queue_local::internal_priority_queue< ValueType, ContainerType, CompareType >::sort_to ( value_type *  target )

inline

Sort all contained elements, write result to target.

Definition at line 170 of file pq_helpers.h.

template<typename ValueType, typename ContainerType = std::vector<ValueType>, typename CompareType = std::less<ValueType>>

const_reference stxxl::priority_queue_local::internal_priority_queue< ValueType, ContainerType, CompareType >::top ( ) const

inline

Returns a read-only (constant) reference to the data at the first element of the queue.

Definition at line 130 of file pq_helpers.h.

Member Data Documentation

template<typename ValueType, typename ContainerType = std::vector<ValueType>, typename CompareType = std::less<ValueType>>

CompareType stxxl::priority_queue_local::internal_priority_queue< ValueType, ContainerType, CompareType >::comp

protected

Definition at line 105 of file pq_helpers.h.

template<typename ValueType, typename ContainerType = std::vector<ValueType>, typename CompareType = std::less<ValueType>>

size_type stxxl::priority_queue_local::internal_priority_queue< ValueType, ContainerType, CompareType >::current_size

protected

Definition at line 106 of file pq_helpers.h.

template<typename ValueType, typename ContainerType = std::vector<ValueType>, typename CompareType = std::less<ValueType>>

container_type stxxl::priority_queue_local::internal_priority_queue< ValueType, ContainerType, CompareType >::heap

protected

Definition at line 104 of file pq_helpers.h.

---

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

• include/stxxl/bits/containers/pq_helpers.h