C++笔记---list

1. list的介绍

list其实就是就是我们所熟知的链表（双向循环带头结点），但其是作为STL中的一个类模板而存在。

也就是说，list是可以用来存储任意类型数据的顺序表，既可以是内置类型，也可以是自定义类型，或是STL中的其他容器。

除了底层的实现不同以外，用法与vector基本相同，但不支持随机访问，以及与随机访问有关的接口。

具体以list - C++ Reference为准，本文为该文档的一个简单总结与标注。

2. list的重要接口

以下表格中的函数都不是官方库中的函数原型，而是为了方便学习和理解而进行了简化的。

2.1 默认成员函数

2.1.1 构造函数

四种构造方式
(1) list();默认构造
(2) list(size_t n, const T& val = T());用val初始化list前n个数据

(3) template<class InputIterator>

list(InputIterator first, InputIterator last);

用迭代器区间进行初始化
(4) list(const list& x);拷贝构造
 2.1.2 赋值重载

 2.2 迭代器相关

begin返回开始位置的迭代器
end返回最后一个数据的下一个位置的迭代器
rbegin用于逆向迭代
rend用于逆向迭代
cbegin用于const修饰的容器的迭代
cend用于const修饰的容器的迭代
crbegin用于const修饰的容器的逆向迭代
crend用于const修饰的容器的逆向迭代

2.3 大小容量相关

bool empty() const;判断list是否为空
size_t size() const;返回list中的数据个数
size_t max_size() const;返回由于系统或数据库限制，list能够存储数据的最大容量（并不一定能达到）

2.4 访问相关

(1) T& front();
(2) constT& front() const;		返回第一个元素的引用
(1) T& back();
(2) constT& back() const;		返回最后一个元素的引用

2.5 元素修改相关

(1) template<class InputIterator>

     void assign(InputIterator first, InputIterator last);

(2) void assign(size_t n, const T& val);

给list赋新的值，效果类似于重新构造这个list
void push_front(const T& val); 在list头部插入一个元素
void push_back(const T& val); 在list尾部插入一个元素
void pop_front();删除list头部的一个元素
void pop_back();删除list尾部的一个元素
(1) iterator insert(iterator pos, const T& val);
(2) void insert(iterator pos, size_t n, const T& val);
(3) template <class InputIterator>
     void insert(iterator position, InputIterator first，InputIterator last);		在指定位置插入元素，常数时间O(1)，效率很高，不会导致迭代器失效
(1) iterator erase(iterator pos);
(2) iterator erase(iterator first, iterator last);		删除指定位置的数据，常数时间O(1)，效率很高，会导致当前位置迭代器失效
void swap(list<T>& x);交换两个list的数据
void resize(size_t n, T val = T());改变list的元素个数，使其容纳n个元素，n<size则删除多余的，n>size则加入n个值与val相同的元素
void clear();清空list

2.6 list结点移动

(1) void splice(iterator position, list& x);
(2) void splice(iterator position, list& x, iterator i);
(3) void splice(iterator position, list& x, iterator first, iterator last);		(1) 将x的结点全部移动到position位置
(2) 将x中i指向的结点移动到position位置
(3) 将x中first到last的结点移动到position位置
void remove(const T& val);移除list中与val值相同的结点
template <class Predicate>
void remove_if(Predicate pred);		按照pred(*it)函数的返回值(true移除/false不移除)来移除结点
(1) void unique();
(2) template <class BinaryPredicate>
     void unique(BinaryPredicate binary_pred);

(1) 移除值连续相等(operator==)的几个结点，只留下这组结点中的第一个(在处理经过排序的list时，能确保各种值得结点只留下一个)

(2) 按照binary_pred(*it, *(it-1))给出的逻辑判断结点的值是否相等，进而删除结点

(1) void merge(list& x);
(2) template <class Compare>
     void merge(list& x, Compare comp);

(1) 将x合并到调用函数的list中(x的结点全部移动到list中，并确保合并后的list中的结点也是有序(operator<)的，但要求两个list事先都是有序的。如果list==*this，该函数无行为)

(2) 按照comp函数给出的比较方式来进行有序的合并

(1) void sort();
(2) template <class Compare>
     void sort(Compare comp);

(1) 按照operator<进行排序

(2) 按照comp给出的比较方式排序

void reverse();逆置list

3. 迭代器失效

迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。

因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

4. list不完全模拟实现示例

