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)。


目录
相关文章
|
4月前
|
存储 算法 C++
C++ STL 初探:打开标准模板库的大门
C++ STL 初探:打开标准模板库的大门
144 10
|
24天前
|
C++ 容器
【c++丨STL】stack和queue的使用及模拟实现
本文介绍了STL中的两个重要容器适配器:栈(stack)和队列(queue)。容器适配器是在已有容器基础上添加新特性或功能的结构,如栈基于顺序表或链表限制操作实现。文章详细讲解了stack和queue的主要成员函数(empty、size、top/front/back、push/pop、swap),并提供了使用示例和模拟实现代码。通过这些内容,读者可以更好地理解这两种数据结构的工作原理及其实现方法。最后,作者鼓励读者点赞支持。 总结:本文深入浅出地讲解了STL中stack和queue的使用方法及其模拟实现,帮助读者掌握这两种容器适配器的特性和应用场景。
55 21
|
2月前
|
编译器 C语言 C++
【c++丨STL】list模拟实现(附源码)
本文介绍了如何模拟实现C++中的`list`容器。`list`底层采用双向带头循环链表结构,相较于`vector`和`string`更为复杂。文章首先回顾了`list`的基本结构和常用接口,然后详细讲解了节点、迭代器及容器的实现过程。 最终,通过这些步骤,我们成功模拟实现了`list`容器的功能。文章最后提供了完整的代码实现,并简要总结了实现过程中的关键点。 如果你对双向链表或`list`的底层实现感兴趣,建议先掌握相关基础知识后再阅读本文,以便更好地理解内容。
42 1
|
2月前
|
算法 C语言 C++
【c++丨STL】list的使用
本文介绍了STL容器`list`的使用方法及其主要功能。`list`是一种双向链表结构,适用于频繁的插入和删除操作。文章详细讲解了`list`的构造函数、析构函数、赋值重载、迭代器、容量接口、元素访问接口、增删查改操作以及一些特有的操作接口如`splice`、`remove_if`、`unique`、`merge`、`sort`和`reverse`。通过示例代码,读者可以更好地理解如何使用这些接口。最后,作者总结了`list`的特点和适用场景,并预告了后续关于`list`模拟实现的文章。
69 7
|
3月前
|
存储 编译器 C语言
【c++丨STL】vector的使用
本文介绍了C++ STL中的`vector`容器,包括其基本概念、主要接口及其使用方法。`vector`是一种动态数组,能够根据需要自动调整大小,提供了丰富的操作接口,如增删查改等。文章详细解释了`vector`的构造函数、赋值运算符、容量接口、迭代器接口、元素访问接口以及一些常用的增删操作函数。最后,还展示了如何使用`vector`创建字符串数组,体现了`vector`在实际编程中的灵活性和实用性。
135 4
|
3月前
|
C语言 C++ 容器
【c++丨STL】string模拟实现(附源码)
本文详细介绍了如何模拟实现C++ STL中的`string`类,包括其构造函数、拷贝构造、赋值重载、析构函数等基本功能,以及字符串的插入、删除、查找、比较等操作。文章还展示了如何实现输入输出流操作符,使自定义的`string`类能够方便地与`cin`和`cout`配合使用。通过这些实现,读者不仅能加深对`string`类的理解,还能提升对C++编程技巧的掌握。
140 5
|
3月前
|
存储 编译器 C语言
【c++丨STL】string类的使用
本文介绍了C++中`string`类的基本概念及其主要接口。`string`类在C++标准库中扮演着重要角色,它提供了比C语言中字符串处理函数更丰富、安全和便捷的功能。文章详细讲解了`string`类的构造函数、赋值运算符、容量管理接口、元素访问及遍历方法、字符串修改操作、字符串运算接口、常量成员和非成员函数等内容。通过实例演示了如何使用这些接口进行字符串的创建、修改、查找和比较等操作,帮助读者更好地理解和掌握`string`类的应用。
89 2
|
3月前
|
存储 算法 Linux
【c++】STL简介
本文介绍了C++标准模板库(STL)的基本概念、组成部分及学习方法,强调了STL在提高编程效率和代码复用性方面的重要性。文章详细解析了STL的六大组件:容器、算法、迭代器、仿函数、配接器和空间配置器,并提出了学习STL的三个层次,旨在帮助读者深入理解和掌握STL。
100 0
|
3月前
|
存储 网络协议 安全
30 道初级网络工程师面试题,涵盖 OSI 模型、TCP/IP 协议栈、IP 地址、子网掩码、VLAN、STP、DHCP、DNS、防火墙、NAT、VPN 等基础知识和技术,帮助小白们充分准备面试,顺利踏入职场
本文精选了 30 道初级网络工程师面试题,涵盖 OSI 模型、TCP/IP 协议栈、IP 地址、子网掩码、VLAN、STP、DHCP、DNS、防火墙、NAT、VPN 等基础知识和技术,帮助小白们充分准备面试,顺利踏入职场。
206 2
|
2月前
|
存储 编译器 C语言
【c++丨STL】vector模拟实现
本文深入探讨了 `vector` 的底层实现原理,并尝试模拟实现其结构及常用接口。首先介绍了 `vector` 的底层是动态顺序表,使用三个迭代器(指针)来维护数组,分别为 `start`、`finish` 和 `end_of_storage`。接着详细讲解了如何实现 `vector` 的各种构造函数、析构函数、容量接口、迭代器接口、插入和删除操作等。最后提供了完整的模拟实现代码,帮助读者更好地理解和掌握 `vector` 的实现细节。
67 0