最近学习了 STL 中的三种容器适配器并亲手实现了它们的简化版本。这篇文章记录实现细节、易错点以及核心思想--具体内容可见代码注释部分一、stack 适配器基于底层容器实现栈LIFO。提供构造可选传入容器对象。empty()、size()判断空、大小const。push()、pop()入栈、出栈。top()返回栈顶元素const 和非 const。swap()交换两个栈。namespace JMP1 { template class T,class Container dequeT 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(stackT 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 dequeT 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(queueT x) { std::swap(_con, x._con); } private: Container _con; }; };三、仿函数less和Greater用于自定义比较规则lessTx yGreaterTx y均实现operator()为const。templateclass T class less { public: bool operator()(const T x,const T y) const//每次写完成员函数都要考虑 const 是否可以加 应该成为肌肉记忆 { return x y; } }; templateclass 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 { templateclass T class less { public: bool operator()(const T x,const T y) const//每次写完成员函数都要考虑 const 是否可以加 应该成为肌肉记忆 { return x y; } }; templateclass T class Greater { public: bool operator()(const T x,const T y) const { return x y; } }; templateclass T, class Container vectorT, class Compare lessT//仿函数还没加进去 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 (child0) { 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_queueT x) { std::swap(_con, x._con); } private: Container _con; Compare _comp; }; };五、常见易错点const 正确性不修改对象的成员函数都加了const。仿函数支持priority_queue使用Compare _comp成员比较时调用_comp(a,b)。默认参数构造函数提供了默认值。交换swap成员函数交换底层容器。我的gitee仓库https://gitee.com/jiangmingpeng0716/c-learning-process
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 dequeT 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(stackT 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 dequeT 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(queueT x) { std::swap(_con, x._con); } private: Container _con; }; };三、仿函数less和Greater用于自定义比较规则lessTx yGreaterTx y均实现operator()为const。templateclass T class less { public: bool operator()(const T x,const T y) const//每次写完成员函数都要考虑 const 是否可以加 应该成为肌肉记忆 { return x y; } }; templateclass 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 { templateclass T class less { public: bool operator()(const T x,const T y) const//每次写完成员函数都要考虑 const 是否可以加 应该成为肌肉记忆 { return x y; } }; templateclass T class Greater { public: bool operator()(const T x,const T y) const { return x y; } }; templateclass T, class Container vectorT, class Compare lessT//仿函数还没加进去 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 (child0) { 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_queueT x) { std::swap(_con, x._con); } private: Container _con; Compare _comp; }; };五、常见易错点const 正确性不修改对象的成员函数都加了const。仿函数支持priority_queue使用Compare _comp成员比较时调用_comp(a,b)。默认参数构造函数提供了默认值。交换swap成员函数交换底层容器。我的gitee仓库https://gitee.com/jiangmingpeng0716/c-learning-process
