保定网站seo服务,上海标志设计公司上海品牌设计,百度网站统计,网站制作外包栈和队列的模拟实现 容器适配器priority_queue(优先级队列#xff09;priority_queue的使用priority_queue的模拟实现#xff1a; 仿函数什么叫仿函数#xff1f;需要自己实现仿函数的情况#xff1a; 栈的模拟实现队列的模拟实现deque#xff08;vector和list的缝合怪priority_queue的使用priority_queue的模拟实现 仿函数什么叫仿函数需要自己实现仿函数的情况 栈的模拟实现队列的模拟实现dequevector和list的缝合怪为什么选择deque作为stack和queue的底层默认容器deque的优缺点 vector和list的优缺点 容器适配器
容器适配器Container Adapter 是一种基于现有容器类如 vector、deque、list 等构建的 包装器Wrapper。 1.容器适配器本身不直接管理数据存储而是依赖底层容器称为 底层容器 或 基础容器实现存储和访问操作。例如 stack 默认基于 deque 实现。 queue 默认基于 deque 实现。 priority_queue 默认基于 vector 实现。 2.适配器会屏蔽底层容器的部分接口仅暴露特定操作所需的接口。 栈stack 只允许在栈顶进行插入push和删除pop操作屏蔽了随机访问等功能。 队列queue 只允许在队尾插入push、队头删除pop屏蔽了中间元素的操作。 3.底层容器可定制。 #include stack
#include vector
#include list// 使用 vector 作为底层容器
std::stackint, std::vectorint stack1;// 使用 list 作为底层容器
std::stackint, std::listint stack2;priority_queue(优先级队列
priority_queue的使用
int main()
{priority_queueint pq;//默认是大的优先级高(大堆//变小堆//priority_queueint,vectorint,greaterint pq;pq.push(4);pq.push(1);pq.push(5);pq.push(7);pq.push(9);while (!pq.empty()){cout pq.top() ;pq.pop();}cout endl;return 0;
}大堆调试 小堆调试
priority_queue的模拟实现
#includevectortemplateclass T
class Less
{
public:bool operator()(const T x, const T y){return x y;}
};templateclass T
class Greater
{
public:bool operator()(const T x, const T y){return x y;}
};namespace bit
{// 默认是大堆templateclass T, class Container vectorT, class Compare LessTclass priority_queue{public:void AdjustUp(int child){Compare com;int parent (child - 1) / 2;while (child 0){//if (_con[parent] _con[child])if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);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){// 先假设左孩子小size_t child parent * 2 1;Compare com;while (child _con.size()) // child n说明孩子不存在调整到叶子了{// 找出小的那个孩子//if (child 1 _con.size() _con[child] _con[child 1])if (child 1 _con.size() com(_con[child], _con[child 1])){child;}//if (_con[parent] _con[child])if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent child;child parent * 2 1;}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}const T top(){return _con[0];}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}
仿函数
什么叫仿函数
仿函数本质是一个类这个类重载operator(),他的对象可以像函数一样使用
templateclass T
class Less
{
public:bool operator()(const T x, const T y){return x y;}
};templateclass T
class Greater
{
public:bool operator()(const T x, const T y){return x y;}
};// 升序
// 降序
templateclass Compare
void BubbleSort(int* a, int n, Compare com)
{for (int j 0; j n; j){// 单趟int flag 0;for (int i 1; i n - j; i){//if (a[i] a[i - 1])if (com(a[i], a[i - 1])){swap(a[i - 1], a[i]);flag 1;}}if (flag 0){break;}}
}int main()
{Lessint LessFunc;Greaterint GreaterFunc;// 函数对象仿函数本质是一个对象cout LessFunc(1, 2) endl;cout LessFunc.operator()(1, 2) endl;int a[] { 9,1,2,5,7,4,6,3 };BubbleSort(a, 8, LessFunc);BubbleSort(a, 8, GreaterFunc);BubbleSort(a, 8, Lessint());BubbleSort(a, 8, Greaterint());return 0;
}需要自己实现仿函数的情况
1.类类型不支持比较大小。 2.支持比较大小但是比较的逻辑不是你想要的。
class Date
{friend ostream operator(ostream _cout, const Date d);
public:Date(int year 1900, int month 1, int day 1): _year(year), _month(month), _day(day){}bool operator(const Date d)const{return (_year d._year) ||(_year d._year _month d._month) ||(_year d._year _month d._month _day d._day);}bool operator(const Date d)const{return (_year d._year) ||(_year d._year _month d._month) ||(_year d._year _month d._month _day d._day);}
private:int _year;int _month;int _day;
};ostream operator(ostream _cout, const Date d)
{_cout d._year - d._month - d._day;return _cout;
}class DateLess
{
public:bool operator()(Date* p1, Date* p2){return *p1 *p2;}
};
//测试
priority_queueDate*, vectorDate*, DateLess q2;priority_queueDate* q2;q2.push(new Date(2018, 10, 29));q2.push(new Date(2018, 10, 28));q2.push(new Date(2018, 10, 30));cout *q2.top() endl;q2.pop();cout *q2.top() endl;q2.pop();cout *q2.top() endl;q2.pop();栈的模拟实现
#includedequenamespace bit
{// Container适配转换出stacktemplateclass T, class Container dequeT//deque:vector和list的缝合怪class stack{public:void push(const T x){_con.push_back(x);}void pop(){_con.pop_back();}const T top() const{return _con.back();}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};}
队列的模拟实现
#includedequenamespace bit
{// Container适配转换出queuetemplateclass T, class Container dequeTclass queue{public:void push(const T x){_con.push_back(x);}void pop(){_con.pop_front();}const T front() const{return _con.front();}const T back() const{return _con.back();}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;};
}dequevector和list的缝合怪
为什么选择deque作为stack和queue的底层默认容器 stack是一种后进先出的特殊线性数据结构因此只要具有push_back()和pop_back()操作的线性结构都可以作为stack的底层容器比如vector和list都可以queue是先进先出的特殊线性数据结构只要具有push_back和pop_front操作的线性结构都可以作为queue的底层容器比如list。但是STL中对stack和queue默认选择deque作为其底层容器主要是因为 stack和queue不需要遍历(因此stack和queue没有迭代器)只需要在固定的一端或者两端进行操作。在stack中元素增长时deque比vector的效率高(扩容时不需要搬移大量数据)queue中的元素增长时deque不仅效率高而且内存使用率高。结合了deque的优点而完美的避开了其缺陷。 deque的优缺点 vector和list的优缺点
