STL:双端队列&容器适配器&仿函数&优先级队列

这篇具有很好参考价值的文章主要介绍了STL:双端队列&容器适配器&仿函数&优先级队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

deque

  • 双端队列可以在头部和尾部进行插入删除操作
  • 与vector相比,头插效率高,不需要搬移元素
    与list相比,空间利用率高

deque逻辑上空间是连续的,物理上并不是,是由一段段小空间拼接而成的

双端队列的迭代器比较复杂

  • cur:指向空间中被遍历的那个元素
  • first:指向空间开始
  • last:指向空间末尾
  • node:指向map中保存该段空间的地址
    当cur走到first或者last位置,说明已经将该空间中的元素遍历结束,需要找下一块空间(node++或者–)

STL:双端队列&容器适配器&仿函数&优先级队列,STL,c++,开发语言

容器适配器

C语言中,栈封装数组,队列封装链表,
C++中,栈和队列使用deque实现
原因:vector中的扩容成本高,list中有大量节点,造成很多内存碎片

容器适配器是将一个接口转换成另外一种接口,这样解释确实过于简单,

  • 先要知道,deque中定义了许多的接口如头插头删,尾插尾删,判空等操作,
  • 这些操作不管是栈中特性函数,还是队列中的特性函数,deque中都有
  • 若实现stack,stl把deque作为stack的底层,抽出deque中的部分方法,
  • 比如尾插尾删,判空,返回队尾元素,进行包装从而实现栈;尾插尾删函数变成出栈入栈函数,返回队尾元素函数变成返回栈顶元素函数

迭代器适配器:list反向迭代器的实现,封装了正向迭代器(抽出正向迭代器中的方法重新进行封装)

仿函数

仿函数又称函数对象(可以像函数一样调用的对象称为函数对象)
实现:在类中将函数调用运算符() 重载,该类的对象就可以像函数一样使用

STL:双端队列&容器适配器&仿函数&优先级队列,STL,c++,开发语言
重载()后,通过less类定义的对象,去调用成员函数

优先级队列(仿函数与容器适配器的应用)

封装vector实现

  • 优先级队列本质是堆
  • 堆是完全二叉树+条件(父节点比孩子节点大或者小)
    完全二叉树适合用数组存储
    所以优先级队列的底层是用vector来存储元素

STL:双端队列&容器适配器&仿函数&优先级队列,STL,c++,开发语言

适配器详述

  • 103行,vector是一个类模板,用int将该模板实例化,所以vector< int >是一个实际类型,将这个类型名用container代替,并用新类型名定义一个变量
  • 优先级队列的pop函数是使用vector中的pop作为核心逻辑,并添加新逻辑而实现的
  • 添加新的函数,向上调整和向下调整函数
  • 组成了新容器的接口,把这种容器称为容器适配器

所以stack和queue严格说并不是容器,而是容器适配器

仿函数详述

仿函数又称函数对象(可以像函数一样调用的对象称为函数对象)
实现:在类中将函数调用运算符重载,该类的对象就可以像函数一样使用
函数调用运算符就是 ( )

通俗来说就是把函数封装到类里面,要使用该函数时,只需要定义一个这个类的对象,通过对象调用运算符重载函数,使用该功能

代码84~100行是实现两个不同比较方式的仿函数,同容器适配器一样,在类模板参数列表中重命名,112行定义类对象,117行是对象调用()运算符重载函数,将括号中的两个参数传给类中的成员函数

sort中仿函数的应用

sort是一个函数模板

  • sort的三个参数,前两个参数是待排序的区间,第三个参数是排序方式
  • 而sort是一个函数,参数是普通变量
  • 仿函数是一个类型,第三个参数不能传类型,
    所以仿函数要想作为sort函数的参数,需要这样写
  • 后面加()表面这个类产生了一个匿名对象

STL:双端队列&容器适配器&仿函数&优先级队列,STL,c++,开发语言

而arr是指针变量,迭代器的本质又是指针,所以可以推出arr就是一个迭代器对象文章来源地址https://www.toymoban.com/news/detail-602600.html

