stackstack指的是栈它的机制是后进先出或先进后出stack的接口push()栈顶入数据pop()栈顶出数据stack()建立一个空栈size()获取有效数据个数empty()判断栈是否为空top()获取栈顶数据stack的模拟实现在模拟实现我们先引入一个问题stack可以用哪些数据结构string、vector、list、queue、deque(deque是双端队列是vector和list的结合顾名思义双端均可实现效率较高的插入删除还可以实现下标访问)高效实现queue可以用哪些数据结构高效实现既然stack和queue的底层是用这些数据结构来实现我们引入容器适配器概念容器适配器是将一个类的接口转换成客户希望的另外一个接口就如stack和queue底层是其他数据结构但我们调用stack和queue时把它们作为一种数据结构实现了转换。那么如何实现呢在设计stack和queue的模板时增添一个模板参数让它作为stack和queue的底层数据结构再在底层上实现stack和queue的功能。C还实现了模板参数缺省的功能如下那么我们为什么要让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总结deque结合了vector和list的优点但相比vector和list优点都不够极致vectorlistdeque优点1.尾插尾删效率高2.随机访问速度快3.cpu高速缓存命中率高1.任意位置插入删除效率高2.仅插入删除当前迭代器失效3.扩容不需要拷贝旧数据不存在容量概念1.头部尾部插入删除效率都高2.cpu高速缓存命中率较高3.支持随机访问但效率不如vector4.扩容不需要拷贝旧数据缺点1.头部以及中间插入删除效率低2.扩容可能要复制旧数据1.cpu高速缓存命中率低2.随机访问效率低1.中间位置插入删除效率低2.内部结构较复杂迭代器开销大queuequeue是队列是一种容器适配器机制是先进先出queue的接口queue()构造空队列empty()判断是否为空size()获取有效数据个数front()获取队头元素back()获取队尾元素push()队尾入数据pop()队头出数据queue的模拟实现priority_queue优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的由此可以想到它的底层是堆而堆的底层可以是vector和deque默认数据结构为vector因为其所需操作vector均可胜任而vector结构简单开销小。因此priority_queue就是堆所有考虑用到堆的地方都可以考虑priority_queue但要注意默认情况下priority_queue是大堆priority_queue的接口priority_queue()/priority_queue(first,last)构造一个优先级队列空/复制另一个容器的数据empty()判断是否为空top()返回堆顶元素即优先级队列的最大最小元素push()优先级队列插入元素pop()删除堆顶元素即优先级队列的最大最小元素priority_queue的模拟实现在模拟实现之前引入仿函数概念其实就是用类中的成员函数operator()其形式与函数十分相像但语义不同匿名对象也可以是有名对象调用operator()函数sort(v.begin(),v.end(),std::greaterint());//greaterint()即为仿函数其设计目的是弥补函数指针的缺陷上图模板参数中的第三个是用来控制priority_queue是大堆还是小堆如果传函数指针这样Compare仅仅只是函数指针类型无法实例化发挥其作用。仿函数可以直接用来比较也可以根据需求来控制比较逻辑如一个类内部未实现比较可以通过仿函数内部代码来实现比较逻辑还有更多场景我们以后还会遇到