当前位置: 首页 > news >正文

STL序列式容器之list

相较于vector的连续性空间,list相对比较复杂;list内部使用了双向环形链表的方式对数据进行存储;list在增加元素时,采用了精准的方式分配一片空间对数据及附加指针等信息进行存储;

list节点定义如下

template<class T>
struct __list_node{__list_node<T>* pre;   // 此处采用了书中建议的写法;与实际定义略有差异__list_node<T>* next;T data;
};

因为list存储节点不是T,所以其迭代器不能使用T*,所以定义了其迭代器

template<class T, class Ref, class Ptr>
struct __list_iterator {// ...typedef __list_node<T> * link_type;// ...link_type node;// ...
};

__list_iterator迭代器的操作符*,->操作符比较明显为:node->data, &node->data;

对于操作符++,和--,分别对应于node=node->next,及node=node->pre;

list采用双向环形链表,list成员只包含一个节点node;

template <class T, class Alloc = alloc>
class list {protected:typedef __list_node<T> list_node;public :typedef list_node* link_type;protected:link_type node;...
};

因为是环形结构,node本身即为list的end,node->next即为list的起始节点;

iterator begin() {return node->next;}
iterator end()   {return node;}
bool empty() const {return node->next == node;}
reference front() {return *begin();}
reference back() {return *(end()--);}

list的insert操作比较简明:

iterator insert(iterator position, const T&x) {link_type tmp = create_node(x);tmp->next = position.node;tmp->pre  = position.node->pre;position.node->pre->next = tmp;position.node->pre = tmp;return tmp;    }

指针插入前后指向情况如下

​​​​​​​

此外,lsit还提供了splice及merge操作,splice用于拼接,merge是两个有序list的合并,看上去很适合归并排序当中的合并操作;

此外在书中,提到了sort函数,用的快排的代码,用到了swap及merge,没能理解,(可能是前面漏掉了部分函数的定义,没有理解算法的含义;等看到了后再补充这块的学习内容)

参考文档《STL源码剖析--侯捷》

相关文章:

STL序列式容器之list

相较于vector的连续性空间&#xff0c;list相对比较复杂&#xff1b;list内部使用了双向环形链表的方式对数据进行存储&#xff1b;list在增加元素时&#xff0c;采用了精准的方式分配一片空间对数据及附加指针等信息进行存储&#xff1b; list节点定义如下 template<clas…...

docker:基于Dockerfile镜像制作完整案例

目录 摘要目录结构介绍起始目录package目录target目录sh目录init.sh脚本start.sh脚本stop.sh脚本restart.sh脚本 config目录 步骤1、编写dockerfilescript.sh脚本 2、构件镜像查看镜像 3、保存镜像到本地服务器4、复制镜像文件到指定目录&#xff0c;并执行init.sh脚本5、查看挂…...

微信小程序自定义顶部导航栏(适配各种机型)

效果图 1.pages.js&#xff0c;需要自定义导航栏的页面设置"navigationStyle": "custom" 2.App.vue,获取设备高度及胶囊位置 onLaunch: function () {// 系统信息const systemInfo uni.getSystemInfoSync()// 胶囊按钮位置信息const menuButtonInfo uni.…...

sslSocketFactory not supported on JDK 9+

clientBuilder.sslSocketFactory(SSLSocketFactory) not supported on JDK 9 at okhttp3.internal.platform.Jdk9Platform.trustManager(Jdk9Platform.kt:61) at okhttp3.OkHttpClient$Builder.sslSocketFactory(OkHttpClient.kt:751) at 1.升版本4.9.3以上 2、加个函数获取X…...

[Codesys]常用功能块应用分享-BMOV功能块功能介绍及其使用实例说明

官方说明 功能说明 参数 类型 功能 pbyDataSrcPOINTER TO BYTE指向源数组指针uiSizeUINT要移动数据的BYTE数pbyDataDesPOINTER TO BYTE指向目标数组指针 实例应用-ST IF SYSTEM_CLOCK.AlwaysTrue THENCASE iAutoState OF0: //读写完成信号在下次读写信号的上升沿或复位信号…...

大语言模型通用能力排行榜(2024年11月8日更新)

数据来源SuperCLUE 榜单数据为通用能力排行榜 排名 模型名称 机构 总分 理科 文科 Hard 使用方式 发布日期 - o1-preview OpenAI 75.85 86.07 76.6 64.89 API 2024年11月8日 - Claude 3.5 Sonnet&#xff08;20241022&#xff09; Anthropic 70.88 82.4…...

信息技术引领未来:大数据治理的实践与挑战

信息技术引领未来&#xff1a;大数据治理的实践与挑战 在信息技术日新月异的今天&#xff0c;大数据已成为企业和社会发展的重要驱动力。大数据治理&#xff0c;作为确保数据质量、安全性和合规性的关键环节&#xff0c;正面临着前所未有的实践挑战与机遇。本文将探讨信息技术…...

Git 分⽀规范 Git Flow 模型

