Detailed description

template< typename Type, typename Sequence = std::vector<Type>, typename Compare = ::std::less<typename Sequence::value_type>>
class nvbio::priority_deque< Type, Sequence, Compare >

Efficient double-ended priority queue.

Author: Nathaniel McClatchey

Copyright: Boost Software License Version 1.0

Parameters

Type	Type of elements in the priority deque.
Sequence	Underlying sequence container. Must provide random-access iterators, front(), push_back(Type const &), and pop_back(). Defaults to std::vector<Type>.
Compare	Comparison class. Compare(A, B) should return true if A should be placed earlier than B in a strict weak ordering. Defaults to std::less<Type>, which encapsulates operator<.

Priority deques are adaptors, designed to provide efficient insertion and access to both ends of a weakly-ordered list of elements. As a container adaptor, priority_deque is implemented on top of another container type. By default, this is std::vector, but a different container may be specified explicitly. Although the priority deque does permit iteration through its elements, there is no ordering guaranteed, as different implementations may benefit from different structures, and all iterators should be discarded after using any function not labeled const.

Note: priority_deque does not provide a stable ordering. If both A<B and B<A are false, then the order in which they appear may differ from the order in which they were added to the priority deque.

Remarks: priority_deque replicates the interface of the STL priority_queue class template.; priority_deque is most useful when removals are interspersed with insertions. If no further insertions are to be performed after the first removal, consider using an array and a sorting algorithm instead.; priority_deque sorts elements as they are added, removed, and modified by its member functions. If the elements are modified by some means other than the public member functions, the order must be restoreed before the priority_deque is used.

See Also: priority_queue

Definition at line 110 of file priority_deque.h.

#include <priority_deque.h>

Public Types
enum	Constructed { CONSTRUCTED }

typedef Sequence	container_type

typedef container_type::value_type	value_type

typedef Compare	value_compare

typedef container_type::size_type	size_type

typedef container_type::const_reference	const_reference

typedef container_type::reference	reference

typedef container_type::pointer	pointer

typedef pointer	const_pointer

typedef container_type::const_iterator	const_iterator

typedef const_iterator	iterator

typedef container_type::difference_type	difference_type

Public Methods
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE	priority_deque (const Compare &=Compare(), const Sequence &=Sequence())
	Constructs a new priority deque. More...

template<typename InputIterator >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE	priority_deque (InputIterator first, InputIterator last, const Compare &=Compare(), const Sequence &=Sequence())

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE	priority_deque (const Sequence &seq, const bool constructed=false)

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE	priority_deque (const Sequence &seq, const Constructed flag)

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	push (const value_type &)
	Copies an element into the priority deque. More...

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	clear (void)
	Removes all elements from the priority deque. More...

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	swap (priority_deque< Type, Sequence, Compare > &)
	Moves the elements from this deque into another, and vice-versa. More...


NVBIO_FORCEINLINE NVBIO_HOST_DEVICE const_reference	maximum (void) const
	Accesses a maximal element in the deque. More...

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE const_reference	minimum (void) const
	Accesses a minimal element in the deque. More...

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE const_reference	top (void) const

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE const_reference	bottom (void) const


NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	pop_top (void)
	Removes a maximal element from the deque. More...

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	pop_bottom (void)
	Removes a minimal element from the deque. More...

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	pop (void)


NVBIO_FORCEINLINE NVBIO_HOST_DEVICE bool	empty (void) const
	Returns true if the priority deque is empty, false if it is not. More...

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE size_type	size (void) const
	Returns the number of elements in the priority deque. More...

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE size_type	max_size (void) const
	Returns the maximum number of elements that can be contained. More...


template<typename InputIterator >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	merge (InputIterator first, InputIterator last)
	Merges a sequence of elements into the priority deque. More...

template<typename SourceContainer >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	merge (const SourceContainer &source)
	Merges a container's elements into the priority deque. More...


NVBIO_FORCEINLINE NVBIO_HOST_DEVICE const_iterator	begin (void) const
	Returns a const iterator at the beginning of the sequence. More...

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE const_iterator	end (void) const
	Returns a const iterator past the end of the sequence. More...

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	update (const_iterator, const value_type &)
	Modifies a specified element of the deque. More...

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	erase (const_iterator)
	Removes a specified element from the deque. More...

Static Public Members
static const bool	constant_time_size = true

static const bool	has_ordered_iterators = false

static const bool	is_mergable = true

static const bool	is_stable = false

static const bool	has_reserve = false

Proteced Methods
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE container_type &	sequence (void)

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE const container_type &	sequence (void) const

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE value_compare &	compare (void)

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE const value_compare &	compare (void) const

Related Functions
(Note that these are not member functions.)
template<typename T , typename S , typename C >
void	swap (priority_deque< T, S, C > &deque1, priority_deque< T, S, C > &deque2)