admin管理员组文章数量:1623784
C++标准库提供了优先队列priority_queue
,顾名思义,就是可以按照优先级出队的队列,而且时间复杂度为
O
(
l
o
g
n
)
O(logn)
O(logn),算法中有很多优化项就是用优先队列来优化的。
C++11的标准库是怎么构造出优先队列的呢?优先队列是用堆来构造的。所以,优先队列其实并不能叫队列,它的完整定义应该是这样的:优先队列是用堆来构造,包装成队列的适配器。
其实想一想,堆确实适合构造优先队列,优先队列每次需要弹出优先级最大的元素,而堆的堆顶恰巧就是优先级最大的元素,关于C++11中的堆,可以参考聊聊C++11标准库中堆(heap)算法的源码。
那就一起来看看MinGW中C++11的标准库stl_queue.h
中的priority_queue
的源码。
先来看看标准库对优先队列的介绍:
/**
* @brief A standard container automatically sorting its contents.
*
* @ingroup sequences
*
* @tparam _Tp Type of element.
* @tparam _Sequence Type of underlying sequence, defaults to vector<_Tp>.
* @tparam _Compare Comparison function object type, defaults to
* less<_Sequence::value_type>.
*
* This is not a true container, but an @e adaptor. It holds
* another container, and provides a wrapper interface to that
* container. The wrapper is what enforces priority-based sorting
* and %queue behavior. Very few of the standard container/sequence
* interface requirements are met (e.g., iterators).
*
* The second template parameter defines the type of the underlying
* sequence/container. It defaults to std::vector, but it can be
* any type that supports @c front(), @c push_back, @c pop_back,
* and random-access iterators, such as std::deque or an
* appropriate user-defined type.
*
* The third template parameter supplies the means of making
* priority comparisons. It defaults to @c less<value_type> but
* can be anything defining a strict weak ordering.
*
* Members not found in @a normal containers are @c container_type,
* which is a typedef for the second Sequence parameter, and @c
* push, @c pop, and @c top, which are standard %queue operations.
*
* @note No equality/comparison operators are provided for
* %priority_queue.
*
* @note Sorting of the elements takes place as they are added to,
* and removed from, the %priority_queue using the
* %priority_queue's member functions. If you access the elements
* by other means, and change their data such that the sorting
* order would be different, the %priority_queue will not re-sort
* the elements for you. (How could it know to do so?)
*/
这里面大致说了优先队列支持哪些成员函数,用了哪个数据结构来存储元素,排序规则等等。
template <typename _Tp, typename _Sequence = vector<_Tp>,
typename _Compare = less<typename _Sequence::value_type>>
class priority_queue
{
public:
typedef typename _Sequence::value_type value_type;
typedef typename _Sequence::reference reference;
typedef typename _Sequence::const_reference const_reference;
typedef typename _Sequence::size_type size_type;
typedef _Sequence container_type;
protected:
// See queue::c for notes on these names.
_Sequence c;
_Compare comp;
}
模板参数中,_Sequence
默认是vector<_Tp>
,也就是说priority_queue
默认以vector
作为容器,但是支持任意有push_back
,pop_back
,front
成员函数,并且提供随机迭代器的容器;
然后就是容器必须的五个类型重定义;
成员函数只有序列c
和比较函数comp
。
从类的模板参数可以看出来,如果想要自定义优先级,那么就必须把第二个模板参数显示地写出来,即std::priority_queue<int, std::vector<int>, std::greater<int>>
public:
explicit priority_queue(const _Compare &__x,
const _Sequence &__s)
: c(__s), comp(__x)
{
std::make_heap(c.begin(), c.end(), comp);
}
explicit priority_queue(const _Compare &__x = _Compare(),
_Sequence &&__s = _Sequence())
: c(std::move(__s)), comp(__x)
{
std::make_heap(c.begin(), c.end(), comp);
}
template <typename _InputIterator>
priority_queue(_InputIterator __first, _InputIterator __last,
const _Compare &__x,
const _Sequence &__s)
: c(__s), comp(__x)
{
c.insert(c.end(), __first, __last);
std::make_heap(c.begin(), c.end(), comp);
}
template <typename _InputIterator>
priority_queue(_InputIterator __first, _InputIterator __last,
const _Compare &__x = _Compare(),
_Sequence &&__s = _Sequence())
: c(std::move(__s)), comp(__x)
{
c.insert(c.end(), __first, __last);
std::make_heap(c.begin(), c.end(), comp);
}
可以看到,priority_queue
的构造函数就是在造一个堆。
bool empty() const
{
return c.empty();
}
size_type size() const
{
return c.size();
}
const_reference top() const
{
return c.front();
}
void push(const value_type &__x)
{
c.push_back(__x);
std::push_heap(c.begin(), c.end(), comp);
}
void push(value_type &&__x)
{
c.push_back(std::move(__x));
std::push_heap(c.begin(), c.end(), comp);
}
template <typename... _Args>
void emplace(_Args &&... __args)
{
c.emplace_back(std::forward<_Args>(__args)...);
std::push_heap(c.begin(), c.end(), comp);
}
void pop()
{
std::pop_heap(c.begin(), c.end(), comp);
c.pop_back();
}
void swap(priority_queue &__pq) noexcept(noexcept(swap(c, __pq.c)) && noexcept(swap(comp, __pq.comp)))
{
using std::swap;
swap(c, __pq.c);
swap(comp, __pq.comp);
}
这些都是priority_queue
的成员函数,其中emplace
和swap
是C++11新增的成员函数,emplace
默认调用std::vector::emplace_back
来构造元素;
出队就std::pop_heap; std::vector::pop_back;
,入队就std::vector::push_back; std::push_heap;
。
template <typename _Tp, typename _Sequence, typename _Compare>
inline void swap(priority_queue<_Tp, _Sequence, _Compare> &__x,
priority_queue<_Tp, _Sequence, _Compare> &__y) noexcept(noexcept(__x.swap(__y)))
{
__x.swap(__y);
}
template <typename _Tp, typename _Sequence, typename _Compare, typename _Alloc>
struct uses_allocator<priority_queue<_Tp, _Sequence, _Compare>, _Alloc>
: public uses_allocator<_Sequence, _Alloc>::type
{
};
这两个是C++11为priority_queue
做的两个特化。
本文标签: 队列库中源码标准priorityqueue
版权声明:本文标题:聊聊C++标准库中优先队列priority_queue的源码 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1728896134a1178432.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论