C/C++工程师面试题(STL篇)

简介: C/C++工程师面试题(STL篇)

image.gif

STL 中有哪些常见的容器

STL 中容器分为顺序容器、关联式容器、容器适配器三种类型,三种类型容器特性分别如下:

1. 顺序容器 容器并非排序的,元素的插入位置同元素的值无关,包含 vector、deque、list

  • vector:动态数组 元素在内存连续存放。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能。
  • deque:双向队列 元素在内存连续存放。随机存取任何元素都能在常数时间完成(仅次于 vector )。在两端增删元素具有较佳的性能(大部分情况下是常数时间)。
  • list:双向链表 元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。不支持随机存取。

2. 关联式容器 元素是排序的;插入任何元素,都按相应的排序规则来确定其位置;在查找时具有非常好的性能;通常以平衡二叉树的方式实现,包含set、map。

  • set  set中不允许相同元素
  • map map 与 set 的不同在于 map 中存放的元素有且仅有两个成员变,一个名为 first,另一个名为 second,map 根据 first 值对元素从小到大排序,并可快速地根据 first 来检索元素。

3. 容器适配器 封装了一些基本的容器,使之具备了新的函数功能,包含 stack、queue。

  • stack:栈 栈是项的有限序列,并满足序列中被删除、检索和修改的项只能是最进插入序列的项(栈顶的项),后进先出。
  • queue:队列 插入只可以在尾部进行,删除、检索和修改只允许从头部进行,先进先出。

STL 容器用过哪些,查找的时间复杂度是多少,为什么?

以下是其中一些常见容器的查找时间复杂度以及原因:

  1. vector(向量):查找时间复杂度为O(n),因为vector是基于数组实现的,需要线性遍历整个数组来查找元素。
  2. deque(双端队列):在未排序状态下,查找时间复杂度为O(n),类似于vector。但在有序状态下,可以利用二分查找,降低查找时间复杂度为O(log n)。
  3. list(链表):查找时间复杂度为O(n),因为链表是一种线性结构,需要从头开始顺序查找元素。
  4. set(集合)multiset(多重集合):查找时间复杂度为O(log n),底层通常使用红黑树实现,具有较好的平衡性能。
  5. map(映射)multimap(多重映射):查找时间复杂度为O(log n),底层通常使用红黑树实现,按键进行自动排序。
  6. stack(栈)queue(队列):查找时间复杂度为O(n),因为它们是容器适配器,提供了先进先出(FIFO)或后进先出(LIFO)的接口,并不支持快速查找操作。

因此,对于不同的STL容器,其查找时间复杂度取决于底层数据结构的实现方式和算法设计。

vector 和 list 的区别,分别适用于什么场景?

vector 和 list 的区别:

  1. 底层数据结构:
  • vector: 底层使用动态数组实现。
  • list: 底层使用双向链表实现。
  1. 插入和删除操作:
  • vector: 插入和删除元素效率低。
  • list: 插入和删除元素效率高,因为只需要修改相邻节点的指针。
  1. 随机访问:
  • vector: 支持随机访问,可以通过下标快速访问元素。
  • list: 不支持随机访问,只能通过迭代器顺序访问元素。
  1. 空间和内存分配:
  • vector: vector 一次性分配好内存,不够时才进行扩容。
  • list: list 每次插入新节点都会进行内存申请。

适用场景:

  • vector: 适用于连续存储,支持随机访问,而不在乎插入和删除的效率。
  • list: 适用于不连续的内存空间,如果需要高效的插入和删除,而不关心随机访问。

简述 vector 的实现原理

vector 是一种动态数组,在内存中具有连续的存储空间,支持快速随机访问,由于具有连续的存储空间,所以在插入和删除操作方面,效率比较慢。

当 vector 的大小和容量相等(size==capacity)时,如果再向其添加元素,那么 vector 就需要扩容。vector 容器扩容的过程需要经历以下 3 步:

  1. 重新在堆上创建更大的动态数组,大小是原来的2倍;
  2. 将旧内存空间中的数据,按原有顺序移动到新的内存空间中;
  3. 最后将旧的内存空间释放。

扩容以后它的内存地址会发生改变

