【C++学习手札】模拟实现list

2024-03-07 13:30
文章标签 c++ 实现 学习 模拟 list 手札

本文主要是介绍【C++学习手札】模拟实现list，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

​

                                                      🎬慕斯主页：修仙—别有洞天

                                                       ♈️今日夜电波：リナリア—まるりとりゅうが

                                                                0:36━━━━━━️💟──────── 3:51
                                                                    🔄   ◀️   ⏸   ▶️    ☰ 

                                      💗关注👍点赞🙌收藏您的每一次鼓励都是对我莫大的支持😍

目录

一、list实际的底层原理

二、list的模拟实现

         写在前面

各层封装的实现

        节点类

        迭代器类 

        list类 

list类详解 

        迭代器实现

list的修改操作

        Insert 

        erase

        swap 

        复用操作（push_back/front、pop_back/front、clear）

list的构造

        建立头节点

        构造函数

        拷贝构造和‘=’重载

        析构函数 

list的空间管理

list的访问相关

三、整体代码 

一、list实际的底层原理

        C++的STL库中的list是使用带头的双向循环链表实现的。list中存储的每个元素包含了两个指针，一个指向前一个节点，一个指向后一个节点，这样就可以方便地在list中进行插入和删除操作，这些操作的时间复杂度都是O(1)。

         大致的结构如下：​

         如多大家对于这个数据结构不太熟悉的话，不妨看看作者之前写的一篇关于带头双向循环链表的文章：🌀【数据结构】—C语言实现双向链表（超详细!） 

二、list的模拟实现

         写在前面

        list的底层虽然是带头双向循环链表，但是对于它的实际实现不只是简单的链表而已，当然了，我们肯定会有链表的数据结构。但是，这个“结构”，经过了三层的封装才得以实现，分别是：  第一层：list的节点类

                第二层：list的迭代器类

                第三层：list类

        本文目前只实现正向的迭代器，反向迭代器会在后面的文章统一vector、string、list一起实现。

各层封装的实现

         节点类

        主要是包括：对于两个双向指针的定义以及数据的定义，再是通过初始化列表对于节点的初始化。

    // 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;};

        迭代器类 

         迭代器实际上是对于指针进行操作，因此我们实例化并且重新命名了节点类的指针PNode,由于迭代器分为是否常量正向迭代器，对此我们额外定义了两个模板参数Ref、Ptr用于控制其中重载运算符 T& operator*() 和 T* operator->()。后面的list类中会有体现。在迭代器中，其中，operator*和operator->返回指向节点的指针，operator++和operator--实现前后缀++/--运算符，operator==和operator!=用来比较两个迭代器是否指向同一个节点。

    //List的迭代器类template<class T, class Ref, class Ptr>class ListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;public:ListIterator(PNode pNode = nullptr):_pNode(pNode){}ListIterator(const Self& l):_pNode(l._pNode){}//T& operator*()//{//	return _pNode->_val;//}//T* operator->()//{//	return &*this;//}Ref operator*(){return _pNode->_val;}Ptr operator->(){return &*this;}Self& operator++(){_pNode = _pNode->_pNext;return *this;}Self operator++(int){Self temp(*this);_pNode = _pNode->_pNext;return temp;}Self& operator--(){_pNode = _pNode->_pPre;return *this;}Self& operator--(int){Self temp(*this);_pNode = _pNode->_pPre;return temp;}bool operator!=(const Self& l){return _pNode != l._pNode;}bool operator==(const Self& l){return !(*this != l);}private:PNode _pNode;};

        list类 

        这里先给出主要的封装，具体的实现后面详解。可以看到我们又对于节点类进行了实例化并且重新命名，并且定义了一个数据变量。下面是重点了：我们对于迭代器类也进行了实例化并且重新命名，特别是对于上面我们所提到的Ref和Ptr是有做变动的注意看：对于是否常量正向迭代器分别做出了如下定义：T&, T*和const T&, const T*。这里所这的一些变动也是为了后续简化代码，避免我们因为动静态多一份代码。

        请结合上面我们迭代器类中我们所提到的operator==和operator!=理解。

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;//静态迭代器重命名public://...private:PNode _pHead;};

list类详解 

        在C++中我们通常会进行各类函数的复用，以减少代码量和增加可读性。对此，我们尽量做到复用。

         迭代器实现

        返回头以及尾的迭代器，注意区分动静态 。

        // 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);}

 list的修改操作

        Insert 

         实现在pos位置前插入值为val的节点，开辟空间->保存原位置节点->新节点的前指针指向原节点的前一个节点->后节点指向原节点->该边原节点的前一个节点的后指针指向，指向新节点->原节点的前指针指向新节点->返回性节点的迭代器。

