admin管理员组文章数量:1624337
下面为priority_queue
的模板参数,第一个为数据类型,第二个为容器类型默认vector,第三个为仿函数默认为less。
template <class _Ty, class _Container = vector<_Ty>, class _Pr = less<typename _Container::value_type>>
这里有一点疑惑,传入的仿函数默认为less
,为什么priority_queue
默认形成大根堆?
源码剖析
less源码如下,若__Left < __Right
,则返回true:
到这里我们就可以知道为什么要通过重载小于号运算符来实现自定义数据类型的优先级队列,而重载大于号不可以,可以推测,STL中像sort也是类似原理。
template <class _Ty = void>
struct less {
_CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty _FIRST_ARGUMENT_TYPE_NAME;
_CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty _SECOND_ARGUMENT_TYPE_NAME;
_CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef bool _RESULT_TYPE_NAME;
constexpr bool operator()(const _Ty& _Left, const _Ty& _Right) const {
return _Left < _Right;
}
};
我们来探究一下仿函数最终用在了哪里?首先从构造函数开始,仿函数被赋值给了 comp
priority_queue(const _Pr& _Pred, _Container&& _Cont) : c(_STD move(_Cont)), comp(_Pred) {
_STD make_heap(c.begin(), c.end(), comp);
}
然后push函数,先在尾部插入一个元素,在向上调整堆,继续看 push_heap
函数:
void push(const value_type& _Val) {
c.push_back(_Val);
_STD push_heap(c.begin(), c.end(), comp);
}
一堆乱七八糟看不懂的,直接继续 _Push_heap_by_index
template <class _RanIt, class _Pr>
_CONSTEXPR20 void push_heap(_RanIt _First, _RanIt _Last, _Pr _Pred) {
// push *(_Last - 1) onto heap at [_First, _Last - 1), using _Pred
_Adl_verify_range(_First, _Last);
const auto _UFirst = _Get_unwrapped(_First);
auto _ULast = _Get_unwrapped(_Last);
using _Diff = _Iter_diff_t<_RanIt>;
_Diff _Count = _ULast - _UFirst;
if (2 <= _Count) {
_Iter_value_t<_RanIt> _Val = _STD move(*--_ULast);
_Push_heap_by_index(_UFirst, --_Count, _Diff(0), _STD move(_Val), _Pass_fn(_Pred));
}
}
最后找到了我们要的东西,代码很抽象,但依稀能辨认出是向上调整的代码
template <class _RanIt, class _Ty, class _Pr>
_CONSTEXPR20 void _Push_heap_by_index(
_RanIt _First, _Iter_diff_t<_RanIt> _Hole, _Iter_diff_t<_RanIt> _Top, _Ty&& _Val, _Pr _Pred) {
// percolate _Hole to _Top or where _Val belongs, using _Pred
using _Diff = _Iter_diff_t<_RanIt>;
for (_Diff _Idx = (_Hole - 1) >> 1; // shift for codegen
_Top < _Hole && _DEBUG_LT_PRED(_Pred, *(_First + _Idx), _Val); //
_Idx = (_Hole - 1) >> 1) { // shift for codegen
// move _Hole up to parent
*(_First + _Hole) = _STD move(*(_First + _Idx));
_Hole = _Idx;
}
*(_First + _Hole) = _STD move(_Val); // drop _Val into final hole
}
关键是这一句, _DEBUG_LT_PRED(_Pred, *(_First + _Idx), _Val)
,传入的仿函数_Pred 用在了这里,当 *(_First + _Idx) < _Val
时返回 true
,即当父节点的值小于新插入的值时继续调整,less函数返回true,父节点被插入结点换了下去,所以我们才可以得出结论 less函数,返回true时,左边的优先级低于右边的优先级,也就清楚了为什么默认传入less
反而形成的是大根堆。
本文标签: stlpriorityqueue是大根堆
版权声明:本文标题:为什么STL priority_queue默认是大根堆? 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1728896580a1178489.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论