C++的侵入式链表

news/2024/12/26 4:00:29 标签: c++, 链表, 开发语言

非侵入式链表

非侵入式链表是一种链表数据结构,其中每个元素(节点)并不需要自己包含指向前后节点的指针。链表的结构和节点的存储是分开的,链表容器会单独管理这些指针。

常见的非侵入式链表节点可以由以下所示,即,在链表节点中包含数据:

在这里插入图片描述

其中每个节点都形如:

struct Node {
    T data;
    Node* prev;
    Node* next;
};

STL标准库就使用的是非侵入式容器。

侵入式链表

侵入式链表是一种链表数据结构,其中每个元素(节点)本身就包含了指向前后节点的指针(prev 和 next)。也就是说,链表的结构是“侵入”到节点内部的,节点必须事先包含这些指针。

侵入式list与STL标准库中的list不同.STL标准库中的list容器将data与prev指针和next指针紧耦合,这就导致每向list中插入一个新元素就要涉及到内存的分配,这对于在堆上分配的内存而言是一种时间浪费。

侵入式链表与之相反,在业务数据结构中包含链表节点结构:

在这里插入图片描述

template <typename T>
struct IntrusiveListNode {
  IntrusiveListNode* prev;
  IntrusiveListNode* next;
  T* owner;
};

struct UserData {
  // ...
  InstruiveListNode list;
};

优点:

  • 更好的data locality:非侵入式结构std::list<T*>遍历过程中需要对T*解引用才能访问T内部数据,但侵入式结构的next和T内部的数据结构是放在一起的,无需额外解引用。
  • 更友好的API:拿到数据后就可以直接将这个节点从链表去除
  • 需要用户自己管理数据节点生命周期

应用举例:Linux源码的侵入式链表结构:

struct list_head {
  struct list_head *next, *prev;
};
//使用list_head的调度模块
struct task_group {
  // 省略一些业务逻辑
  struct list_head list;
};
/*
 * Default task group.
 * Every task in system belongs to this group at bootup.
 */
struct task_group root_task_group;
LIST_HEAD(task_groups);

list_add(&root_task_group.list, &task_groups);

参考链接

  1. https://hcoona.github.io/Data-Structure/instrusive-linked-list-summary/
  2. https://zhiqiang.org/coding/boost-intrusive-containers.html

http://www.niftyadmin.cn/n/5799769.html

相关文章

C语言的预处理器

C语言的预处理器是C语言编译器的一个组成部分&#xff0c;它在编译代码之前对源代码进行文本替换和条件编译等操作。预处理器指令以#字符开头&#xff0c;它们不是C语言的正式语法部分&#xff0c;但它们在代码生成过程中起着非常重要的作用。 C语言预处理器的功能 宏定义&am…

云手机与Temu矩阵:跨境电商运营新引擎

云手机与 Temu 矩阵结合的基础 云手机技术原理 云手机基于先进的 ARM 虚拟化技术&#xff0c;在服务器端运行 APP。通过在服务器上利用容器虚拟化软件技术&#xff0c;能够虚拟出多个独立的手机操作系统实例&#xff0c;每个实例等同于一部单独的手机&#xff0c;可独立运行各…

【Linux】虚拟机扩展磁盘

文章目录 1、扩展虚拟机磁盘2、扩展卷3、扩展文件系统磁盘存储知识扩展在 CentOS 上扩展磁盘空间并将其应用到根目录(/)的过程通常包括以下几个步骤: 1、扩展虚拟机磁盘 扩展前使用lsblk命令 sda 8:0 0 4G 0 disk ├─sda1 8:1 0 30…

【201】进销存管理系统

--基于springboot的图书进销存管理系统 本图书进销存管理系统管理员功能有: 个人中心&#xff0c;用户管理&#xff0c;图书类型管理&#xff0c;进货订单管理&#xff0c;商品退货管理&#xff0c;批销订单管理&#xff0c;图书信息管理&#xff0c;客户信息管理&#xff0c;供…

VMware虚拟机三种网络工作模式

vmware为我们提供了三种网络工作模式,它们分别是:Bridged(桥接模式)、NAT(网络地址转换模式)、Host-Only(仅主机模式)。 打开vmware虚拟机,我们可以在选项栏的“编辑”下的“虚拟网络编辑器”中看到VMnet0(桥接模式)、VMnet1(仅主机模式)、VMnet8(NAT模式),那…

WEB:如何在 Vue 中同步数据的技术指南

1、简述 在 Vue 应用中&#xff0c;数据同步是保持用户界面和数据状态一致的关键。当多个组件或页面共享同一个状态时&#xff0c;如何保证它们的同步更新变得尤为重要。本篇博客将介绍 Vue 中几种常见的数据同步技术&#xff0c;包括 v-model 双向绑定、事件总线、Vuex 状态管…

基于ISO 21434的汽车网络安全实践

商业领域的IT系统和嵌入式产品的IT系统正在融合为一种多功能系统。相应地&#xff0c;关注汽车网络安全的ISO 21434标准应运而生。该标准的意义在于提供了一个指南&#xff0c;可用于降低产品、项目和组织中存在的安全风险。为了有效实施ISO 21434标准&#xff0c;本文介绍了遵…

中职计算机网络技术理实一体化实训室建设方案

构建理实一体化教学模式对于改善中等职业学校计算机网络技术课程的教学现状、提升教学质量和效率具有重要意义。在中职教育不断深化改革的背景下&#xff0c;积极推进理实一体化教学模式的发展&#xff0c;不仅能够提高计算机网络技术课程的教学水平&#xff0c;满足教育改革的…