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

ops/2025/1/15 21:58:05/

目录

      • 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.ppmy.cn/ops/107683.html

相关文章

最佳实践-模板设计模式

目录 一、什么是设计模式 二、模板设计模式-介绍 三、模板设计模式-最佳实践 1、开发需求 2、使用传统的方法来解决 3、优化-使用模板设计模式来解决 一、什么是设计模式 1)设计模式是在大量的实践中总结和理论化之后优选的代码结构、编程风格、以及解决问题…

基于tesseract实现文档OCR识别

导入环境 导入必要的库 numpy: 用于处理数值计算。 argparse: 用于处理命令行参数。 cv2: OpenCV库,用于图像处理。 import numpy as np import argparse import cv2设置命令行参数 ap argparse.ArgumentParser() ap.add_argument("-i", "--imag…

nano 和 vim对比

nano 和 vim 是两种流行的文本编辑器,各有优缺点和适用场景。以下是对这两种编辑器的详细对比: Nano 优点: 1.简单易用:nano 的界面和命令非常简单,易于新手上手。所有的命令都列在屏幕底部,不需要记住复…

流媒体技术革新,EasyCVR视频汇聚平台赋能视频监控全面升级

随着科技的飞速发展,流媒体技术和视频监控正经历着前所未有的变革与融合。本文将从流媒体技术的新兴趋势出发,探讨其与视频监控领域的深度结合,以及这一融合所带来的创新与发展。 一、流媒体技术的新兴趋势 1、5G网络的广泛应用 5G网络以其…

js(vue)如何实现页面截图,向后端传递,生成PDF

利用 htmm12canvas 首先引入 npm install express multer # 或者 yarn add express multer 代码如下&#xff1a; <template><!-- <div style"width:100%;height:100%;overflow-y: scroll"><img :src"svg" style"width: 100%;&…

C++笔记---vector

1. vector的介绍 vector其实就是我们所熟知的顺序表&#xff0c;但其是作为STL中的一个类模板而存在。 也就是说&#xff0c;vector是可以用来存储任意类型数据的顺序表&#xff0c;既可以是内置类型&#xff0c;也可以是自定义类型&#xff0c;或是STL中的其他容器。 vecto…

npm login 或者 npm publish 超时timeout

场景&#xff1a;空闲时间想自己尝试下npm发布包&#xff0c;毕竟这东西可以不用&#xff0c;但不能不会 步骤很简单 1.npm login 2.npm publish 这里有个坑。。。因为想发布到npm上&#xff0c;所以这里的镜像源要换回https://registry.npmjs.org&#xff0c;不能使用淘宝镜像…

算法入门-深度优先搜索2

第六部分&#xff1a;深度优先搜索 104.二叉树的最大深度&#xff08;简单&#xff09; 题目&#xff1a;给定一个二叉树 root &#xff0c;返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1&#xff1a; 输入&#xff1a;ro…