NVBIO
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Types | Public Methods | Static Public Members | Proteced Methods | Related Functions | List of all members
boost::container::priority_deque< Type, Sequence, Compare > Class Template Reference

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
Parameters
TypeType of elements in the priority deque.
SequenceUnderlying sequence container. Must provide random-access iterators, front(), push_back(Type const &), and pop_back(). Defaults to std::vector<Type>.
CompareComparison 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_typesequence (void)
 
const container_typesequence (void) const
 
value_comparecompare (void)
 
const value_comparecompare (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
compComparison class.
seqContainer 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,lastRange of elements.
compInstance of comparison class.
seqInstance 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_itAn 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,lastInput 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
valueElement 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
otherPriority 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_itA valid iterator in the range [begin, end).
valueThe 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 
)
related
Parameters
deque1,deque2Priority 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: