deque
- 双端队列可以在头部和尾部进行插入删除操作
- 与vector相比,头插效率高,不需要搬移元素
与list相比,空间利用率高
deque逻辑上空间是连续的,物理上并不是,是由一段段小空间拼接而成的
双端队列的迭代器比较复杂
- cur:指向空间中被遍历的那个元素
- first:指向空间开始
- last:指向空间末尾
- node:指向map中保存该段空间的地址
当cur走到first或者last位置,说明已经将该空间中的元素遍历结束,需要找下一块空间(node++或者–)
容器适配器
C语言中,栈封装数组,队列封装链表,
C++中,栈和队列使用deque实现
原因:vector中的扩容成本高,list中有大量节点,造成很多内存碎片
容器适配器是将一个接口转换成另外一种接口,这样解释确实过于简单,
- 先要知道,deque中定义了许多的接口如头插头删,尾插尾删,判空等操作,
- 这些操作不管是栈中特性函数,还是队列中的特性函数,deque中都有
- 若实现stack,stl把deque作为stack的底层,抽出deque中的部分方法,
- 比如尾插尾删,判空,返回队尾元素,进行包装从而实现栈;尾插尾删函数变成出栈入栈函数,返回队尾元素函数变成返回栈顶元素函数
迭代器适配器:list反向迭代器的实现,封装了正向迭代器(抽出正向迭代器中的方法重新进行封装)
仿函数
仿函数又称函数对象(可以像函数一样调用的对象称为函数对象)
实现:在类中将函数调用运算符() 重载,该类的对象就可以像函数一样使用
重载()后,通过less类定义的对象,去调用成员函数
优先级队列(仿函数与容器适配器的应用)
封装vector实现
- 优先级队列本质是堆
- 堆是完全二叉树+条件(父节点比孩子节点大或者小)
完全二叉树适合用数组存储
所以优先级队列的底层是用vector来存储元素
适配器详述
- 103行,vector是一个类模板,用int将该模板实例化,所以vector< int >是一个实际类型,将这个类型名用container代替,并用新类型名定义一个变量
- 优先级队列的pop函数是使用vector中的pop作为核心逻辑,并添加新逻辑而实现的
- 添加新的函数,向上调整和向下调整函数
- 组成了新容器的接口,把这种容器称为容器适配器
所以stack和queue严格说并不是容器,而是容器适配器
仿函数详述
仿函数又称函数对象(可以像函数一样调用的对象称为函数对象)
实现:在类中将函数调用运算符重载,该类的对象就可以像函数一样使用
函数调用运算符就是 ( )
通俗来说就是把函数封装到类里面,要使用该函数时,只需要定义一个这个类的对象,通过对象调用运算符重载函数,使用该功能
代码84~100行是实现两个不同比较方式的仿函数,同容器适配器一样,在类模板参数列表中重命名,112行定义类对象,117行是对象调用()运算符重载函数,将括号中的两个参数传给类中的成员函数
sort中仿函数的应用
sort是一个函数模板
- sort的三个参数,前两个参数是待排序的区间,第三个参数是排序方式
- 而sort是一个函数,参数是普通变量
- 仿函数是一个类型,第三个参数不能传类型,
所以仿函数要想作为sort函数的参数,需要这样写- 后面加()表面这个类产生了一个匿名对象
文章来源:https://www.toymoban.com/news/detail-602600.html
而arr是指针变量,迭代器的本质又是指针,所以可以推出arr就是一个迭代器对象文章来源地址https://www.toymoban.com/news/detail-602600.html
到了这里,关于STL:双端队列&容器适配器&仿函数&优先级队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!