到了这里,关于STL:双端队列&容器适配器&仿函数&优先级队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【STL】顺序容器与容器适配器

    给出以下顺序容器表: 顺序容器类型 作用 vector 可变大小的数组,支持快速访问,除尾元素的插入或者删除很慢 string 与vector相似,只不过专门用来存字符 list 双向链表。只能双向顺序访问,插入删除的效率都很高 forward_list 单向链表。只能单向顺序访问,插入删除的效率都

    2024年04月14日
    浏览(31)
  • C++ [STL容器适配器]

    本文已收录至《C++语言》专栏! 作者:ARMCSKGT 前面我们介绍了适配器模式中的反向迭代器,反向迭代器通过容器所支持的正向迭代器适配为具有反向迭代功能的迭代器,本节我们介绍STL中另一种适配器: 容器适配器 ! 前面我们提到过STL适配器模式,关于适配器的解释: S

    2024年02月11日
    浏览(44)
  • C++ STL学习之【容器适配器】

    ✨个人主页: 北 海 🎉所属专栏: C++修行之路 🎊每篇一句: 图片来源 A year from now you may wish you had started today. 明年今日,你会希望此时此刻的自己已经开始行动了。 适配器(配接器)是 STL 中的六大组件之一,扮演着轴承、转换器的角色,使得 STL 中组件的使用更为灵活,

    2023年04月22日
    浏览(61)
  • STL: 容器适配器stack 与 queue

      目录 1.容器适配器 1.1 STL标准库中stack和queue的底层结构 1.2 deque的简单介绍(了解) 1.2.1 deque的原理介绍 1.2.2 deque的缺陷 1.2.3 为什么选择deque作为stack和queue的底层默认容器 2. stack的介绍和使用 2.1 stack的介绍  2.2 stack的使用 2.3 利用deque模拟实现stack 3.queue的介绍和使用 3.1 queue的

    2024年02月05日
    浏览(47)
  • 22 标准模板库STL之容器适配器

    概述         提到适配器,我们的第一印象是想到设计模式中的适配器模式:将一个类的接口转化为另一个类的接口,使原本不兼容而不能合作的两个类,可以一起工作。STL中的容器适配器与此类似,是一个封装了序列容器的类模板,它在一般序列容器的基础上提供了一

    2024年02月05日
    浏览(41)
  • 【C++】STL之容器适配器——使用deque适配stack和queue

    个人主页:🍝在肯德基吃麻辣烫 分享一句喜欢的话:热烈的火焰,冰封在最沉默的火山深处。 本文章主要介绍容器适配器的功能,以及一个适配的场景。 容器适配器,按字面意思理解的话,就是用来对一个容器进行匹配的。在C++STL中,容器有:vector,list,deque,map,set等。

    2024年02月16日
    浏览(56)
  • 【C++】STL之适配器---用deque实现栈和队列

    目录 前言 一、deque  1、deque 的原理介绍  2、deque 的底层结构  3、deque 的迭代器  4、deque 的优缺点   4.1、优点   4.2、缺点 二、stack 的介绍和使用  1、stack 的介绍  2、stack 的使用  3、stack 的模拟实现 三、queue 的介绍和使用  1、queue 的介绍   2、queue 的使用  3、queue 的模

    2024年02月07日
    浏览(54)
  • STL容器适配器 -- stack和queue(使用+实现)(C++)

    栈和队列数据结构+画图分析如果对栈和队列的结构不了解的,可以先看该链接的内容 使用stack时需要头文件 #includestack stack是一种容器适配器,用于具有 后进先出 (LIFO)的环境中。只能从容器的一端(栈顶),执行删除、插入和提取操作。 stack是作为容器适配器实现的,容器

    2024年02月14日
    浏览(63)
  • 【C++】STL 算法 ⑩ ( 函数适配器 | 函数适配器概念 | 函数适配器分类 | 函数适配器辅助函数 | std::bind2nd 函数原型及示例 | std::bind 函数原型及示例 )

    在 STL 中 预定义了很多 函数对象 , 如果要 对 函数对象 的 参数 / 返回值 进行 计算 或 设置 , 可以 使用 \\\" 函数适配器 \\\" 实现上述需求 ; \\\" 函数适配器 \\\" 可以 将 已存在的 函数对象 转化为 另一种符合要求的 函数对象 ; \\\" 函数适配器 \\\" 定义在 functional 头文件 中 ; \\\" 函数适配器

    2024年02月02日
    浏览(65)
  • 【STL】容器适配器stack和queue常见用法及模拟实现

    1.stack介绍及使用 1.1 stack的介绍 stack文档介绍 stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。 stack是作为容器适配器被实现的,容器适配器是使用特定容器类的封装对象作为其基础容器的类,提供一

    2024年02月06日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包