#pragma once
#include<iostream>
using namespace std;namespace lbz
{// List的节点类template<class T>struct ListNode{ListNode(const T& val = T()):_val(val),_pPre(nullptr),_pNext(nullptr){}ListNode<T>* _pPre;ListNode<T>* _pNext;T _val;};//List的迭代器类template<class T, class Ref, class Ptr>struct ListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;typedef Ref _Ref;typedef Ptr _Ptr;public:ListIterator(PNode pNode = nullptr):_pNode(pNode){}ListIterator(const Self& l):_pNode(l._pNode){}T& operator*(){return _pNode->_val;}// 按理来说在使用时需要两个->，但编译器为了可读性做了优化T* operator->(){return &(_pNode->_val);}Self& operator++(){_pNode = _pNode->_pNext;return (*this);}Self operator++(int){Self tmp = (*this);_pNode = _pNode->_pNext;return tmp;}Self& operator--(){_pNode = _pNode->_pPre;return (*this);}Self& operator--(int){Self tmp = (*this);_pNode = _pNode->_pPre;return tmp;}bool operator!=(const Self& l) const{return (this->_pNode != l._pNode);}bool operator==(const Self& l) const{return (this->_pNode == l._pNode);}PNode _pNode;};template<class iterator>struct reverseListIterator{typedef typename iterator::_Ref Ref;typedef typename iterator::_Ptr Ptr;typedef reverseListIterator<iterator> Self;reverseListIterator(iterator it):_it(it){}Ref operator*(){iterator tmp(_it);--tmp;return *tmp;}Ptr operator->(){return &(operator*());}Self& operator++(){--_it;return *this;}Self& operator++(int){Self tmp(*this);--_it;return tmp;}Self& operator--(){++_it;return *this;}Self& operator--(int){Self tmp(*this);++_it;return tmp;}bool operator==(const Self& rit) const{return _it == rit._it;}bool operator!=(const Self& rit) const{return _it != rit._it;}iterator _it;};//list类template<class T>class list{typedef ListNode<T> Node;typedef Node* PNode;public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T&> const_iterator;typedef reverseListIterator<iterator> reverse_iterator;typedef reverseListIterator<const_iterator> const_reverse_iterator;public:///// List的构造list(){CreateHead();}list(int n, const T& value = T()){CreateHead();while (n--){push_back(value);}}template <class Iterator>list(Iterator first, Iterator last){CreateHead();while (first != last){push_back(*first);++first;}}list(const list<T>& l){CreateHead();list tmp(l.begin(), l.end());swap(tmp);}// 支持用大括号参数列表构造/隐式类型转换list(initializer_list<T> il){CreateHead();for (auto& e : il){push_back(e);}}list<T>& operator=(const list<T> l){list tmp(l.begin(), l.end());swap(tmp);return *this;}~list(){clear();delete _pHead;_pHead = nullptr;}///// List Iteratoriterator begin(){return iterator(_pHead->_pNext);}iterator end(){return iterator(_pHead);}const_iterator begin() const{return const_iterator(_pHead->_pNext);}const_iterator end() const{return const_iterator(_pHead);}const_iterator cbegin() const{return const_iterator(_pHead->_pNext);}const_iterator cend() const{return const_iterator(_pHead);}reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator crbegin() const{return const_reverse_iterator(cend());}const_reverse_iterator crend() const{return const_reverse_iterator(cbegin());}///// List Capacitysize_t size()const{return _size;}bool empty()const{return !_size;}// List AccessT& front(){return _pHead->_pNext->_val;}const T& front()const{return _pHead->_pNext->_val;}T& back(){return _pHead->_pPre->_val;}const T& back()const{return _pHead->_pPre->_val;}// List Modifyvoid push_back(const T& val) { insert(end(), val); }void pop_back() { erase(--end()); }void push_front(const T& val) { insert(begin(), val); }void pop_front() { erase(begin()); }// 在pos位置前插入值为val的节点iterator insert(iterator pos, const T& val){PNode newnode = new Node(val);newnode->_pNext = pos._pNode;newnode->_pPre = pos._pNode->_pPre;pos._pNode->_pPre->_pNext = newnode;pos._pNode->_pPre = newnode;_size++;return pos;}// 删除pos位置的节点，返回该节点的下一个位置iterator erase(iterator pos){pos._pNode->_pNext->_pPre = pos._pNode->_pPre;pos._pNode->_pPre->_pNext = pos._pNode->_pNext;iterator ret = pos._pNode->_pNext;delete pos._pNode;--_size;return ret;}void clear(){PNode cur = _pHead->_pNext->_pNext;while (cur != _pHead->_pNext){delete cur->_pPre;cur = cur->_pNext;}_pHead->_pNext = _pHead;_pHead->_pPre = _pHead;_size = 0;}void swap(list<T>& l){std::swap(_pHead, l._pHead);std::swap(_size, l._size);}private:void CreateHead(){_pHead = new Node;_pHead->_pNext = _pHead;_pHead->_pPre = _pHead;}PNode _pHead;size_t _size = 0;};
};