前言 GitFlow 是一种流行的 Git 分支管理策略&#xff0c;由 Vincent Driessen 在 2010 年提出。它提供了一种结构化的方法来管理项目的开发、发布和维护&#xff0c;特别适合大型和复杂的项目。GitFlow 定义了一套明确的分支模型和工作流程&#xff0c;使得团队成员可以更有效…...

基于YOLOv8深度学习的公共卫生防护口罩佩戴检测系统(PyQt5界面+数据集+训练代码)

在全球公共卫生事件频发的背景下&#xff0c;防护口罩佩戴检测成为保障公众健康和控制病毒传播的重要手段之一。特别是在人员密集的公共场所&#xff0c;例如医院、学校、公共交通工具等地&#xff0c;口罩的正确佩戴对降低病毒传播风险、保护易感人群、遏制疫情扩散有着至关重…...

Nature Communications 基于触觉手套的深度学习驱动视触觉动态重建方案

在人形机器人操作领域&#xff0c;有一个极具价值的问题&#xff1a;鉴于操作数据在人形操作技能学习中的重要性&#xff0c;如何有效地从现实世界中获取操作数据的完整状态&#xff1f;如果可以&#xff0c;那考虑到人类庞大规模的人口和进行复杂操作的简单直观性与可扩展性&a…...

构建SSH僵尸网络

import argparse import paramiko# 定义一个名为Client的类&#xff0c;用于表示SSH客户端相关操作 class Client:# 类的初始化方法&#xff0c;接收主机地址、用户名和密码作为参数def __init__(self, host, user, password):self.host hostself.user userself.password pa…...

WPF中MVVM工具包 CommunityToolkit.Mvvm

CommunityToolkit.Mvvm&#xff0c;也称为MVVM工具包&#xff0c;是Microsoft Community Toolkit的一部分。它是一个轻量级但功能强大的MVVM&#xff08;Model-View-ViewModel&#xff09;库&#xff0c;旨在帮助开发者更容易地实现MVVM设计模式。 特点 独立于平台和运行时&a…...

学习空闲任务函数

一、user_StopEnterTask 停止 进入任务 /* Private includes -----------------------------------------------------------*/ //includes #include "user_TasksInit.h" #include "user_MPUCheckTask.h"#include "ui.h" #include "ui_Hom…...

Hyper-v中ubuntu与windows文件共享

Hyper-v中ubuntu与windows文件共享 前言相关链接第一步--第一个链接第二步--第二个链接测试与验证 前言 关于Hyper-V的共享我搞了好久&#xff0c;网上的很多教程太过冗余&#xff0c;我直接采用最简单的办法吧 相关链接 Hyper-V中Ubuntu 同windows系统共享文件夹-百度经验 …...

【软件工程】一篇入门UML建模图(类图)

&#x1f308; 个人主页&#xff1a;十二月的猫-CSDN博客 &#x1f525; 系列专栏&#xff1a; &#x1f3c0;软件开发必练内功_十二月的猫的博客-CSDN博客 &#x1f4aa;&#x1f3fb; 十二月的寒冬阻挡不了春天的脚步&#xff0c;十二点的黑夜遮蔽不住黎明的曙光 目录 1. 前…...

Windows 安装Docker For Desktop概要

Windows 安装docker 下载部分的工作需要使用科学技术。如果没有可以联系博主发送已下载好的文件。 本文档不涉及技术的讲解&#xff0c;仅有安装的步骤。 准备工作 包含下载与环境准备&#xff0c;下载的文件仅下载&#xff0c;在后续步骤进行安装。 微软关于wsl的文档&…...

解决循环依赖报错问题

Caused by: org.springframework.beans.factory.BeanCurrentlyInCreationException: Error creating bean with name ‘asyncTaskServiceImpl’: Bean with name ‘asyncTaskServiceImpl’ has been injected into other beans [resignServiceImpl] in its raw version as part…...

代码随想录第46期 单调栈

这道题主要是单调栈的简单应用 class Solution { public:vector<int> dailyTemperatures(vector<int>& T) {vector<int> result(T.size(),0);stack<int> st;st.push(0);for(int i1;i<T.size();i){if(T[i]<T[st.top()]){st.push(i);}else{wh…...

中仕公考怎么样?事业编面试不去有影响吗?

事业编考试笔试已经通过&#xff0c;但是面试不去参加会有影响吗&#xff1f; 1. 自动放弃面试资格&#xff1a;未能按时出席事业单位的面试将被视为主动放弃该岗位的竞争机会。 2. 个人信誉问题&#xff1a;面试作为招聘流程的关键步骤&#xff0c;无故缺席可能被解释为诚信…...

OMV7 树莓派 tf卡安装

​ 升级7之后&#xff0c;问题多多&#xff0c;不是docker不行了&#xff0c;就是代理不好使 今天又重装了一遍&#xff0c;用官方的链接&#xff0c;重新再折腾一遍…… 使用raspberry pi imager安装最新版lite OS。 注意是无桌面 Lite版 配置好树莓派初始化设置&#xff0…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...