嵌入式开发高频面试题——第四章 常见算法(下)

2024-09-06 18:52

本文主要是介绍嵌入式开发高频面试题——第四章 常见算法(下),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

      • 4.2.1 Vector和List的异同
      • 4.2.2 Vector的内存增长与底层实现
      • 4.2.3 Vector和Deque的比较
      • 4.2.4 STL里有sort函数,为什么list还要定义sort?
      • 4.2.5 STL底层数据结构实现
      • 4.2.6 利用迭代器删除元素会发生什么?
      • 4.2.7 Map的实现与查找效率
      • 4.2.8 几种模板插入的时间复杂度

4.2.1 Vector和List的异同

VectorList 都是C++ STL中的序列容器,但它们在底层实现和适用场景上有明显的区别。

  • 底层实现

    • Vector 是动态数组,它在内存中占据连续的空间,因此支持通过索引直接访问元素。
    • List 是双向链表,在内存中不要求元素是连续存储的,因此不支持直接索引访问,而是通过指针进行遍历。
  • 访问速度

    • Vector 的随机访问速度快,因为可以通过索引直接访问元素。
    • List 的随机访问速度慢,访问某个元素需要从头遍历链表直到找到目标元素。
  • 插入和删除操作

    • Vector 的插入和删除操作(尤其是在中间位置)效率较低,因为需要移动插入点之后的所有元素以保持内存连续。
    • List 的插入和删除操作效率高,只需调整相邻节点的指针即可,不需要移动其他元素。
  • 内存使用

    • Vector 使用连续的内存,因此可能需要频繁的内存分配和重新分配来扩展容量。
    • List 不要求内存连续,因此内存分配和释放的频率较低,但每个元素需要额外存储指向前后节点的指针。

4.2.2 Vector的内存增长与底层实现

Vector 的内存是通过动态数组实现的,内存增长机制如下:

  • 内存增长策略:当 vector 容量不足时,它会按照一定的增长策略分配新的内存空间。通常会以当前容量的2倍(有些实现可能是1.5倍)来增长。

  • 重新分配:当 vector 扩展容量时,它会在新的内存区域中分配两倍大小的空间,然后将旧数组中的元素移动到新的内存区域中。旧的内存空间随后会被释放。

  • 底层实现

    • vector 通过动态数组管理内存,因此它支持常量时间的随机访问。
    • 在插入或删除操作时,如果操作位置在 vector 的中间或开头,所有后续元素都需要移动以保持数组的连续性,这可能导致时间复杂度为O(n)的开销。

4.2.3 Vector和Deque的比较

VectorDeque 都是序列容器,它们的主要区别在于内存管理和操作效率:

  • 内存管理

    • Vector 使用单块连续内存存储数据。
    • Deque 使用一系列固定大小的内存块来存储元素,不要求内存是连续的,因此在首尾添加和删除元素的效率更高。
  • 操作效率

    • Vector 在尾部添加或删除元素的时间复杂度为O(1),但在头部添加或删除元素的时间复杂度为O(n)。
    • Deque 支持在头尾两端的快速插入和删除操作,时间复杂度为O(1)。
  • 适用场景

    • 使用 vector 的场景适合频繁的随机访问和尾部操作。
    • 使用 deque 的场景适合需要在两端进行插入或删除操作的场景。

4.2.4 STL里有sort函数,为什么list还要定义sort?

STL 中的 sort 函数是针对随机访问迭代器设计的,这意味着它要求底层容器(如 vectordeque)支持随机访问(通过索引访问元素)。但是 list 是一个双向链表,只支持双向迭代器,因此无法直接使用 sort

list 中定义的 sort 函数使用的是基于合并排序的算法,因为合并排序可以在链表中高效实现,且稳定。链表不适合随机访问,所以快速排序等算法在链表上不适用。

4.2.5 STL底层数据结构实现

STL 底层数据结构基于泛型编程,使用模板来实现一系列常用的数据结构和算法。STL 中常用的容器及其底层实现:

  • Vector:基于动态数组实现,支持随机访问。
  • List:基于双向链表实现,支持高效的插入和删除操作。
  • Deque:基于分段连续数组实现,适用于两端快速操作。
  • Map/Set:基于红黑树(平衡二叉搜索树)实现,支持快速的查找、插入和删除。
  • Unordered Map/Set:基于哈希表实现,支持均摊时间复杂度为O(1)的查找、插入和删除。

4.2.6 利用迭代器删除元素会发生什么?

在STL容器中使用迭代器删除元素时,可能会发生以下情况:

  • Vector/Deque:删除一个元素后,所有指向删除元素之后的迭代器都会失效(因为元素被移动,地址发生变化)。解决方案是使用 erase 函数,该函数会返回删除元素之后的有效迭代器。

  • List:删除一个元素后,只有指向被删除元素的迭代器会失效,其他迭代器仍然有效。可以安全地使用 erase 函数。

  • Map/Set:删除元素后,只有指向被删除元素的迭代器失效,其他迭代器不会失效。

4.2.7 Map的实现与查找效率

