【C++】- 掌握STL List类:带你探索双向链表的魅力

在这里插入图片描述

文章目录

  • 前言:
  • 一.list的介绍及使用
    • 1. list的介绍
    • 2. list的使用
      • 2.1 list的构造
      • 2.2 list iterator的使用
      • 2.3 list capacity
      • 2.4 list element access
      • 2.5 list modifiers
      • 2.6 list的迭代器失效
  • 二.list的模拟实现
    • 1. list的节点
    • 2. list的成员变量
    • 3.list迭代器相关问题
      • 3.1 普通迭代器
      • 3.2 const迭代器
    • 4. list的成员函数
      • 4.1 list的空初始化
      • 4.2 push_back
      • 4.3 构造函数
      • 4.4 insert
      • 4.4 erase
      • 4.5 push_front
      • 4.6 pop_front
      • 4.7 pop_back
      • 4.8 clear
      • 4.8 析构函数
      • 4.9 swap
      • 4.10 赋值运算符重载
  • 最后想说:

前言:

 C++中的List容器是标准模板库(STL)中的一种序列容器,它实现了双向链表的功能。与数组(如vector)和单向链表相比,List容器提供了更加灵活的元素插入和删除操作,特别是在容器中间位置进行这些操作时。

一.list的介绍及使用

1. list的介绍

  • 双向链表结构: list容器使用双向链表来存储元素,每个元素(节点)都包含数据部分两个指针,分别指向前一个元素和后一个元素。这种结构使得在链表的任何位置进行插入和删除操作都非常高效,时间复杂度为O(1)
  • 动态大小: list容器的大小可以在运行时动态改变,即可以在程序运行过程中添加或移除元素。
  • 不支持随机访问:vectorarray等连续内存的容器不同,list不支持随机访问迭代器,不能直接通过索引获取元素,而需要通过迭代器遍历。
  • 迭代器稳定性: 在list中插入或删除元素不会导致其他迭代器失效(除了指向被删除元素的迭代器)。这是因为它通过调整相邻节点的指针来维护链表结构,而不需要移动元素或重新分配内存。

2. list的使用

list的使用参考文档:list的文档介绍
在这里插入图片描述

2.1 list的构造

构造函数接口说明
list (size_type n, const value_type& val =value_type() )构造的list中包含n个值为val的元素
list()构造空的list
list (const list& x)拷贝构造函数
list (InputIterator first, InputIterator last)用[first, last)区间中的元素构造list

代码演示:

#include<list>
int main()
{list<int> l1;//构造空的l1;list<int> l2(4,100);//l2中存放4个值为100的元素list<int> l3(l2.begin(),l2.end());//用l2的[begin,end)左开右闭区间构造l3;list<int> l4(l3);//用l3拷贝构造l4// 以数组为迭代器区间构造l5int array[] = { 16,2,77,29 };list<int> l5(array, array + sizeof(array) / sizeof(int));// 列表格式初始化C++11list<int> l6{ 1,2,3,4,5 };// 用迭代器方式打印l5中的元素list<int>::iterator it = l5.begin();while (it != l5.end()){cout << *it << " ";++it;}cout << endl;// C++11范围for的方式遍历for (auto& e : l5)cout << e << " ";cout << endl;return 0;
}

2.2 list iterator的使用

此处,大家可暂时将迭代器理解成一个指针,该指针指向list中的某个节点。

函数声明接口说明
begin返回第一个元素的迭代器
end返回最后一个元素下一个位置的迭代器
rbegin返回一个指向容器中最后一个元素的反向迭代器(即容器的反向起始)
rend返回一个反向迭代器,该迭代器指向列表容器中第一个元素之前的理论元素(该元素被认为是其反向结束)。

注意:

  1. begin与end为正向迭代器,对迭代器执行++操作,迭代器向后移动
  2. rbegin(end)与rend(begin)为反向迭代器,对迭代器执行++操作,迭代器向前移动

代码演示:

int main()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));// 使用正向迭代器正向list中的元素// list<int>::iterator it = l.begin();   // C++98中语法auto it = l.begin();                     // C++11之后推荐写法while (it != l.end()){cout << *it << " ";++it;}cout << endl;// 使用反向迭代器逆向打印list中的元素// list<int>::reverse_iterator rit = l.rbegin();auto rit = l.rbegin();while (rit != l.rend()){cout << *rit << " ";++rit;}cout << endl;return 0;
}

2.3 list capacity

函数声明接口说明
front检测list是否为空,是返回true,否则返回false
size返回list中有效节点的个数

2.4 list element access

函数声明接口说明
front返回list的第一个节点中值的引用
back返回list的最后一个节点中值的引用

2.5 list modifiers

函数声明接口说明
push_front在list首元素前插入值为val的元素
pop_front删除list中第一个元素
push_back在list尾部插入值为val的元素
pop_back删除list中最后一个元素
insert在list position 位置中插入值为val的元素
erase删除list position位置的元素
swap交换两个list中的元素
clear清空list中的有效元素

代码演示:

#include<iostream>
#include<vector>
using namespace std;void PrintList(const list<int>& l)
{// 注意这里调用的是list的 begin() const,返回list的const_iterator对象for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it){cout << *it << " ";}cout << endl;
}// list插入和删除
// push_back/pop_back/push_front/pop_front
void TestList1()
{int array[] = { 1, 2, 3 };list<int> L(array, array + sizeof(array) / sizeof(array[0]));// 在list的尾部插入4,头部插入0L.push_back(4);L.push_front(0);PrintList(L);// 删除list尾部节点和头部节点L.pop_back();L.pop_front();PrintList(L);
}// insert /erase 
void TestList2()
{int array1[] = { 1, 2, 3 };list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));// 获取链表中第二个节点auto pos = ++L.begin();cout << *pos << endl;// 在pos前插入值为4的元素L.insert(pos, 4);PrintList(L);// 在pos前插入5个值为5的元素L.insert(pos, 5, 5);PrintList(L);// 在pos前插入[v.begin(), v.end)区间中的元素vector<int> v{ 7, 8, 9 };L.insert(pos, v.begin(), v.end());PrintList(L);// 删除pos位置上的元素L.erase(pos);PrintList(L);// 删除list中[begin, end)区间中的元素,即删除list中的所有元素L.erase(L.begin(), L.end());PrintList(L);
}// resize/swap/clear
void TestList3()
{// 用数组来构造listint array1[] = { 1, 2, 3 };list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));PrintList(l1);// 交换l1和l2中的元素list<int> l2;l1.swap(l2);PrintList(l1);PrintList(l2);// 将l2中的元素清空l2.clear();cout << l2.size() << endl;
}int main()
{TestList1();TestList2();TestList3();return 0;
}

运行结果:
在这里插入图片描述

2.6 list的迭代器失效

 前面已经说过了,此处可以将迭代器理解为类似于指针的东西,迭代器失效即迭代器指向的节点失效了,即该节点被删除了。因为list的底层结构为带头结点的双向循环链表,因此在list进行插入操作时不会导致迭代器失效,只有删除时才会失效,并且失效的是被删除节点的迭代器,其他迭代器不会受到影响。

二.list的模拟实现

1. list的节点

template<class T>
struct list_node
{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& x = T()):_data(x), _next(nullptr), _prev(nullptr){}
};

2. list的成员变量

template<class T>
class list
{typedef list_node<T> Node;
public://成员函数
private:Node* _head; //哨兵位的头节点
};

 没有用访问限定符限制的成员class默认是私有的,struct默认是公有的,如果一个类既有公有也有私有就用class,全部为公有一般用struct。这不是规定,只是个惯例。

3.list迭代器相关问题

简单分析:
&emsp; 这里不能像以前一样给一个结点的指针作为迭代器,如果it是typedef的节点的指针,it解引用得到的是节点,不是里面的数据,但是我们期望it解引用是里面的数据,++it我们期望走到下一个节点去,而list中++走不到下一个数据,因为数组的空间是连续的,++可以走到下一个数据。但是链表达不到这样的目的。所以原身指针已经无法满足这样的行为,怎么办呢?这时候我们的类就登场了
用类封装一下节点的指针,然后重载运算符,模拟指针。
例如:

