一 List 核心字段和接口

1. 节点字段

template<class T>
struct __list_node
{typedef void* void_pointer;void_pointer prev;void_pointer next;T data;
}

由于 链表 不是连续的内存块，所以对每一个申请到的内存块要进行统一组织，也就是封装成一个类，添加前后指针来关联申请到的内存块，在由 List 统一管理起来。

2. List本身字段

template<class T.class Alloc=alloc>
class list
{protecred:// node 节点typedef __list_node<T> list_node;public:typedef list_node* link_type;ptotected:link_type node;// 这里没有按 T 来开辟空间，是按节点来开辟空间typedef simple_alloc<list_node,Alloc> list_node_allocator;    // 申请一个节点link_type get_node(){ return list_node_allocator::allocate(); }// 释放一个节点void put_node(link_type p){ list_node_allocator::deallocate(p); }// 申请并构造这个节点link_type create_node(const T& x){link_type p = get_node();construct(&p->data,x);        // 全局函数return p;    }// 析构并销毁这个节点void destroy_node(link_type p){destroy(&p->data);            // 全局函数put_node(p);}public:// 无参构造，初始化哨兵节点list(){ empty_initialize(); }protected:void empty_initialize(){node = get_node();node->next = node;node->prev = node;}
}

list的无参构造表示没有节点，但要有个哨兵节点，因为list是双向带头循环链表，为了处理边界情况，所以有一个领头羊。

那么怎么访问/遍历/修改 List 中的节点，一个个的访问吗？下面来看看 List 的迭代器。

由于 List 不像vector那样有一段连续的空间，所以不能直接用裸指针作为 List 的迭代器，但可以为这个指针封装一层，让他模拟指针的行为即可。

