当前位置：首页 > news >正文

C++学习：模拟priority_queue

news 2025/6/29 8:05:31

一：仿函数

开始模拟前咱先了解一下仿函数。有了它，我们就可以自己传个代码让优先级队列升序还是降序，自己模拟时也不用在需要升序降序时改代码。这是个很有用的东西。

不写模版也可以，但模版能用在更多地方嘛

template <class T>
struct Less
{bool operator()(const T& x, const T& y){return x < y;}
};
template<class T>
struct Greater
{bool operator()(const T& x, const T& y){return x > y;}
};

这里没用class，因为反正都要用的就直接用默认public的struct了。定义时可以看成重载小括号，千万别漏了嗷。接下来用直接像函数一样用就行了，我们来模拟。

二：优先级队列

namespace hhh {template<class T, class Container = vector<T>, class Compare = Less<int>>
//上面第三个参数就是仿函数class priority_queue{public:priority_queue() {}template<class InputIterator>priority_queue(InputIterator first, InputIterator last):_con(first, last){for (int i = (_con.size() - 2) / 2; i >= 0; i--)adjust_down(i);}void adjust_up(int child){Compare com;//使用仿函数前别忘先搞个对象int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child]))//这里就在用了 看到吧不用写小于大于了{swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else break;}}void adjust_down(int parent){Compare com;size_t child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() &&com(_con[child], _con[child + 1]))//这里也是++child;if (com(_con[child], _con[parent])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else break;}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T& top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};
}