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

简介: C++容器STL相关面试问题

1、六大组件介绍

容器:数据结构,用来存放数据 算法:常用算法 迭代器:容器和算法之间的胶合剂,“范型指针”

仿函数:一种重载了operator()的类,使得这个类的使用看上去像函数 配置器:为容器分配并管理内存 适配器:修改其他组件接口

2、为何map和set的插入删除效率比用其他序列容器高?

对于关联容器来说,不需要做内存拷贝和内存移动。map和set容器内所有元素都是以节点的方式来存储,其节点结构和链表差不多,指向父节点和子节点

3、红黑树有什么性质?

1.每个节点都是红色或黑色

2.根节点为黑色

3.叶节点为黑色的NULL结点。

4.如果结点为红,其子节点必须为黑

5.任一节点到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一般采用 红黑树(RB Tree) 实现。因此其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的实现?

1.next_permutation(下一个排列)   首先,从最尾端开始往前寻找2个相邻元素,令第一个元素为i,第二个元素为I,且满足i< I,找到这样一组相邻元素后,再从尾端开始向前检验,找出第一个大于i的元素j,将i和j对调,再将ii之后的所有元素颠倒排列,此即所求“下一个”排列组合。

2.partion:   令头端迭代器first向尾部移动,尾部迭代器last向头部移动。当first所指的值大于或等于枢轴时就停下来,当last所指的值小于或等于枢轴时也停下来,然后检验两个迭代器是否交错。如果first仍然在last左边,就将连着元素互换,然后各自调整一个位置(向中央逼近),再继续进行相同的行为。如果发现两个迭代器叫错了,表示整个序列已经调整完毕。

19、不允许有遍历行为的容器有哪些?(不提供迭代器)

1.queue ,除了头部外,没有其他方法存取deque的其他元素。

2.stack(底层以deque实现),除了最顶端外,没有任何方法可以存取stack的其他元素。

3.heap,所有元素都必须遵循特别的排序规则,不提供遍历功能。

20、list自带排序函数的排序原理。

将前两个元素合并,再将后两个元素合并,然后合并这两个子序列成4个元素的子序列,重复这一过程,得到8个,16个,…,子序列,最后得到的就是排序后的序列。时间复杂度:O(nlgn)

面试题均取之于网络,如有问题还请各位前辈多多指正。


目录
打赏
0
0
0
0
6
分享
相关文章
【c++丨STL】map/multimap的使用
本文详细介绍了STL关联式容器中的`map`和`multimap`的使用方法。`map`基于红黑树实现,内部元素按键自动升序排列,存储键值对,支持通过键访问或修改值;而`multimap`允许存在重复键。文章从构造函数、迭代器、容量接口、元素访问接口、增删操作到其他操作接口全面解析了`map`的功能,并通过实例演示了如何用`map`统计字符串数组中各元素的出现次数。最后对比了`map`与`set`的区别,强调了`map`在处理键值关系时的优势。
96 73
【c++丨STL】set/multiset的使用
本文深入解析了STL中的`set`和`multiset`容器,二者均为关联式容器,底层基于红黑树实现。`set`支持唯一性元素存储并自动排序,适用于高效查找场景;`multiset`允许重复元素。两者均具备O(logN)的插入、删除与查找复杂度。文章详细介绍了构造函数、迭代器、容量接口、增删操作(如`insert`、`erase`)、查找统计(如`find`、`count`)及`multiset`特有的区间操作(如`lower_bound`、`upper_bound`、`equal_range`)。最后预告了`map`容器的学习,其作为键值对存储的关联式容器,同样基于红黑树,具有高效操作特性。
17 3
C++ 容器全面剖析:掌握 STL 的奥秘,从入门到高效编程
C++ 标准模板库(STL)提供了一组功能强大的容器类,用于存储和操作数据集合。不同的容器具有独特的特性和应用场景,因此选择合适的容器对于程序的性能和代码的可读性至关重要。对于刚接触 C++ 的开发者来说,了解这些容器的基础知识以及它们的特点是迈向高效编程的重要一步。本文将详细介绍 C++ 常用的容器,包括序列容器(`std::vector`、`std::array`、`std::list`、`std::deque`)、关联容器(`std::set`、`std::map`)和无序容器(`std::unordered_set`、`std::unordered_map`),全面解析它们的特点、用法
C++ 容器全面剖析:掌握 STL 的奥秘,从入门到高效编程
|
20天前
|
【c++丨STL】priority_queue(优先级队列)的使用与模拟实现
本文介绍了STL中的容器适配器`priority_queue`(优先级队列)。`priority_queue`根据严格的弱排序标准设计,确保其第一个元素始终是最大元素。它底层使用堆结构实现,支持大堆和小堆,默认为大堆。常用操作包括构造函数、`empty`、`size`、`top`、`push`、`pop`和`swap`等。我们还模拟实现了`priority_queue`,通过仿函数控制堆的类型,并调用封装容器的接口实现功能。最后,感谢大家的支持与关注。
55 1
|
2月前
|
【c++丨STL】stack和queue的使用及模拟实现
本文介绍了STL中的两个重要容器适配器:栈(stack)和队列(queue)。容器适配器是在已有容器基础上添加新特性或功能的结构,如栈基于顺序表或链表限制操作实现。文章详细讲解了stack和queue的主要成员函数(empty、size、top/front/back、push/pop、swap),并提供了使用示例和模拟实现代码。通过这些内容,读者可以更好地理解这两种数据结构的工作原理及其实现方法。最后,作者鼓励读者点赞支持。 总结:本文深入浅出地讲解了STL中stack和queue的使用方法及其模拟实现,帮助读者掌握这两种容器适配器的特性和应用场景。
69 21
深入浅出 C++ STL:解锁高效编程的秘密武器
C++ 标准模板库(STL)是现代 C++ 的核心部分之一,为开发者提供了丰富的预定义数据结构和算法,极大地提升了编程效率和代码的可读性。理解和掌握 STL 对于 C++ 开发者来说至关重要。以下是对 STL 的详细介绍,涵盖其基础知识、发展历史、核心组件、重要性和学习方法。
【IO面试题 四】、介绍一下Java的序列化与反序列化
Java的序列化与反序列化允许对象通过实现Serializable接口转换成字节序列并存储或传输,之后可以通过ObjectInputStream和ObjectOutputStream的方法将这些字节序列恢复成对象。
面试官:单核 CPU 支持 Java 多线程吗?为什么?被问懵了!
本文介绍了多线程环境下的几个关键概念,包括时间片、超线程、上下文切换及其影响因素,以及线程调度的两种方式——抢占式调度和协同式调度。文章还讨论了减少上下文切换次数以提高多线程程序效率的方法,如无锁并发编程、使用CAS算法等,并提出了合理的线程数量配置策略,以平衡CPU利用率和线程切换开销。
面试官:单核 CPU 支持 Java 多线程吗?为什么?被问懵了!
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
本文详解自旋锁的概念、优缺点、使用场景及Java实现。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
大厂面试必看!Java基本数据类型和包装类的那些坑
本文介绍了Java中的基本数据类型和包装类,包括整数类型、浮点数类型、字符类型和布尔类型。详细讲解了每种类型的特性和应用场景,并探讨了包装类的引入原因、装箱与拆箱机制以及缓存机制。最后总结了面试中常见的相关考点,帮助读者更好地理解和应对面试中的问题。
117 4

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等