priority_queue (STL/CLR)

priority_queue

Visual C++ Libraries

Updated: December 2008

The template class describes an object that controls a varying-length ordered sequence of elements that has limited access. You use the container adapter priority_queue to manage an underlying container as a priority queue.

In the description below, GValue is the same as Value unless the latter is a ref type, in which case it is Value^. Similarly, GContainer is the same as Container unless the latter is a ref type, in which case it is Container^.

template<typename Value,
    typename Container>
    ref class priority_queue
        System::ICloneable,
        Microsoft::VisualC::StlClr::IPriorityQueue<GValue, GContainer>
    { ..... };

Parameters

Value: The type of an element in the controlled sequence.
Container: The type of the underlying container.

Members

Type Definition	Description
priority_queue::const_reference (STL/CLR)	The type of a constant reference to an element.
priority_queue::container_type (STL/CLR)	The type of the underlying container.
priority_queue::difference_type (STL/CLR)	The type of a signed distance between two elements.
priority_queue::generic_container (STL/CLR)	The type of the generic interface for the container adapter.
priority_queue::generic_value (STL/CLR)	The type of an element for the generic interface for the container adapter.
priority_queue::reference (STL/CLR)	The type of a reference to an element.
priority_queue::size_type (STL/CLR)	The type of a signed distance between two elements.
priority_queue::value_compare (STL/CLR)	The ordering delegate for two elements.
priority_queue::value_type (STL/CLR)	The type of an element.

Member Function	Description
priority_queue::assign (STL/CLR)	Replaces all elements.
priority_queue::empty (STL/CLR)	Tests whether no elements are present.
priority_queue::get_container (STL/CLR)	Accesses the underlying container.
priority_queue::pop (STL/CLR)	Removes the hghest-priority element.
priority_queue::priority_queue (STL/CLR)	Constructs a container object.
priority_queue::push (STL/CLR)	Adds a new element.
priority_queue::size (STL/CLR)	Counts the number of elements.
priority_queue::top (STL/CLR)	Accesses the highest-priority element.
priority_queue::to_array (STL/CLR)	Copies the controlled sequence to a new array.
priority_queue::value_comp (STL/CLR)	Copies the ordering delegate for two elements.

Property	Description
priority_queue::top_item (STL/CLR)	Accesses the highest-priority element.

Operator	Description
priority_queue::operator= (STL/CLR)	Replaces the controlled sequence.

Interfaces

Interface	Description
ICloneable	Duplicate an object.
IPriorityQueue<Value, Container>	Maintain generic container adapter.

Remarks

The object allocates and frees storage for the sequence it controls through an underlying container, of type Container, that stores Value elements and grows on demand. It keeps the sequence ordered as a heap, with the highest-priority element (the top element) readily accessible and removable. The object restricts access to pushing new elements and popping just the highest-priority element, implementing a priority queue.

The object orders the sequence it controls by calling a stored delegate object of type priority_queue::value_compare (STL/CLR). You can specify the stored delegate object when you construct the priority_queue; if you specify no delegate object, the default is the comparison operator<(value_type, value_type). You access this stored object by calling the member function priority_queue::value_comp (STL/CLR)().

Such a delegate object must impose a strict weak ordering on values of type priority_queue::value_type (STL/CLR). That means, for any two keys X and Y:

value_comp()(X, Y) returns the same Boolean result on every call.

If value_comp()(X, Y) is true, then value_comp()(Y, X) must be false.

If value_comp()(X, Y) is true, then X is said to be ordered before Y.

If !value_comp()(X, Y) && !value_comp()(Y, X) is true, then X and Y are said to have equivalent ordering.

For any element X that precedes Y in the controlled sequence, key_comp()(Y, X) is false. (For the default delegate object, keys never decrease in value.)

The highest priority element is thus one of the elements which is not ordered before any other element.

Since the underlying container keeps elements ordered as a heap:

The container must support random-access iterators.

Elements with equivalent ordering may be popped in a different order than they were pushed. (The ordering is not stable.)

Thus, candidates for the underlying container include deque (STL/CLR) and vector (STL/CLR).

Requirements

Header: <cliext/queue>

Namespace: cliext

Reference

Other Resources

STL/CLR Library Reference

Change History

Date	History	Reason
December 2008	Added link to parent.	Customer feedback.

Date

History

Reason

December 2008

Added link to parent.

Customer feedback.