// 在pos位置前插入值为val的节点iterator insert(iterator pos, const T& val){PNode pNewNode = new Node(val);PNode pCur = pos._pNode;pNewNode->_pPre = pCur->_pPre;pNewNode->_pNext = pCur;pNewNode->_pPre->_pNext = pNewNode;pCur->_pPre = pNewNode;return iterator(pNewNode);}

         erase

         删除pos位置的节点，返回该节点的下一个位置，保存删除j节点，保存原节点的下一个节点（用于返回）->一些列删除解链接操作->返回原节点的下一个节点的迭代器

        // 删除pos位置的节点，返回该节点的下一个位置iterator erase(iterator pos){PNode pDel = pos._pNode;PNode pRet = pDel->_pNext;pDel->_pPre->_pNext = pDel->_pNext;pDel->_pNext->_pPre = pDel->_pPre;delete pDel;return iterator(pRet);}

        swap 

        void swap(list<T>& l){pNode tmp = _pHead;_pHead = l._pHead;l._pHead = tmp;}

         复用操作（push_back/front、pop_back/front、clear）

        void 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());}void clear(){iterator p = begin();while (p != end()){p = erase(p);}_pHead->_pPre = _pHead;_pHead->_pNext = _pHead;}

 list的构造

         建立头节点

        因为我们在构造、 拷贝等很多的场景中都会用到对于头结点的初始化，对此额外写一个函数用于减少代码量。

        void CreateHead(){_pHead = new Node;_pHead->_pPre = _pHead;_pHead->_pNext = _pHead;}

         构造函数

        实现无参、含参初始化、迭代器构造。

        // List的构造list(){CreateHead();}list(int n, const T& value = T()){CreateHead();for (int i = 0; i < n; ++i){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<T> temp(l.begin(), l.end());this->swap(temp);}list<T>& operator=(const list<T> l){this->swap(l);return *this;}

        析构函数 

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

 list的空间管理

        size_t size()const{size_t size = 0;ListNode* p = _pHead->_pNext;while (p != _pHead){size++;p = p->_pNext;}return size;}bool empty()const{return size() == 0;}

list的访问相关

        主要还是要区分是否为动静态相关。

        T& front(){assert(!empty());return _pHead->_pNext->_val;}const T& front()const{assert(!empty());return _pHead->_pNext->_val;}T& back(){assert(!empty());return _pHead->_pPre->_val;}const T& back()const{assert(!empty());return _pHead->_pPre->_val;}

三、整体代码 

