C++初阶：STL容器list的使用与初版自实现

目录

  • 1. list的接口与使用
    • 1.1 默认成员函数
    • 1.2 迭代器与容量相关成员函数
    • 1.3 存储数据操作相关成员函数
    • 1.4 其他list操作成员函数
  • 2. list的自实现
    • 2.1 list的自实现功能
    • 2.2 list的结点结构
    • 2.3 list的迭代器
    • 2.3 list的结构
    • 2.4 list迭代器的运算符重载
    • 2.5 list的成员函数
  • 3. const迭代器，operator->运算符重载与模板参数的应用
    • 3.1 const迭代器
    • 3.2 迭代器的operator->运算符重载

1. list的接口与使用

  1. list对标的是数据结构中的双向带头循环链表

1.1 默认成员函数

构造与拷贝构造

//无参构造
list<int> l1;
//指定个数值构造
list<int> l2(3, 100);
//迭代器区间构造
list<int> l3(l2.begin(), l2.end());
//拷贝构造
list<int> l4(l3);

赋值重载操作符

//给正在定义的对象使用赋值，会自动调用拷贝构造
list<int> l1(3,100);list<int> l2 = l1;list3<int> l3;ls = l1;

1.2 迭代器与容量相关成员函数

迭代器相关

//正向反向迭代器
list<int> l1;
l1.begin();
l1.rbegin();//const迭代器
l1.cbegin();
l1.crbegin();

容量大小相关

//list的现容量
list<int> l1;
l1.capacity();
//list的现存储数据长度
l1.size();
//理论上的最大长度
l1.max_size();

1.3 存储数据操作相关成员函数

数据操作相关

//返回list的头尾元素
list<int> l1;
l1.front();
l1.back();list<int> l2(3,10);
//给已存在list使用指定值赋值
//使用指定值
l1.assgin(4, 99);
//使用迭代器区间
l1.assgin(l2.begin(), l2.end());//头插，头删
l1.push_front(100);
l1.pop_front();//尾插，尾删
l1.push_back(100);
l1.pop_back();//指定位置插入
//在指定迭代器位置之前插入一个值
l1.insert(l1.begin(), 100);
//在指定迭代器位置之前插入n个数
l1.insert(l1.begin(), 3, 100);
//在指定迭代器位置之前插入一段迭代器区间
l1.insert(l1.beign(), l2.begin(), l2.end());//指定位置删除
//删除指定迭代器位置的值
l1.erase(v.begin());
//删除指定的一段迭代器区间
l1.erase(v.begin(), v.begin() + 2);//将两个list的结点交换
l1.swap(l2);//调整链表的容量大小
//n大时扩容，n小时不缩容
//将list扩容至长度为10，并将新增加的结点值赋予为10
l1.resize(10,80);//清空list的所有结点
l1.clear();

1.4 其他list操作成员函数

接合/转移：splice

//list之间的接合
list<int> l1(5, 10);
list<int> l2(5, 9);//将list2拼接到list1的指定迭代器位置
l1.splice(l1.begin() + 1, l2);//将l1上的一个指定迭代器位置结点拼接到l2上的指定迭代器位置
l2.splice(l2.begin(), l1, l1.end() - 1);//将l1上的一段迭代器区间拼接l2的指定位置上
l2.splice(l2.begin(), l1.begin(), l1.begin() + 2);

寻找指定值并移除：remove，去重：unique

list<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
//找到list中值等于3的结点并移除
l1.remove(3);//对list进行去重操作，只保留不同值
l1.unique();

排序与逆置

list<int> l1;
l1.push_back(3);
l1.push_back(2);
l1.push_back(1);//对list进行排序
//归并排序
l1.merge();
l1.sort();//将整个链表逆置
l1.reverse();

2. list的自实现

2.1 list的自实现功能

  1. 结点与迭代器类型的定义，创建
  2. 迭代器的一系列运算符的重载
  3. list的默认成员函数：构造，析构，赋值重载，拷贝构造，析构
  4. list的插入删除相关成员函数：push_back，pop_back，push_front，pop_front，insert，erase