reference operator*()const
{return (*node).data;
}
self& opertor++()
{node = (link_type)((*node).next);return *this;
}

3.1 普通迭代器

template<class T>
struct list_iterator
{typedef list_node<T> Node;typedef list_iterator<T> Self;Node* _node;list_iterator(Node* node):_node(node){}T& operator*() //用引用返回可以读数据也可以修改数据{return _node->_data;}T* operator->(){return &_node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& s){return _node != s._node;}
};

3.2 const迭代器

const迭代器在定义的时候不能直接定义成typedef const list_iterator<T> const_iterator,const迭代器的本质是限制迭代器指向的内容不能被修改,而前面的这种写法限制了迭代器本身不能被修改,所以迭代器就不能进行++操作。那该怎能办呢?答案是我们可以实现一个单独的类:

template<class T>
struct list_const_iterator
{typedef list_node<T> Node;typedef list_const_iterator<T> Self;Node* _node;list_const_iterator(Node* node):_node(node){}const T& operator*(){return _node->_data; //返回这个数据的别名,但是是const别名,所以不能被修改}const T* operator->(){return &_node->_data; //我是你的指针,const指针}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& s){return _node != s._node;}
};

普通法迭代器与const迭代器的区别就是:普通迭代器可读可写,const迭代器只能读
上面是我们自己实现的普通迭代器和const迭代器,用两个类,并且这两个类高度相似,下来就让我们一起看一看库里面是怎么实现的吧!

在这里插入图片描述
我们可以看到库里面是写了两个模板,让编译器去生成对应的类。其本质上也是写了两个类,只不过是让编译器去生成对应的类。

迭代器不需要我们自己写析构函数、拷贝构造函数、赋值运算符重载函数,因为这里要的是浅拷贝,例如我把一个迭代器赋值给另外一个迭代器,就是期望两个迭代器指向同一个节点,这里用浅拷贝即可,拷贝给你我们两个迭代器就指向同一个节点。

4. list的成员函数

4.1 list的空初始化

void empty_init() //空初始化
{_head = new Node();_head->_next = _head;_head->_prev = _head;
}

4.2 push_back

//普通版本
void push_back(const T& x)
{Node* new_node = new Node(x);Node* tail = _head->_prev;tail->_next = new_node;new_node->_prev = tail;new_node->_next = _head;_head->_prev = new_node;
}
//复用insert版本insert(end(),x);

4.3 构造函数

list_node(const T& x = T()):_data(x), _next(nullptr), _prev(nullptr)
{}

4.4 insert

iterator insert(iterator position; const T& val)
{Node* cur = pos._node;Node* newnode = new Node(val);Node* prev = cur->_prev;//prev newnode curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return iterator(newnode);
}

4.4 erase

iterator erase(iterator pos)
{assert(pos != end());Node* del = pos._node;Node* prev = del->_prev;Node* next = del->_next;prev->_next = next;next->_prev = prev;delete del;return iterator(next);
}

4.5 push_front

void push_front(const T& x)
{insert(begin(), x);
}

4.6 pop_front

void pop_front()
{erase(begin());
}

4.7 pop_back

void pop_back()
{erase(--end());
}

4.8 clear

void clear()
{auto it = begin();while (it != end()){it = erase(it);}
}

4.8 析构函数

~list()
{clear();delete _head;_head = nullptr;
}

4.9 swap

void swap(list<T>& tmp)
{std::swap(_head, tmp._head);//交换哨兵位的头节点
}

4.10 赋值运算符重载

//现代写法
//lt2=lt3
//list<T>& operator=(list<T> lt)
list& operator=(list lt) //不加模板参数
{swap(lt);//交换就是交换哨兵位的头节点return *this;
}//lt3传给lt去调用拷贝构造,所以lt就和lt3有一样大的空间一样大的值,lt2很想要,也就是/this想要,lt2之前的数据不想要了,交换给lt,此时lt2就和lt3有一样大的空间一样大的值,
//lt出了作用域就被销毁了

构造函数和赋值运算符重载函数的形参和返回值类型可以只写类名 list,不需要写模板参数,这种写法在类里面可以不加,只能在类里面可以这样写,类外面是不行的,一般情况下加上好一点。


最后想说:

本章我们STL的List就介绍到这里,下期我将介绍关于stackqueue的有关知识,如果这篇文章对你有帮助,记得点赞,评论+收藏 ,最后别忘了关注作者,作者将带领你探索更多关于C++方面的问题。

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

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

相关文章

Facebook的隐私保护政策:用户数据如何在平台上被管理?

在当今数字化世界&#xff0c;社交平台如何管理用户数据并保护隐私成为了一个热点话题。作为全球最大的社交网络&#xff0c;Facebook&#xff08;现Meta&#xff09;在数据隐私方面的政策备受关注。本文将简要介绍Facebook的隐私保护措施&#xff0c;以及用户数据如何在平台上…

Git-分支(branch)常用命令

分支 我们在做项目开发的时候&#xff0c;无论是软件项目还是其他机械工程项目&#xff0c;我们为了提高效率以及合理的节省时间等等原因&#xff0c;现在都不再是线性进行&#xff0c;而是将一个项目抽离出诸进行线&#xff0c;每一条线在git中我们就叫做分支&#xff0c;bran…

0101多级nginx代理websocket配置-nginx-web服务器

1. 前言 项目一些信息需要通过站内信主动推动给用户&#xff0c;使用websocket。web服务器选用nginx&#xff0c;但是域名是以前通过阿里云申请的&#xff0c;解析ip也是阿里云的服务器&#xff0c;甲方不希望更换域名。新的系统需要部署在内网服务器&#xff0c;简单拓扑图如…

Android Stduio 2024版本设置前进和后退按钮显示在主界面

Android Studio 2024&#xff08;Ladybug&#xff09;安装后发现前进和后退按钮不显示在主界面的工具栏&#xff0c;且以前在View中设置的办法无效&#xff1a; Android Studio 2024&#xff08;Ladybug&#xff09;的设置方式&#xff1a; File->Settings->Appearance&…

【C++算法】48.分治_归并_数组中的逆序对

文章目录 题目链接&#xff1a;题目描述&#xff1a;解法C 算法代码&#xff1a;图解 题目链接&#xff1a; 剑指 Offer 51. 数组中的逆序对 题目描述&#xff1a; 解法 解法一&#xff1a;暴力解法&#xff1a;暴力枚举 两层for循环 本题不能用&#xff0c;用了会超时。 解法…

少样本学习之CAML算法

上下文感知元学习&#xff08;Context-Aware Meta-Learning, CAML&#xff09; 概述 在机器学习和深度学习领域&#xff0c;元学习&#xff08;Meta-Learning&#xff09;旨在通过学习如何学习&#xff0c;使模型能够在面对新任务时快速适应。传统的元学习方法通常需要在特定…

【ChatGPT】解锁AI思维链:如何让机器像人类一样思考?

在人工智能领域&#xff0c;我们一直在追求让机器像人类一样思考。然而&#xff0c;即使是最先进的AI&#xff0c;也常常被诟病缺乏“常识”&#xff0c;难以理解复杂问题&#xff0c;更不用说像人类一样进行逻辑推理和解决问题了。最经常的表现就是遇到不会的地方&#xff0c;…

leetcode 面试经典 150 题:长度最小的子数组

链接长度最小的子数组题序号209题型数组解题方法滑动窗口难度中等 题目 给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl1, …, numsr-1, numsr] &#xff0c;并返回其长度。如果不存在符合条件…