#pragma once
#include<iostream>
#include<assert.h>using namespace std;namespace lt
{// 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>class ListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;public:ListIterator(PNode pNode = nullptr):_pNode(pNode){}ListIterator(const Self& l):_pNode(l._pNode){}T& operator*(){return _pNode->_val;}T* operator->(){return &*this;}Self& operator++(){_pNode = _pNode->_pNext;return *this;}Self operator++(int){Self temp(*this);_pNode = _pNode->_pNext;return temp;}Self& operator--(){_pNode = _pNode->_pPre;return *this;}Self& operator--(int){Self temp(*this);_pNode = _pNode->_pPre;return temp;}bool operator!=(const Self& l){return _pNode != l._pNode;}bool operator==(const Self& l){return !(*this != l);}private:PNode _pNode;};//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;//静态迭代器重命名public:///// List的构造list(){CreateHead();}list(int n, const T& value = T()){CreateHead();for (int i = 0; i < n; ++i){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<T> temp(l.begin(), l.end());this->swap(temp);}list<T>& operator=(const list<T> l){this->swap(l);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);}///// List Capacitysize_t size()const{size_t size = 0;ListNode* p = _pHead->_pNext;while (p != _pHead){size++;p = p->_pNext;}return size;}bool empty()const{return size() == 0;}// List AccessT& front(){assert(!empty());return _pHead->_pNext->_val;}const T& front()const{assert(!empty());return _pHead->_pNext->_val;}T& back(){assert(!empty());return _pHead->_pPre->_val;}const T& back()const{assert(!empty());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 pNewNode = new Node(val);PNode pCur = pos._pNode;pNewNode->_pPre = pCur->_pPre;pNewNode->_pNext = pCur;pNewNode->_pPre->_pNext = pNewNode;pCur->_pPre = pNewNode;return iterator(pNewNode);}// 删除pos位置的节点，返回该节点的下一个位置iterator erase(iterator pos){PNode pDel = pos._pNode;PNode pRet = pDel->_pNext;pDel->_pPre->_pNext = pDel->_pNext;pDel->_pNext->_pPre = pDel->_pPre;delete pDel;return iterator(pRet);}void clear(){iterator p = begin();while (p != end()){p = erase(p);}_pHead->_pPre = _pHead;_pHead->_pNext = _pHead;}void swap(list<T>& l){pNode tmp = _pHead;_pHead = l._pHead;l._pHead = tmp;}private:void CreateHead(){_pHead = new Node;_pHead->_pPre = _pHead;_pHead->_pNext = _pHead;}PNode _pHead;};
};

                        感谢你耐心的看到这里ღ( ´･ᴗ･` )比心，如有哪里有错误请踢一脚作者o(╥﹏╥)o！ 

                                       

                                                                         给个三连再走嘛~  

这篇关于【C++学习手札】模拟实现list的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/783671。

相关文章

分布式锁在Spring Boot应用中的实现过程

分布式锁在Spring Boot应用中的实现过程

《分布式锁在SpringBoot应用中的实现过程》文章介绍在SpringBoot中通过自定义Lock注解、LockAspect切面和RedisLockUtils工具类实现分布式锁,确保多实例并发操作... 目录Lock注解LockASPect切面RedisLockUtils工具类总结在现代微服务架构中，分布
阅读更多...
Java使用Thumbnailator库实现图片处理与压缩功能

Java使用Thumbnailator库实现图片处理与压缩功能

《Java使用Thumbnailator库实现图片处理与压缩功能》Thumbnailator是高性能Java图像处理库,支持缩放、旋转、水印添加、裁剪及格式转换,提供易用API和性能优化,适合Web应... 目录1. 图片处理库Thumbnailator介绍2. 基本和指定大小图片缩放功能2.1 图片缩放的
阅读更多...
Python使用Tenacity一行代码实现自动重试详解

Python使用Tenacity一行代码实现自动重试详解

《Python使用Tenacity一行代码实现自动重试详解》tenacity是一个专为Python设计的通用重试库,它的核心理念就是用简单、清晰的方式,为任何可能失败的操作添加重试能力,下面我们就来看... 目录一切始于一个简单的 API 调用Tenacity 入门：一行代码实现优雅重试精细控制：让重试按我
阅读更多...
Redis客户端连接机制的实现方案

Redis客户端连接机制的实现方案

《Redis客户端连接机制的实现方案》本文主要介绍了Redis客户端连接机制的实现方案,包括事件驱动模型、非阻塞I/O处理、连接池应用及配置优化,具有一定的参考价值,感兴趣的可以了解一下... 目录1. Redis连接模型概述2. 连接建立过程详解2.1 连php接初始化流程2.2 关键配置参数3. 最大连
阅读更多...
Python实现网格交易策略的过程

Python实现网格交易策略的过程

《Python实现网格交易策略的过程》本文讲解Python网格交易策略,利用ccxt获取加密货币数据及backtrader回测,通过设定网格节点,低买高卖获利,适合震荡行情,下面跟我一起看看我们的第一... 网格交易是一种经典的量化交易策略，其核心思想是在价格上下预设多个“网格”，当价格触发特定网格时执行买
阅读更多...
python设置环境变量路径实现过程

python设置环境变量路径实现过程

《python设置环境变量路径实现过程》本文介绍设置Python路径的多种方法：临时设置（Windows用`set`,Linux/macOS用`export`）、永久设置（系统属性或shell配置文件... 目录设置python路径的方法临时设置环境变量（适用于当前会话）永久设置环境变量（Windows系统
阅读更多...
python运用requests模拟浏览器发送请求过程

python运用requests模拟浏览器发送请求过程

《python运用requests模拟浏览器发送请求过程》模拟浏览器请求可选用requests处理静态内容,selenium应对动态页面,playwright支持高级自动化,设置代理和超时参数,根据需... 目录使用requests库模拟浏览器请求使用selenium自动化浏览器操作使用playwright
阅读更多...
C++11范围for初始化列表auto decltype详解

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3
阅读更多...
C++11右值引用与Lambda表达式的使用

C++11右值引用与Lambda表达式的使用

《C++11右值引用与Lambda表达式的使用》C++11引入右值引用,实现移动语义提升性能,支持资源转移与完美转发；同时引入Lambda表达式,简化匿名函数定义,通过捕获列表和参数列表灵活处理变量... 目录C++11新特性右值引用和移动语义左值 / 右值常见的左值和右值移动语义移动构造函数移动复制运算符
阅读更多...
Python对接支付宝支付之使用AliPay实现的详细操作指南

Python对接支付宝支付之使用AliPay实现的详细操作指南

《Python对接支付宝支付之使用AliPay实现的详细操作指南》支付宝没有提供PythonSDK,但是强大的github就有提供python-alipay-sdk,封装里很多复杂操作,使用这个我们就... 目录一、引言二、准备工作2.1 支付宝开放平台入驻与应用创建2.2 密钥生成与配置2.3 安装ali
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2