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

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

QT3D学习笔记——圆台、圆锥

类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体&#xff08;对象或容器&#xff09;QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质&#xff08;定义颜色、反光等&#xff09;QFirstPersonC…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...

Ubuntu系统多网卡多相机IP设置方法

目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机&#xff0c;交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息&#xff0c;系统版本&#xff1a;Ubuntu22.04.5 LTS&#xff1b;内核版本…...