template <class T,class Ref,class Ptr>
struct __list_iterator
{// 非 const 迭代器，list操作时使用typedef __list_iterator<T,T&,T*> iterator;// const/非 const迭代器，迭代器内部使用typedef __list_iterator<T,Ref,Ptr> self;// 表示该迭代器是双向迭代器，前章vector的迭代器是随机访问迭代器typedef bidirectional_iterator_tag iterator_category;// 迭代器管理的节点内部 T 对象typedef T value_type;// 迭代器管理的节点内部 T 指针typedef Ptr pointer;// 迭代器管理的节点内部 T 引用typedef Ref reference;// 迭代器管理的节点指针typedef __list_node<T>* link_type;// 无符号整型typedef size_t size_type;// 有符号整型typedef ptrdiff_t difference_type;// node 指针link_type node;// 指针构造__list_iterator(link_type x):node(x){}// 无参构造__list_iterator(){}// 迭代器的拷贝构造，这里是浅拷贝__list_iterator(const iterator& x):node(x.node){}// 迭代器判相等bool operator==(const self& x)const {return node == x.node;}// 迭代器判不相等bool operator!=(const self& x)const {return node != x.node;}// 迭代器模拟指针访问 node 内部的 Treference operator*()const {return (*node).data;}    // 迭代器模拟指针访问 node 内部的 T 的地址reference operator->()const {return &(operator*());}// 前置++ ，返回下一个迭代器的引用self& operator++(){// 先访问 node 内部的 next，在把 next 强转成 node*，next 是 void* 类型node = (link_type)(*node).next;return *this;}//后置++，返回当前迭代器的拷贝self operator++(int){// 当前迭代器拷贝给临时对象self tmp = *this;// this 是指针，解引用成迭代器对象，然后进行 ++++*this;// 返回临时对象，值返回有拷贝return tmp;}// 下面2个--，和上面2个++一样 Self& operator--(){self tmp = *this;return *this}self operator--(int){self tmp = *this;--*this;return tmp;}};

list 内部对管理的 node 进行操作的函数：

template <class T,class Alloc = alloc>
class list
{public:// 返回第一个节点，并用这个节点构造一个迭代器iterator begin() { return (link_type)((*node).next); }// 返回最后一个节点，原理同上iterator end() { return node; }// 判空，和哨兵节点比较bool empty() const { return node->next == node; }// 这里调用了distance，针对迭代器类型进行计数，比如vector(end() - begin())，List就逐个遍历了size_type size() const{size_type result = 0;distance(begin(),end(),result);return result;}// 返回第一个迭代器内部的 T 对象的引用reference front() { return *begin(); }// 返回最后一个迭代器内部 T 对象的引用reference back() { return *(--end()); }// 头插void push_front(const T& x) { insert(begin(),x); }// 尾插void push_back(const T& x) { insert(end(),x); }// 头删void pop_front() { erase(begin()); }// 尾删，这里 end() 是哨兵节点，所以要--到前一个节点，也就是实际的最后一个节点// tmp 是浅拷贝的 end()void pop_back() {iterator tmp = end();erase(--tmp);}// 在 pos 位置前面插入 Tvoid insert(iterator position,const T& x){// 构造 node 节点link_type tmp = create_node(x);// 让这个新节点 next 指向 pos// 下面2个操作不需要强转，因为只需要改变指针的指向，并不访问指针内容tmp->next = position.node;// 让这个新节点 prev 指向 pos 的上一个节点(prev)tmp->prev = position.node->prev;// 这里需要访问指针的内容，让这样内容的 next 指向 tmp，所以要强转// 让 pos 的 prev 的 next 指向 tmp(link_type(position.node->prev))->next = tmp;// 让 pos 的 prev 指向 tmp，这里也不需要强转，不访问 prev，只是改变指向position.node->prev = tmp;return tmp;}// 删除指定迭代器，并返回迭代器的下一个迭代器iterator erase(iterator position){// 该迭代器的下一个迭代器link_type next_node = link_type(position.node->next);// 该迭代器的上一个迭代器link_type prev_node = link_type(position.node->prev);// 让该迭代器的上一个迭代器指向该迭代器的下一个迭代器prev_node->next = next_node;// 让该迭代器的下一个迭代器指向该迭代器的上一个迭代器next_node->prev = prev_node;// 释放该迭代器destroy_node(position.node);// 返回该迭代器的下一个迭代器return iterator(next_node);}// 清空节点，保留哨兵节点template<class T,class Alloc>void list<T,Alloc>::clear(){// cur = 哨兵节点的下一个link_type cur = (link_type)node->next;while(cur != node){// tmp 指向 cur 的 nodelink_type tmp = cur;// cur 访问 node 的 next，在强转 next 为 node*，这里 next 是 void* 类型cur = (link_type)cur->next;// 析构并释放destroy_node(tmp);}// 这里删除全部节点，没删除一个没有处理相互之间的链接关系，哨兵节点的指针是不可预期的// 所以要重置成初始状态node->next = node;node->prev = node;}// 删除所有的 T 对象template<class T,class Alloc>void list<T,Alloc>::remove(const T& value){// 取 List 的头iterator first = begin();// 取哨兵节点iterator last = end();while(first != last){// 这个地方删除用到了迭代器，不像 clear 直接操作 node iterator next = first;++next;相等就删除，并调整链接前后关系if(*first == value)erase(first);first = next;}}// 删除连续且相同的 T，不连续相同不删除template<class T,class Alloc>void list<T,Alloc>::unique(){// 和 remove 一样iterator first = begin();iterator last = end();// 空链表直接返回if(first == last) return;iterator next = first;while(++next != last){// 这里删除的是后一个 Tif(*first == *next) erase(next);// 不相等让前一个 T first 等于 后一个不相等的 T nextelse first = next;// 删完了，让后一个 T 也就是 next，等于前一个 T 也就是 firstnext = first;}}// 将 first ~ last 这个区间的迭代器移动到 pos 的前面，不包含 last// 该函数只能用于同一个 list 内部的迭代器进行操作，不同的list不行，即使模板参数一样void transfer(iterator position,iterator first,iterator last){// 尾和 pos 先等不需要移动，因为 first ~ last 已经在 pos 的前面了if(position != last){// 让 last 的上一个 node 的 next 指向 pos(*(link_type((*last.node).prev))).next = position.node;// 让 first 的上一个 node 的 next 指向 last(*(link_type((*first.node).prev))).next = last.node;// 让 pos 的上一个的 next 指向 first(*(link_type((*position.node).prev))).next = first.node;// tmp 指向 pos 的上一个 nodelink_type tmp = link_type((*position.node).prev);// 让 pos 的 prev 等于 last 的上一个 node(*position.node).prev = (*last.node).prev;// 让 last 的上prev 等于 first 的上一个 node(*last.node).prev = (*first.node).prev;// 让 first 的 prev 指向 tmp(*first.node).prev = tmp;// 让 5,6,7 插入到4的前面pos = 4,first = 5,last = 8[1,2,3,4,5,6,7,8] -> [1,2,3,5,6,7,4,8]第一步：让 last  的上一个 node      即7,指向4第二步：让 first 的上一个 node      即4，指向8第三步：让 pos   的上一个 node      即3，指向5第四步：让 tmp = pos 的上一个       即3第五步：让 pos   的 prev           即3，指向7第六步：让 last  的 prev           即7，指向3第七步：让 first 的 prev           即3，指向 tmp 4}}// STL源码刨析这本书里的 splice 都只能作用与同一个 list，不能跨 list// 主要是因为都调用了 transfer 接口，这个接口只是针对单个 list// 把一个 list 的所有节点挪到 该迭代器的前面void splice(iterator position,list&,iterator i){// 不为空直接调用if(!x.empty()) transfer(position,x.begin(),x.end());}// 把一个迭代器挪到 pos 前面void splice(iterator position,list&,iterator i){iterator j = i;++j;if(position ==i || position == j) return;transfer(position,i,j);}// 把一个迭代器区间挪到 pos 前面void splice(iterator position,list&,iterator first,iterator last){if(first != last) transfer(position,first,last);}// 合并2个有序的 listtemplate<class T,class Alloc>void merage(list<T,ALloc>& x){// 标记2个list的头和尾iterator first1 = begin();iterator last1 = end();iterator first2 = x.begin();iterator last2 = x.end();// 有一个为空则结束循环while(first1 != last1 && first2 != last2){// 如果第二个list的当前迭代器小于第一个list的当前迭代器if(*first2 < *first1){// 标记 first2iterator next = first2;// 把单个 first2 放到 first1 的前面transfer(first1,first2,++next);// 更新 first2first2 = next;}else ++first1;}// 如果 first2 的迭代器没有到结尾，则把剩余的元素挪到 first1 的前面// list1：1，2，3，4 list2：0，5，6，7，8// 上面的 while 循环把 0 挪到 1 的前面：list1 0，1，2，3，4// 然后 list1 的迭代器到结尾，4的后面// 此时 list2 的迭代器指向 5，在把 5 到 last2，也就是 list2 的结尾，5，6，7，8 挪到// last1(4 的后面),在用 transfer 函数把 5，6，7，8 挪到 last的前面，即 4 的后面if(first2 != last2) transfer(last1,first2,last2);}// 反转 list 所有节点void reverse(){// 如果为空或者只有一个节点，直接返回if(node->next == node || (link_type)(node->next)->next == node) return;// 保存下一个节点iterator first = begin();++first;// 下一个节点不等于 end()while(first != end()){// 保存下一个节点iterator old = frist;// 让 first + 到后面一个节点++first;// 在让 old ~ first 这个区间的节点移到 begin() 的前面// 其实只是移动一个节点,这里 first 是 old 的后面的节点，是开区间，不包括 first// 只是单纯的把 old 移到 begin() 前面transfer(begin(),old,first);}}void sort(){// 如果为空或者只有一个节点，直接返回if(node->next == node || (link_type)(node->next)->next == node) return;// 这个对象为后面交换合并做铺垫list<T,Alloc> carry;// 定义 64 个桶，每个桶是 2^n 次方个元素list<T,Alloc> counter[64];// 桶的最高层数int fill = 0;// 4 3 2 1while(!empty()){// 先取当前要排序对象的 第一个节点carry.splice(carry.begin(),*this,begin());// 该变量表示要合并的层数int i = 0;// 循环和合并while(i < fill && !counter[i].empty()){counter[i].merage(carry);carry.swap(counter[i++]);}// 合并之后的结果放到对应的桶里carry.swap(count[i]);// 如果合并的层数达到最高的层数,则让最高的层数++if(i == fill) ++fill;}// 从 1 开始 合并前面的 桶for(int i = i;i < fill;++i){counter[i].merge(counter[i-1]);}// 最后在交换回去swap(counter[fill - 1]);}
}

transfer：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/news/914101.shtml
繁体地址，请注明出处：http://hk.pswp.cn/news/914101.shtml
英文地址，请注明出处：http://en.pswp.cn/news/914101.shtml

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

相关文章

苹果App上架流程：不用Mac也可以上架的方法

苹果App上架流程：不用Mac也可以上架的方法

iOS App 的上架流程一直被认为是门槛最高、流程最繁琐的移动端工作之一。对很多使用 Windows 或 Linux 进行开发的跨平台团队来说&#xff0c;Mac 的缺位更放大了每一步的难度。 在我们近期为一款本地生活类 App 进行 iOS 上架时&#xff0c;团队成员几乎没有配备本地 Mac&…
阅读更多...
【爬虫】- 爬虫原理及其入门

【爬虫】- 爬虫原理及其入门

爬虫01 - 爬虫原理及其入门 文章目录爬虫01 - 爬虫原理及其入门一&#xff1a;爬虫原理1&#xff1a;爬虫的优势‌2&#xff1a;爬虫的核心库3&#xff1a;经典举例4&#xff1a;合规问题一&#xff1a;爬虫原理 学习爬虫之前前置知识需要了解这些&#xff1a; 我的HTTP介绍, 了…
阅读更多...
G5打卡——Pix2Pix算法

G5打卡——Pix2Pix算法

&#x1f368; 本文为&#x1f517;365天深度学习训练营中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 Pix2Pix 是一种基于条件生成对抗网络&#xff08;cGANs&#xff09;的图像到图像翻译算法&#xff0c;由 Phillip Isola 等人在 2016 年提出。该算法的核心思想…
阅读更多...
动力系统模拟与推导-AI云计算数值分析和代码验证

动力系统模拟与推导-AI云计算数值分析和代码验证

当系统是连续的&#xff0c;并且其状态变量不仅随时间变化&#xff0c;而且随空间维度变化时&#xff0c;需要使用偏微分方程&#xff08;PDEs&#xff09;来推导运动方程。偏微分方程提供了描述这些空间分布属性如何相互作用和演化的数学框架。 选择使用常微分方程&#xff08…
阅读更多...
P4597 序列 sequence题解

P4597 序列 sequence题解

P4597 序列 sequence 给定一个数列&#xff0c;每次操作可以使任意一个数1或-1&#xff0c;求小的操作次数&#xff0c;使得数列变成不降数列. 1.对于前面比当前位的数字大的数&#xff0c;设最大数为 xxx &#xff0c;当前的数为 yyy ,则对于 xxx 到 yyy 中间的任意数&#xf…
阅读更多...
雨污管网智慧监测系统网络建设方案：基于SD-WAN混合架构的最佳实践

雨污管网智慧监测系统网络建设方案：基于SD-WAN混合架构的最佳实践

随着城市化的快速推进&#xff0c;雨污管网的管理与运行面临着日益复杂的挑战&#xff0c;例如内涝、污水溢流、非法排污等问题频发。为了更高效地管理分布广泛的监测点&#xff0c;保障系统运行稳定性&#xff0c;构建一套高效、低成本、易运维的网络架构至关重要。本文将分享…
阅读更多...
世俱杯直播数据源通过反汇编获取到

世俱杯直播数据源通过反汇编获取到

在当今的互联网体育赛事直播中&#xff0c;许多平台为了保护其直播资源&#xff0c;会采用加密、混淆或动态加载等方式隐藏真实的视频流地址&#xff08;如 .m3u8 或 .flv&#xff09;。对于普通用户和开发者来说&#xff0c;直接通过网页源码或浏览器调试器难以快速定位这些关…
阅读更多...
字节豆包又一个新功能，超级实用，4 种玩法，你肯定用得上！（建议收藏）

字节豆包又一个新功能，超级实用，4 种玩法，你肯定用得上！（建议收藏）

前段时间&#xff0c;分享了一个非常好用的视频总结工具——百度网盘和百度文库联合推出的「AI 笔记」。它能自动根据视频内容&#xff0c;生成图文视频总结、表格总结、思维导图等。关键是带时间戳&#xff0c;能直接跳转到视频的位置。但这个功能隐藏在百度网盘里&#xff0c…
阅读更多...
AI进化论08：机器学习的崛起——数据和算法的“二人转”，AI“闷声发大财”

AI进化论08：机器学习的崛起——数据和算法的“二人转”，AI“闷声发大财”

上回咱们聊了第二次AI寒冬&#xff0c;AI为了“活下去”&#xff0c;不得不“改头换面”&#xff0c;从“AI”变成了“机器学习”。结果你猜怎么着&#xff1f;这“机器学习”啊&#xff0c;还真就“闷声发大财”了&#xff01;它不再执着于模拟人类的“思维过程”&#xff0c;…
阅读更多...
【MySQL】———— 索引

【MySQL】———— 索引

作者主页&#xff1a; 作者主页 本篇博客专栏&#xff1a;Linux 创作时间 &#xff1a;2025年7月11日 Mysql索引 索引介绍 索引是什么 根据官方对索引的介绍&#xff0c;索引是帮助MySQL高效的获取数据的数据结构&#xff0c;在我看来&#xff0c;索引就相当于一本书的目…
阅读更多...
页面html，当鼠标点击图标，移开图标，颜色方块消失

页面html，当鼠标点击图标，移开图标，颜色方块消失

html页面代码&#xff1a;<!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><title>颜色选择器</title><style>body {font-family: "Microsoft YaHei", sans-serif;padding: 20px;}.c…
阅读更多...
netdxf—— CAD c#二次开发之（netDxf 处理 DXF 文件）

netdxf—— CAD c#二次开发之（netDxf 处理 DXF 文件）

1.创建新项目打开 VS2022&#xff0c;选择 "创建新项目"搜索 "控制台应用"&#xff0c;选择 ".NET 6.0 (C#)" 模板&#xff0c;点击 "下一步"项目名称&#xff1a;"DxfProcessor"&#xff0c;位置&#xff1a;自选&#xff…
阅读更多...
如何将一个本地的jar包安装到 Maven 仓库中

如何将一个本地的jar包安装到 Maven 仓库中

我们需要执行以下步骤&#xff1a; 首先&#xff0c;打开命令提示符&#xff08;CMD&#xff09;或 PowerShell&#xff0c;执行以下命令&#xff1a; mvn install:install-file ^ -Dfile"你的jar包路径" ^ -DgroupId"组织ID" ^ -DartifactId"项目ID&…
阅读更多...
AI赋能的企业音频智能中枢：重构会议价值提升决策效率的数字化转型实践

AI赋能的企业音频智能中枢：重构会议价值提升决策效率的数字化转型实践

在当今快节奏的商业环境中&#xff0c;企业管理者每天都要处理海量信息&#xff0c;其中音频内容占据了重要位置。你是否经常遇到这样的困扰&#xff1a;重要会议结束后&#xff0c;录音文件静静躺在设备里&#xff0c;迟迟无法变成可用的会议纪要跨部门协作时&#xff0c;收到…
阅读更多...
医学+AI！湖北中医药大学信息工程学院与和鲸科技签约101数智领航计划

医学+AI！湖北中医药大学信息工程学院与和鲸科技签约101数智领航计划

为积极推动人工智能与中医药信息化深度融合&#xff0c;着力培育既精通中医药理论又掌握人工智能技术的复合型人才&#xff0c;6 月 27 日&#xff0c;湖北中医药大学信息工程学院与上海和今信息科技有限公司&#xff08;以下简称 “和鲸科技”&#xff09;召开校企合作座谈会&…
阅读更多...
全面掌控 Claude Code：命令 + 参数 + 快捷键一文全整理（建议收藏）

全面掌控 Claude Code：命令 + 参数 + 快捷键一文全整理（建议收藏）

近日&#xff0c;随着Cursor套餐定价的风波&#xff0c;Claude Code 无疑成为了最近颇受欢迎的代码助手&#xff0c;不仅支持多种编程语言&#xff0c;还比Cursor更能理解复杂的上下文逻辑&#xff0c;极受广大开发者的青睐。 不过&#xff0c;与其他AI编程助手不同的是&#x…
阅读更多...
深度学习-正则化

深度学习-正则化

摘要 本文系统阐述了深度学习中的正则化技术体系&#xff0c;围绕防止过拟合这一核心目标展开。首先通过偏差-方差框架解析过拟合/欠拟合本质&#xff0c;并使用对比表明确区分特征&#xff1b;其次深入分析了L1/L2正则化的数学原理&#xff08;2mλ​∥w∥2与mλ​∥w∥1​&a…
阅读更多...
STM32之风扇模块（开关控制+PWM调速）

STM32之风扇模块（开关控制+PWM调速）

目录 一、系统概述 二、5V直流风扇模块简介 2.1 基本概述 2.2 关键特性 2.3 接口定义 2.4 典型驱动电路 2.4.1 继电器驱动方案&#xff08;开关控制&#xff09; 2.4.2 三极管驱动方案&#xff08;调速控制&#xff09; 2.5 常见问题解决 三、继电器模块控制风…
阅读更多...
AGX Xavier 搭建360环视教程【二、环境配置】

AGX Xavier 搭建360环视教程【二、环境配置】

AGX Xavier 场景下的 【OpenCV FFmpeg CUDA GStreamer】 重装 & 编译的2025年稳定方案✅ 1️⃣ 先卸载老版本AGX 自带很多预装包&#xff0c;原则&#xff1a;卸载干净&#xff0c;避免旧库和新编译冲突。&#x1f539; 卸载 OpenCVdpkg -l | grep opencv sudo apt-get …
阅读更多...
Cesium实战：交互式多边形绘制与编辑功能完全指南（最终修复版）

Cesium实战：交互式多边形绘制与编辑功能完全指南（最终修复版）

&#x1f4cb; 文章目录 引言功能概述环境准备核心实现步骤 地图初始化多边形绘制顶点编辑功能颜色与透明度自定义面积计算与显示 常见问题解决方案 多边形颜色显示异常面积标签不可见控制台alpha类型错误地图交互无法恢复 完整代码总结与扩展 引言 Cesium作为一款强大的3D地…
阅读更多...
最新文章

Copyright @ 2022~2023