Detailed description

template< typename Type, typename Sequence = std::vector<Type>, typename Compare = ::std::less<typename Sequence::value_type>>
class boost::container::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 49 of file priority_deque.hpp.

#include <priority_deque.hpp>

Public Types
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
	priority_deque (const Compare &=Compare(), const Sequence &=Sequence())
	Constructs a new priority deque. More...

template<typename InputIterator >
	priority_deque (InputIterator first, InputIterator last, const Compare &=Compare(), const Sequence &=Sequence())
	Constructs a new priority deque from a sequence of elements. More...

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

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

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

template<typename InputIterator >
	priority_deque (InputIterator first, InputIterator last, const C &comp, const S &seq)

template<typename InputIterator >
void	merge (InputIterator first, InputIterator last)


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

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

const_reference	top (void) const


void	pop_maximum (void)
	Removes a maximal element from the deque. More...

void	pop_minimum (void)
	Removes a minimal element from the deque. More...

void	pop (void)


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

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

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


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

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


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

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

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

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
container_type &	sequence (void)

const container_type &	sequence (void) const

value_compare &	compare (void)

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)

Member Typedef Documentation

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

typedef container_type::const_iterator boost::container::priority_deque< Type, Sequence, Compare >::const_iterator

May be used to examine, but not modify, elements in the deque.

Definition at line 107 of file priority_deque.hpp.

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

typedef pointer boost::container::priority_deque< Type, Sequence, Compare >::const_pointer

Definition at line 105 of file priority_deque.hpp.

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

typedef container_type::const_reference boost::container::priority_deque< Type, Sequence, Compare >::const_reference

May be used to examine, but not modify, an element in the deque.

Definition at line 102 of file priority_deque.hpp.

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

typedef Sequence boost::container::priority_deque< Type, Sequence, Compare >::container_type

Underlying container type.

Definition at line 96 of file priority_deque.hpp.

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

typedef container_type::difference_type boost::container::priority_deque< Type, Sequence, Compare >::difference_type

STL Container specifies that this is a signed integral type.

Definition at line 110 of file priority_deque.hpp.

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

typedef const_iterator boost::container::priority_deque< Type, Sequence, Compare >::iterator

Definition at line 108 of file priority_deque.hpp.

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

typedef container_type::pointer boost::container::priority_deque< Type, Sequence, Compare >::pointer

Definition at line 104 of file priority_deque.hpp.

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

typedef container_type::reference boost::container::priority_deque< Type, Sequence, Compare >::reference

Definition at line 103 of file priority_deque.hpp.

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

typedef container_type::size_type boost::container::priority_deque< Type, Sequence, Compare >::size_type

STL Container specifies that this is an unsigned integral type.

Definition at line 100 of file priority_deque.hpp.

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

typedef Compare boost::container::priority_deque< Type, Sequence, Compare >::value_compare

Definition at line 98 of file priority_deque.hpp.

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

typedef container_type::value_type boost::container::priority_deque< Type, Sequence, Compare >::value_type

Definition at line 97 of file priority_deque.hpp.

Constructor & Destructor Documentation

template<typename T , typename S, typename C>

boost::container::priority_deque< T, S, C >::priority_deque	(	const C &	comp = `Compare()`,
		const S &	seq = `Sequence()`
	)

explicit

Constructs a new priority deque.

Parameters

comp	Comparison class.
seq	Container class.

Postcondition: Deque contains copies of all elements from sequence.

Remarks: Complexity: O(n)

Definition at line 243 of file priority_deque.hpp.

template<typename T , typename S, typename C>

template<typename InputIterator >

boost::container::priority_deque< T, S, C >::priority_deque	(	InputIterator	first,
		InputIterator	last,
		const C &	comp = `Compare()`,
		const S &	seq = `Sequence()`
	)

Constructs a new priority deque from a sequence of elements.

Parameters

first,last	Range of elements.
comp	Instance of comparison class.
seq	Instance of container class.

Postcondition: Deque contains copies of all elements in sequence (if specified) and in the range [ first, last).

Remarks: Complexity: O(n)

Definition at line 268 of file priority_deque.hpp.

Member Function Documentation

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

