如何自定义STL中priority_queue类型并分析其源码实现？

本文共计1261个文字，预计阅读时间需要6分钟。

使用 `priority_queue`，这里介绍优先级队列的其他用法。首先，我们来看默认的究竟是大顶堆还是小顶堆？

priority_queue使用

这里说一下优先级队列的其他的用法,这里我们先看默认的究竟是建立大堆还是小堆?

#include <iostream> #include <queue> int main() { int arr[] = { 10, 2, 1, 3, 5, 4, 0 }; std::priority_queue<int> q; for (size_t i = 0; i < sizeof(arr)/sizeof(arr[0]); i++) { q.push(arr[i]); } while (!q.empty()) { std::cout << q.top() << " "; q.pop(); } return 0; }

是大堆,那么我们应该如何让他建立成小堆呢?先来它他们的构造函数.

这个是C++98的,我们发现这里有两个,这里测试第一个,我们发现comp是一个对象,此时我们就想到了仿函数对象,那么是不是呢?直接测试.

#include <iostream> #include <queue> #include <vector> int main() { int arr[] = { 10, 2, 1, 3, 5, 4, 0 }; std::priority_queue<int, std::vector<int>, std::less<int>> q; for (size_t i = 0; i < sizeof(arr)/sizeof(arr[0]); i++) { q.push(arr[i]); } while (!q.empty()) { std::cout << q.top() << " "; q.pop(); } return 0; }

那么greater就是小根堆了,测试一下.

#include <iostream> #include <queue> #include <functional> int main() { int arr[] = { 10, 2, 1, 3, 5, 4, 0 }; std::priority_queue<int, std::vector<int>, std::greater<int>> q; for (size_t i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) { q.push(arr[i]); } while (!q.empty()) { std::cout << q.top() << " "; q.pop(); } return 0; }

下面我们测试一下自定义类型的入堆操作,这里我们直接写出一个仿函数.

struct node { int x; int y; }; struct cmp { bool operator()(const node& n1, const node& n2){ return n1.x > n2.x; } }; int main() { node n1 = { 1, 2 }; node n2 = { 2, 4 }; node n3 = { 3, 4 }; priority_queue<node, vector<node>, cmp>q; q.push(n1); q.push(n2); q.push(n3); return 0; }

如果我们要是不想写仿函数,那么我们在结构体里面重载<操作符,看大家的喜好吧.

struct node { int x; int y; bool operator<(const node& n) const { return x > n.x; // 这里可以控制是大堆还是小堆 } }; int main() { node n1 = { 1, 2 }; node n2 = { 2, 4 }; node n3 = { 3, 4 }; priority_queue<node>q; q.push(n1); q.push(n2); q.push(n3); return 0; }

priority_queue源码

这里我们简单的分析一下源码,主要是加深一下印象.

template <class T, class Sequence = vector<T>, class Compare = less<typename Sequence::value_type> > class priority_queue { public: typedef typename Sequence::value_type value_type; typedef typename Sequence::size_type size_type; typedef typename Sequence::reference reference; typedef typename Sequence::const_reference const_reference; protected: Sequence c; Compare comp; public: priority_queue() : c() {} explicit priority_queue(const Compare& x) : c(), comp(x) {} void push(const value_type& x) { __STL_TRY { c.push_back(x); push_heap(c.begin(), c.end(), comp); } __STL_UNWIND(c.clear()); } };

先来得到第一个结论

试一下上面我们说的,新的构造方式,不过我们很少用.

struct node { int x; int y; }; struct cmp { bool operator()(const node& n1, const node& n2){ return n1.x > n2.x; } cmp(const cmp& c) { } cmp() { } }; int main() { node n1 = { 1, 2 }; node n2 = { 2, 4 }; node n3 = { 3, 4 }; cmp c; priority_queue<node, vector<node>, cmp> q(c); q.push(n1); q.push(n2); q.push(n3); return 0; }

下面我们来谈当我们数据进入数组的时候,我们调整堆的操作,这里不做具体的分析,就谈为何我们的重载了<就不用写仿函数了,应该是这个函数,我们直接来分析一下吧.

template <class RandomAccessIterator, class Distance, class T, class Compare> void __push_heap(RandomAccessIterator first, Distance holeIndex, Distance topIndex, T value, Compare comp) { Distance parent = (holeIndex - 1) / 2; while (holeIndex > topIndex && comp(*(first + parent), value)) { *(first + holeIndex) = *(first + parent); holeIndex = parent; parent = (holeIndex - 1) / 2; } *(first + holeIndex) = value; }

首先我们调用的是默认的无参构造函数,此时我们的Compare的实际类型是less\<Node\>,后面我们使用比较的,那么此时我们使用的就是less类型的,也就是我们的标准提供的仿函数.

struct node { int x; int y; bool operator<(const node& n) const { return x > n.x; // 这里可以控制是大堆还是小堆 } }; int main() { node n1 = { 1, 2 }; node n2 = { 2, 4 }; node n3 = { 3, 4 }; priority_queue<node>q; q.push(n1); q.push(n2); q.push(n3); return 0; }

下面就到了观察less类型了,我们这里继续进去看.

template <class T> struct less : public binary_function<T, T, bool> { bool operator()(const T& x, const T& y) const { return x < y; } };

看到了吗.这里面重载了括号,看到函数体内存在一个<吗?这里调用的就是我们在Node中写的<重载操作符,这里就是我们为何是这样的.那么此时我们也可以重载>,看下面的操作.

struct node { int x; int y; bool operator>(const node& n) const { return x > n.x; } }; int main() { node n1 = { 1, 2 }; node n2 = { 2, 4 }; node n3 = { 3, 4 }; priority_queue<node, vector<node>, greater<node>>q; q.push(n1); q.push(n2); q.push(n3); return 0; }