首页 > 其他分享 >为什么stack和queue默认使用deque作为底层容器?

为什么stack和queue默认使用deque作为底层容器?

时间:2023-12-04 16:12:22浏览次数:31  
标签:deque 容器 默认 queue stack 底层

在C++中,stackqueue默认使用deque作为底层容器的原因主要有以下几点:

  1. 操作效率deque(双端队列)支持在头尾两端进行插入和删除操作,且时间复杂度都为O(1),非常高效1。而vector在增长到一定长度时为了保证完全连续,需要重新申请更长的内存,并把原来的元素全部拷贝过去2。这使得vector的尾部插入操作在某些情况下的时间复杂度会变为O(n),效率较低2

  2. 空间利用率deque并不是真正连续的一段空间,而是由一段段连续的小空间拼接而成1。这使得deque在空间利用率上相比于list、vector有优势1

  3. 适应性deque的特性使其更能贴合stackqueue的需求1stack为先进后出结构,所有具有push_backpop_back的容器都可以作为底层默认容器1queue为先进先出结构,所有具有push_backpop_front的容器都可以作为底层默认容器1deque恰好满足这两种操作的需求1

  4. 灵活性:虽然dequestackqueue的默认底层容器,但C++标准库允许用户根据自己的需求选择其他容器作为底层容器2。例如,如果能预分配足够的容量,使用vector作为stack的底层容器可能会更优2

总的来说,deque作为stackqueue的默认底层容器,是因为它在操作效率、空间利用率和适应性等方面的综合考虑结果12

 

标签:deque,容器,默认,queue,stack,底层
From: https://www.cnblogs.com/whcjob/p/17875187.html

相关文章

  • stack和queue的底层容器封装 以及提供随机存储的容器
    在C++中,std::stack和std::queue是容器适配器,它们提供了特定的接口,依赖于某个容器类(如std::deque或std::list)来处理元素1。std::stack:std::stack默认使用std::deque作为其底层容器2。但是,你也可以在创建std::stack对象时指定其他的底层容器,只要这个容器支持......
  • 阻塞队列之 LinkedBlockingQueue
    LinkedBlockingQueue:Java多线程编程中的阻塞队列在Java多线程编程中,LinkedBlockingQueue是一个非常重要的类,它提供了一种用于在生产者和消费者之间进行数据传递的机制。LinkedBlockingQueue广泛应用于各种场景,如线程池、任务队列等。本文将详细介绍LinkedBlockingQueue的原理......
  • java 捕获异常Exception 获取异常信息的方法 e.toString() e.getMessage() e.printSta
    Java异常中e.getMessage()和e.toString()e.printStackTrace()的区别e.getMessage():打印异常的原因e.toString():打印异常类型和异常的原因e.printStackTrace():打印完整的异常堆栈信息  总结e.getMessage()和e.toString()方法:打印的异常信息太少,没有具体......
  • 1.Java集合(List、Set、Queue)
    1.集合概述Java集合也被称为容器。主要由两个接口组成,一个是Collection接口,主要存放单一元素;一个是Map接口,主要存放键值对。Collection下面还有三个子接口,分别是List、Set、Queue。Java框架如下图所示:1.1List、Set、Queue、Map简介List(对付顺序的好帮手):存储的元素有序、......
  • yocto-queue 库如何实现替代数组【玩转源码】
    前言前面提到了可以使用yocto-queue库代替Array操作数组,本篇则深入源码了解一下yocto-queue是如何实现替代数组的。yocto-queue源码分析源码中的代码量相对较少,读起来会比较轻松,看似可以琢磨的点少,其实不然。代码中包含知识点主要包括类的属性、链表与数组的对比、队列、自定义迭代......
  • dump 日志收集与分析(jmap 和 jstack 工具)讲解与实战操作
    目录一、概述二、常见的dump工具三、dump可能会导致进程卡住风险(生产谨慎操作)四、安装JDK五、jmap介绍与示例讲解1)jmap介绍2)Kafka安装(单机)1、下载安装包2、配置环境变量3、配置kafka3、配置ZooKeeper4、启动kafka5、验证3)示例讲解【示例一】执行jmap命令查看内存使用情况【......
  • 四、Work Queues(工作队列)
    一、轮训分发消息1、抽取工具类2、启动两个工作线程2.1两个工作线程(消费者)2.2生产者3、启动一个发送线程4、结果展示二、消息应答1、概念2、自动应答3、消息应答的方法4、Multiple的解释5、消息自动重新入队6、消息手动应答代码......
  • 2023ISCTFpwn题目:stack题解
    这是我在这次比赛中遇到最有意思的一题,不仅让我看到了一种有意思的题型,而且让我开始看懂了pwndbg的调试界面。IDA里面是这样的,有直接可以提权的backdoor函数,有read函数,看似有点像ret2system。让我们分析一下这个函数的读入逻辑:首先让你输入一个size值,read会总共分size次读入一个字......
  • 关于Vue3中调试APP触发异常:exception:white screen cause create instanceContext fai
    bug:reportJSException>>>>exceptionfunction:createInstanceContext,exception:whitescreencausecreateinstanceContextfailed,checkjsstack->atuseStore(app-service.js:2309:15)问题在于:使用了pinia,并且在所有js文件或ts文件中调用超前,导致的加载错误 解决方......
  • packestack 部署openstack
    一、部署packstack1.1简介对于openstack初学者而言,传统部署openstack流程是在过于繁琐,需要多台虚拟机,packstack完美解决这个问题,可以减少了许多繁琐且容易出错的部署流程,packstack可以选择单节点或双节点部署,本次完美使用单节点部署allinone。1.2性能搭配推荐处理器内核至少3个......