C/C++面试八股题(十)

更多专栏:

超详细的嵌入式面经专栏(适用于小白学习和大佬复习):https://www.nowcoder.com/creation/manager/columnDetail/mGYoDz

校招公司汇总专栏:https://www.nowcoder.com/creation/manager/columnDetail/0ybKdp

目录:

1.STL中常用的容器有哪些?

2.请你说说STL容器有哪些并且说一下时间复杂度?

3.请说说vector和list有什么区别?

4.vector和deque的区别?

5.请你说明一下STL底层数据结构实现?

6.请你说说map和set区别差异?

7.请你说说STL迭代器怎样删除元素?

内容:

1.STL中常用的容器有哪些?

顺序容器

1. vector

  • 动态数组,支持随机访问。
  • 元素存储在连续的内存空间中,支持高效的索引操作(O(1) 时间复杂度)。
  • 在尾端增删元素。

2. deque

  • 双端队列,支持在两端高效地插入和删除。
  • 支持随机访问。
  • 相较于 vector,不需要频繁搬移整个数组,但随机访问性能稍差。
  • 需要在头尾进行频繁插入或删除操作。

3.list

  • 双向链表,支持高效的插入和删除。
  • 不支持随机访问。
  • 插入和删除操作仅需要调整指针,时间复杂度为 O(1)。
  • 频繁插入和删除操作,但对随机访问要求不高。

4 .forward_list

  • 单向链表,支持单向遍历和高效的插入、删除操作。
  • 相较于 list,更加轻量级。
  • 使用单向链表实现,元素通过单指针链接,内存不连续。
  • 需要简单链表操作,内存开销较小的场景。

5. string

  • 专门用于操作字符串的容器,功能类似 vector<char>。
  • 基于动态数组实现,支持动态扩容。
  • 提供了大量字符串处理函数,例如拼接、查找、替换等。
  • 字符串操作。

关联容器

1. map

  • 存储键值对,键是唯一的,支持高效的查找、插入、删除操作(O(log n))。
  • 数据按照键值排序,支持有序遍历。
  • 需要按键有序存储键值对,并支持快速查找。

2. multimap

  • 和 map 类似,但允许键重复。
  • 和 map 一样基于红黑树实现,区别在于支持存储重复键。
  • 键值对存储,但允许键重复。

3. set

  • 存储唯一的键,自动按顺序排列。
  • 支持高效的插入、查找、删除操作(O(log n))。
  • 基于红黑树实现。
  • 元素作为键值存储,不能重复。
  • 需要存储唯一值,并支持快速查找和有序遍历。

4. multiset

  • 和 set 类似,但允许重复值。
  • 和 set 一样基于红黑树实现,区别在于允许重复值。
  • 数据存储需支持重复值,但仍需要有序存储。

5. unordered_map

  • 存储键值对,键是唯一的,查找和插入操作的平均时间复杂度为 O(1)。
  • 基于哈希表实现。
  • 数据无序存储。
  • 快速查找键值对,但对顺序无要求。

6. unordered_multimap

  • 和 unordered_map 类似,但允许键重复。
  • 基于哈希表实现,支持重复键。
  • 快速查找键值对,允许键重复。

7. unordered_set

  • 存储唯一值,无序排列。
  • 基于哈希表实现。
  • 无序存储唯一值,并支持快速查找。

8. unordered_multiset

  • 和 unordered_set 类似,但允许重复值。
  • 基于哈希表实现。
  • 无序存储值,并允许重复。

总结

容器类型

特点

底层实现

适用场景

vector

动态数组,随机访问高效

动态数组

数据量变化大,需要高效随机访问

deque

双端队列,支持头尾插入删除

分段数组

频繁的头尾操作

list

双向链表,插入删除高效

双向链表

频繁插入删除,随机访问不重要

array

静态数组,大小固定

静态数组

固定大小数组

map

有序键值对存储,键唯一

红黑树

需要有序键值对存储

unordered_map

无序键值对存储,键唯一

哈希表

快速键值对查找,但无需顺序

set

存储唯一值,有序排列

红黑树

存储唯一值,并需要排序

unordered_set

存储唯一值,无序排列

哈希表

存储唯一值,但无需排序

2.请你说说STL容器有哪些并且说一下时间复杂度?

顺序容器

顺序容器中的元素按插入顺序存储,主要用于序列存储。

容器

特点

插入复杂度

删除复杂度

访问复杂度

vector

动态数组,支持随机访问,内存连续,支持动态扩容

O(1)(尾部),O(n)(其他位置)

O(n)

O(1)

deque

双端队列,支持头尾快速插入删除