const_iterator boost::container::priority_deque< Type, Sequence, Compare >::begin ( void ) const

inline

Returns a const iterator at the beginning of the sequence.

Definition at line 197 of file priority_deque.hpp.

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

void boost::container::priority_deque< Type, Sequence, Compare >::clear ( void )

inline

Removes all elements from the priority deque.

Definition at line 180 of file priority_deque.hpp.

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

value_compare& boost::container::priority_deque< Type, Sequence, Compare >::compare ( void )

inlineprotected

Definition at line 226 of file priority_deque.hpp.

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

const value_compare& boost::container::priority_deque< Type, Sequence, Compare >::compare ( void ) const

inlineprotected

Definition at line 227 of file priority_deque.hpp.

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

bool boost::container::priority_deque< Type, Sequence, Compare >::empty ( void ) const

inline

Returns true if the priority deque is empty, false if it is not.

Definition at line 169 of file priority_deque.hpp.

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

const_iterator boost::container::priority_deque< Type, Sequence, Compare >::end ( void ) const

inline

Returns a const iterator past the end of the sequence.

Definition at line 199 of file priority_deque.hpp.

template<typename T , typename Sequence , typename Compare >

void boost::container::priority_deque< T, Sequence, Compare >::erase ( const_iterator random_it)

Removes a specified element from the deque.

Parameters

random_it An iterator in the range [begin, end)

Precondition: Priority deque contains one or more elements.

Postcondition: The deque no longer contains the element previously at random_it.; All iterators and references are invalidated.

See Also: set

Remarks: Complexity: O(log n)

Definition at line 508 of file priority_deque.hpp.

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

size_type boost::container::priority_deque< Type, Sequence, Compare >::max_size ( void ) const

inline

Returns the maximum number of elements that can be contained.

Definition at line 173 of file priority_deque.hpp.

template<typename T , typename Sequence , typename Compare >

priority_deque< T, Sequence, Compare >::const_reference boost::container::priority_deque< T, Sequence, Compare >::maximum ( void ) const

inline

Accesses a maximal element in the deque.

Returns: Const reference to a maximal element in the priority deque.

Precondition: Priority deque contains one or more elements.

See Also: minimum, pop_maximum

Remarks: Complexity: O(1)

Definition at line 349 of file priority_deque.hpp.

template<typename T , typename S , typename C >

template<typename InputIterator >

void boost::container::priority_deque< T, S, C >::merge	(	InputIterator	first,
		InputIterator	last
	)

Merges a sequence of elements into the priority deque.

Parameters

first,last Input iterators bounding the range [ first, last)

Postcondition: Priority deque contains its original elements, and copies of those in the range.; All iterators and references are invalidated.

Remarks: Complexity: O(n); Exception safety: Basic.

Definition at line 424 of file priority_deque.hpp.

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

template<typename SourceContainer >

void boost::container::priority_deque< Type, Sequence, Compare >::merge ( const SourceContainer & source)

inline

Merges a container's elements into the priority deque.

Definition at line 189 of file priority_deque.hpp.

template<typename T , typename Sequence , typename Compare >

priority_deque< T, Sequence, Compare >::const_reference boost::container::priority_deque< T, Sequence, Compare >::minimum ( void ) const

Accesses a minimal element in the deque.

Returns: Const reference to a minimal element in the priority deque.

Precondition: Priority deque contains one or more elements.

See Also: maximum, pop_minimum

Remarks: Complexity: O(1)

Definition at line 364 of file priority_deque.hpp.

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

void boost::container::priority_deque< Type, Sequence, Compare >::pop ( void )

inline

Identical to std::priority_queue pop().

See Also: pop_maximum

Definition at line 163 of file priority_deque.hpp.

template<typename T , typename Sequence , typename Compare >

void boost::container::priority_deque< T, Sequence, Compare >::pop_maximum ( void )

Removes a maximal element from the deque.

Precondition: Priority deque contains one or more elements.

Postcondition: A minimal element has been removed from the priority deque.; All iterators and references are invalidated.

See Also: minimum, pop_maximum

Remarks: Complexity: O(log n)

Definition at line 399 of file priority_deque.hpp.

template<typename T , typename Sequence , typename Compare >

