初识《list》及手搓模拟《list》

news/2024/10/18 16:54:05/

目录

前言：

list%E7%9A%84%E4%BB%8B%E7%BB%8D%E5%8F%8A%E4%BD%BF%E7%94%A8-toc" style="margin-left:0px;">1. list的介绍及使用

list%E7%9A%84%E4%BB%8B%E7%BB%8D%EF%BC%9A-toc" style="margin-left:40px;">list的介绍：

list%E7%9A%84%E4%BD%BF%E7%94%A8%EF%BC%9A-toc" style="margin-left:40px;">list的使用：

list%E7%9A%84%E6%9E%84%E9%80%A0%E2%80%8B%E7%BC%96%E8%BE%91-toc" style="margin-left:80px;">1、list的构造​编辑

list%20iterator%E7%9A%84%E4%BD%BF%E7%94%A8-toc" style="margin-left:80px;">2、list iterator的使用

list%20capacity-toc" style="margin-left:80px;">3、list capacity

list%20element%20access-toc" style="margin-left:80px;">4、list element access

list%20modifiers-toc" style="margin-left:80px;">5、list modifiers

list%E7%9A%84%E6%A8%A1%E6%8B%9F%E5%AE%9E%E7%8E%B0-toc" style="margin-left:0px;">2.list的模拟实现

1、关于迭代器：

2、迭代器类的封装：

 3、模板为类的时候：

4、关于const迭代器：

一：而额外封装一个const迭代器。const_iterator

二：利用模板

list%E7%9A%84%E5%8C%BA%E5%88%AB%EF%BC%9A-toc" style="margin-left:0px;">3.vector与list的区别：

总结：

前言：

现阶段我们已经逐渐熟悉了各个STL库中的容器，对于他们的各个接口都大差不差，在我们学习完vector之后我们就可以陆陆续续接触一些算法题。我们的《好题分析》这一专栏也会不断的进行更新！下面我们先来熟悉以下list这个容器。

list%E7%9A%84%E4%BB%8B%E7%BB%8D%E5%8F%8A%E4%BD%BF%E7%94%A8">1. list的介绍及使用

list%E7%9A%84%E4%BB%8B%E7%BB%8D%EF%BC%9A">list的介绍：

  1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
  2. list的底层是双向带头链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
  3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
  4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
  5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

list%E7%9A%84%E4%BD%BF%E7%94%A8%EF%BC%9A">
list的使用：

list%E7%9A%84%E6%9E%84%E9%80%A0%E2%80%8B%E7%BC%96%E8%BE%91">1、list的构造

list%20iterator%E7%9A%84%E4%BD%BF%E7%94%A8">2、list iterator的使用

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

 

注意！！

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

list%20capacity">3、list capacity

list%20element%20access">4、list element access

list%20modifiers">5、list modifiers

 6、list的迭代器失效

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

void TestListIterator1()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));auto it = l.begin();while (it != l.end()){// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，// 必须先给其赋值l.erase(it);++it;}
}// 改正
void TestListIterator()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));auto it = l.begin();while (it != l.end()){l.erase(it++); // it = l.erase(it);}
}

list%E7%9A%84%E6%A8%A1%E6%8B%9F%E5%AE%9E%E7%8E%B0" style="background-color:transparent;">2.list的模拟实现

1、关于迭代器：

我们对list的迭代器的理解与我们之前对于string 和 vector中的iterator的理解有十分大的区别。string和vector的迭代器我们可以替换理解为指针，在我们遍历vector或者string时，仅需要对++运算符进行重载，我们就可以拿到下一个位置的值，而operator++()也很好理解，就是指针+1指向下一个下标的位置。

但是这次我们的list就大有不同，我们都知道list是一个带头的双向链表，而想要获得下一个结点的数据，应当是node = node -> next; 如果我们将运算符++重载为这个代码，那对于其它的代码想要运用++操作符，就纯粹扯淡。

这个时候的唯一解决方法就是————————封装一个类！！！

2、迭代器类的封装：

// 一个结点的结构！！！
template<class T>
struct ListNode
{T _data;ListNode<T>* _next;ListNode<T>* _prev;ListNode(const T& x = T()):_next(nullptr), _prev(nullptr), _data(x){}
};// 将迭代器封装成一个类
template<class T>
struct ListIterator
{typedef ListIterator<T> Self;typedef ListNode<T> Node;Node* _node;// iteratorListConstIterator(Node* node):_node(node){}bool operator != (const Self& it){return _node != it._node;}Self& operator++(){_node = _node->_next;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}Self operator--(){Self tmp(*this);_node = _node->_prev;return tmp;}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}
};

