下载此文档

C++容器STL相关面试问题.pdf


文档分类:IT计算机 | 页数:约3页 举报非法文档有奖
1/3
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/3 下载此文档
文档列表 文档介绍
该【C 容器STL相关面试问题 】是由【小小布】上传分享,文档一共【3】页,该文档可以免费在线阅读,需要了解更多关于【C 容器STL相关面试问题 】的内容,可以使用淘豆网的站内搜索功能,选择自己适合的文档,以下文字是截取该文章内的部分文字,如需要获得完整电子版,请下载此文档到您的设备,方便您编辑和打印。C++容器STL相关⾯试问题
1、六⼤组件介绍
容器:数据结构,⽤来存放数据算法:常⽤算法迭代器:容器和算法之间的胶合剂,“范型指针”
仿函数:⼀种重载了operator()的类,使得这个类的使⽤看上去像函数配置器:为容器分配并管理内存适配器:修改其他组件接⼝
2、为何map和set的插⼊删除效率⽐⽤其他序列容器⾼?
对于关联容器来说,不需要做内存拷贝和内存移动。map和set容器内所有元素都是以节点的⽅式来存储,其节点结构和链表差不多,
指向⽗节点和⼦节点
3、红⿊树有什么性质?
⾊或⿊⾊
⿊⾊
⿊⾊的NULL结点。
,其⼦节点必须为⿊
⼀节点到NULL的任何路径,所含⿊结点数必须相同
4、为何map和set的插⼊删除效率⽐其他序列⾼
因为不需要内存拷贝和移动
5、为何map和set每次insert之后,以前保存的iterator不会失效?
因为插⼊操作只是结点指针换来换去,结点内存没有改变,⽽iterator就像指向结点的指针,内存没变,指向内存的指针也不会变。
6、当数据元素增多时,(从10000到20000),map、set查找速度会怎样变化?
红⿊树⽤⼆分查找法,时间复杂度为logN,所以查找次数从log100000=14变为log20000=15,多了1次⽽已。
7、STL常⽤的容器有哪些以及各⾃的特点是什么?
vector:底层数据结构为数组,⽀持快速随机访问。list:底层数据结构为双向链表,⽀持快速增删。
deque:底层数据结构为⼀个中央控制器和多个缓冲区,⽀持⾸尾(中间不能)快速增删,也⽀持随机访问。
stack:底层⼀般⽤deque/list实现,封闭头部即可,不⽤vector的原因应该是容量⼤⼩有限制,扩容耗时。
queue:底层⼀般⽤deque/list实现,封闭头部即可,不⽤vector的原因应该是容量⼤⼩有限制,扩容耗时。
priority_queue:的底层数据结构⼀般为vector为底层容器,堆heap为处理规则来管理底层容器实现。
set:底层数据结构为红⿊树,有序,不重复。multiset:底层数据结构为红⿊树,有序,可重复。
map:底层数据结构为红⿊树,有序,不重复。multimap:底层数据结构为红⿊树,有序,可重复。
unordered_set:底层数据结构为hash表,⽆序,不重复。
unordered_multiset:底层数据结构为hash表,⽆序,可重复。unordered_map
:底层数据结构为hash表,⽆序,不重复。unordered_multimap:底层数据结构为hash表,⽆序,可重复。
8、为何每次insert之后,以前保存的iterator不会失效?
iterator这⾥就相当于指向节点的指针,内存没有变,指向内存的指针怎么会失效呢(当然被删除的那个元素本⾝已经失效了)。相对于
vector来说,每⼀次删除和插⼊,指针都有可能失效,调⽤push_back在尾部插⼊也是如此。因为为了保证内部数据的连续存
放,iterator指向的那块内存在删除和插⼊过程中可能已经被其他内存覆盖或者内存已经被释放了。即使时push_back的时候,容器
内部空间可能不够,需要⼀块新的更⼤的内存,只有把以前的内存释放,申请新的更⼤的内存,复制已有的数据元素到新的内存,最
后把需要插⼊的元素放到最后,那么以前的内存指针⾃然就不可⽤了。特别时在和find等算法在⼀起使⽤的时候,牢记这个原则:不要
使⽤过期的iterator。
9、说说vector和list的区别
vector底层实现是数组,所以在内存中是连续存放的,随机读取效率⾼,但插⼊、删除效率低;list底层实现是双向链表,所以在内存
中是任意存放的,插⼊、删除效率⾼,但访问元素效率低。
vector在中间节点进⾏插⼊、删除会导致内存拷贝,⽽list不会。
vector⼀次性分配好内存,不够时才进⾏2倍扩容;list每次插⼊新节点都会进⾏内存申请。
10、deque与vector的区别
vector是单向开⼝的连续线性空间,deque是双向开⼝的连续线程空间。
deque没有提供空间保留功能,vector则要提供空间保留功能。deque也提供随机访问迭代器,但是其迭代器⽐vector复杂很多
11、vector扩容原理
以原内存空间⼤⼩的两倍配置⼀份新的内存空间,并将原空间数据拷贝过来进⾏初始化。
12、vector插⼊删除和list有什么区别
vector插⼊删除数据,需要对现有数据复制移动,如果vector存储的对象很⼤或者构造函数很复杂,则开销很⼤,如果是简单的⼩数
据,效率优于list
list插⼊和删除数据,需要对现有数据进⾏遍历,但要在⾸部插⼊数据,效率很⾼。
13、map和set有什么区别
map中的元素是键值对;Set仅是关键字的简单集合;set的迭代器是const的,不允许修改元素的值;
map允许修改value,但不允许修改key;map⽀持⽤关键字作下标操作,set不⽀持下标操作。
14、hash_map和map的区别在哪⾥?
构造函数。hash_map需要hash函数,等于函数;map只需要⽐较函数(⼩于函数).
存储结构。hash_map采⽤hash表存储,map⼀般采⽤红⿊树(RBTree)实现。因此其memory数据结构是不⼀样的。
15、map和unordered_map的区别
map:map内部实现了⼀个红⿊树,红⿊树的每⼀个节点都代表着map的⼀个元素,因此所有元素都是有序的,对其进⾏查找、插
⼊、删除得效率都是O(log
n);但是,因为每个结点都需要额外保存数据,所以空间占⽤率⽐较⾼。
unordered_map:unordered_map内部实现了⼀个哈希表,因此内部元素是⽆序的,对其进⾏查找、插⼊、删除得效率都是O(1);
但是建⽴哈希表⽐较费时。
16、STL中迭代器的作⽤,有指针为何还要迭代器
Iterator(迭代器)模式⼜称Cursor(游标)模式,⽤于提供⼀种⽅法顺序访问⼀个聚合对象中各个元素,
⽽⼜不需暴露该对象的内部表⽰。
迭代器不是指针,是类模板,表现的像指针。他只是模拟了指针的⼀些功能,通过重载了指针的⼀些操作符,->、*、++、–等,相当
于⼀种智能指针。
迭代器产⽣原因:Iterator采⽤的是⾯向对象的思想,把不同集合类的访问逻辑抽象出来,使得不⽤暴露集合内部的结构⽽达到循环遍
历集合的效果。
17、auto_ptr可以做vector的元素吗?为什么?
不能。因为STL的标准容器规定它所容纳的元素必须是可以拷贝构造和可被转移赋值的。⽽auto_ptr不能,可以⽤shared_ptr智能指
针代替。
18、简单说⼀下next_permutation和partition的实现?
(下⼀个排列) ⾸先,从最尾端开始往前寻找2个相邻元素,令第⼀个元素为i,第⼆个元素为I,且满⾜i<I,
找到这样⼀组相邻元素后,再从尾端开始向前检验,找出第⼀个⼤于i的元素j,将i和j对调,再将ii之后的所有元素颠倒排列,此即所
求“下⼀个”排列组合。
: 令头端迭代器first向尾部移动,尾部迭代器last向头部移动。当first所指的值⼤于或等于枢轴时就停下来,当last所
指的值⼩于或等于枢轴时也停下来,然后检验两个迭代器是否交错。如果first仍然在last左边,就将连着元素互换,然后各⾃调整⼀
个位置(向中央逼近),再继续进⾏相同的⾏为。如果发现两个迭代器叫错了,表⽰整个序列已经调整完毕。
19、不允许有遍历⾏为的容器有哪些?(不提供迭代器)
,除了头部外,没有其他⽅法存取deque的其他元素。
(底层以deque实现),除了最顶端外,没有任何⽅法可以存取stack的其他元素。
,所有元素都必须遵循特别的排序规则,不提供遍历功能。
20、list⾃带排序函数的排序原理。
将前两个元素合并,再将后两个元素合并,然后合并这两个⼦序列成4个元素的⼦序列,重复这⼀过程,得到8个,16个,…,⼦序
列,最后得到的就是排序后的序列。时间复杂度:O(nlgn)
⾯试题均取之于⽹络,如有问题还请各位前辈多多指正。

C++容器STL相关面试问题 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数3
  • 收藏数0 收藏
  • 顶次数0
  • 上传人小小布
  • 文件大小442 KB
  • 时间2022-11-21