多进程并发跑程序:pytest-xdist记录

多进程并发跑程序&#xff1a;pytest-xdist记录 pytest -s E:\testXdist\test_dandu.py pytest -s testXdist\test_dandu.py pytest -s &#xff1a;是按用例顺序依次跑用例 pytest -vs -n auto E:\testXdist\test_dandu.py pytest -vs -n auto&#xff0c;auto表示以全部进程…

Vue2二、指令补充,computed 计算属性vs方法,watch 侦听器,

一、指令补充 1.修饰符。2.动态操作class。3.动态操作style。4.v-model 用于其他表单元素 1.修饰符 ① 按键修饰符 keyup.enter → 键盘回车监听 <body><div id"app"><h3>keyup.enter → 监听键盘回车事件</h3><input v-model"…

spring\strust\springboot\isp前后端那些事儿

后端 一. 插入\更新一条数据&#xff08;老&#xff09; Map<String, Object> parameterMap MybatisUtil.initParameterSave("Send_ProjectFrozenLog", sendProjectFrozenLog); commonMapper.insert(parameterMap);parameterMap MybatisUtil.initParameter…

uniapp连接蓝牙操作(蓝牙设备地锁)

介绍&#xff1a; 本文采用uni-app框架来创建一个简单的用户界面&#xff0c;用于搜索、连接和发送命令给蓝牙设备。 1.打开蓝牙适配器 function openBluetooth() {uni.openBluetoothAdapter({success() {uni.offBluetoothDeviceFound();// 监听新设备发现事件uni.onBlueto…

