关于priority_queue
1,关于STL中的priority_queue:确定用top()查看顶部元素时,该元素是具有最高优先级的一个元素.调用pop()删除之后,将促使下一个元素进入该位置.
2,如同stack和queue,priority_queue是一个基于基本序列容器进行构建的适配器,默认的序列器是vector.
先看一个示例:
#include <iostream>#include <cstdlib>#include <ctime>#include <queue>#include <functional>using namespace std;int main(){ srand(time(0)); priority_queue<int> prique_int; for (int i = 0; i < 100; i++) prique_int.push(rand() % 25); while (!prique_int.empty()) { cout << prique_int.top() <<' '; prique_int.pop(); } return 0;}
注:默认较大的值有较高的优先权.
下面这个示例,给予较小值较大的优先权.
#include <iostream>#include <cstdlib>#include <ctime>#include <queue>#include <functional>using namespace std;int main(){ srand(time(0)); //优先队列的完成构造. priority_queue<int, vector<int>, greater<int> > prique_int; for (int i = 0; i < 100; i++) prique_int.push(rand() % 25); while (!prique_int.empty()) { cout << prique_int.top() <<' '; prique_int.pop(); } return 0;}
下面的示例重载了operator<,可以存在主次两个优先级.
#include <iostream>#include <queue>#include <string>using namespace std;class ToDoItem{ char primary; int secondary; string item;public: ToDoItem(string td, char pri = 'A', int sec = 1) : primary(pri), secondary(sec), item(td) {} friend bool operator<(const ToDoItem& x, const ToDoItem& y) { if(x.primary > y.primary) return true; if(x.primary == y.primary) if(x.secondary > y.secondary) return true; return false; } friend ostream& operator<<(ostream& os, const ToDoItem& td) { return os << td.primary << td.secondary << ": " << td.item; }};int main(){ priority_queue<ToDoItem> toDoList; toDoList.push(ToDoItem("Empty trash", 'C', 4)); toDoList.push(ToDoItem("Feed dog", 'A', 2)); toDoList.push(ToDoItem("Feed bird", 'B', 7)); toDoList.push(ToDoItem("Mow lawn", 'C', 3)); toDoList.push(ToDoItem("Water lawn", 'A', 1)); toDoList.push(ToDoItem("Feed cat", 'B', 1)); while(!toDoList.empty()) { cout << toDoList.top() << endl; toDoList.pop(); } return 0;}
3,由于设计上的原因,不能在一个priority_queue上从头到尾进行迭代.
通过观察priority_queue的实现,它使用的函数有make_heap(),push_heap()以及pop_heap().
可以说优先级队列只是对堆的一个封装.
priority_queue使用的容器时protected的,标准c++规定其标识符为c,所以可以继承一个新类.
#include <iostream>#include <cstdlib>#include <ctime>#include <queue>#include <iterator>#include <algorithm>using namespace std;class PQI : public priority_queue<int>{public: vector<int>& iml() //返回序列器 { return c; //父类的protected成员 }};int main(){ srand(time(0)); PQI pqi; for (int i = 0; i < 30; i++) pqi.push(rand() % 20); vector<int> iml = pqi.iml(); copy(iml.begin(), iml.end(), ostream_iterator<int>(cout, " ")); cout << endl; while (!pqi.empty()) { cout << pqi.top() <<' '; pqi.pop(); } return 0;}
4,下面的示例,用一个vector实现priority_queue.
//私有继承
#include <iostream>#include <cstdlib>#include <ctime>#include <queue>#include <iterator>#include <algorithm>using namespace std;template<class T, class Compare>class PQV : private vector<T>{public: PQV(Compare cmp = Compare()) : comp(cmp) { make_heap(vector<T>::begin(), vector<T>::end(), comp); } const T& top() { return vector<T>::front(); } //关键 void push(const T& x) { vector<T>::push_back(x); push_heap(vector<T>::begin(), vector<T>::end(), comp); } //关键 void pop() { pop_heap(vector<T>::begin(), vector<T>::end(), comp); vector<T>::pop_back(); } bool empty() const { return vector<T>::empty(); } bool size() const { return vector<T>::size(); }private: Compare comp;};int main(){ srand(time(0)); PQV< int, less<int> > pqi; for(int i = 0; i < 100; i++) { pqi.push(rand() % 50); } while(!pqi.empty()) { cout << pqi.top() << ' '; pqi.pop(); } return 0;}
5,使用laying技术来实现
#include <iostream>#include <cstdlib>#include <ctime>#include <queue>#include <iterator>#include <algorithm>using namespace std;template<class T, class Compare>class PQV{public: PQV(Compare cmp = Compare()) : comp(cmp) { make_heap(v.begin(), v.end(), comp); } const T& top() { return v.front(); } //关键 void push(const T& x) { v.push_back(x); push_heap(v.begin(), v.end(), comp); } //关键 void pop() { pop_heap(v.begin(), v.end(), comp); v.pop_back(); } bool empty() const { return v.empty(); } bool size() const { return v.size(); }private: Compare comp; vector<T> v;};int main(){ srand(time(0)); PQV< int, less<int> > pqi; for(int i = 0; i < 100; i++) { pqi.push(rand() % 50); } while(!pqi.empty()) { cout << pqi.top() << ' '; pqi.pop(); } return 0;}
页:
[1]