迭代器失效原因,有哪些情况

迭代器失效是指迭代器在遍历容器过程中,由于容器的结构发生改变而导致迭代器指向的元素不再有效。

以下是导致迭代器失效的常见情况:

  1. 插入和删除操作: 当在容器中插入或删除元素时,可能会导致容器内存重新分配或元素位置的改变,这可能会使迭代器失效。
  2. 清空容器: 清空容器会使容器内的所有元素被删除,这样迭代器指向的元素就会失效。
  3. 使用引起重新分配的操作: 例如,在vector中使用push_back()添加元素时,如果超出了当前容量,可能会触发重新分配操作,从而使所有迭代器失效。
  4. 排序操作: 如果在排序过程中,容器的元素被移动了位置,迭代器可能会失效。

deque 的实现原理

分段连续内存、中控器

deque 是由一段一段的连续空间构成。

deque 采取一块所谓的 map(不是 STL 的 map 容器)作为主控,这里所谓的 map 是一小块连续的内存空间,其中的每个元素(此处成为一个结点)都是一个指针,指向另一段连续的内存空间,称作缓冲区。缓冲区才是 deque的存储空间的主体。

红黑树的特性,为什么要有红黑树

红黑树是一种自平衡的二叉搜索树,它具有以下特性:

  1. 节点颜色: 每个节点要么是红色,要么是黑色。
  2. 根节点和叶子节点: 根节点、叶子节点(NIL节点,即空节点)是黑色的
  3. 颜色相邻节点规则: 不能有两个相邻的红色节点。
  4. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。 这保证了红黑树的关键性质:最长路径不超过最短路径的两倍。

2. 各操作的时间复杂度 插入: O(logN) 查看: O(logN) 删除: O(logN)

map/Set 实现原理,各操作的时间复杂度是多少

1. map 实现原理 map 内部实现了一个红黑树,红黑树有自动排序的功能,因此 map 内部所有元素都是有序的,红黑树的每一个节点都代表着 map 的一个元素。因此,对于 map 进行的查找、删除、添加等一系列的操作都相当于是对红黑树进行的操作。map 中的元素是按照二叉树存储的,特点就是左子树上所有节点的键值都小于根节点的键值,右子树所有节点的键值都大于根节点的键值,使用中序遍历可将键值按照从小到大遍历出来。

2. 各操作的时间复杂度 插入: O(logN) 查看: O(logN) 删除: O(logN)

unordered_map 实现原理

unordered_map 容器和 map 容器一样,以键值对(pair类型)的形式存储数据,存储的各个键值对的键互不相同且不允许被修改。但由于 unordered_map 容器底层采用的是哈希表存储结构,该结构本身不具有对数据的排序功能,所以此容器内部不会自行对存储的键值对进行排序。底层采用哈希表实现无序容器时,会将所有数据存储到一整块连续的内存空间中,并且当数据存储位置发生冲突时,解决方法选用的是“链地址法”(又称“开链法”).

map,unordered_map 的区别

  1. map是基于红黑树实现的,unordered_map是基于哈希表实现的
  2. map根据元素的键值会自动排序,而unordered_map是乱序的
  3. map的增删改查时间复杂度是O(logN),而unordered_map的时间复杂度是最好情况是O(1),最坏情况是O(N)。


