当前位置: 首页 > 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…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

纯 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、…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...