STL---stack/queue/deque/priority_queue详解(从使用到底层)

前言stringvectorlist等容器都在我的C专栏里有收录重复的接口相似的使用我就不再过多介绍了大家可以去我的C专栏里看string那篇文章基本的使用写的比较详细。本文的重点在于讲解底层。stack和queue的使用#includequeue #includestack #includeiostream using namespace std; //stack和queue都没有迭代器因为要支持后进先出和先进先出 //因为迭代器支持随机访问但stack和queue的访问进出机制有着严格的规定 int main() { stackint st; st.push(1); st.push(2); st.push(3); st.push(4); while (!st.empty()) { cout st.top() ;//4 3 2 1 st.pop(); } cout endl; queueint q; q.push(1); q.push(2); q.push(3); q.push(4); while (!q.empty()) { cout q.front() ; q.pop(); } cout endl; return 0; }stack和queue的容器适配器底层实现思路传统的方式是用数组去实现栈链表去实现队列。但之前已经实现好了vector跟list没有必要再去单独的写了直接复用。这就是容器适配器的思路定义成模板参数传vector就相当于是一个数组栈传list就变成了链式栈队列也是一样的思路。拿stack举例stack的类模板就相当于是一个插头vector和list就是插座一个插头可以去适配许多不同的插座此谓容器适配器。这本质上也是一种封装stack和queue的上层都是固定的接口但是stack底层可以用数组链表deque来实现。queue底层可以用链表deque来实现。stack.h#pragma once #includevector #includelist #includeiostream using namespace std; namespace xxc { templateclass T, class Container vectorT class stack { public: //栈不需要写构造因为当成员变量是自定义类型的时候默认生成的构造会去调用它的构造 void push(const T x) { _con.push_back(x); } void pop() { _con.pop_back(); } const T top() const { return _con.back(); } T top() { return _con.back(); } size_t size() const { return _con.size(); } bool empty() const { return _con.empty(); } private: Container _con; }; }queue.h#pragma once #includevector #includelist #includeiostream using namespace std; namespace xxc { //queue不能用vector去适配 //第一点是vector不支持pop_front() //虽然可以用_con.erase(_con.begin())但依旧不建议因为vector的头删的效率太低了 templateclass T, class Container listT class queue { public: void push(const T x) { _con.push_back(x); } void pop() { _con.pop_front(); } T front() { return _con.front(); } const T front() const { return _con.front(); } T back() { return _con.back(); } const T back() const { return _con.back(); } size_t size() const { return _con.size(); } bool empty() const { return _con.empty(); } private: Container _con; }; }deque的底层(仅了解)在库里边stack跟queue的默认适配容器是deque。deque是双端队列兼具vector跟list的功能但是无法替代掉vector和list数组跟链表都有独属于它们极致的优点也有极致的缺点。当它们的功能集于一身的时候就显得很平庸了就是优缺点都不突出了因此deque基本是不会去使用的。数组和链表(带头双向循环链表的最优结构)的优缺点如下结构与迭代器deque既想像数组一样支持下标的随机访问拥有数组的高命中率的内存连续空间又要像链表一样即用即开空间。于是它将数据都存在了一个个buff数组里边一个buff数组满了再开一个buff数组每个buff数组的大小是一样的。deque还额外开了一个指针数组map也叫中控数组里边的指针指向的都是一个个buff数组当deque满了就代表中控数组满了就需要将map数组扩容而不需要像vector那样异地扩容还要拷贝原空间里的数据到新空间里map是指针数组每个数据都是固定的大小哪怕deque里边装的是自定义类型map数组里的每一个指针在32位地址下也依旧是4个字节大小异地扩容扩的是中控数组拷贝那些指针到新空间的代价可远远小于拷贝deque里的数据。deque的迭代器里边有4个指针first指针指向buff数组的开始last指针指向buff数组的结束node指针(二级指针)指向map中控数组中当前所在的buff的地址cur指针就用来便利当前的buff数组的。deque的结构就是有两个迭代器指针一个指向第一个buff数组一个指向最后一个buff数组还有两个指针一个是二级指针指向map数组一个是标记的map数组的总大小便于判断map数组是否要扩容。(类似以下这种样子)templateclass T struct _deque_iterator { T* cur; T* first; T* last; map_pointer node; }; templateclass T class deque { iterator start;//begin() iterator finish;//end() map_pointer map;//二级指针 T** size_type map_size; };知道了大致的结构就可以来分析一下用迭代器便利deque的时候其迭代器内部的operator*operator!operator大致是如何实现的了。如果还在当前的buff数组内operator*其实只要返回cur指向的数据就可以了operator则也就只是简单的cur但如果cur之后已经等于last那么整个迭代器就要指向下一个buff数组了node指向下一个buff的地址node解引用给给first由于每个buff数组的大小是确定的如下图的就是8那first8给给last就可以了cur在初始时就指向first此过程就是迭代器的移动。再简单说一下begin()和end()这两个迭代器begin()就没什么好说的了指向的就是第一个buff数组end()指向的是最后一个buff数组不太一样的主要是cur指针它指向的是最后一个buff里的最后一个有效元素的下一个位置(下图所示)。因此operator!比较的其实是cur指针是否相等。由此可见deque是极度依赖迭代器的。deque的尾插如果finish指向的buff数组没有满的话新数据尾插到buff数组的cur指向的位置随后cur如果curlast就说明此buff数组已经满了那就要新开一块空间map数组也要增加一个指针指向新开的buff数组如果map数组也满了则map数组也要扩容。deque的头插这里先知道一个小细节从上边的图片里边也能发现中控数组是从中间开始存放数据的前边空着的位置就是为了去头插使用的。先开一块buff数组的空间然后从后往前插入数据因为如果从前往后的话deque的逻辑结构就不连续了其他都类似first指向buff的起始位置last指向buff的结束位置cur指针指向当前插入的元素的位置如果再想插入元素就cur--往cur指向的位置去插入当curfirst的时候就代表当前的buff满了再同理去处理就可以了。deque的operator[]大致的逻辑就是先算出来该下标是在第几个buff的第几个位置*(*(nodei) j)。(下边是大致的计算逻辑代码)T operator[](size_t pos) { size_t i pos / 8;//假设每个buff数组的大小是8i算出来的就是第几个buff size_t j pos % 8;//算出来的j就是第i个buff里的第j下标的位置 //..... }有了上边的基本逻辑就可以来看看库里边的代码是怎么计算的了。由于库里边是复用的逻辑最终具体计算的代码在operator里边就直接看里边的代码就可以了(如下)。源码是先计算了相对位置offsetn是下标cur-first其实就是为了应对头插的那种情况头插之后第一个buff有可能是不满的cur-first就是计算第一个buff有几个空元素一起加到n里边去才对应n下标正确的数据计算完了offset就是判断如果就在当前的buff直接返回对应的cur。如果不是则就要计算offset在第几个buff的第几个位置由于%和/的效率低于加减一般都会规避掉%和/因此源码用的是减法的逻辑计算的相对位置。从简单的分析中就可以得知deque下标随机访问数据的效率基本上不变因为逻辑就是计算第几个buff的第几个下标加加减减效率也不算慢是远远高于list的(list下标访问需要0(N)的时间复杂度)但跟vector比还是差了很多。self operator(difference_type n) { difference_type offset n (cur - first); if (offset 0 offset difference_type(buffer_size())) cur n; else { difference_type node_offset offset 0 ? offset / difference_type(buffer_size()) : -difference_type((-offset - 1) / buffer_size()) - 1; set_node(node node_offset); cur first (offset - node_offset * difference_type(buffer_size())); } return *this; }总结deque优点deque适合头尾插入删除效率最高(相比vector和list)。头插vector效率低list每头插一次都要申请一个结点。尾插list也要申请一个结点插入一次vector一旦发生异地扩容需要重新开辟一大块空间并且把旧数据拷贝过来如果里边存着自定义类型将是一个大工程。deque的头插尾插只需要将数据给给*cur倘若buff数组满了重开一个buff也只需要new一块空间不用拷贝旧数据哪怕是中控数组满了要重新异地扩容拷贝的数据也都是固定字节大小。deque下标随机访问效率还行如果大量数据(100w级数据)效率略低于vector毕竟deque要计算下标第几个buff的第几个位置还是需要点时间的。缺点deque的insert和erase就需要大量挪动数据效率比list和vector都低。可能有人会想能不能只挪动要删除数据所在的buff数组肯定是不行如果插入删除都在一个buff里边的话那每个buff的大小就不一样了用下标访问数据的时候效率就不能像原来那么高了。所以具体怎么操作还得看每个编译器的选择因为这个C并没有规定。//综上deque优点都不够极致是不如vector和list的但作为stack和queue的默认容器适配器很适合因为stack和queue就经常需要头尾插入删除。priority_queue的使用优先级队列的底层是用堆来实现的。它也是容器适配器底层默认用vector去适配。另外优先级队列还涉及到一个叫仿函数的东西看其类模板参数就会知道它默认传了less这个仿函数默认就为大堆如果传了greater这个参数就变成了小堆。这里注意是反着来的本质上是C涉及的一个问题因为语言都要向前兼容之前的代码哪怕错了也不好改了一改之前写的程序就会有bug了。sort也是用的仿函数默认是升序传greater是降序传less是升序。#includeiostream #includealgorithm #includequeue using namespace std; int main() { priority_queueint pq; //priority_queueint, vectorint, greaterint pq;//此时3个参数都要传因为缺省参数没法隔着传 pq.push(1); pq.push(2); pq.push(3); pq.push(4); while (!pq.empty()) { cout pq.top() ;//4 3 2 1 pq.pop(); } cout endl; vectorint v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); sort(v1.begin(), v1.end()); //sort(v1.begin(), v1.end(), greaterint());//降序 for (auto e : v1) { cout e ; } cout endl; return 0; }这里有一个问题为什么sort传的是仿函数的对象priority_queue传的是仿函数的类型原因就是一个是函数模板参数要传对象一个是类模板参数要传类型。priority_queue的底层实现仿函数(也叫函数对象)由于函数指针太过于复杂仿函数是想要去规避函数指针。对于普通的函数/函数模板来说传函数指针是可以去回调函数/模板自动推导类型去调用函数。但是对于类模板来说它需要传的是类型只能显示指定类型去实例化不能自动推导类型如果传了函数指针类型给对应的模板参数编译器也不知道将去调用哪个函数除非显示将函数指针传给构造函数但是非常麻烦还有一种情况是函数指针可以是空指针或者野指针就很难去控制。仿函数想传对象就传其对象想传类型就传其类型使用起来比较灵活不用写死是小于的比较还是大于的比较。bool cmp(int x, int y) { return x y; } priority_queueint, vectorint, bool (*)(int, int) p(cmp); //err priority_queueint, vectorint, cmp p(cmp);仿函数功能仿照函数的功能其对象可以像函数一样使用(本质重载了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 T, class Compare void BubbleSort(T* a, int n, Compare com) { int exchange 0; for (int i 0; i n; i) { for (int j 0; j n - i - 1; j) { /* * 升序的话要写a[j 1] a[j] * 降序的话要写a[j 1] a[j] * 但是每次都要手动改太麻烦了因此加一个模板参数来控制这里的逻辑 * 上述就是仿函数的简单引用 */ if (com(a[j 1], a[j]))//调用operator()就像是直接在调用函数一样 { exchange 1; swap(a[j], a[j 1]); } } if (exchange 0) { break; } } } int main() { int a[] { 1,2,4,5,2,1,3,7 }; //BubbleSortint, Lessint(a, 8, Lessint());//显示实例化 BubbleSort(a, 8, Lessint());//隐式实例化 for (auto e : a) { cout e ; } cout endl; BubbleSort(a, 8, Greaterint()); for (auto e : a) { cout e ; } cout endl; return 0; }传仿函数的对象到BubbleSort里边对应的com会转化为调用仿函数里边的operator()重载函数也像是一种函数回调。priority_queue的模拟实现#includevector #includeiostream using namespace std; 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; } }; //默认为大堆在库里边传less是大堆传greater是小堆 //也就是 是大堆是小堆这个就要注意下边传com参数的顺序(先传_con[parent]还是_con[child]) namespace xxc { //类模板容器适配器仿函数 templateclass T, class Container vectorT, class Compare LessT class priority_queue { public: priority_queue() default;//自动生成默认构造 template class InputIterator priority_queue(InputIterator first, InputIterator last) :_con(first, last) { for (int i (_con.size() - 1 - 1) / 2; i 0; i--) { adjust_down(i);//时间复杂度比向上调整建堆要低 } } 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); } size_t size() const { return _con.size(); } const T top() { return _con[0]; } bool empty() const { return _con.empty(); } private: void adjust_down(int parent) { Compare com; size_t child (parent * 2) 1; while (child _con.size()) { if (child 1 _con.size() com(_con[child], _con[child 1])) child; if (com(_con[parent], _con[child])) { swap(_con[child], _con[parent]); parent child; child (parent * 2) 1; } else { break; } } } void adjust_up(int child) { Compare com; size_t parent (child - 1) / 2; while (child 0) { if (com(_con[parent], _con[child])) { swap(_con[child], _con[parent]); child parent; parent (child - 1) / 2; } else { break; } } } private: Container _con; }; }仿函数的使用场景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); private: int _year; int _month; int _day; }; ostream operator(ostream _cout, const Date d) { _cout d._year - d._month - d._day; return _cout; } struct PDateLess { bool operator()(const Date* p1, const Date* p2) { return *p1 *p2; } }; int main() { xxc::priority_queueDate, vectorDate, PDateLess q1; xxc::priority_queueDate*, vectorDate*, PDateLess q2; //情况1 q1.push(Date(2018, 10, 29)); q1.push(Date(2018, 10, 28)); q1.push(Date(2018, 10, 30)); //情况2传过去的是指针priority_queue里的仿函数的逻辑就按指针比较 //不是自己想要的比较逻辑 q2.push(new Date(2018, 10, 29)); q2.push(new Date(2018, 10, 28)); q2.push(new Date(2018, 10, 30)); while (!q1.empty()) { cout *q1.top() ; q1.pop(); } cout endl; return 0; }假设往我们自己模拟实现的优先级队列里边pushDate类的对象。情况1若是Date类没有重载比较大小函数此时需要自己去写仿函数传到priority_queue的模板参数里边去。情况2重载了比较大小函数Date类的对象是new出来的比较的逻辑不是自己想要的需要自己写仿函数按照自己的比较逻辑(上边的代码里已有)。(库里边的priority_queue也一样的处理方式)仿函数不止是去比较大小还有很多丰富的功能。这里先暂时了解一点请看下边的两个算法模板里边的参数需要用到仿函数来看看它的简单使用。#includealgorithm struct OP1 { public: bool operator()(int x) { return x % 2 0; } }; struct OP2 { public: int operator()(int x) { return x * 2; } }; int main() { int a[] { 1,2,3,4,5,6 }; //查找第一个偶数 auto it1 find_if(a, a 6, OP1()); cout *it1 endl; //所有值 * 2 transform(a, a 6, a, OP2()); for (auto e : a) { cout e ; } cout endl; return 0; }