void boost::container::priority_deque< T, Sequence, Compare >::pop_minimum ( void )

Removes a minimal element from the deque.

Precondition: Priority deque contains one or more elements.

Postcondition: A maximal element has been removed from the priority deque.; All iterators and references are invalidated.

See Also: maximum, pop, pop_minimum

Remarks: Complexity: O(log n)

Definition at line 379 of file priority_deque.hpp.

template<typename T , typename Sequence , typename Compare >

void boost::container::priority_deque< T, Sequence, Compare >::push ( const value_type & value)

Copies an element into the priority deque.

Parameters

value Element to add the the priority deque.

Postcondition: Priority deque contains value or a copy of value.; All iterators and references are invalidated.

Remarks: Complexity: O(log n)

Definition at line 306 of file priority_deque.hpp.

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

container_type& boost::container::priority_deque< Type, Sequence, Compare >::sequence ( void )

inlineprotected

Definition at line 224 of file priority_deque.hpp.

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

const container_type& boost::container::priority_deque< Type, Sequence, Compare >::sequence ( void ) const

inlineprotected

Definition at line 225 of file priority_deque.hpp.

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

size_type boost::container::priority_deque< Type, Sequence, Compare >::size ( void ) const

inline

Returns the number of elements in the priority deque.

Definition at line 171 of file priority_deque.hpp.

template<typename T, typename S, typename C>

void boost::container::priority_deque< T, S, C >::swap ( priority_deque< T, S, C > & other)

inline

Moves the elements from this deque into another, and vice-versa.

Parameters

other Priority deque with which to swap.

Postcondition: Deque contains the elements from source, and source contains the elements from this deque.; All iterators and references are invalidated.

Note: Sequence containers are required to have swap functions.

Remarks: Complexity: O(1)

Definition at line 443 of file priority_deque.hpp.

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

const_reference boost::container::priority_deque< Type, Sequence, Compare >::top ( void ) const

inline

Identical to std::priority_queue top().

See Also: maximum

Definition at line 155 of file priority_deque.hpp.

template<typename T , typename S , typename C >

void boost::container::priority_deque< T, S, C >::update	(	const_iterator	random_it,
		const value_type &	value
	)

Modifies a specified element of the deque.

Parameters

random_it	A valid iterator in the range [begin, end).
value	The new value.

Precondition: Priority deque contains one or more elements.

Postcondition: The element at random_it is set to value.; All iterators and references are invalidated.

See Also: erase

Elements within the deque may be unordered.

Remarks: Complexity: O(log n); Exception safety: Basic. Exceptions won't lose elements, but may corrupt the heap.

Definition at line 476 of file priority_deque.hpp.

Friends And Related Function Documentation

template<typename T , typename S , typename C >

void swap	(	priority_deque< T, S, C > &	deque1,
		priority_deque< T, S, C > &	deque2
	)

deque1,deque2 Priority deques.

Postcondition: deque1 contains the elements originally in deque2, and deque2 contains the elements originally in deque1; All iterators and references are invalidated.

Remarks: Complexity: O(1)

Definition at line 456 of file priority_deque.hpp.

Member Data Documentation

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

const bool boost::container::priority_deque< Type, Sequence, Compare >::constant_time_size = true

static

Definition at line 212 of file priority_deque.hpp.

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

const bool boost::container::priority_deque< Type, Sequence, Compare >::has_ordered_iterators = false

static

Definition at line 214 of file priority_deque.hpp.

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

const bool boost::container::priority_deque< Type, Sequence, Compare >::has_reserve = false

static

Definition at line 220 of file priority_deque.hpp.

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

const bool boost::container::priority_deque< Type, Sequence, Compare >::is_mergable = true

static

Definition at line 216 of file priority_deque.hpp.

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

const bool boost::container::priority_deque< Type, Sequence, Compare >::is_stable = false

static

Definition at line 218 of file priority_deque.hpp.

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

E:/git/nvbio/contrib/priority-deque/priority_deque.hpp
E:/git/nvbio/nvbio/basic/priority_deque.h

Detailed description

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

Public Types

Public Methods

Static Public Members

Proteced Methods

Related Functions

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation

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