突破编程_C++_面试(STL 编程 list)

news/2024/5/25 11:06:36/文章来源:https://blog.csdn.net/h8062651/article/details/136510946

面试题 1 :描述 std::list 的内部数据结构是什么,以及它如何影响性能?

std::list 的内部数据结构是一个双向链表。这意味着它是由一系列节点组成的,每个节点都包含两部分:一部分是存储实际数据的数据域,另一部分是存储指向下一个和上一个节点的指针的指针域。

这种双向链表结构对 std::list 的性能有重要影响:

(1)插入和删除操作的高效性: 由于链表节点不是连续存储的,因此在链表中间插入或删除节点不需要移动其他节点。这使得 std::list 的插入和删除操作的时间复杂度为 O(1),即常数时间。无论链表的大小如何,这些操作的速度都是恒定的。

(2)不支持随机访问: 由于链表节点不是连续存储的,所以不能通过索引直接访问元素。这意味着你不能直接跳到链表的任意位置。要访问链表中的元素,必须从链表头或尾开始遍历,直到到达所需位置。这使得随机访问链表元素的效率较低。

(3)空间利用率较低: 每个链表节点都需要额外的空间来存储指向下一个和上一个节点的指针。这导致 std::list 的空间利用率比连续存储的容器(如 std::vector)低。然而,这种空间效率的牺牲换来的是插入和删除操作的高效性。

(4)内存分配和释放: 每次插入新节点时,都需要分配新的内存空间。同样,删除节点时会释放相应的内存。这种动态内存分配和释放可能会影响性能,尤其是在大量插入和删除操作的情况下。

总的来说,std::list 的双向链表结构使得它在插入和删除操作方面非常高效,但牺牲了随机访问和空间利用率。因此,在选择使用 std::list 还是其他容器时,需要根据具体的应用场景和需求来权衡这些性能特点。

面试题 2 :在 std::list 中,什么是插入和删除操作的时间复杂度?

在 std::list 中,插入和删除操作的时间复杂度都是 O(1),也就是常数时间复杂度。这是因为 std::list 是基于双向链表实现的,链表中的每个节点都包含指向前一个节点和后一个节点的指针。

对于插入操作:

如果在链表的头部或尾部插入元素,时间复杂度是 O(1),因为可以直接修改头指针或尾指针。
如果在链表的中间插入元素,例如在第 i 个位置插入一个新元素,时间复杂度同样是 O(1)。这是因为只需更改相邻节点的指针,将新节点插入到链表中,而无需移动其他元素。

对于删除操作:

删除链表的头部或尾部元素同样具有 O(1) 的时间复杂度,因为可以直接修改头指针或尾指针。
删除链表中间的元素,如第 i 个元素,时间复杂度也是 O(1)。这是因为你只需找到要删除元素的前一个节点,然后更改其指针以跳过要删除的元素,并可能还需要更改要删除元素的后一个节点的指针。这些操作都是常数时间内的。

需要注意的是,虽然插入和删除操作的时间复杂度是 O(1),但如果要在特定位置插入或删除多个元素,总的时间复杂度将是 O(n),其中 n 是要插入或删除的元素数量。然而,每个单独的操作仍然是 O(1)。

面试题 3 :如何在 std::list 中进行元素的查找?

在 C++ 的 std::list 中查找元素,可以使用 std::find 函数,这个函数在<algorithm>头文件中定义。std::find 函数会遍历列表,直到找到匹配的元素或者到达列表的末尾。

以下是一个简单的示例,展示如何在std::list中查找元素:

#include <iostream>  
#include <list>  
#include <algorithm>  int main() 
{std::list<int> my_list = { 1, 2, 3, 4, 5 };// 查找元素  int value_to_find = 3;auto it = std::find(my_list.begin(), my_list.end(), value_to_find);// 检查是否找到了元素  if (it != my_list.end()) {std::cout << "Found element " << value_to_find << " at position " << std::distance(my_list.begin(), it) << std::endl;}else {std::cout << "Element not found in the list " << value_to_find << std::endl;}return 0;
}

上面代码的输出为:

Found element 3 at position 2

std::find函数是线性搜索,也就是说,在最坏的情况下,它可能需要遍历整个列表。因此,对于大型列表,可能需要考虑使用其他数据结构(如 std::set 或 std::unordered_set),这些数据结构提供了更快的查找速度。

面试题 4 :如何在 std::list 的开始、中间和末尾插入元素?

在 std::list 中插入元素有几种方法,这取决于你想在列表的哪个位置插入元素。以下是如何在 std::list 的开始、中间和末尾插入元素的方法:

