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

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开发Markdown表格结构转换为Excel工具

《利用Python开发Markdown表格结构转换为Excel工具》在数据管理和文档编写过程中,我们经常使用Markdown来记录表格数据,但它没有Excel使用方便,所以本文将使用Python编写一... 目录1.完整代码2. 项目概述3. 代码解析3.1 依赖库3.2 GUI 设计3.3 解析 Mark

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

java常见报错及解决方案总结

《java常见报错及解决方案总结》:本文主要介绍Java编程中常见错误类型及示例,包括语法错误、空指针异常、数组下标越界、类型转换异常、文件未找到异常、除以零异常、非法线程操作异常、方法未定义异常... 目录1. 语法错误 (Syntax Errors)示例 1:解决方案:2. 空指针异常 (NullPoi

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

基于Python开发批量提取Excel图片的小工具

《基于Python开发批量提取Excel图片的小工具》这篇文章主要为大家详细介绍了如何使用Python中的openpyxl库开发一个小工具,可以实现批量提取Excel图片,有需要的小伙伴可以参考一下... 目前有一个需求,就是批量读取当前目录下所有文件夹里的Excel文件,去获取出Excel文件中的图片,并

基于Python开发PDF转PNG的可视化工具

《基于Python开发PDF转PNG的可视化工具》在数字文档处理领域,PDF到图像格式的转换是常见需求,本文介绍如何利用Python的PyMuPDF库和Tkinter框架开发一个带图形界面的PDF转P... 目录一、引言二、功能特性三、技术架构1. 技术栈组成2. 系统架构javascript设计3.效果图

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

MySQL常见的存储引擎和区别说明

《MySQL常见的存储引擎和区别说明》MySQL支持多种存储引擎,如InnoDB、MyISAM、MEMORY、Archive、CSV和Blackhole,每种引擎有其特点和适用场景,选择存储引擎时需根... 目录mysql常见的存储引擎和区别说明1. InnoDB2. MyISAM3. MEMORY4. A

基于Python开发PDF转Doc格式小程序

《基于Python开发PDF转Doc格式小程序》这篇文章主要为大家详细介绍了如何基于Python开发PDF转Doc格式小程序,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 用python实现PDF转Doc格式小程序以下是一个使用Python实现PDF转DOC格式的GUI程序,采用T