5. list的迭代器

由于底层结构的复杂性，list的迭代器不再像string和vector那样可以直接由指针代劳。

我们依然将结点指针作为list迭代器的底层，但是各操作符原本的逻辑已经无法满足我们的需要，均需要进行重载。

于是，我们用ListIterator类对结点的指针进行了包装，并对所需的操作符进行了相应的重载。

//List的迭代器类
template<class T, class Ref, class Ptr>
struct ListIterator
{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;typedef Ref _Ref;typedef Ptr _Ptr;
public:ListIterator(PNode pNode = nullptr):_pNode(pNode){}ListIterator(const Self& l):_pNode(l._pNode){}T& operator*(){return _pNode->_val;}// 按理来说在使用时需要两个->，但编译器为了可读性做了优化T* operator->(){return &(_pNode->_val);}Self& operator++(){_pNode = _pNode->_pNext;return (*this);}Self operator++(int){Self tmp = (*this);_pNode = _pNode->_pNext;return tmp;}Self& operator--(){_pNode = _pNode->_pPre;return (*this);}Self& operator--(int){Self tmp = (*this);_pNode = _pNode->_pPre;return tmp;}bool operator!=(const Self& l) const{return (this->_pNode != l._pNode);}bool operator==(const Self& l) const{return (this->_pNode == l._pNode);}PNode _pNode;
};

其中Ref代表T的引用，Ptr代表T的指针，根据这两个参数是否被const修饰，我们可以实例化出普通的迭代器和const迭代器：

typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T&> const_iterator;

6. list反向迭代器

与正向迭代器相比，反向迭代器只是在进行++或--的行为与其不同。

我们可以采用适配器模式（stack和queue也是采用该种模式对其他容器进行包装）来实现反向迭代器：

用迭代器作为反向迭代器的底层，通过对正向迭代器的接口进行包装，使其行为满足我们的需求。

template<class iterator>
struct reverseListIterator
{typedef typename iterator::_Ref Ref;typedef typename iterator::_Ptr Ptr;typedef reverseListIterator<iterator> Self;reverseListIterator(iterator it):_it(it){}Ref operator*(){iterator tmp(_it);--tmp;return *tmp;}Ptr operator->(){return &(operator*());}Self& operator++(){--_it;return *this;}Self& operator++(int){Self tmp(*this);--_it;return tmp;}Self& operator--(){++_it;return *this;}Self& operator--(int){Self tmp(*this);++_it;return tmp;}bool operator==(const Self& rit) const{return _it == rit._it;}bool operator!=(const Self& rit) const{return _it != rit._it;}iterator _it;
};

 同理，我们可以定义出普通反向迭代器和const反向迭代器：

typedef reverseListIterator<iterator> reverse_iterator;
typedef reverseListIterator<const_iterator> const_reverse_iterator;

7. list和vector的区别

容器listvector
底层结构带头结点的双向循环链表动态顺序表，一段连续空间
随机访问不支持随机访问，访问某个元素效率O(N)支持随机访问，访问某个元素效率O(N)
插入和删除任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1)

任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容

增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低

空间利用率底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低底层为连续空间，不容易造成内存碎片，空间利用
率高，缓存利用率高
迭代器对原生态指针(节点指针)进行封装原生态指针
迭代器失效插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效
使用场景大量插入和删除操作，不关心随机访问需要高效存储，支持随机访问，不关心插入删除效率

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

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

相关文章

六西格玛绿带培训多少钱

六西格玛绿带培训多少钱

在探讨“六西格玛绿带培训多少钱”这一主题时&#xff0c;我们不得不深入了解六西格玛方法论在企业质量管理中的重要作用&#xff0c;以及绿带培训作为这一方法论推广和应用的关键环节。六西格玛&#xff0c;作为一种以数据驱动的管理哲学和方法论&#xff0c;旨在通过减少缺陷…
阅读更多...
深入理解Java中的clone对象

深入理解Java中的clone对象