复用关系
在这里插入图片描述

2.2 list的结点结构

//结点，struct默认成员函数为公有
template<class T>
struct ListNode
{//类型名typedef ListNode<T> Node;Node* _prev;Node* _next;T val;//构造函数：ListNode(T x = T()):val(x),_prev(nullptr),_next(nullptr){}
};

2.3 list的迭代器

//迭代器
template<class T>
struct __list_iterator
{//内置类型无法进行运算符重载typedef __list_iterator<T> self;typedef ListNode<T> Node;__list_iterator(Node* node):_node(node){}//将指针进行封装Node* _node;
}

2.3 list的结构

template<class T>
class list
{
public://typedef的作用域只在类域中typedef __list_iterator<T> iterator;typedef ListNode<T> Node;private:Node* Head;
};

2.4 list迭代器的运算符重载

1. ++，–

self& operator++()
{_node = _node->_next;return *this;
}self operator++(int)
{self tmp(_node);_node = _node->_next;return tmp;
}self operator--(int)
{self tmp(_node);_node = _node->_prev;return tmp;
}self& operator--()
{_node = _node->_prev;return *this;
}

2. 解引用，!=，==

//后续可能存在值的修改
T& operator*()
{return _node->val;
}//直接使用beign()的返回值作为参数
//形成中间临时变量，临时变量具有常性
//直接传引用会导致权限的放大
//self生成拷贝，self&权限放大
bool operator!=(const self& it)
{return _node != it._node;
}bool operator==(const self& it)
{return _node == it._node;
}

2.5 list的成员函数

1. 构造

void init_empty()
{Head = new Node;Head->_next = Head;Head->_prev = Head;
}list()
{init_empty();
}

2. 迭代器

//单参数的构造函数，支持隐式类型转换
iterator begin()
{return Head->_next;
}iterator end()
{return Head;
}

3. 随机插入删除

void insert(iterator pos, T val)
{//在pos之前插入Node* cur = pos._node;Node* pre = cur->_prev;Node* newnode = new Node(val);newnode->_prev = pre;newnode->_next = cur;cur->_prev = newnode;pre->_next = newnode;
}//指定删除会导致，迭代器失效，野指针
iterator erase(iterator pos)
{//会进行优化，直接使用end()返回的指针进行优化assert(pos != end());//删除当前位置Node* cur = pos._node;Node* pre = cur->_prev;Node* next = cur->_next;pre->_next = next;next->_prev = pre;delete cur;return next;
}

4. 头插，头删，尾插，尾删

void push_back(T val)
{insert(end(), val);
}void push_front(T val)
{insert(begin(), val);
}void pop_back()
{erase(--end());
}void pop_front()
{erase(begin());
}

5. clear与swap

void swap(list<T> s)
{std::swap(Head, s.Head);
}void clear()
{while (begin() != end()){pop_back();}
}

6. 拷贝构造，赋值，析构

//没有写const迭代器
list(list<T>& s)
{//链接环状链表init_empty();//没有const迭代器for (auto e : s){push_back(e);}
}list<T>& operator=(list<T> s)
{swap(s);return *this;
}~list()
{clear();delete Head;Head = nullptr;
}

3. const迭代器，operator->运算符重载与模板参数的应用

3.1 const迭代器

  1. 我们对list容器的数据结构对象进行修开操作时，除开list提供的接口外，想要进行对指定位置的结点进行修改，需要先从链表中拿到这一结点位置信息，而我们只能通过迭代器访问遍历的方式做到这一操作。
  2. 想要修改或者访问list的某一结点都是通过迭代器的方式进行的，而list的插入删除操作等接口也是通过迭代器从而实现的。
  3. 当list被const进行修饰，其不想内部的数据被修改，即对我们仅开放只读权限时，我想要对list进行遍历，普通的迭代器因为类型不匹配的原因我们无法进行调用。
  4. 因此，我们需要专门创建支持this指针指向内容被const修饰的迭代器，即只有访问权限无法对其指向进行更改操作的迭代器。
  5. const迭代器的其他操作行为都与普通相同，只是operator*操作符重载返回的值是const修饰的无法更改，所以我们独立去编写一份相似度极高的代码是非常低效的。
  6. 解决方式采用引入新的模板参数来做operator*返回值类型的区分。