在列表的开始插入元素
可以使用 std::list 的 push_front 成员函数来在列表的开始插入元素。

#include <iostream>  
#include <list>  int main() 
{std::list<int> my_list;// 在列表的开始插入元素  my_list.push_front(1);my_list.push_front(2);// 打印列表  for (int num : my_list) {std::cout << num << ' ';}std::cout << std::endl;return 0;
}

在列表的中间插入元素
要在列表的中间插入元素,可以使用 insert 成员函数,并传递一个迭代器,该迭代器指向你想要插入新元素的位置。

#include <iostream>  
#include <list>  int main() 
{  std::list<int> my_list = {1, 2, 4, 5};  // 在列表的中间插入元素  auto it = my_list.begin();  std::advance(it, 2); // 移动到第三个元素之前  my_list.insert(it, 3); // 在第三个元素之前插入 3  // 打印列表  for (int num : my_list) {  std::cout << num << ' ';  }  std::cout << std::endl;  return 0;  
}

在列表的末尾插入元素
可以使用 push_back 成员函数来在列表的末尾插入元素。

#include <iostream>  
#include <list>  int main() 
{  std::list<int> my_list = {1, 2, 3};  // 在列表的末尾插入元素  my_list.push_back(4);  my_list.push_back(5);  // 打印列表  for (int num : my_list) {  std::cout << num << ' ';  }  std::cout << std::endl;  return 0;  
}

在所有情况下,插入操作在 std::list 中都是非常高效的,因为 std::list 是一个双向链表,它可以在常数时间内完成在列表开始和末尾的插入操作,以及在已知位置的中间插入操作。

面试题 5 :std::list 和 std::vector 在性能上有哪些主要的区别?

std::list 和 std::vector 在C++ STL中都是常用的序列式容器,但它们在性能上有一些主要的区别,这些区别主要源于它们内部实现的不同。

随机访问性能:
std::vector:由于其内部使用数组实现,元素存储在连续的内存空间中,因此随机访问其任何元素的时间复杂度是 O(1),即常数时间。这使得std::vector在需要频繁随机访问元素时表现出色。
std::list:由于元素是分散在内存中的,不能利用指针进行随机访问,只能顺序访问。这意味着访问列表中的特定元素(除头尾节点外)需要遍历整个列表,时间复杂度为 O(n),其中 n 是列表中元素的数量。因此,std::list 在随机访问方面性能较差。

插入和删除性能:
std::vector:在向量中间插入或删除元素会导致元素移动,因为需要保持元素的连续性。这通常是一个 O(n) 的操作,因为它可能涉及大量的内存拷贝。然而,在向量末尾添加元素(使用 push_back)通常是 O(1) 操作,因为向量通常会在内部预留一些额外的空间。
std::list:由于链表结构,std::list 在任意位置插入或删除元素都是 O(1) 的操作,因为不需要移动其他元素。这使得std::list在需要频繁插入或删除元素的场景下性能更佳。

空间利用率:
std::vector:由于其内部实现为连续数组,空间利用率通常较高,因为内存分配是连续的,不容易产生内存碎片。
std::list:链表中的每个节点可能单独分配,这可能导致内存碎片,特别是在频繁插入和删除操作时。

内存分配:
std::vector:一次性分配好内存,当空间不足时才进行 2 倍扩容,这可能会导致额外的内存分配和拷贝成本。
std::list:每次插入新节点时都会进行内存申请,每次删除节点时都会释放内存,这可能导致更多的内存分配和释放操作。

迭代器:
std::vector:迭代器是原生态的指针,可以直接进行指针算术运算。
std::list:迭代器是对原生态指针进行了封装,不能直接进行指针算术运算。

综上所述,std::vector 在随机访问和连续存储方面性能较好,适用于需要高效随机访问的场景;而 std::list 在插入和删除操作方面性能更佳,适用于需要频繁插入和删除的场景。在选择使用哪种容器时,应根据具体的应用需求和性能要求来决定。

面试题 6 :std::list 和 std::forward_list 有什么不同?

std::list 和 std::forward_list 是 C++ 标准库中两种不同类型的链表容器,它们之间存在一些关键的不同点。

内存布局和存储:
std::list:是一个双向链表,每个节点都包含指向前一个节点和后一个节点的指针。因此,其内存布局相对较大,每个节点都需要额外的空间来存储这些指针。
std::forward_list:是一个单向链表,每个节点只包含指向下一个节点的指针。因此,它的内存布局更紧凑,占用更少的内存。