目录 1. 为什么要使用clone 2. new和clone的区别 3. 复制对象和复制引用的区别 4.浅克隆和深克隆 5. 注意事项 1. 为什么要使用clone 在实际编程过程中&#xff0c;我们常常遇到这种情况&#xff1a;有一个对象 A&#xff0c;需要一个和 A 完全相同新对象 B&#xff0c;并…
阅读更多...
ModuleNotFoundError: No module named ‘keras.layers.core‘怎么解决

ModuleNotFoundError: No module named ‘keras.layers.core‘怎么解决

问题 ModuleNotFoundError: No module named keras.layers.core&#xff0c;如图所示&#xff1a; 如何解决 将from keras.layers.core import Dense,Activation改为from tensorflow.keras.layers import Dense,Activation&#xff0c;如图所示&#xff1a; 顺利运行&#xf…
阅读更多...
IOS Siri和快捷指令打开app

IOS Siri和快捷指令打开app

使用场景 需要Siri打开应用或者在自定义快捷指令打开应用&#xff0c;并携带内容进入应用。 1.创建Intents文件 1.1 依次点开File->New->File 1.2 搜索intent关键字找到 SiriKit Intent Definition File文件 1.3 找到刚才创建的Intent文件&#xff0c;点击然后New Inte…
阅读更多...
【JS逆向学习】快乐学堂登陆接口（自定义DES加密、ddddocr验证码识别）

【JS逆向学习】快乐学堂登陆接口（自定义DES加密、ddddocr验证码识别）

逆向目标 网址&#xff1a;https://www.91118.com/Passport/Account/Login接口&#xff1a;https://www.91118.com/passport/Account/LoginPost参数&#xff1a; passr 逆向过程 输入手机号、密码、验证码 点击登陆&#xff0c;多试几次&#xff0c;然后观察并比较不通请求…
阅读更多...
MMO 地图传送，UI系统框架设计

MMO 地图传送，UI系统框架设计

地图传送 创建传送点 建碰撞器触发 //位置归零 建一个传送门cube放到要传送的位置&#xff08;这个teleporter1是传出的区域 这是从另一张地图传入时的传送门 创建一个脚本TeleporterObject给每个传送cube都绑上脚本 通过脚本&#xff0c;让传送门在编辑器下面还能绘制出来 …
阅读更多...
GIT | git提交注释自动添加信息头

GIT | git提交注释自动添加信息头

GIT | git提交注释自动添加信息头 时间&#xff1a;2024年9月6日10:20:11 文章目录 GIT | git提交注释自动添加信息头1.操作2.commit-msg文件 1.操作 2.commit-msg文件 #!/bin/sh # # An example hook script to check the commit log message. # Called by "git commit&q…
阅读更多...
基于SpringBoot+Vue+MySQL的流浪猫狗宠物救助救援网站管理系统

基于SpringBoot+Vue+MySQL的流浪猫狗宠物救助救援网站管理系统

系统展示 用户前台界面 管理员后台界面 系统背景 在当今社会&#xff0c;随着宠物数量的激增及人们关爱动物意识的提升&#xff0c;流浪猫狗问题日益严峻。为解决这一问题&#xff0c;构建一套高效、便捷的流浪猫狗宠物救助救援网站管理系统显得尤为重要。本系统基于SpringBoot…
阅读更多...
CSP-CCF★★★201812-2小明放学★★★

CSP-CCF★★★201812-2小明放学★★★

目录 一、问题描述 二、解答 &#xff08;1&#xff09;注意&#xff1a; &#xff08;2&#xff09;80分版&#xff1a; &#xff08;3&#xff09;100分版&#xff1a; 三、总结 一、问题描述 二、解答 &#xff08;1&#xff09;注意&#xff1a; 题目的n小于等于10的…
阅读更多...
m3u8网页视频文件爬取与视频合成

m3u8网页视频文件爬取与视频合成

文章目录 m3u8网页视频文件爬取与视频合成下载m3u8文件下载m3u8文件列表所对应的ts文件下载ffmpeg m3u8网页视频文件爬取与视频合成 我们经常在网络上找到的自己想要的视频素材却无法下载&#xff0c;并且打开控制台一看视频是通过分割成一份份的.ts文件发送过来的。 下载m3u8…
阅读更多...
零信任安全：重新思考数字世界的访问

零信任安全：重新思考数字世界的访问

目录 ​编辑 网络安全形势的演变 数字安全的变化 引入零信任安全 零信任的当今意义 了解零信任原则 零信任架构的核心概念 实施微分段 持续验证&#xff1a;积极主动的立场 与传统安全模型的对比 在现代企业中实施零信任 零信任实施基础知识 多重身份验证 (MFA) 的…
阅读更多...
c++（继承、模板进阶）