template<class T, class Ref>
struct __list_iterator
{typedef __list_iterator<T, Ref> self;typedef ListNode<T> Node;Node* _node;__list_iterator(Node* node):_node(node){}//const T&/T&//根据不同的模板参数，返回类型也不同Ref operator*(){return _node->val;}//其他操作与普通迭代器相同//......
};//增加const迭代器后的list容器
template<class T>
class list
{
public://同一模板，传递模板参数不同，得到的迭代器不同typedef __list_iterator<T, T&> iterator;typedef __list_iterator<T, const T&> const_iterator;//const迭代器//const修饰的变量，表示其值不想不被改变const_iterator begin() const{return Head->_next;}const_iterator end() const{return Head;}void init_empty(){Head = new Node;Head->_next = Head;Head->_prev = Head;}list(){init_empty();}private:Node* Head;
};
  1. 创建const迭代器后，拷贝构造可以直接使用const修饰的参数，提高效率。

3.2 迭代器的operator->运算符重载

  1. operator->运算重载的意义：当list存储的结点数据为自定义类型，且自定义类型其自身并没有重载流插入运算符，我们又要对其结点内部的值进行访问与打印时，迭代器重载的operator->就可以让我们来进行自定义结点内部数据的访问。
template<class T, class Ref, class Ptr>
struct __list_iterator
{typedef __list_iterator<T, Ref, Ptr> self;typedef ListNode<T> Node;Node* _node;__list_iterator(Node* node):_node(node){}//返回结点的数据的地址，间接达到对自定类型结点内部数据的访问//const迭代器中对值的访问都要用const修饰，添加新的模板参数Ptr operator->(){return &_node->val;}//其他操作与普通迭代器相同//......
};//list结构
template<class T>
class list
{
public://同一模板，传递模板参数不同，得到的迭代器不同typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;private:Node* Head;
};struct A
{int _aa;int _bb;A(int aa = 1, int bb = 1):_aa(aa),_bb(bb){}
};zyc::list<A> l1;l1.push_back(A());
l1.push_back(A(2,3));
l1.push_back(A(2,2));auto it = l1.begin();
//operator->的调用被编译器优化为一个箭头
//原本调用逻辑：it->->_aa，it.operator->()._aa
//优化调用
cout << it->_aa << endl;

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

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

相关文章

专题二_滑动窗口(1)

专题二_滑动窗口(1)

目录 209. 长度最小的子数组 解析 题解 3. 无重复字符的最长子串 解析 题解 1004. 最大连续1的个数 III 解析 题解 209. 长度最小的子数组 209. 长度最小的子数组 - 力扣&#xff08;LeetCode&#xff09; 解析 题解 class Solution { public:int minSubArrayLen(int…
阅读更多...
Medium 级别 DOM 型 XSS 攻击演示（附链接）

Medium 级别 DOM 型 XSS 攻击演示（附链接）

环境准备 DVWA 靶场https://eclecticism.blog.csdn.net/article/details/135834194?spm1001.2014.3001.5502 测试 打开 DVWA 靶场并登录&#xff0c;找到 DOM 型 XSS 页面&#xff08;笔者这里是 Medium 级别&#xff09; 跟 Low 级别一样&#xff0c;直接上手 <script…
阅读更多...
vue多语言包i18n

vue多语言包i18n

1.安装 如果是vue2直接安装8.2.1版本&#xff0c;否则会出现版本不匹配的错误 npm install vue-i18n8.2.1 --save2.文件编辑 在src目录下创建文件 en.js export const h {system: "Background management system",loginOut:"LoginOut",LayoutSet:Layout …
阅读更多...
双通道内存@DDR5多通道内存

