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

这篇具有很好参考价值的文章主要介绍了C++面试八股文:std::deque用过吗?。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

某日二师兄参加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中。

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

面试官: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++!(狗头)文章来源地址https://www.toymoban.com/news/detail-501270.html

到了这里,关于C++面试八股文:std::deque用过吗?的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • C++面试八股文:std::string是如何实现的?

    某日二师兄参加XXX科技公司的C++工程师开发岗位第18面: 面试官: std::string 用过吧? 二师兄:当然用过(废话,C++程序员就没有没用过 std::string 的)。 面试官: std::string(\\\"hello\\\")+\\\"world\\\" 、 \\\"hello\\\"+std::string(\\\"world\\\") 和 std::string(\\\"hello\\\")+std::string(\\\"world\\\") 的结果是什么?为什么? 二师

    2024年02月09日
    浏览(40)
  • C++面试八股文:std::array如何实现编译器排序?

    某日二师兄参加XXX科技公司的C++工程师开发岗位第25面: 面试官: array 熟悉吗? 二师兄:你说的是原生数组还是 std::array ? 面试官:你觉得两者有什么区别? 二师兄:区别不是很大,原生数组(非动态数组)和std::array都在栈上开辟空间,初始化的时候需要提供数组长度,且

    2024年02月10日
    浏览(48)
  • C++面试八股文:知道std::unordered_set/std::unordered_map吗?

    某日二师兄参加XXX科技公司的C++工程师开发岗位第27面: 面试官:知道 std::unordered_set/std::unordered_map 吗? 二师兄:知道。两者都是C++11引入的新容器,和 std::set 和 std::map 功能类似, key 唯一, unordered_map 的 value 可变。 二师兄:不同于 set/map , unordered_set/unordered_map 都是无序

    2024年02月11日
    浏览(40)
  • C++面试八股文:技术勘误

    不知不觉,《C++面试八股文》已经更新30篇了,这是我第一次写技术博客,由于个人能力有限,出现了不少纰漏,在此向各位读者小伙伴们致歉。 为了不误导更多的小伙伴,以后会不定期的出勘误文章,请各位小伙伴留意。 在《C++面试八股文:C++中,设计一个类要注意哪些东

    2024年02月11日
    浏览(50)
  • C++面试八股文:如何避免死锁?

    某日二师兄参加XXX科技公司的C++工程师开发岗位第31面: 面试官:什么是锁?有什么作用? 二师兄:在C++中,锁(Lock)是一种同步工具,用于保护共享资源,防止多个线程同时访问,从而避免数据竞争和不一致。 面试官:有哪些锁? 二师兄:从种类上分,可以分为普通锁、

    2024年02月12日
    浏览(49)
  • C++面试八股文:什么是智能指针?

    某日二师兄参加XXX科技公司的C++工程师开发岗位第19面: 面试官:什么是智能指针? 二师兄:智能指针是C++11引入的类模板,用于管理资源,行为类似于指针,但不需要手动申请、释放资源,所以称为智能指针。 面试官:C++11引入了哪些智能指针? 二师兄:三种,分别是 s

    2024年02月09日
    浏览(44)
  • C++面试八股文:了解位运算吗?

    某日二师兄参加XXX科技公司的C++工程师开发岗位第12面: 面试官:了解位运算吗? 二师兄:了解一些。(我很熟悉) 面试官:请列举以下有哪些位运算? 二师兄:按位与( )、按位或( | )、按位异或( ^ ),按位取反( ~ )、左移( )和右移( )。 面试官:好的。那你

    2024年02月08日
    浏览(41)
  • C++面试八股文:什么是构造函数?

    某日二师兄参加XXX科技公司的C++工程师开发岗位第29面: 面试官:什么是构造函数? 二师兄:构造函数是一种特殊的成员函数,用于创建和初始化类的对象。构造函数的名称与类的名称相同,并且没有返回类型。构造函数在对象被创建时自动调用。 面试官:什么是默认构造

    2024年02月11日
    浏览(47)
  • C++面试八股文:聊一聊指针?

    某日二师兄参加XXX科技公司的C++工程师开发岗位第17面: 面试官:聊一聊指针? 二师兄:好的。 面试官:你觉得指针本质上是什么? 二师兄:这要从内存地址开始说起了。如果有一块容量是1G的内存,假设它的地址是从 0x00000000 到 0x3fffffff ,每一个字节都对应一个地址。当

    2024年02月09日
    浏览(37)
  • C++面试八股文:什么是RAII?

    某日二师兄参加XXX科技公司的C++工程师开发岗位第13面: 面试官:什么是 RAII ? 二师兄: RAII 是 Resource Acquisition Is Initialization 的缩写。翻译成中文是资源获取即初始化。 面试官: RAII 有什么特点和优势? 二师兄:主要的特点是,在对象初始化时获取资源,在对象析构时释放

    2024年02月08日
    浏览(54)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包