priority_queue (STL/CLR)

2015-06-09

此模板类描述用于控制受限访问的变长有序元素序列的对象。使用容器适配器 priority_queue 管理基础容器作为优先级队列。

在下面的解释中，GValue 与 Value 相同，除非后者是 ref （引用）类型，在这种情况下，它是 Value^。同样，GContainer 与 Container 相同，除非后者是 ref 类型，在这种情况下，它是 Container^。

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

参数

值
受控序列中的元素的类型。
容器
基础容器的类型。

成员

类型定义	说明
priority_queue::const_reference (STL/CLR)	元素的常量引用的类型。
priority_queue::container_type (STL/CLR)	基础容器的类型。
priority_queue::difference_type (STL/CLR)	两个元素间的带符号距离的类型。
priority_queue::generic_container (STL/CLR)	泛型接口的容器适配器类型。
priority_queue::generic_value (STL/CLR)	容器适配器的泛型接口的元素的类型。
priority_queue::reference (STL/CLR)	元素的引用的类型。
priority_queue::size_type (STL/CLR)	两个元素间的带符号距离的类型。
priority_queue::value_compare (STL/CLR)	两个元素的排序委托。
priority_queue::value_type (STL/CLR)	元素的类型。

成员函数	说明
priority_queue::assign (STL/CLR)	替换任何元素。
priority_queue::empty (STL/CLR)	测试元素是否存在。
priority_queue::get_container (STL/CLR)	访问基础容器。
priority_queue::pop (STL/CLR)	移除 hghest 优先级元素。
priority_queue::priority_queue (STL/CLR)	构造容器对象。
priority_queue::push (STL/CLR)	添加一个新元素。
priority_queue::size (STL/CLR)	计算元素的数量。
priority_queue::top (STL/CLR)	访问要求优先级最高的元素。
priority_queue::to_array (STL/CLR)	复制控制序列到新数组。
priority_queue::value_comp (STL/CLR)	复制两个元素的排序委托。

Property	说明
priority_queue::top_item (STL/CLR)	访问要求优先级最高的元素。

运算符	说明
priority_queue::operator= (STL/CLR)	替换控件序列。

接口

接口	说明
ICloneable	复制对象。
IPriorityQueue<Value，容器>	维护泛型容器适配器。

备注

对象为它控制的序列分配和释放存储，通过基础容器 Container 类型，其存储了 Value 元素和成长的需求。它以堆形式保持序列排序，并其优先级最高的元素 (顶部元素) 可以方便地访问和删除。对象限制只能推入新元素并弹出优先级最高的元素，实现了优先级队列。

对象通过调用存储的 priority_queue::value_compare (STL/CLR) 类型的委托对象，对它控制的序列进行排序。当在构造 priority_queue 时，您可以指定该存储的委托对象；如果您未指定委托对象，默认比较为 operator<(value_type, value_type)。通过调用成员函数访问该存储区的对象priority_queue::value_comp (STL/CLR)()。

此委托对象必须强加弱序化在 priority_queue::value_type (STL/CLR) 类型的值上。这意味着，任何两键的 X 和 Y:

value_comp()(X, Y) 返回对每个调用相同的布尔值结果。

如果 value_comp()(X, Y) 为 true，则 value_comp()(Y, X) 必须是错误的。

如果 value_comp()(X, Y) 为 true，则 X 被视为 Y之前的排序。

如果 !value_comp()(X, Y) && !value_comp()(Y, X) 为 true，则 X 和 Y 是具有相同顺序。

在控制序列中，对优先于Y 的所有元素 X来说，key_comp()(Y, X) 为 false。(对于默认委托对象，键值从来不会是降序排列。)

优先级最高的元素为在其他元素之前的未排序的一个元素。

因为基础容器保持元素顺序为堆：

容器必须支持随机访问迭代器。

具有等效的顺序元素可能以与它们推入的顺序不同的顺序弹出。(排序不是稳定的。)

因此，基础容器的候选对象包括 deque (STL/CLR) vector (STL/CLR)。