O(1)(头/尾)

O(1)(头/尾)

O(1)(随机访问)

list

双向链表,插入删除高效,不支持随机访问

O(1)(任意位置)

O(1)(任意位置)

O(n)(线性访问)

forward_list

单向链表,仅支持单向遍历和插入删除

O(1)

O(1)

O(n)(线性访问)

array

定长数组,大小在编译时确定,支持随机访问

O(1)

O(1)

O(1)

string

动态字符数组,功能类似于 vector<char>,专为字符串操作优化

O(1)(尾部),O(n)(其他位置)

O(n)

O(1)

关联容器

关联容器通常按键值对存储,底层实现基于红黑树,支持有序存储和快速查找。

容器

特点

插入复杂度

删除复杂度

查找复杂度

map

有序字典,键唯一,支持按键值快速查找

O(log n)

O(log n)

O(log n)

multimap

有序字典,键允许重复

O(log n)

O(log n)

O(log n)

set

有序集合,存储唯一元素

O(log n)

O(log n)

O(log n)

multiset

有序集合,允许重复元素

O(log n)

O(log n)

O(log n)

无序关联容器

无序关联容器底层基于哈希表实现,支持快速的查找、插入和删除操作,但不保证元素的顺序。

容器

特点

插入复杂度

删除复杂度

查找复杂度

unordered_map

无序字典,键唯一

O(1)(均摊),O(n)(最坏)

O(1)(均摊),O(n)(最坏)

O(1)(均摊),O(n)(最坏)

unordered_multimap

无序字典,键允许重复

O(1)(均摊),O(n)(最坏)

O(1)(均摊),O(n)(最坏)

O(1)(均摊),O(n)(最坏)

unordered_set

无序集合,存储唯一元素

O(1)(均摊),O(n)(最坏)

O(1)(均摊),O(n)(最坏)

O(1)(均摊),O(n)(最坏)

unordered_multiset

无序集合,允许重复元素

O(1)(均摊),O(n)(最坏)

O(1)(均摊),O(n)(最坏)

O(1)(均摊),O(n)(最坏)

容器适配器

容器

底层实现

插入复杂度

删除复杂度

特点

stack

通常基于 dequevector

O(1)

O(1)

后进先出(LIFO),只操作栈顶。

queue

通常基于 deque

O(1)

O(1)

先进先出(FIFO),只操作队首和队尾。

priority_queue

通常基于 vector

O(log n)

O(log n)

优先队列,堆实现,最大/最小元素优先出队。

3.请说说vector和list有什么区别?

相同点

  • 两者都属于顺序容器,用于按插入顺序存储元素。
  • 支持动态大小调整(虽然实现方式不同)。
  • 都能通过 STL 提供的标准迭代器(iterator)进行元素的访问和操作。
  • 两者提供类似的容器操作接口,如插入(insert)、删除(erase)、遍历(begin/end)等。
  • 支持 STL 算法(如 std::sort,但需要注意 list 需要先转为其他容器才支持随机访问相关算法)。
  • 容器中的元素可以是基本数据类型,也可以是用户自定义的复杂类型。

不同点

特性

vector

list

底层实现

动态数组,存储在连续的内存块中。

双向链表,每个节点存储元素和前后指针。

内存分配方式

单块连续内存,扩容时可能导致整块重新分配。

分散的非连续内存,每个节点单独分配内存空间。

随机访问

支持随机访问(O(1)),例如通过索引 v[i]

不支持随机访问,只能通过迭代器线性遍(

O(n))。

插入/删除复杂度

尾部操作为 O(1),中间插入/删除需移动元素,复杂度 O(n)

任意位置操作为 O(1)(只需调整指针)。

遍历性能

由于数据连续,访问时缓存性能更好,速度更快。

数据分散,遍历性能较慢,但在长链表中删除或插入性能更高。

动态扩展

扩容时容量按 倍数增长,可能会导致内存重新分配及数据拷贝。

每次添加一个节点,仅分配所需的节点内存,无需整体重新分配。

排序

使用 STL 中的 std::sort,复杂度为 O(n log n)

使用成员函数 list::sort,复杂度为

O(n log n),不需要额外空间。

内存利用率

连续内存分配,开销小,内存利用率高。

每个节点需额外存储两个指针,内存开销更大。

使用场景

vector 的场景

  • 需要随机访问,如果需要频繁按索引访问元素,vector 是更好的选择。
  • 数据量变化不频繁,数据量相对固定或变化不频繁,避免频繁的动态扩容带来的性能开销。
  • 需要排序或二分查找,vector 支持快速排序和二分查找等操作,效率比 list 高。
  • 空间效率高,内存连续分配,不需要额外的指针存储。

