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`在处理键值关系时的优势。
103 73
【c++丨STL】基于红黑树模拟实现set和map(附源码)
本文基于红黑树的实现,模拟了STL中的`set`和`map`容器。通过封装同一棵红黑树并进行适配修改,实现了两种容器的功能。主要步骤包括:1) 修改红黑树节点结构以支持不同数据类型;2) 使用仿函数适配键值比较逻辑;3) 实现双向迭代器支持遍历操作;4) 封装`insert`、`find`等接口,并为`map`实现`operator[]`。最终,通过测试代码验证了功能的正确性。此实现减少了代码冗余,展示了模板与仿函数的强大灵活性。
19 2
【c++丨STL】set/multiset的使用
本文深入解析了STL中的`set`和`multiset`容器,二者均为关联式容器,底层基于红黑树实现。`set`支持唯一性元素存储并自动排序,适用于高效查找场景;`multiset`允许重复元素。两者均具备O(logN)的插入、删除与查找复杂度。文章详细介绍了构造函数、迭代器、容量接口、增删操作(如`insert`、`erase`)、查找统计(如`find`、`count`)及`multiset`特有的区间操作(如`lower_bound`、`upper_bound`、`equal_range`)。最后预告了`map`容器的学习,其作为键值对存储的关联式容器,同样基于红黑树,具有高效操作特性。
24 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 的奥秘,从入门到高效编程
|
22天前
|
【c++丨STL】priority_queue(优先级队列)的使用与模拟实现
本文介绍了STL中的容器适配器`priority_queue`(优先级队列)。`priority_queue`根据严格的弱排序标准设计,确保其第一个元素始终是最大元素。它底层使用堆结构实现,支持大堆和小堆,默认为大堆。常用操作包括构造函数、`empty`、`size`、`top`、`push`、`pop`和`swap`等。我们还模拟实现了`priority_queue`,通过仿函数控制堆的类型,并调用封装容器的接口实现功能。最后,感谢大家的支持与关注。
59 1
深入浅出 C++ STL:解锁高效编程的秘密武器
C++ 标准模板库(STL)是现代 C++ 的核心部分之一,为开发者提供了丰富的预定义数据结构和算法,极大地提升了编程效率和代码的可读性。理解和掌握 STL 对于 C++ 开发者来说至关重要。以下是对 STL 的详细介绍,涵盖其基础知识、发展历史、核心组件、重要性和学习方法。
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
【C++进阶】特殊类设计 && 单例模式
通过对特殊类设计和单例模式的深入探讨,我们可以更好地设计和实现复杂的C++程序。特殊类设计提高了代码的安全性和可维护性,而单例模式则确保类的唯一实例性和全局访问性。理解并掌握这些高级设计技巧,对于提升C++编程水平至关重要。
37 16
类和对象(中 )C++
本文详细讲解了C++中的默认成员函数,包括构造函数、析构函数、拷贝构造函数、赋值运算符重载和取地址运算符重载等内容。重点分析了各函数的特点、使用场景及相互关系,如构造函数的主要任务是初始化对象,而非创建空间;析构函数用于清理资源;拷贝构造与赋值运算符的区别在于前者用于创建新对象,后者用于已存在的对象赋值。同时,文章还探讨了运算符重载的规则及其应用场景,并通过实例加深理解。最后强调,若类中存在资源管理,需显式定义拷贝构造和赋值运算符以避免浅拷贝问题。
类和对象(上)(C++)
本篇内容主要讲解了C++中类的相关知识,包括类的定义、实例化及this指针的作用。详细说明了类的定义格式、成员函数默认为inline、访问限定符(public、protected、private)的使用规则,以及class与struct的区别。同时分析了类实例化的概念,对象大小的计算规则和内存对齐原则。最后介绍了this指针的工作机制,解释了成员函数如何通过隐含的this指针区分不同对象的数据。这些知识点帮助我们更好地理解C++中类的封装性和对象的实现原理。

热门文章

最新文章

AI助理

你好,我是AI助理

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