c++（继承、模板进阶）

一、模板进阶 1、非类型模板参数 模板参数分类类型形参与非类型形参。 类型形参即&#xff1a;出现在模板参数列表中&#xff0c;跟在class或者typename之类的参数类型名称。 非类型形参&#xff0c;就是用一个常量作为类(函数)模板的一个参数&#xff0c;在类(函数)模板中…
阅读更多...
非监督式机器学习:群集

非监督式机器学习:群集

聚类分析是一种非监督式机器学习形式&#xff0c;在此形式下&#xff0c;基于观察值的数据值或特征的相似性&#xff0c;将观察值分组到群集中。 这种就是非监督式机器学习&#xff0c;因为它不使用先前已知的标签值来训练模型。 在聚类分析模型中&#xff0c;标签是群集&#…
阅读更多...
帧缓冲 framebuffer

帧缓冲 framebuffer

一、基本概念 framebuffer: 帧缓存、帧缓存&#xff08;显示设备&#xff09; Linux内核为显示提供的一套应用程序接口。&#xff08;驱动内核支持&#xff09; 分辨率&#xff1a; 像素点 显示屏&#xff1a;800 * 600&#xff08;横向有800个像素点&#xff0c;纵向有60…
阅读更多...
DAY73

DAY73

作业 pro文件&#xff1a; QT texttospeech 头文件&#xff1a; #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QPushButton> //按钮类 #include <QLabel> //标签类 #include <QLineEdit> //行编译器类 #include…
阅读更多...
阿里中间件——diamond

阿里中间件——diamond

一、前言 最近工作不忙闲来无事&#xff0c;仔细分析了公司整个项目架构&#xff0c;发现用到了很多阿里巴巴集团开源的框架&#xff0c;今天要介绍的是中间件diamond. 二、diamond学习笔记 1、diamond简介 diamond是一个管理持久配置&#xff08;持久配置是指配置数据会持久化…
阅读更多...
【Datawhale X 李宏毅苹果书 AI夏令营】《深度学习详解》Task3 打卡

【Datawhale X 李宏毅苹果书 AI夏令营】《深度学习详解》Task3 打卡

文章目录 前言学习目标一、优化策略二、模型偏差三、优化问题三、过拟合增加训练集给模型一些限制 四、交叉验证五、不匹配总结 前言 本文是【Datawhale X 李宏毅苹果书 AI夏令营】的Task3学习笔记打卡。 学习目标 李宏毅老师对应视频课程&#xff1a;https://www.bilibili.…
阅读更多...
QDY421F-16P-25液氨不锈钢液动紧急切断阀

QDY421F-16P-25液氨不锈钢液动紧急切断阀

一、产品概述 QDY421F-16P-25液氨不锈钢液动紧急切断阀&#xff0c;采用先进的液动驱动技术&#xff0c;结合高质量的不锈钢材质&#xff0c;专为满足液氨等腐蚀性介质的紧急切断需求而设计。该阀门的工作压力可达16MPa&#xff0c;适用于DN25&#xff08;即25毫米&#xff09;…
阅读更多...
系统架构师考试学习笔记第四篇——架构设计实践知识（18）面向服务架构设计理论与实践

系统架构师考试学习笔记第四篇——架构设计实践知识（18）面向服务架构设计理论与实践

本章考点&#xff1a; 第18课时主要学习面向服务架构设计理论与实践。根据考试大纲&#xff0c;本课时知识点会涉及单选题型&#xff08;约占2~5分&#xff09;和案例题&#xff08;25分&#xff09;&#xff0c;本课时内容偏重于方法的掌握和应用&#xff0c;根据以往全国计算…
阅读更多...
时序预测|基于小龙虾优化高斯过程GPR数据回归预测Matlab程序COA-GPR 多特征输入单输出 附赠基础GPR

时序预测|基于小龙虾优化高斯过程GPR数据回归预测Matlab程序COA-GPR 多特征输入单输出 附赠基础GPR

时序预测|基于小龙虾优化高斯过程GPR数据回归预测Matlab程序COA-GPR 多特征输入单输出 附赠基础GPR 文章目录 一、基本原理二、实验结果三、核心代码四、代码获取五、总结 时序预测|基于小龙虾优化高斯过程GPR数据回归预测Matlab程序COA-GPR 多特征输入单输出 附赠基础GPR 一、…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发