list 的场景

  • 需要频繁的插入/删除操作,特别是在容器中间进行大量插入或删除操作时,list 的性能比 vector 好。
  • 数据较大或变化频繁,数据量较大时,可以避免因 vector 扩容带来的大量内存分配和拷贝。
  • 不需要随机访问,如果只需顺序访问,链表的性能足够且更灵活。

例子:

vector

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3};
    v.push_back(4); // 在尾部插入
    v[2] = 5;       // 通过索引修改
    for (int i : v) {
        cout << i << " "; // 输出:1 2 5 4
    }
    return 0;
}

list

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> l = {1, 2, 3};
    auto it = l.begin();
    advance(it, 1); // 移动迭代器到第二个元素
    l.insert(it, 5)

剩余60%内容,订阅专栏后可继续查看/也可单篇购买

嵌入式/C++八股 文章被收录于专栏

本人双飞本,校招上岸广和通。此专栏覆盖嵌入式常见面试题,有C/C++相关的知识,数据结构和算法也有嵌入式相关的知识,如操作系统、网络协议、硬件知识。本人也是校招过来的,大家底子甚至项目,可能都不错,但是在面试准备中常见八股可能准备不全。此专栏很适合新手学习基础也适合大佬备战复习,比较全面。最终希望各位友友们早日拿到心仪offer。也希望大家点点赞,收藏,送送小花。这是对我的肯定和鼓励。 持续更新

全部评论
有用速更速更
点赞 回复 分享
发布于 01-19 16:40 陕西

相关推荐

头像
10-13 18:10
已编辑
东南大学 C++
。收拾收拾心情下一家吧————————————————10.12更新上面不知道怎么的,每次在手机上编辑都会只有最后一行才会显示。原本不想写凉经的,太伤感情了,但过了一天想了想,凉经的拿起来好好整理,就像象棋一样,你进步最快的时候不是你赢棋的时候,而是在输棋的时候。那废话不多说,就做个复盘吧。一面:1,经典自我介绍2,项目盘问,没啥好说的,感觉问的不是很多3,八股问的比较奇怪,他会深挖性地问一些,比如,我知道MMU,那你知不知道QMMU(记得是这个,总之就是MMU前面加一个字母)4,知不知道slab内存分配器-&gt;这个我清楚5,知不知道排序算法,排序算法一般怎么用6,写一道力扣的,最长回文子串反问:1,工作内容2,工作强度3,关于友商的问题-&gt;后面这个问题问HR去了,和中兴有关,数通这个行业和友商相关的不要提,这个行业和别的行业不同,别的行业干同一行的都是竞争关系,数通这个行业的不同企业的关系比较微妙。特别细节的问题我确实不知道,但一面没挂我。接下来是我被挂的二面,先说说我挂在哪里,技术性问题我应该没啥问题,主要是一些解决问题思路上的回答,一方面是这方面我准备的不多,另一方面是这个面试写的是“专业面试二面”,但是感觉问的问题都是一些主管面/综合面才会问的问题,就是不问技术问方法论。我以前形成的思维定式就是专业面会就是会,不会就直说不会,但事实上如果问到方法论性质的问题的话得扯一下皮,不能按照上面这个模式。刚到位置上就看到面试官叹了一口气,有一些不详的预感。我是下午1点45左右面的。1,经典自我介绍2,你是怎么完成这个项目的,分成几个步骤。我大致说了一下。你有没有觉得你的步骤里面缺了一些什么,(这里已经在引导我往他想的那个方向走了),比如你一个人的能力永远是不够的,,,我们平时会有一些组内的会议来沟通我们的所思所想。。。。3,你在项目中遇到的最困难的地方在什么方面4,说一下你知道的TCP/IP协议网络模型中的网络层有关的协议......5,接着4问,你觉得现在的socket有什么样的缺点,有什么样的优化方向?6,中间手撕了一道很简单的快慢指针的问题。大概是在链表的倒数第N个位置插入一个节点。————————————————————————————————————10.13晚更新补充一下一面说的一些奇怪的概念:1,提到了RPC2,提到了fu(第四声)拷贝,我当时说我只知道零拷贝,知道mmap,然后他说mmap是其中的一种方式,然后他问我知不知道DPDK,我说不知道,他说这个是一个高性能的拷贝方式3,MMU这个前面加了一个什么字母我这里没记,别问我了4,后面还提到了LTU,VFIO,孩子真的不会。
走呀走:华子二面可能会有场景题的,是有些开放性的问题了
点赞 评论 收藏
分享
评论
14
36
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务