目录
打赏
0
6
6
1
38
分享
相关文章
【c++丨STL】基于红黑树模拟实现set和map(附源码)
本文基于红黑树的实现,模拟了STL中的`set`和`map`容器。通过封装同一棵红黑树并进行适配修改,实现了两种容器的功能。主要步骤包括:1) 修改红黑树节点结构以支持不同数据类型;2) 使用仿函数适配键值比较逻辑;3) 实现双向迭代器支持遍历操作;4) 封装`insert`、`find`等接口,并为`map`实现`operator[]`。最终,通过测试代码验证了功能的正确性。此实现减少了代码冗余,展示了模板与仿函数的强大灵活性。
26 2
【c++丨STL】map/multimap的使用
本文详细介绍了STL关联式容器中的`map`和`multimap`的使用方法。`map`基于红黑树实现,内部元素按键自动升序排列,存储键值对,支持通过键访问或修改值;而`multimap`允许存在重复键。文章从构造函数、迭代器、容量接口、元素访问接口、增删操作到其他操作接口全面解析了`map`的功能,并通过实例演示了如何用`map`统计字符串数组中各元素的出现次数。最后对比了`map`与`set`的区别,强调了`map`在处理键值关系时的优势。
113 73
【c++丨STL】set/multiset的使用
本文深入解析了STL中的`set`和`multiset`容器,二者均为关联式容器,底层基于红黑树实现。`set`支持唯一性元素存储并自动排序,适用于高效查找场景;`multiset`允许重复元素。两者均具备O(logN)的插入、删除与查找复杂度。文章详细介绍了构造函数、迭代器、容量接口、增删操作(如`insert`、`erase`)、查找统计(如`find`、`count`)及`multiset`特有的区间操作(如`lower_bound`、`upper_bound`、`equal_range`)。最后预告了`map`容器的学习,其作为键值对存储的关联式容器,同样基于红黑树,具有高效操作特性。
29 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 的奥秘,从入门到高效编程
|
5月前
|
C++ STL 初探:打开标准模板库的大门
C++ STL 初探:打开标准模板库的大门
154 10
|
25天前
|
【c++丨STL】priority_queue(优先级队列)的使用与模拟实现
本文介绍了STL中的容器适配器`priority_queue`(优先级队列)。`priority_queue`根据严格的弱排序标准设计,确保其第一个元素始终是最大元素。它底层使用堆结构实现,支持大堆和小堆,默认为大堆。常用操作包括构造函数、`empty`、`size`、`top`、`push`、`pop`和`swap`等。我们还模拟实现了`priority_queue`,通过仿函数控制堆的类型,并调用封装容器的接口实现功能。最后,感谢大家的支持与关注。
66 1
|
2月前
|
【c++丨STL】stack和queue的使用及模拟实现
本文介绍了STL中的两个重要容器适配器:栈(stack)和队列(queue)。容器适配器是在已有容器基础上添加新特性或功能的结构,如栈基于顺序表或链表限制操作实现。文章详细讲解了stack和queue的主要成员函数(empty、size、top/front/back、push/pop、swap),并提供了使用示例和模拟实现代码。通过这些内容,读者可以更好地理解这两种数据结构的工作原理及其实现方法。最后,作者鼓励读者点赞支持。 总结:本文深入浅出地讲解了STL中stack和queue的使用方法及其模拟实现,帮助读者掌握这两种容器适配器的特性和应用场景。
73 21
深入浅出 C++ STL:解锁高效编程的秘密武器
C++ 标准模板库(STL)是现代 C++ 的核心部分之一,为开发者提供了丰富的预定义数据结构和算法,极大地提升了编程效率和代码的可读性。理解和掌握 STL 对于 C++ 开发者来说至关重要。以下是对 STL 的详细介绍,涵盖其基础知识、发展历史、核心组件、重要性和学习方法。
【c++丨STL】list模拟实现(附源码)
本文介绍了如何模拟实现C++中的`list`容器。`list`底层采用双向带头循环链表结构,相较于`vector`和`string`更为复杂。文章首先回顾了`list`的基本结构和常用接口,然后详细讲解了节点、迭代器及容器的实现过程。 最终,通过这些步骤,我们成功模拟实现了`list`容器的功能。文章最后提供了完整的代码实现,并简要总结了实现过程中的关键点。 如果你对双向链表或`list`的底层实现感兴趣,建议先掌握相关基础知识后再阅读本文,以便更好地理解内容。
69 1
【c++丨STL】list的使用
本文介绍了STL容器`list`的使用方法及其主要功能。`list`是一种双向链表结构,适用于频繁的插入和删除操作。文章详细讲解了`list`的构造函数、析构函数、赋值重载、迭代器、容量接口、元素访问接口、增删查改操作以及一些特有的操作接口如`splice`、`remove_if`、`unique`、`merge`、`sort`和`reverse`。通过示例代码,读者可以更好地理解如何使用这些接口。最后,作者总结了`list`的特点和适用场景,并预告了后续关于`list`模拟实现的文章。
103 7

热门文章

最新文章

相关实验场景

更多