翻译:
empty():检测容器是否为空。
size():返回容器中有效元素个数。
front():返回容器中第一个元素的引用。
push_back():在容器尾部插入元素。
pop_back():删除容器尾部元素。
优先级队列默认使用vector作为其底层存储数据的容器,在vector上又使用了堆算法(堆的创建与应用)将vector中元素构造成堆的结构,因此priority_queue就是堆,所有需要用到堆的位置,都可以考虑使用priority_queue。注意:默认情况下priority_queue是大堆。
⭐️⭐️⭐️:常用的函数接口
下面我们就举一个例子:
存放自定义类型,这样更具代表性!
template<class T> class greater { public: bool operator()(const T& p1, const T& p2) const { return p1 > p2; } }; struct person { person(string name = "", int age = -1) :_name(name) , _age(age) {} bool operator<(const person& p) const { return _age < p._age; } bool operator>(const person& p) const { return _age > p._age; } string _name; int _age; }; ostream& operator<<(ostream& out, const person& p) { out << "name:" << p._name << " " << "age:" << p._age << endl; return out; } void test02() { person arr[] = { { "pxl", 23 }, { "dyx", 21 }, { "wjz", 24 }, { "ztd", 20 } }; priority_queue<person, vector<person>, greater<person>> pq(arr, arr + sizeof(arr) / sizeof(arr[0]));//小堆 pq.push(person("yzc", 22)); cout <<"堆顶元素是:"<< pq.top() << endl; while (!pq.empty()) { cout << pq.top() << endl; pq.pop(); } } int main() { test02();//自定义类型 system("pause"); return 0; }
⚠️⚠️⚠️注意点:
template<class T> struct less { bool operator()(const T& x, const T& y) const { return x < y; } }; template<class T> struct greater { bool operator()(const T& x, const T& y) const { return x > y; } }; // 优先级队列 -- 大堆 < 小堆 > template<class T, class Container = vector<T>, class Compare = less<T>> class priority_queue { public: void AdjustUp(int child) { Compare comFunc; int parent = (child - 1) / 2; while (child > 0) { //if (_con[parent] < _con[child]) if (comFunc(_con[parent], _con[child])) { swap(_con[parent], _con[child]); child = parent; parent = (child - 1) / 2; } else { break; } } } void push(const T& x) { _con.push_back(x); AdjustUp(_con.size() - 1); } void AdjustDown(int parent) { Compare comFunc; size_t child = parent * 2 + 1; while (child < _con.size()) { //if (child+1 < _con.size() && _con[child] < _con[child+1]) if (child + 1 < _con.size() && comFunc(_con[child], _con[child + 1])) { ++child; } //if (_con[parent] < _con[child]) if (comFunc(_con[parent], _con[child])) { swap(_con[parent], _con[child]); parent = child; child = parent * 2 + 1; } else { break; } } } void pop() { assert(!_con.empty()); swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); AdjustDown(0); } const T& top() { return _con[0]; } size_t size() { return _con.size(); } bool empty() { return _con.empty(); } private: Container _con; };
代码解释:
适配器是一种设计模式(设计模式是一套被反复使用的,多数人知晓的,经过分类编目的,代码设计经验的总结),该模式是讲一个类的接口转换成客户希望的另一个接口。
虽然stack和queue也可以存放元素,但是在STL中并没有将其划分在容器的行列,而是将其称为容器适配器,这是因为栈和队列只是对其他容器的接口进行了包装,STL中stack和queue默认使用deque,比如:
当然了,这里的容器都是默认容器,容器不唯一,我们可以显式传对应的容器。