插入和删除效率:
std::list:由于每个节点都有指向前一个和后一个节点的指针,插入和删除操作可能涉及修改多个指针,因此在某些情况下可能相对较慢。
std::forward_list:由于它只包含指向下一个节点的指针,插入和删除操作通常更高效,因为只需要修改一个指针。

随机访问:
std::list:不支持随机访问,只能通过迭代器顺序访问元素。
std::forward_list:同样不支持随机访问,只能通过迭代器从头部开始顺序访问元素。

接口和用法:
std::list:提供了丰富的接口,包括成员函数和操作符重载,用于执行各种操作,如排序、合并等。
std::forward_list:接口相对有限,主要关注基本的链表操作,如插入、删除和遍历。它被视为对 C 语言风格单链表的封装,并提供了 O(1) 复杂度的元素插入。

空间利用率:
当不需要双向迭代时,std::forward_list 通常具有比 std::list 更高的空间利用率,因为它不需要存储指向前一个节点的指针。

综上所述,std::list 和 std::forward_list 在内存布局、插入和删除效率、随机访问、接口和用法以及空间利用率等方面存在显著差异。在选择使用哪种链表容器时,应根据具体的应用需求和性能要求来决定。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1005906.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

12 list的使用

文档介绍 文档介绍 1.list是可以在常数范围内的任意位置进行插入和删除的序列式容器&#xff0c;并且该容器可以前后双向迭代 2.list的底层是带头双向链表循环结构&#xff0c;双向链表中每个元素存储在互不相关的独立节点中&#xff0c;在节点中通过指针指向其前一个元素和…

罐头鱼AI短视频矩阵获客|AI视频批量生成

罐头鱼AI传单功能操作说明&#xff0c;智能化提升您的视频营销效率&#xff01; 在这个信息爆炸的时代&#xff0c;短视频已成为企业营销的重要方式之一。而为了更高效地进行视频营销&#xff0c;罐头鱼AI传单功能应运而生&#xff0c;为您提供全方位的视频管理和发布服务。 首…

7、设计模式之桥接模式(Bridge)

一、什么是桥接模式 桥接模式是一种结构型设计模式。它将抽象部分和实现部分分离&#xff0c;使它们可以独立地变化。 二、角色组成 抽象部分&#xff08;Abstraction&#xff09;&#xff1a;定义了抽象部分的接口&#xff0c;并包含对实现部分的引用。 实现部分&#xff08;…

WordPress建站入门教程:如何创建菜单和设置前端导航菜单?

前面我们跟大家分享了WordPress如何上传安装WordPress主题&#xff0c;但是启用主题后前端没有看到有导航菜单&#xff0c;这是因为我们还没有创建菜单和设置导航菜单。 JianYue主题导航菜单和右上角菜单 今天boke112百科就继续跟大家分享WordPress站点如何创建菜单和设置前端…

day36 贪心算法part5

435. 无重叠区间 中等 给定一个区间的集合 intervals &#xff0c;其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量&#xff0c;使剩余区间互不重叠 。 气球问题稍加改动就可ac 一个交叉区间里&#xff0c;最终只能保留一个&#xff0c;其他的全部要去掉。…

欧科云链:角力Web3.0,香港如何为合规设线?

在香港拥抱Web3.0的过程中,以欧科云链为代表的合规科技企业将凸显更大重要性。 ——据香港商报网报道 据香港明报、商报等媒体报道&#xff0c;港区全国政协兼香港选委界立法会议员吴杰庄在日前召开的全国两会上提出在大湾区建设国际中小企业创新Web3融资平台等提案&#xff0…

Solidity攻击合约:重入攻击与危害分析

以太坊智能合约开发中&#xff0c;重入攻击是一种常见的安全漏洞。这种攻击通常发生在合约的递归调用中&#xff0c;攻击者通过构造恶意交易&#xff0c;使得原本合约在执行过程中不断调用自身或其他合约&#xff0c;从而耗尽合约的Gas&#xff08;交易费用&#xff09;&#x…

STM32(18)I2C

串口通信缺点 一个设备就需要一个串口&#xff0c;单片机可能没有那么多串口外设 总线/非总线 主机&#xff1a;负责管理总线&#xff0c;可控制波特率、数据的通信方向 波特率&#xff1a;由主机产生波特率信号 数据的传输 每个从机都有7位地址&#xff0c;最后移位是读&a…

django学习记录07——订单案例(复选框+ajax请求)

