stack&&queue
在这之前我们要清楚，容器和适配器是不一样的，适配器的底层是容器，而且根据需求，可以用不同的容器，构造出类似的容器。
而stack和queue里的FIFOqueue和priority_queue都是适配器。
目录
一.stack
1.使用
1.1构造方式
c++11有7种构造方式，但我这里就说下常用的一种，其他的可以自己去c++文档里面查 默认构造 stack<int>k; 拷贝构造 stack<int>a(k); 赋值 stack<int>a=k;注意，更具体的一些多参数，比如调用不同的容器，可以看我下面的模拟
1.2遍历方式
while (!a.empty()) { cout << a.top(); a.pop(); } 注意，stack是没有迭代器的，所以范围for是不能用的，因此 用上面的方式来遍历
1.3成员函数
1.3.1empty()
bool empty() const; 判断栈是不是空的，是空的就返回真，不是空就返回假 stack<int>a; a.empty();1.3.2size()
size_type size() const; 返回栈里面有多少个元素 stack<int>a; a.size();1.3.3top()
value_type& top(); const value_type& top() const; 两个版本，一个是返回无const修饰，一个是返回const修饰 返回栈顶元素 stack<int>a; a.top();1.3.4push()
void push (const value_type& val); void push (value_type&& val); 同理，插入const修饰或无const修饰的值 入栈操作 stack<int>a; a.push(3);1.3.5pop()
void pop(); 出栈操作 stack<int>a; a.pop();1.3.6swap()
void swap (stack& x) 交换操作 stack<int>a; a.push(3); stack<int>k; k.swap(a);
2.模拟
#pragma once //注意stack严格意义上只是适配器,可以适配不同的容器 //底层数据的存储、调用都是通过其他容器来实现 //stack本身可以适配vector，list，deque //库里默认是deque namespace maba { //第二个参数传容器类型，例如vector<int>,list<int>,deque<int> template<class T,class Container=deque<T>> class stack { public: void push(const T& x) { con.push_back(x); } void pop() { con.pop_back(); } bool empty() { return con.empty(); } const T& top() { return con.back(); } size_t size() { return con.size(); } private: Container con; }; }
二 queue
1.FIFOqueue使用
1.1构造方式
queue<int>mp;//默认构造 mp.push(1); queue<int>m1 = mp;//赋值 queue<int>m2(mp);//拷贝构造
1.2遍历方式
queue<int>mp;//默认构造 mp.push(1); mp.push(2); while (!mp.empty()) { cout << mp.front(); mp.pop(); }
1.3成员函数
1.3.1empty()
很常见，比如，队列为空返回真，不为空返回假
queue<int>mp;//默认构造 mp.push(1); mp.push(2); while (!mp.empty()) { cout << mp.front(); mp.pop(); }
1.3.2size()
返回当前队列里的元素个数
a1.size()
1.3.3front()
返回队列的队头元素
queue<int>mp;
mp.push(1);
int a1=mp.front();
1.3.4back()
返回队尾元素
queue<int>mp;//默认构造 mp.push(1); mp.push(2); cout << mp.back(); //2
1.3.5push()
在队尾插入数据
queue<int>mp;//默认构造 mp.push(1); mp.push(2);
1.3.6pop()
删除队头数据
mp.pop();
1.3.7 swap()
交换,与其他队列进行交换数据
mp.swap(m2);
2.FIFOqueue模拟
#pragma once //queue也是适配器，但是可以适配的内容不多 //vector不行，list可以，deque也可以，主要还是看容器提供的操作与适配器里的是否匹配 //最合适的还是deque namespace maba { template<class T,class Container=deque<T>> class queue { public: void push(const T& x) { con.push_back(x); } void pop() { con.pop_front(); } const T& front() { return con.front(); } const T& back() { return con.back(); } size_t size() { return con.size(); } bool empty() { return con.empty(); } private: Container con; }; }
3.priority_queue使用
使用上跟FIFOqueue区别不大，我就不啰嗦了,注意的是priority_queue没有front()和back(),只有top(),
我们知道的是，FIFO是先进先出，而priority_queue的底层逻辑是堆，可以实现优先级排列，比如默认是大堆，最大的数据在堆顶，利用堆排序的相关操作（库里algorithm有相应的操作函数，具体这里不多说，可以自己去了解下）。
priority_queue<int>q; q.push(1); q.push(2); //2 1 //此时是默认大堆 priority_queue<int,vector<int>,greater<int>>q1; q1.push(2); q1.push(3); //2 3 //第二个参数默认就是vector，如果我们不需要改变优先级，只需要默认的大堆的话 //就可以像第一个q一样，只用给一个类型。 //第三个参数类似，默认是less,如果不需要改可以不加 //比如此时，我们建立的q1就是一个小堆。注意，针对自定义类型，我们需要给他们进行相应><运算符重载
#include<iostream> #include<queue> #include<string> using namespace std; class kp { public: int a; string b; kp(int _a=-1, string _b="") { a = _a, b = _b; } //方便构造 bool operator >(const kp &h) const { if (a == h.a) { return b > h.b; } return a > h.a; } bool operator<(const kp& h)const { if (a == h.a)return b < h.b; return a < h.a; } //sort是个函数模板，参数，传的是对象，所以，我们必须传一个具体的比较方法，比如一个bool函数，又或者一个实例化的仿函数对象 //因此sort可以直接在bool函数里设定自定义类型对象的比较方式 //而priority_queue是个类模板，第三个参数传的是类型，所以，我们不能传具体的比较方法 //因此，为了能够适应自定义类型，我们可以把自定义类型的><运算符重载，这样就可以依赖原有的类模板，默认（less），greater，来实现自定义类型的排序了 //注意，我试过自己写个类模板，但是我发现，自定义类型的关键就是我们不知道里面有多少个参数， //我看了less和greater的定义，我发现，重点还是在重载了自定义类型的比较运算符，所以没有必要 //自己写一个less，greater，用现成的就行. }; int main() { //重载了< priority_queue<kp,vector<kp>,greater<kp>>q; q.push(kp(1,"wdw")); q.push(kp(2, "wdd")); //重载了> priority_queue<kp>q1; q1.push(kp(4, "wda")); q1.push(kp(5, "wda")); }
4.priority_queue模拟
在写这个之前，我们先看下仿函数，仿函数是通过类的方式，用起来像函数，主要是为了方便。
namespace maba{ template<class T> class ess { public: bool operator() (const T& a, const T& b) { return a < b; } }; template<class T> class greaer { public: bool operator() (const T& a, const T& b) { return a > b; } }; } ess a; a(3,4); //我这里maba是我自己创的命名空间，区别于std priority_queue<int, vector<int>, maba::ess<int>>mp; mp.push(1); mp.push(3); mp.push(2); mp.push(3); while (!mp.empty()) { cout << mp.top() << " "; mp.pop(); }#pragma once //queue也是适配器，但是可以适配的内容不多 //vector不行，list可以，deque也可以，主要还是看容器提供的操作与适配器里的是否匹配 //最合适的还是deque namespace maba { template<class T,class Container=deque<T>> class queue { public: void push(const T& x) { con.push_back(x); } void pop() { con.pop_front(); } const T& front() { return con.front(); } const T& back() { return con.back(); } size_t size() { return con.size(); } bool empty() { return con.empty(); } private: Container con; }; //这块的仿函数主要是方便调用，而且相比函数指针 //利用类模板，只需要传类型，就可以构造相应的类，重载了()之后，用起来跟函数一样 //在priority_queue这，也只需要传个类型即可，不需要自己额外手动写一个函数。 //平时用的时候，不用自己写这两类，库里有。 template<class T> class ess { public: bool operator() (const T& a, const T& b) { return a < b; } }; template<class T> class greaer { public: bool operator() (const T& a, const T& b) { return a > b; } }; //注意，优先级队列本质上还是个堆，要用到[]访问，deque的[]访问比vector慢，所以库里默认的是vector //大坑，swap如果报错，是因为你cpp文件的头文件调用问题 //如果你写顺了，把展开std命名空间的语句写在了最后面，这时候，当我们自己写的queue头文件展开了，这时候 //还没碰到这语句，也就是说，std命名空间还没展开，这样编译器就找不到swap了，所以如果你是这样写的，在我们 //自己写的queue头文件的swap前面加个std::即可。 template<class T, class Container = vector<T>,class Compare=ess<T>> //第三个参数，是用来比较的仿函数 class priority_queue { public: Compare com; void adjust_up(int child) { int parent = (child - 1) / 2; while (child > 0) { if (com(con[child],con[parent])) { swap(con[child], con[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } void adjust_down(int parent) { int child = parent * 2 + 1; while (child < con.size()) { if (child + 1 < con.size() && com(con[child + 1], con[child])) { 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]; } size_t size() { return con.size(); } bool empty() { return con.empty(); } private: Container con; }; }w
三deque
1.使用
在使用上，可以看作是list和vector的结合，所以我这就只是罗列一下(直接从文档网站那截图下来的)deque - C++ Reference (cplusplus.com)
2.deque分析
首先，从使用上我们就可以看出vector和list的影子，这里我不做具体的模拟，只是做一些底层分析
vector本身具有：下标随机访问，缓存命中高的优点，这两个优点都是得益于物理存储结构连续的（缓存命中高，可以理解为，我们电脑在使用的时候，是有很多层缓存，硬盘，内存，缓存，缓存就可以理解为提前取一块区域的数据，命中高意味着每次取到的内容符合我们要求的几率高，而物理存储结构连续，说明相应数据是存储在一块相连的空间，那这样缓存就很容易命中）
但也由于这种结果，导致头插的效率很低（要挪动数据），扩容有消耗（扩容机制使得可能存在浪费现象）
list 得益于分散的物理结构，与vector恰恰相反，优点是任意位置插入数据效率很高，占用空间不会浪费（按需申请释放空间），但也有缺点，不支持下标随机访问，缓存命中低。
而deque，则两边都取点，尽量的结合了两者的优点
首先，利用中控（指针数组，存一段段空间的地址）这样的话，命中率也会提高（因为缓存每次截取也只是截取一部分，而之所以缓存命中很重要，是因为假如我们读第一个数据缓存了一部分数据，第二个数据也在这部分数据里，这样就可以节省去内存、硬盘找数据的次数了。而deque的这种结构，就可以做到节省读取内存、硬盘的次数），而对于vector的缺点（扩容有消耗）因为每段空间大小几乎相同，每次扩容比起vector的（2\1.5扩容）消耗小一些。
针对vector头插的劣势，deque的头插是在第一段空间插入数据（第一段空间默认是空的）
对于随机访问，假设每段空间都是10，那么第i个位置(假如头插过，那就让i-=第一个空间的数据个数)就是在第i/10个空间的第i%10的位置，效率很高。
但考虑中间插入删除的效率问题，每段空间不能保存一样大，否则效率比vector的还慢。
如果每段空间大小不用一样大，这样中间插入删除，只需要扩容或挪动数据，因为每段空间不会很大，这样效率也不差。
这样的话，为了维持随机访问，随机访问只能通过一段段空间找的方式了，所以效率会很慢
综合以上：deque的优点是头插头删，尾插尾删都不错，支持随机访问
缺点：随机访问的效率和中间插入删除的效率是一个鱼和熊掌不可兼得的问题，不同库的处理不同。
针对deque、vector、list，deque适用头插头删尾插尾删多，list适用中间插入删除多，vector适用下标随机访问多
接下来我们继续分析一下deque的迭代器。
跟vector和list不同，deque采用4个指针来构成一个迭代器
first是一段空间的开始，last一段空间的结束，cur当前空间中的某个数据，node是当前空间在中控的指针数组中的位置
而deque的迭代器成员，有两个，start（第一段空间，cur是第一个数据，first是第一段空间的开始，last是第一段空间的结束，node也是第一段空间在指针数据的位置），finish（最后一段空间，cur是最后一个数据的下一个位置，其他类似）
原文地址：https://blog.csdn.net/MXZSL/article/details/140335877
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！