双通道内存@DDR5多通道内存

文章目录 多通道内存DDR4及以前的内存的双通道DDR5往后的双通道和多通道半位宽4通道组合 其他组合测试 DDR5介绍概览重要Features特点 总结 多通道内存 DDR4及以前的内存的双通道 双通道内存是一种内存架构设计&#xff0c;通过在主板上配置两个或多个独立且同时工作的内存控制…
阅读更多...
MySQL高阶SQL语句（二）

MySQL高阶SQL语句（二）

文章目录 MySQL高阶SQL语句&#xff08;二&#xff09;一、MySQL常用查询1、子查询1.1 语法1.1.1 结合select语句查询1.1.2 结合insert语句查询1.1.3 结合update语句查询1.1.4 结合delete语句查询1.1.5 在in前面添加not1.1.6 exists关键字 2、别名 二、MySQL视图1、视图介绍1.1…
阅读更多...
【uniapp】uniapp实现免密登录

【uniapp】uniapp实现免密登录

文章目录 一、概要二、整体架构流程三、技术名词解释四 、技术细节1.存取token有效期&#xff1f;2.使用setStorageSync而不使用setStorage&#xff1f;3.使用onLaunch而不使用全局路由&#xff1f; 一、概要 打开一个网页或小程序的时候&#xff0c;我们有时候会自动进入主页…
阅读更多...
那些王道书里的题目-----计算机网络篇

那些王道书里的题目-----计算机网络篇

注&#xff1a;仅记录个人认为有启发的题目 p155 34.下列四个地址块中&#xff0c;与地址块 172.16.166.192/26 不重叠&#xff0c;且与172.16.166.192/26聚合后的地址块不会引入多余地址的是&#xff08;&#xff09; A.172.16.166.192/27 B.172.16.166.128/26 …
阅读更多...
MySQL高级sql语句

MySQL高级sql语句

目录 一、子查询 1.1查询分数大于80的记录 1.2将test3里的记录全部删除&#xff0c;重新插入class表的记录 ​编辑1.3将meixi的分数改为20 1.4删除分数大于80的记录 1.5删除分数不是大于等于80的记录 1.6查询如果存在分数等于80的记录则计算class的字段数 2.子查询&…
阅读更多...
cuda python课程中“使用 Numba 的 CUDA Python 的自定义核函数和内存管理“一个大坑

cuda python课程中“使用 Numba 的 CUDA Python 的自定义核函数和内存管理“一个大坑

总觉得自己的算法没问题&#xff0c;最终还是测试结果不符。 错误出现在一个很顺眼的位置。 解决方案 在最终测验阶段有一个看起来没问题不需要任何修改的Cell&#xff0c;就是这一句&#xff0c;看起来没什么毛病 d_histogram_out cuda.device_array_like(histogram_out)需…
阅读更多...
Go通道机制与应用详解

Go通道机制与应用详解

目录 一、概述二、Go通道基础通道&#xff08;Channel&#xff09;简介创建和初始化通道通道与协程&#xff08;Goroutine&#xff09;的关联nil通道的特性 三、通道类型与操作通道类型1. 无缓冲通道 (Unbuffered Channels)2. 有缓冲通道 (Buffered Channels) 通道操作1. 发送操…
阅读更多...
预期为文件结尾。json [行2,列1]

预期为文件结尾。json [行2,列1]

报错背景 在huggingface上传数据集后&#xff0c;Dataset Viewer无法显示&#xff0c;报错&#xff1a; The dataset viewer is not available for this split. Cannot extract the features (columns) for the split train of the config default of the dataset. Error cod…
阅读更多...
HCIP作业

HCIP作业

实验要求&#xff1a; 1、R6为ISP&#xff0c;接口IP地址均为公有地址&#xff0c;该设备只能配置IP地址&#xff0c;之后不能再对其进行任何配置&#xff1b; 2、R1-R5为局域网&#xff0c;私有IP地址192.168.1.0/24&#xff0c;请合理分配&#xff1b; 3、R1、R2、R4&#x…
阅读更多...
Jenkins常用插件安装及全局配置