1.订单的数据表 1.1 数据表结构 1.2 数据表的创建 models.py class Order(models.Model):"""订单号"""oid models.CharField(max_length64, verbose_name"订单号")title models.CharField(max_length64, verbose_name"名称&…

Hack The Box-Codify

目录 信息收集 rustscan nmap dirsearch WEB 提权 get user get root 信息收集 rustscan ┌──(root㉿ru)-[~/kali/hackthebox] └─# rustscan -b 2250 10.10.11.239 --range0-65535 --ulimit4500 -- -A -sC .----. .-. .-. .----..---. .----. .---. .--. .-. …

Long-term Correlation Tracking LCT 目标跟踪算法源码运行

资源 LCT-tracker项目地址VLFeat官网OpenCV下载地址OTB50数据集百度网盘资源 参考博客 一步一步教你跑lct-tracker&#xff08;Win10Matlab 2016bVisual Studio 2015&#xff09;LCT代码跑起来先文章思路总结 正文 1. 环境配置 我的环境&#xff1a;Win11、Visual Studio…

LF253DT运算放大器芯片中文资料规格书PDF数据手册引脚图图片参数价格功能

产品概述&#xff1a; 这些电路是高速JFET输入双运算放大器&#xff0c;在单片集成电路中集成了匹配良好的高压JFET和双极晶体管。 这些器件具有高转换速率、低输入偏置和失调电流以及低失调电压温度系数。 产品功能&#xff1a; 无闩锁操作内部频率补偿低功耗低输入偏置和…

JS数组相关知识

获取数组的最大值/最小值&#xff1a; let arrary [2,5,4] let max arrary[0] for(let i 0;i<arrary.length;i){if(arrary[i]>max){max arrary[i]} }console.log(max);//查询数组最小值let arr [2,21,34,23,45] let min arr[0] for(let i 0;i<arr.length;i){if…

24考研调剂 | 武汉纺织大学

教育部重点实验室招收24年调剂生&#xff0c;材料、化学、机械工程、计算机、力学等相关专业 考研调剂招生信息 学校:武汉纺织大学 专业:工学->材料科学与工程 年级:2024 招生人数:100 招生状态:正在招生中 联系方式:********* (为保护个人隐私,联系方式仅限APP查看)…

JavaEE:网络编程

网络编程&#xff1a;通过代码完成基于网络的跨主机通信 跨主机通信方式&#xff1a; 1.TCP/IP网络 2.蓝牙通信 3.近场通信NFC 4.毫米波通信&#xff1a;功率高&#xff0c;带宽高&#xff0c;抗干扰能力差 其中TCP/IP网络是日常编程中最常涉及到的&#xff0c;最通用的跨主机通…

吴恩达机器学习-可选实验:使用ScikitLearn进行线性回归(Linear Regression using Scikit-Learn)

文章目录 实验一目标工具梯度下降加载数据集缩放/规范化训练数据创建并拟合回归模型查看参数作出预测绘制结果 恭喜 实验二目标工具线性回归&#xff0c;闭式解加载数据集创建并拟合模型查看参数作出预测 第二个例子恭喜 有一个开源的、商业上可用的机器学习工具包&#xff0c;…

day42 动态规划part4

先遍历物品还是先遍历背包二刷再考虑吧。累了&#xff0c;不想停留太久。 背包问题 二维 &#xff08;卡码网题目&#xff09; 各种解释&#xff1a; 要理解的是这个表格每一个格子都是当前所处情况的最大价值&#xff0c;我们用已经推导出的最大价值来推导当前情况的最大价值…

用chatgpt写论文重复率高吗?如何降低重复率?

ChatGPT写的论文重复率很低 ChatGPT写作是基于已有的语料库和文献进行训练的&#xff0c;因此在写作过程中会不可避免地引用或借鉴已有的研究成果和观点。同时&#xff0c;由于ChatGPT的表述方式和写作风格与人类存在一定的差异&#xff0c;也可能会导致论文与其他文章相似度高…

LiveGBS流媒体服务器中海康摄像头GB28181公网语音对讲、语音喊话的配置

LiveGBS海康摄像头国标语音对讲大华摄像头国标语音对讲GB28181语音对讲需要的设备及服务准备 1、背景2、准备2.1、服务端必备条件&#xff08;注意&#xff09;2.2、准备语音对讲设备2.2.1、不支持跨网对讲示例2.2.2、 支持跨网对讲示例 3、开启音频开始对讲4、搭建GB28181视频…

Linux学习笔记(一)Linux基本指令

文章目录 前言目录常见命令1. pwd 打印当前所在路径2. cd 改变路径、切换路径3. 家目录 回到顶级目录4. 当前路径和上一路径5. 上一次路径6. 绝对路径和相对路径7. ls 列出目录内容8. mkdir 创建目录9. rmdir 删除目录10. touch 创建文件11. mv 修改文件目录、移动路径12. cp 复…