我们在之后的项目中，如果发现我们目前处理的数据中的内置类型不满足我们的需求，不妨我们可以将其封装成一个类！！！

首先我们先通过画图得方式来理解代码：


 因为这个iterator类我们并不会定义私有成员，所以我们这里用的struct来定义。

而我们在整个链表的总体类中，我们需要先找到两个 头 和 尾 结点的位置，即begin 和 end.

	iterator begin(){return iterator(_head->_next); // 匿名对象// iterator it(_head->_next); // 调用 iterator类 里面的 构造函数// return it;}iterator end(){return iterator(_head); // 匿名对象// iterator it(_head); // 调用 iterator类 里面的 构造函数// return it;}

 

 3、模板为类的时候：

想要去到_a1, 若是不进行函数重载, 则代码为:

list<A>::iterator it = ls.begin();
std::cout << it._node->_data._a1 << " " << it._node->_data._a2 << std::endl;
it++;
std::cout << it._node->_data._a1 << " " << it._node->_data._a2 << std::endl;

很明显代码非常的冗长和麻烦, 因此我们可以利用函数重载:

T* operator->()
{return &_node->_data;
}
list<A>::iterator it = ls.begin();
std::cout << it->_a1 << " " << it->_a2 << std::endl;
it++;
std::cout << it->_a1 << " " << it->_a2 << std::endl;

it.operator->()->_a1 
在这里编译器会自动优化代码，将代码的可读性提高。
it->_a1    <==>   it.operator->()->_a1     <==>      it->->_a1
通过公式推导，我们不难发现 it->_a1  <==>    it->->_a1    这两个式子是等价的

4、关于const迭代器：

const迭代器，需要的是迭代器指向的内容不能被修改而const iteratror 作返回值时，代表了迭代器的指向不可被修改。

一：而额外封装一个const迭代器。const_iterator

在我们实施这个方法后，我们会发现仅仅只有Self& operator*() 和 Self* operator->()的返回值是需要加const，其它的都不变

 //对于每一个容器来说，都有存在const的类型接口，因此我们也需要创建一个const迭代器。//（运用const主要还是 防止 在进行 拷贝构造 或者 ++ -- 等出现 修改一个 const链表的情况。）
template<class T>
struct List_const_iterator
{typedef ListNode<T> Node;typedef List_const_iterator<T> Self;Node* _node;// 最重要的一行代码，代表在 List_iterator 类中 封装一个 _node 用来指向结点，通过在类里面// 控制运算符重载来操纵迭代器List_const_iterator(Node* node) // 传值构造:_node(node){}// ++itSelf& operator++(){_node = _node->_next;return *this;}// it++Self operator++(int){Self tmp(*this); // 无需写拷贝构造函数， 默认的 浅拷贝 即可完成操作_node = _node->_next;return *this;}// *itconst T& operator*(){return _node->_data;}// it->_data，此时的 _data 是结构体时才调用const T* operator->(){return &_node->_data;}bool operator!=(const Self& it){return _node != it._node;}};

 

因此我们没必要多此一举。

二：利用模板

// 我们在创建 const_iterator 迭代器时发现在整个类中，仅仅只是对 operator*() 与 operator->() 的返回值进行了修改
// 为了尽可能的减少代码量，利用模板是一个不错的选择。
// Ref == reference    ,    Prt == pointer
//                      T&         T* 
template<class T, class Ref, class Ptr> 
//template<class T>
struct List_iterator
{typedef ListNode<T> Node;typedef List_iterator<T, Ref, Ptr> Self;Node* _node;// 最重要的一行代码，代表在 List_iterator 类中 封装一个 _node 用来指向结点，通过在类里面// 控制运算符重载来操纵迭代器List_iterator(Node* node) // 传值构造:_node(node){}// ++itSelf& operator++(){_node = _node->_next;return *this;}// it++Self operator++(int){Self tmp(*this); // 无需写拷贝构造函数， 默认的 浅拷贝 即可完成操作_node = _node->_next;return *this;}// *it 返回类型为T&Ref operator*(){return _node->_data;}// it->_data，此时的 _data 是结构体时才调用, 返回类型为T*Ptr operator->(){return &_node->_data;}bool operator!=(const Self& it){return _node != it._node;}};

 在list类中：

 template<class T>class list{public:typedef ListNode<T> Node;typedef List_iterator<T, T&, T*> iterator;typedef List_iterator<T, const T&, const T*> const_iterator;//typedef List_const_iterator<T> const_iterator;// 构造函数创建 哨兵位 的头结点

 利用模板是最高效的方法！！！

list%E7%9A%84%E5%8C%BA%E5%88%AB%EF%BC%9A">3.vector与list的区别：

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：

总结：

本文的代码思路与之前大为不同，本次首先接触到了利用类封装一个迭代器。


http://www.ppmy.cn/news/1425357.html

相关文章

鸿蒙原生应用元服务-访问控制（权限）开发场景与权限声明

鸿蒙原生应用元服务-访问控制（权限）开发场景与权限声明

一、场景介绍 应用的APL&#xff08;Ability Privilege Level&#xff09;等级分为normal、system_basic和system_core三个等级&#xff0c;默认情况下&#xff0c;应用的APL等级都为normal等级。权限类型分为system_grant和user_grant两种类型。 二、配置文件权限声明 应用需要…
阅读更多...
Vue3+Ant Design 父组件调用子组件方法

Vue3+Ant Design 父组件调用子组件方法

父组件代码 <template><search-module-date ref"rangeDateRef" :option"rangeDateOption" callBackFun"onRangeChange" /><a-button type"default" click"reset">重置</a-button> </template&g…
阅读更多...
深度学习知识点：循环神经网络（RNN）、长短期记忆网络（LSTM）、门控循环单元（GRU）

深度学习知识点：循环神经网络（RNN）、长短期记忆网络（LSTM）、门控循环单元（GRU）

深度学习知识点&#xff1a;循环神经网络&#xff08;RNN&#xff09;、长短期记忆网络&#xff08;LSTM&#xff09;、门控循环单元&#xff08;GRU&#xff09; 前言循环神经网络&#xff08;RNN&#xff09;RNNs&#xff08;循环神经网络&#xff09;训练和传统ANN&#xff…
阅读更多...
洛谷P1057 [NOIP2008 普及组] 传球游戏

洛谷P1057 [NOIP2008 普及组] 传球游戏

#include<iostream> using namespace std; int n;// n个人传球游戏 默认开始球在编号为1的位置 int m;// 传递m次球 int main(){cin>>n>>m;// 动态转方程&#xff1a;// 球传递到编号为k人的手中// 种类总数 传递到k-1编号种类总数 传递到k1编号种类总数//…
阅读更多...
ASP.NET MVC企业级程序设计 (接上个作品加了添加)

ASP.NET MVC企业级程序设计 (接上个作品加了添加)

效果图 实现过程 控制器代码 using System; using System.Collections.Generic; using System.Linq; using System.Web; using System.Web.Mvc; using MvcApplication1.Models; namespace MvcApplication1.Controllers {public class HomeController : Controller{//// GET:…
阅读更多...
JIT在汽车行业中的革命性应用：颠覆传统制造模式，引领智能制造新时代

JIT在汽车行业中的革命性应用：颠覆传统制造模式，引领智能制造新时代

随着科技的飞速发展和市场竞争的日益激烈&#xff0c;汽车行业正面临着前所未有的变革。其中&#xff0c;准时制生产&#xff08;Just-In-Time&#xff0c;简称JIT&#xff09;作为一种先进的生产管理方式&#xff0c;已经在汽车行业中得到了广泛应用&#xff0c;成为推动汽车产…
阅读更多...
Vast+产品展厅 | Vastbase G100数据库是什么架构？(1)

Vast+产品展厅 | Vastbase G100数据库是什么架构？(1)

Vastbase G100是海量数据融合了多年对各行业应用场景的深入理解&#xff0c;基于openGauss内核开发的企业级关系型数据库。 了解Vastbase G100的架构&#xff0c;可以帮助您确保数据库系统的高效、可靠和安全运行。 “Vast产品展厅”将分两期&#xff0c;为您详细讲解Vastbas…
阅读更多...
【leetcode面试经典150题】61. 反转链表 II（C++）

【leetcode面试经典150题】61. 反转链表 II（C++）

【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主&#xff0c;题解使用C语言。&#xff08;若有使用其他语言的同学也可了解题解思路&#xff0c;本质上语法内容一致&…
阅读更多...
最新文章

Copyright @ 2022~2023