STL-- C++ stack_queue _priority_queue类模拟实现-编程实验室

最近学习了 STL 中的三种容器适配器，并亲手实现了它们的简化版本。这篇文章记录实现细节、易错点以及核心思想--具体内容可见代码注释部分

一、stack 适配器

基于底层容器实现栈（LIFO）。提供：

构造：可选传入容器对象。
empty()、size()：判断空、大小（const）。
push()、pop()：入栈、出栈。
top()：返回栈顶元素（const 和非 const）。
swap()：交换两个栈。

namespace JMP1 { template <class T,class Container = deque<T>> class stack { public: stack(const Container& ctnr = Container()) :_con(ctnr) { } bool empty() const { return _con.empty(); } void push(const T& data) { _con.push_back(data); } void pop() { _con.pop_back(); } T& top() { return _con.back(); } const T& top() const { return _con.back(); } void swap(stack<T>& x) { std::swap(_con, x._con); } size_t size() const { return _con.size(); } private: Container _con; }; };

二、queue 适配器

基于底层容器实现队列（FIFO）。提供：

构造：可选传入容器对象。
empty()、size()：判断空、大小（const）。
push()、pop()：入队、出队。
front()、back()：访问队首/队尾元素（const 和非 const）。
swap()：交换两个队列。

namespace JMP2 { template <class T,class Container = deque<T>> class queue { public: queue(const Container& ctnr = Container()) :_con(ctnr) { } bool empty() const { return _con.empty(); } size_t size() const { return _con.size(); } T& front() { return _con.front(); } const T& front() const { return _con.front(); } T& back() { return _con.back(); } const T& back() const { return _con.back(); } void push(const T& data ) { _con.push_back(data); } void pop() { _con.pop_front(); } void swap(queue<T>& x) { std::swap(_con, x._con); } private: Container _con; }; };

三、仿函数（`less`和`Greater`）

用于自定义比较规则：

less<T>：x < y
Greater<T>：x > y
均实现operator()为const。

template<class T> class less { public: bool operator()(const T& x,const T& y) const//每次写完成员函数都要考虑 const 是否可以加 应该成为肌肉记忆 { return x < y; } }; template<class T> class Greater { public: bool operator()(const T& x,const T& y) const { return x > y; } };

四、priority_queue 适配器

基于底层容器（默认vector）和比较器（默认less）实现二叉堆（默认最大堆）。提供：

构造函数：
- priority_queue(const Container&, const Compare&)：用容器和比较器构造。
- 模板迭代器构造函数：用 [first, last) 区间构造，并建堆。
容量：empty()、size()（const）。
访问：top()返回堆顶元素（const 和非 const）。
修改：
- push()：插入元素，向上调整。
- pop()：删除堆顶，向下调整。
- swap()：交换两个优先队列。
辅助算法：
- adjust_up()：向上调整（上浮）。
- adjust_down()：向下调整（下沉）。

namespace JMP3 { template<class T> class less { public: bool operator()(const T& x,const T& y) const//每次写完成员函数都要考虑 const 是否可以加 应该成为肌肉记忆 { return x < y; } }; template<class T> class Greater { public: 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: //priority_queue() = default; template <class InputIterator> priority_queue(InputIterator first, InputIterator last, const Compare& comp = Compare())//实现迭代器构造函数 :_comp(comp)//初始化列表的这个细节不能忘 { Container v(first, last); if (!v.empty())//当size为0时出现 溢出情况 若写的条件类型是size_t就会导致无限循环 { for (int i = (v.size() - 1 - 1) / 2; i >= 0; i--)//其实可以根据传什么参数来 反推前面的代码可能是什么样子 { adjust_down(v, i); } } _con = v; } priority_queue( const Container& ctnr = Container(),const Compare & comp = Compare()) :_con(ctnr) ,_comp(comp) { } bool empty() const { return _con.empty(); } size_t size() const { return _con.size(); } T& top() { return _con.front(); } const T& top() const { return _con.front(); } void adjust_up(Container &hp,size_t child) { size_t parent = (child - 1) / 2; while (child>0) { if (_comp(hp[parent], hp[child])) { std::swap(hp[child], hp[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } void push(const T& data) { _con.push_back(data); adjust_up(_con, _con.size()-1); } void adjust_down(Container& hp, size_t parent) { size_t child = parent * 2 + 1; while (child < hp.size()) { if (child + 1 < hp.size() && _comp(hp[child], hp[child + 1])) ++child; if (_comp(hp[parent],hp[child] )) { std::swap(hp[child], hp[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } void pop() { std::swap(_con.front(),_con.back()); _con.pop_back(); adjust_down(_con,0); } void swap(priority_queue<T>& x) { std::swap(_con, x._con); } private: Container _con; Compare _comp; }; };