安防监控Liveweb视频汇聚融合平台助力执法记录仪高效使用

Liveweb平台可接入的设备除了常见的智能分析网关与摄像头以外 &#xff0c;还可通过GB28181协议接入执法记录仪&#xff0c;实现对执法过程的全程监控与录像&#xff0c;并对执法轨迹与路径进行调阅回看。那么&#xff0c;如何做到执法记录仪高效使用呢&#xff1f; 由于执法记…

10 JVM内置锁

我们先想明白一个问题&#xff0c;什么是锁&#xff1f; 我们去给自己家锁门的时候&#xff0c;只有对应的一把钥匙能开锁。当用钥匙去开锁的时候&#xff0c;锁孔的内置型号会验证钥匙能不能对的上。能对上就能把锁打开&#xff0c;然后进到家里使用家里的资源。否则就在外面等…

建立在商用GPT上的简单高效单细胞表示模型

大规模基因表达数据正被用于单细胞表示模型的预训练。然而&#xff0c;这样的模型需要大量的数据管理和训练。在这里&#xff0c;作者探索了一种更简单的替代方案&#xff1a;使用 GPT-3.5 从单个基因的文本描述中生成基因嵌入&#xff0c;然后通过基因表达量加权gene embeddin…

tryhackme-Pre Security-Defensive Security Intro(防御安全简介)

任务一&#xff1a;Introduction to Defensive Security防御安全简介 此room的两个要点&#xff1a; Preventing intrusions from occurring 防止入侵发生Detecting intrusions when they occur and responding properly 检测发生的入侵并正确响应 防御安全还有更多内容。 除上…

[Unity] Text文本首行缩进两个字符

Text文本首行缩进两个字符的方法比较简单。通过代码把"\u3000\u3000"加到文本字符串前面即可。 比如&#xff1a; 效果&#xff1a; 代码&#xff1a; TMPtext1.text "\u3000\u3000" "选择动作类型&#xff1a;";

Python:Matplotlib详细使用

1.Matplotlib简介 Matplotlib是python数据分析三剑客之一&#xff0c;是一个功能强大且非常流行的Python数据可视化库。Matplotlib可用于绘制折线图(line plot)、散点图(scatter plot)、条形图(bar plot)、直方图(histogram plot)、饼图(pie plot)等&#xff0c;同时也支持部分…

MIT S6081 2024 Lab 1 | Operating System | Notes

目录 安装与下载 实验1 开始我们的实验 sleep&#xff08;简单&#xff09; pingpong&#xff08;简单&#xff09; primes (中等)/(困难) find&#xff08;中等&#xff09; xargs&#xff08;中等&#xff09; finally Reference I. Tools Debian 或 Ubuntu Arch…

【Java】mac安装Java17(JDK17)

文章目录 下载java17一、安装二、环境变量 下载java17 官网下载&#xff1a;https://www.oracle.com/java/technologies/downloads 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 一、安装 直接安装后&#xff0c;安装完后目录会存放在下面目录下 /…