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

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

相关文章

SQL BETWEEN 的常见用法小结

《SQLBETWEEN的常见用法小结》BETWEEN操作符是SQL中非常有用的工具,它允许你快速选取某个范围内的值,本文给大家介绍SQLBETWEEN的常见用法,感兴趣的朋友一起看看吧... 在SQL中,BETWEEN是一个操作符,用于选取介于两个值之间的数据。它包含这两个边界值。BETWEEN操作符常用

python中各种常见文件的读写操作与类型转换详细指南

《python中各种常见文件的读写操作与类型转换详细指南》这篇文章主要为大家详细介绍了python中各种常见文件(txt,xls,csv,sql,二进制文件)的读写操作与类型转换,感兴趣的小伙伴可以跟... 目录1.文件txt读写标准用法1.1写入文件1.2读取文件2. 二进制文件读取3. 大文件读取3.1

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

使用Python开发一个带EPUB转换功能的Markdown编辑器

《使用Python开发一个带EPUB转换功能的Markdown编辑器》Markdown因其简单易用和强大的格式支持,成为了写作者、开发者及内容创作者的首选格式,本文将通过Python开发一个Markd... 目录应用概览代码结构与核心组件1. 初始化与布局 (__init__)2. 工具栏 (setup_t

前端下载文件时如何后端返回的文件流一些常见方法

《前端下载文件时如何后端返回的文件流一些常见方法》:本文主要介绍前端下载文件时如何后端返回的文件流一些常见方法,包括使用Blob和URL.createObjectURL创建下载链接,以及处理带有C... 目录1. 使用 Blob 和 URL.createObjectURL 创建下载链接例子:使用 Blob

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

Spring Shell 命令行实现交互式Shell应用开发

《SpringShell命令行实现交互式Shell应用开发》本文主要介绍了SpringShell命令行实现交互式Shell应用开发,能够帮助开发者快速构建功能丰富的命令行应用程序,具有一定的参考价... 目录引言一、Spring Shell概述二、创建命令类三、命令参数处理四、命令分组与帮助系统五、自定义S

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》:本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve

Pytest多环境切换的常见方法介绍

《Pytest多环境切换的常见方法介绍》Pytest作为自动化测试的主力框架,如何实现本地、测试、预发、生产环境的灵活切换,本文总结了通过pytest框架实现自由环境切换的几种方法,大家可以根据需要进... 目录1.pytest-base-url2.hooks函数3.yml和fixture结论你是否也遇到过

Python通过模块化开发优化代码的技巧分享

《Python通过模块化开发优化代码的技巧分享》模块化开发就是把代码拆成一个个“零件”,该封装封装,该拆分拆分,下面小编就来和大家简单聊聊python如何用模块化开发进行代码优化吧... 目录什么是模块化开发如何拆分代码改进版:拆分成模块让模块更强大:使用 __init__.py你一定会遇到的问题模www.