首页 > 编程语言 >C++面试八股文:std::deque用过吗?

C++面试八股文:std::deque用过吗?

时间:2023-06-26 23:32:56浏览次数:58  
标签:std deque chunk list C++ 插入 vector stack

某日二师兄参加XXX科技公司的C++工程师开发岗位第26面:

面试官:deque用过吗?

二师兄:说实话,很少用,基本没用过。

面试官:为什么?

二师兄:因为使用它的场景很少,大部分需要性能、且需要自动扩容的时候使用vector,需要随机插入和删除的时候可以使用list

面试官:那你知道STL中的stack是如何实现的吗?

二师兄:默认情况下,stack使用deque作为其底层容器,但也可以使用vectorlist作为底层容器。

面试官:你觉得为什么STL中默认使用deque作为stack的底层容器吗?

二师兄:额。。(stack也不需要双端插入啊,不应该vector更好吗。。)不是很清楚。。

面试官:没关系。那你知道deque是如何实现的吗?

二师兄:与vector内存空间连续不同,deque是部分连续的。deque通常维护了一个map(不是std::map),map的每个元素指向一个固定大小的chunk。同时维护了两个指针,指向头chunk和尾chunk。在deque的头部或尾部插入元素时,deque会找到头部或尾部的指针,并通过指针找到对应的chunk。如果chunk中还有未被元素填充的位置,则将元素填充到数组中,如果此指针指向的chunk已经被元素填满,则需要重新开辟一块固定大小的chunk,并将chunk记录在map中。

file

面试官:deque的查找、插入、删除的时间复杂度是什么?

二师兄:dqueue查找的时间复杂度是O(N),插入要分情况,如果是头插和尾插,时间复杂度为O(1),如果是中间插入,则是O(N)。删除元素和插入元素的时间复杂度相同。

面试官:好的。面试结束,回去等通知吧。

让我们来看一下二师兄的表现:

为什么STL中默认使用deque作为stack的底层容器吗?

STL默认选择deque最为stack的底层容器肯定是有原因的。vectorlist同样可以作为deque的底层容器,让我们比较一下三个容器的差异:(只考虑头插和尾插,因为stack不需要随机插入)

deque vector list
插入 O(1) O(1) O(1)
删除 O(1) O(1) O(1)

从上表中看到,三种容器的插入和是删除的时间复杂度相同。

但是如果连续插入时,情况发生变化。vectorcapacity被耗尽,元素发生搬移。

list倒没有这个顾虑,但是当元素尺寸很小时,list的空间利用率太低。

deque虽然遍历效率不如vector、随机插入效率不然list,但stack并不需要这两种操作,所以dequestack底层容器的最佳选择。

今天的面试分享到这里就结束了,让我们继续期待二师兄的表现吧。

关注我,带你21天“精通”C++!(狗头)

标签:std,deque,chunk,list,C++,插入,vector,stack
From: https://blog.51cto.com/binarch/6558808

相关文章

  • C++指针函数
    指针函数指针函数有些像C#中的委托delegate(不知道理解的对不对)。定义函数指针int*compare(int,int);一般简写为typedefint(*compare)(int,int);这样就定义了一个名为compare的函数指针。compare指针类型为:指向返回int类型并带有两个int参数的函数的指针。函数指......
  • C++ 指针形参与引用参数
    指针形参与引用参数指针形参指针作形参时,若在函数中修改指针对象的值,则对应实参的值会对应修改。#include<iostream>usingnamespacestd;voidChange(int*p){*p=400;};intmain(intargc,charconst*argv[]){intvalue=1;int*argsPiont=&va......
  • C++11特性简单介绍
    自动类型推导autoautox=10;//推导x为int类型autostr="Hello";//推导str为constchar*类型基于范围的For循环for(int&i:someDataStructure){doSomething();}for(inti:someDataStructure)doSomething();在上面的两个for循环中,第一个使用引用,第二个启用按......
  • 学习C++就这么简单 ——《写给大家看的C++书》
    C++已经有很多年的历史了,虽然在它之后又出现了Java和C#之类的新语言,但它至今仍是人们开发软件时的最佳选择之一。那些巨头中的巨头,如微软、Adobe、英特尔、亚马逊、Google、苹果、诺基亚等公司,都在使用C++。这门语言相对比较容易使用(选用本书作为入门教材就更是如此了......
  • C/C++航空客运订票系统[2023-06-26]
    C/C++航空客运订票系统[2023-06-26]实验1航空客运订票系统问题描述:航空客运订票的业务活动包括查询航线和客票预订的信息、客票预订和办理退票等,设计一个程序使上述任务借助计算机来完成。基本要求:(一)系统必须存储的数据信息。1.信息:飞机抵达的城市、航班号、飞机号、起降......
  • C++一读一写无锁队列
    //一读一写的无锁管道队列template<classT>classPipelineList{private:template<classT>structqnode{structqnode*next;Tdata;};structqnode<T>*volatilem_front;structqnode<T>*volatilem_......
  • c++ std::execution::par,std::execution::par_unseq
    #include<algorithm>#include<chrono>#include<cstdint>#include<execution>#include<iostream>#include<random>#include<vector>std::random_devicerd;std::mt19937_64mt{rd()};template<typenameT>......
  • 为什么 Keil 中C/C++选项要 define STM32F10X_LD/MD/HD
    原因1:配置相应的中断向量表 原因2:配置相应的寄存器  总结原因:因为所有的stm32f10x 系列的芯片都会用到stm32f10x.h 这个头文件,但是问题的所在是:每种芯片的配置不同(中断向量个数、寄存器个数等等)因此宏条件编译#if!defined 判断这个宏(这个宏就是STM32F10X_LD......
  • Linux搭建C++开发环境
    Linux搭建C++开发环境https://blog.csdn.net/weixin_44666217/article/details/127594532LinuxC/C++开发环境搭建https://blog.csdn.net/zcteo/article/details/117528089 ......
  • C/C++按位读取
    RinpoStk按位读取在C中无法直接按位读取,常见的方法是通过位运算获取每一位的数据。//获取B5第4位//(B5&(1<<5))>>5 10110101& 00010000;= 00010000//得到1采取共用体(联合)可以得到一个既可以按位读取,也可以按字节读取的数据类型union{struct{un......