Map 是通过红黑树(平衡二叉搜索树)实现的,红黑树是一种自平衡二叉搜索树。它的查找、插入和删除操作的时间复杂度为O(log n)。

红黑树的特点:

  • 每个节点都是红色或黑色。
  • 根节点是黑色。
  • 叶节点(NIL节点)是黑色。
  • 红色节点的子节点必须是黑色(不能有两个红色节点相连)。
  • 从任一节点到其每个叶子节点的所有路径都包含相同数量的黑色节点。

4.2.8 几种模板插入的时间复杂度

  • Vector:在末尾插入元素的时间复杂度为O(1),在中间插入元素的时间复杂度为O(n)。
  • List:在任意位置插入元素的时间复杂度为O(1),前提是已知插入位置的迭代器。
  • Deque:在两端插入元素的时间复杂度为O(1),在中间插入元素的时间复杂度为O(n)。
  • Map/Set:插入元素的时间复杂度为O(log n)(红黑树的性质)。

这些时间复杂度使得不同的STL容器在不同的场景下各有优劣,因此选择合适的容器和算法是关键。

这篇关于嵌入式开发高频面试题——第四章 常见算法(下)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1142836

相关文章

python常见环境管理工具超全解析

《python常见环境管理工具超全解析》在Python开发中,管理多个项目及其依赖项通常是一个挑战,下面:本文主要介绍python常见环境管理工具的相关资料,文中通过代码介绍的非常详细,需要的朋友... 目录1. conda2. pip3. uvuv 工具自动创建和管理环境的特点4. setup.py5.

Python实例题之pygame开发打飞机游戏实例代码

《Python实例题之pygame开发打飞机游戏实例代码》对于python的学习者,能够写出一个飞机大战的程序代码,是不是感觉到非常的开心,:本文主要介绍Python实例题之pygame开发打飞机... 目录题目pygame-aircraft-game使用 Pygame 开发的打飞机游戏脚本代码解释初始化部

使用Python开发一个现代化屏幕取色器

《使用Python开发一个现代化屏幕取色器》在UI设计、网页开发等场景中,颜色拾取是高频需求,:本文主要介绍如何使用Python开发一个现代化屏幕取色器,有需要的小伙伴可以参考一下... 目录一、项目概述二、核心功能解析2.1 实时颜色追踪2.2 智能颜色显示三、效果展示四、实现步骤详解4.1 环境配置4.

java中long的一些常见用法

《java中long的一些常见用法》在Java中,long是一种基本数据类型,用于表示长整型数值,接下来通过本文给大家介绍java中long的一些常见用法,感兴趣的朋友一起看看吧... 在Java中,long是一种基本数据类型,用于表示长整型数值。它的取值范围比int更大,从-922337203685477

Python使用smtplib库开发一个邮件自动发送工具

《Python使用smtplib库开发一个邮件自动发送工具》在现代软件开发中,自动化邮件发送是一个非常实用的功能,无论是系统通知、营销邮件、还是日常工作报告,Python的smtplib库都能帮助我们... 目录代码实现与知识点解析1. 导入必要的库2. 配置邮件服务器参数3. 创建邮件发送类4. 实现邮件

详解Linux中常见环境变量的特点与设置

《详解Linux中常见环境变量的特点与设置》环境变量是操作系统和用户设置的一些动态键值对,为运行的程序提供配置信息,理解环境变量对于系统管理、软件开发都很重要,下面小编就为大家详细介绍一下吧... 目录前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变

Java中常见队列举例详解(非线程安全)

《Java中常见队列举例详解(非线程安全)》队列用于模拟队列这种数据结构,队列通常是指先进先出的容器,:本文主要介绍Java中常见队列(非线程安全)的相关资料,文中通过代码介绍的非常详细,需要的朋... 目录一.队列定义 二.常见接口 三.常见实现类3.1 ArrayDeque3.1.1 实现原理3.1.2

MyBatis设计SQL返回布尔值(Boolean)的常见方法

《MyBatis设计SQL返回布尔值(Boolean)的常见方法》这篇文章主要为大家详细介绍了MyBatis设计SQL返回布尔值(Boolean)的几种常见方法,文中的示例代码讲解详细,感兴趣的小伙伴... 目录方案一:使用COUNT查询存在性(推荐)方案二:条件表达式直接返回布尔方案三:存在性检查(EXI

Python struct.unpack() 用法及常见错误详解

《Pythonstruct.unpack()用法及常见错误详解》struct.unpack()是Python中用于将二进制数据(字节序列)解析为Python数据类型的函数,通常与struct.pa... 目录一、函数语法二、格式字符串详解三、使用示例示例 1:解析整数和浮点数示例 2:解析字符串示例 3:解

基于Python开发一个有趣的工作时长计算器

《基于Python开发一个有趣的工作时长计算器》随着远程办公和弹性工作制的兴起,个人及团队对于工作时长的准确统计需求日益增长,本文将使用Python和PyQt5打造一个工作时长计算器,感兴趣的小伙伴可... 目录概述功能介绍界面展示php软件使用步骤说明代码详解1.窗口初始化与布局2.工作时长计算核心逻辑3