Jenkins常用插件安装及全局配置

Jenkins常用插件安装及全局配置 前言 ​ Jenkins是一个流行的持续集成工具&#xff0c;通过安装适用的插件&#xff0c;可以扩展Jenkins的功能&#xff0c;并与其他工具和系统集成。本文将介绍一些常用的Jenkins插件以及安装和配置的步骤。通过安装和配置这些常用插件&#xf…
阅读更多...
鸿蒙开发之ArkUI组件常用组件图片和文本

鸿蒙开发之ArkUI组件常用组件图片和文本

ArkUI即方舟开发框架是HarmonyOS应用的UI开发提供了完整的基础设施&#xff0c;包括简洁的UI语法、丰富的UI功能&#xff08;组件、布局、动画以及交互事件&#xff09;&#xff0c;以及实时界面预览工具等&#xff0c;可以支持开发者进行可视化界面开发。 开发文档地址 &…
阅读更多...
Docker安装各种组件

Docker安装各种组件

列举镜像 docker images // 列举镜像 搜索镜像 docker search jdk 下载镜像&#xff1a; docker pull java 查看镜像&#xff1a; docker images 启动镜像&#xff1a; docker run -it --name jdk1.8 -d java:latest /bin/bash 查看容器&#xff1a; docker ps 查看…
阅读更多...
STM32之HAL开发——系统定时器（SysTick）

STM32之HAL开发——系统定时器（SysTick）

系统定时器&#xff08;SysTick&#xff09;介绍 SysTick—系统定时器是属于 CM3 内核中的一个外设&#xff0c;内嵌在 NVIC 中。系统定时器是一个 24bit的向下递减的计数器&#xff0c;计数器每计数一次的时间为 1/SYSCLK&#xff0c;一般我们设置系统时钟 SYSCLK等于 72M。当…
阅读更多...
ChatGPT智能聊天系统源码v2.7.6全开源Vue前后端+后端PHP

ChatGPT智能聊天系统源码v2.7.6全开源Vue前后端+后端PHP

测试环境：Linux系统CentOS7.6、宝塔、PHP7.4、MySQL5.6，根目录public，伪静态thinkPHP，开启ssl证书 具有文章改写、广告营销文案、编程助手、办公达人、知心好友、家庭助手、出行助手、社交平台内容、视频脚本创作、AI绘画、思维导图等功能 ai通道：文心一言、MiniMax、智…
阅读更多...
Qt中QIcon图标设置（标题、菜单栏、工具栏、状态栏图标）

Qt中QIcon图标设置（标题、菜单栏、工具栏、状态栏图标）

1 exe程序图标概述 在 Windows 操作系统中&#xff0c;程序图标一般会涉及三个地方&#xff1b; &#xff08;1&#xff09; 可执行程序&#xff08;以及对应的快捷方式&#xff09;的图标 &#xff08;2&#xff09; 程序界面标题栏图标 &#xff08;3&#xff09;程序在任务…
阅读更多...
知攻善防应急靶场-Linux(1)

知攻善防应急靶场-Linux(1)

前言&#xff1a; 堕落了三个月&#xff0c;现在因为被找实习而困扰&#xff0c;着实自己能力不足&#xff0c;从今天开始 每天沉淀一点点 &#xff0c;准备秋招 加油 注意&#xff1a; 本文章参考qax的网络安全应急响应和知攻善防实验室靶场&#xff0c;记录自己的学习过程&am…
阅读更多...
再仔细品品Elasticsearch的向量检索

再仔细品品Elasticsearch的向量检索

我在es一开始有向量检索&#xff0c;就开始关注这方面内容了。特别是在8.X之后的版本&#xff0c;更是如此。我也已经把它应用在亿级的生产环境中&#xff0c;用于多模态检索和语义检索&#xff0c;以及RAG相关。 也做过很多的优化&#xff1a;ES 8.x 向量检索性能测试 & 把…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023