网站建设挣钱,今天上海重大新闻事件,php综合网站源码,北京网站建设服务公司目录
一、栈#xff08;stack#xff09;
1.stack的使用
2.容器适配器
3.stack的模拟实现
二、队列#xff08;queue#xff09;
1.queue的使用
2.queue的模拟实现
三、双端队列#xff08;deque#xff09;
1.vector#xff0c;list的优缺点
2.认识deque
四…目录
一、栈stack
1.stack的使用
2.容器适配器
3.stack的模拟实现
二、队列queue
1.queue的使用
2.queue的模拟实现
三、双端队列deque
1.vectorlist的优缺点
2.认识deque
四、priority_queue-优先级队列
1.priority_queue的使用
2.priority_queue的模拟实现
3.仿函数 一、栈stack
1.stack的使用
stack是一种容器适配器专门用在具有后进先出操作的上下文环境中其删除只能从容器的一端进行元素的插入与提取操作。 相信stack的使用大家都已经熟悉了下面的所有接口也都很好理解 测试代码
#includeiostream
#includestack
using namespace std;void test()
{stackint s;s.push(1);s.push(2);s.push(3);s.push(4);while (!s.empty()){cout s.top() ;s.pop();}
}int main()
{test()return 0;
}
2.容器适配器
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)该种模式是将一个类的接口转换成客户希望的另外一个接口。简单而言就是将一个类设计为另一个类的封装。
比如说下面的stack和queue的实现就是一个很好的例子。
设计模式的使用将提高软件系统的开发效率和软件质量节省开发成本。有助于初学者深入理解面向对象思想设计模式使设计方案更加灵活方便后期维护修改。
3.stack的模拟实现
我们之前提到过代码的复用既然已经有现成的东西了我为什么不用呢
stack在我们看来是一个容器数据只能后进先出这个容器可以是vector也可以是list甚至更多的数据结构。也就是说我们如果以vector作为stack的底层数据结构stack的尾插就可以使用vector的push_back()尾删就可以使用vector的pop_back()。以vector作为stack的底层数据结构也是一样的只是使用了list的接口这就是一种适配器的模式。
stack是一个模板类有两个模板参数T标识存储的数据类型container表示实现stack的底层数据结构。
stack我们更常用vector作为被封装的类
#pragma once
#includevector
#include listnamespace my_stack
{templateclass T, class container dequeTclass stack{public:void push(const T x){_con.push_back(x);}void pop(){_con.pop_back();}const T top(){return _con.back();}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:container _con;};
}
二、队列queue
1.queue的使用
队列也是一种容器适配器专门用于在FIFO上下文(先进先出)中操作其中从容器一端插入元素另一端提取元素。 queue的接口也差不多 测试代码
#includeiostream
#includequeue
using namespace std;void test()
{queueint q;q.push(1);q.push(2);q.push(3);q.push(4);while (!s.empty()){cout s.front() ;q.pop();}
}int main()
{test()return 0;
}
2.queue的模拟实现
依然是代码的复用不过这次是先进先出。
queue我们更常用list作为被封装的类
#pragma once
#includevector
#includelistnamespace my_queue
{templateclass T, class container dequeTclass queue{public:void push(const T x){_con.push_back(x);}void pop(){_con.pop_front();}const T top(){return _con.back();}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:container _con;};
}
三、双端队列deque
在stack和deque中都有一个缺省的被封装的类以实现适配器这个缺省值为什么既不是vector也不是list而是deque呢最主要的原因还是vectorlist各有其优缺点。
1.vectorlist的优缺点
vector
优缺点支持随机访问但是头部和中部的插入删除效率低并且还需要扩容操作。
list
优缺点list在任何地方插入删除效率都很高但是链表不支持随机访问且CPU高速缓存命中率低CPU在访问内存时往往是取一块较大的内存然后再其中找对应的数据位置链表开辟的每一个节点的地址位置时不确定的所以相比于连续的vector缓存的命中率低
而deque这个类是一个缝合怪它既有vector的随机访问也有list的高效率插入删除。所以对于这里选择deque最好。
2.认识deque
1底层原理
我们再cplusplus网站中可以查看deque
deque - C Reference (cplusplus.com)
这是deque实现的思路
deque是由中控和一段一段的buffer数组组成的也就是说deque并不是完全连续的空间它是由一段一段这样的buffer数组通过算法拼接而成而所谓中控其实是一个指针数组每一个元素都保存着各个buffer的数组指针。我们可以大致理解为C语言中的二维数组或者C的vector。 它的头尾插大概是这样的 查找也是一样先在map找buffer再在buffer找数据。
我们可以很明显地发现它的下标访问相比vector一定是复杂而又缓慢的。当deque在中间插入数据时它挪动数据的算法可就比vector复杂多了与list相比的消耗就更大了。
2迭代器
由于deque的迭代器设计也很复杂所以deque不适合遍历操作。在遍历时deque的迭代器要频繁地检测其是否移动到数组buffer的的边界这就导致它的访问效率很低下。而在现实中遍历操作的使用是很频繁的所以需要线性结构时大多数情况下都会考虑vector和listdeque的应用很少而我们目前能看到的一个就是在STL中作为stack和queue的底层数据结构。
我们大致看一下它的迭代器的实现 deque的维护需要两个迭代器分别是start和finsh。因为deque更多时候是作为stack和queue的底层默认容器来使用的所以一般deque是不需要在中间插入数据的那么有了分别指向数据头尾的start和finsh就可以很好地处理头插与尾插。迭代器中的frist和last指向buffer的头尾如果buffer满了就可以通过node链接到map主控再新开辟buffer。其中的头部和尾部数据获取top()和back()就通过start的cur和finish的cur控制。
总的来说deque虽然集成了vector和list的优点但它也不是完美的而在写代码中我们大部分时间都会追求极致它也就很少用到了。
四、priority_queue-优先级队列
优先级队列priority_queue虽然叫队列但它不满足先进先出的条件优先级队列会保证每次出队列的元素是队列所有元素中优先级最高的那个元素这个优先级可以通过元素的大小等进行定义。比如定义元素越大或越小优先级越高那么每次出队都是将当前队列中最大最小的那个元素出队它的底层其实就是一个堆也就是二叉树的结构。
1.priority_queue的使用
priority_queue的使用来说也是比较简单的接口也比较少。 测试代码
#includeiostream
using namespace std;
void test()
{priority_queueint p;p.push(7);p.push(1);p.push(9);p.push(2);p.push(3);p.push(4);while (!p.empty()){cout p.top() ;p.pop();}
}
int main()
{test();return 0;
}
2.priority_queue的模拟实现
我这里建的是小堆大堆也是同理如果不记得向上向下调整可以看这里
(6条消息) 二叉树详解_聪明的骑士的博客-CSDN博客
templatetypename T, class container vectorT
class priority_queue
{
public:templateclass iteratorpriority_queue(iterator first, iterator last)//建堆:_con(first, last){for (size_t i (_con.size() - 1 - 1) / 2; i 0; --i)//所有节点的父节点全部向下调整size()减1得到尾下标再减1除2得到父节点{adjust_down(i);}}void adjust_down(size_t parent){size_t min_child parent * 2 1;while (min_child _con.size()){if (min_child 1 _con.size() _con[min_child] _con[min_child 1]){minchild;}if (_con[min_child] _con[parent]){std::swap(_con[min_child], _con[parent]);parent min_child;min_child parent * 2 1;}elsebreak;}}void adjust_up(size_t child){size_t parent (child - 1) / 2;while (parent 0){if (_con[parent] _con[child]){std::swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}elsebreak;}}void push(const T x){_con.push_back(x);_con.adjust_up(_cons.size() - 1);}void pop(){assert(!_con.empty());std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T top(){return _con[0];}const empty() const{return _con.empty();}size_t size() const{return _con.size();}private:container _con;
};
3.仿函数
1什么是仿函数
仿函数(functor)就是使一个类的使用看上去像一个函数。本质就是在类中实现一个()的重载函数这个类就有了类似函数的行为就成为一个仿函数类了。
namespace function
{templateclass Tclass less{public:bool operator()(const T x, const T y){return x y;}};templateclass Tclass more{public:bool operator()(const T x, const T y){return x y;}};
}
int main()
{function::lessint lessFunc;//创建一个变量if (lessFunc(3, 2))//用变量也可以达到函数的效果cout yes endl;elsecout no endl;return 0;
}
2仿函数的使用
我们写一个插入排序
namespace sort
{templateclass Tvoid insert_sort(T* arr, size_t size){int i 1;for (i 1; i size; i){int j i;while (j 0){if (arr[j - 1] arr[j]){std::swap(arr[j - 1], arr[j]);--j;}elsebreak;}}}
}
排序一个数组
int main()
{int arr[10] { 9,8,7,6,5,4,3,2,1,0 };sort::insert_sortint(arr, sizeof(arr) / sizeof(arr[0]));for (int i 0; i sizeof(arr) / sizeof(arr[0]); i){printf(%d , arr[i]);}
}
//结果0 1 2 3 4 5 6 7 8 9
我们发现如果我们想把数组排为降序那么就要改变底层代码中的arr[j - 1] arr[j]变为arr[j - 1] arr[j]再大部分情况下使用者都是不能看到代码的实现的使用者也就不能更改为排降序。那么我们是否可以通过加一个函数指针来实现呢
template
void insert_sort(T* arr, size_t size, bool (*ptr)(int, int))
函数指针最直观的特点就是它太不直观了阅读性很低而且这个函数还要传递更多的参数。
所以我们为什么部添加一个仿函数的模板参数来实现升降序的控制呢
我们修改一下就可以正常运行了
templateclass T, typename compare
void insert_sort(T* arr, size_t size, typename compare)
{int i 1;for (i 1; i size; i){int j i;while (j 0){if (compare(arr[j - 1], arr[j])){std::swap(arr[j - 1], arr[j]);--j;}else{break;}}}
}void test_insertSort()
{func::lessint lessFunc;int arr[] { 9,8,7,6,5,4,3,2,1,0 };insert_sort(arr, sizeof(arr) / sizeof(arr[0]), lessFunc);for (int i 0; i sizeof(arr) / sizeof(arr[0]); i){printf(%d , arr[i]);}
}int main()
{test_insertSort();return 0;
}
在比较内置类型时可以直接使用大于小于号而比较自定义类型的大小我们可以通过大于小于的重载确定类型比较大小的方式。但是如果传递的参数是指针类型我们传指针大部分时候都是为了比较指针指向的数据如果只是比较指针的数值本身就失去比较的意义了。
那么对于指针的比较就不应该沿用之前的比较方式所以我们创建一个struct类-默认公共类然后通过函数模板的调用实现了比较非自定义变量指针的大小相当于堆指针的特殊化处理。
#include iostream
#include queue
#include functionalusing namespace std;class Date
{
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);}friend ostream operator(ostream _cout, const Date d){_cout d._year - d._month - d._day;return _cout;}private:int _year;int _month;int _day;
};struct PDateLess
{bool operator()(const Date* d1, const Date* d2){return *d1 *d2;}
};struct PDateGreater
{bool operator()(const Date* d1, const Date* d2){return *d1 *d2;}
};void TestPriorityQueue()
{// 大堆需要用户在自定义类型中提供的重载priority_queueDate q1;q1.push(Date(2018, 10, 29));q1.push(Date(2018, 10, 28));q1.push(Date(2018, 10, 30));cout q1.top() endl;// 如果要创建小堆需要用户提供的重载priority_queueDate, vectorDate, greaterDate q2;q2.push(Date(2018, 10, 29));q2.push(Date(2018, 10, 28));q2.push(Date(2018, 10, 30));cout q2.top() endl;// 大堆priority_queueDate*, vectorDate*, PDateLess q3;q3.push(new Date(2018, 10, 29));q3.push(new Date(2018, 10, 28));q3.push(new Date(2018, 10, 30));cout *q3.top() endl;// 小堆priority_queueDate*, vectorDate*, PDateGreater q4;q4.push(new Date(2018, 10, 29));q4.push(new Date(2018, 10, 28));q4.push(new Date(2018, 10, 30));cout *q4.top() endl;
}int main()
{TestPriorityQueue();return 0;
}
