(C++ STL)list类的简单模拟实现与源码展示

2024-09-04 00:12
文章标签 简单 c++ 实现 源码 模拟 展示 list stl

本文主要是介绍(C++ STL)list类的简单模拟实现与源码展示，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

list类的简单模拟实现

  • 一、前言
  • 二、ListNode 单个节点的成员变量
  • 三、ListIterator 迭代器
  • 四、ReverseListIterator 迭代器
  • 五、list 的成员变量与初始化
  • 六、list 部分函数实现
    • insert
    • erase
  • 七、list 源代码

以下代码环境为 VS2022 C++。

一、前言

list类 本质上是数据结构中的双向带头链表。（可参考：双向链表的讲解与实现）

不过要注意的是，list类 的本身并不支持随机访问，迭代器要求的前后 ++、-- 也不支持，导致这个重担交给了 list 的迭代器，使得它迭代器的设计要比 vector、string 的复杂不少。

接下来我们来简单实现 list类 和 部分对应函数。

参考：legacy.cplusplus.com中的 std::list

二、ListNode 单个节点的成员变量

在 list.hpp 中：

namespace my
{// List的节点类template<class T>struct ListNode{ListNode(const T& val = T()):_val(val),_pPrev(nullptr),_pNext(nullptr){;}ListNode<T>* _pPrev;	// 前一个节点地址ListNode<T>* _pNext;	// 后一个节点地址T _val;};
}

将 list 的节点单独封装为一个类，便于后续组合操作。

三、ListIterator 迭代器

在 namespace my 中：

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

ListIterator 设计了三个模版关键字，class T, class Ref, class Ptr，这是考虑到 const_iterator 的返回类型。

例如：当返回 operator*() 的返回值时，使用 iterator 返回的是 T 的 引用，也就是 T&，
但使用 const_iterator 返回的是 const T&，两者只差一个 const 权限。pointer、Self 同理。

当然，也可以选择重新设计一个 const_iterator类，这里只是用模版减少了工作量。

四、ReverseListIterator 迭代器

在 namespace my 中：

    // 反向迭代器template<class Iter>struct ReverseListIterator{typedef ReverseListIterator<Iter> Self;typedef typename Iter::reference reference;typedef typename Iter::pointer pointer;ReverseListIterator(const Iter& it = Iter()):_it(it){;}ReverseListIterator(const Self& listIter):_it(listIter._it){;}reference operator*(){return *_it;}reference operator*() const{return *_it;}pointer operator->(){return _it->_val;}pointer operator->() const{return _it->_val;}Self& operator++(){--_it;return *this;}Self operator++(int){Self temp = *this;--_it;return temp;}Self& operator--(){++_it;return *this;}Self operator--(int){Self temp = *this;++_it;return temp;}bool operator!=(const Self& listIter) const{return (*_it) != (*listIter._it);}bool operator==(const Self& listIter) const{return (*_it) == (*listIter._it);}Iter _it;};

反向迭代器组合了 ListIterator类，毕竟 iterator 的 + + 等价 reverse_iterator 的 - -，而它的 - - 等价 reverse_iterator 的 + +。

五、list 的成员变量与初始化

在 namespace my 中：

    template<class T>class list{public:typedef ListNode<T>* PNode;typedef ListNode<T> Node;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;private:PNode CreateNode(const T& value = T()){return new Node(value);}PNode CreateHead(){PNode temp = CreateNode();temp->_pNext = temp;temp->_pPrev = temp;return temp;}PNode _pHead = CreateHead();	// 走初始化列表时会执行size_t _size;};

考虑到 list类 必须要带头，这里直接声明在初始化时候带头，方便后续操作。

六、list 部分函数实现

insert

这里只实现一个。

参考：std::list::insert

在 list.hpp 中：

template<typename T>
typename my::list<T>::iterator my::list<T>::insert(my::list<T>::iterator pos, const T& val)
{PNode cur = pos._pNode;PNode prev = pos._pNode->_pPrev;PNode newNode = CreateNode(val);newNode->_pPrev = prev;newNode->_pNext = cur;prev->_pNext = newNode;cur->_pPrev = newNode;++_size;return newNode;
}

erase

参考：std::list::erase

这里只实现一个。

在 list.hpp 中：

template<typename T>
typename my::list<T>::iterator my::list<T>::erase(my::list<T>::iterator pos)
{PNode cur = pos._pNode;PNode prev = cur->_pPrev;PNode next = cur->_pNext;prev->_pNext = next;next->_pPrev = prev;--_size;delete cur;pos = nullptr;return next;
}

其他实现了的函数不是复用就是代码量小，就不单独拎出来介绍了。

七、list 源代码

#pragma once#include<iostream>namespace my
{// List的节点类template<class T>struct ListNode{ListNode(const T& val = T()):_val(val),_pPrev(nullptr),_pNext(nullptr){;}ListNode<T>* _pPrev;	// 前一个节点地址ListNode<T>* _pNext;	// 后一个节点地址T _val;};//List的迭代器类template<class T, class Ref, class Ptr>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;typedef Ref reference;typedef Ptr pointer;ListIterator(Node* pNode = nullptr):_pNode(pNode){;}ListIterator(const Self& listIter):_pNode(listIter._pNode){;}reference operator*(){return _pNode->_val;}reference operator*() const{return _pNode->_val;}pointer operator->(){return &_pNode->_val;}pointer operator->() const{return &_pNode->_val;}Self& operator++(){_pNode = _pNode->_pNext;return *this;}Self operator++(int){Self temp = _pNode;_pNode = _pNode->_pNext;return temp;}Self& operator--(){_pNode = _pNode->_pPrev;return *this;}Self operator--(int){Self temp = _pNode;_pNode = _pNode->_pPrev;return temp;}bool operator!=(const Self& listIter) const{return _pNode->_val != listIter._pNode->_val;}bool operator==(const Self& listIter) const{return _pNode->_val == listIter._pNode->_val;}Node* _pNode;};// 反向迭代器template<class Iter>struct ReverseListIterator{typedef ReverseListIterator<Iter> Self;typedef typename Iter::reference reference;typedef typename Iter::pointer pointer;ReverseListIterator(const Iter& it = Iter()):_it(it){;}ReverseListIterator(const Self& listIter):_it(listIter._it){;}reference operator*(){return *_it;}reference operator*() const{return *_it;}pointer operator->(){return _it->_val;}pointer operator->() const{return _it->_val;}Self& operator++(){--_it;return *this;}Self operator++(int){Self temp = *this;--_it;return temp;}Self& operator--(){++_it;return *this;}Self operator--(int){Self temp = *this;++_it;return temp;}bool operator!=(const Self& listIter) const{return (*_it) != (*listIter._it);}bool operator==(const Self& listIter) const{return (*_it) == (*listIter._it);}Iter _it;};//list类template<class T>class list{public:typedef ListNode<T>* PNode;typedef ListNode<T> Node;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(int n, const T& value = T()){for (int i = 0; i < n; ++i){push_back(value);}}list(std::initializer_list<T> il){for (const auto& e : il){push_back(e);}}template <class Iterator>list(Iterator first, Iterator last){while (first != last){push_back(*first);++first;}}list(const list<T>& list1){for (auto& e : list1){push_back(e);}}static void swap(list<T> list1, list<T> list2){std::swap(list1._pHead, list2._pHead);std::swap(list1._size, list2._size);}list<T>& operator=(list<T> list1){swap(*this, list1);return *this;}~list(){clear();delete _pHead;_pHead = nullptr;}//-----------------------------------------------iterator begin(){return _pHead->_pNext;}iterator end(){return _pHead;}const_iterator begin() const{return _pHead->_pNext;}const_iterator end() const{return _pHead;}reverse_iterator rbegin(){return iterator(_pHead->_pPrev);}reverse_iterator rend(){return iterator(_pHead);}const_reverse_iterator rbegin() const{return const_iterator(_pHead->_pPrev);}const_reverse_iterator rend() const{return const_iterator(_pHead);}//-----------------------------------------------size_t size() const{return _size;}bool empty() const{return _size == 0;}//-----------------------------------------------T& front(){return _pHead->_pNext;}const T& front()const{return _pHead->_pNext;}T& back(){return _pHead->_pPrve;}const T& back() const{return _pHead->_pPrve;}//-----------------------------------------------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());}iterator insert(iterator pos, const T& val);iterator erase(iterator pos);void clear(){iterator it = begin();while (it != end()){it = erase(it);}}private:PNode CreateNode(const T& value = T()){return new Node(value);}PNode CreateHead(){PNode temp = CreateNode();temp->_pNext = temp;temp->_pPrev = temp;return temp;}PNode _pHead = CreateHead();size_t _size;};
};template<typename T>
typename my::list<T>::iterator my::list<T>::insert(my::list<T>::iterator pos, const T& val)
{PNode cur = pos._pNode;PNode prev = pos._pNode->_pPrev;PNode newNode = CreateNode(val);newNode->_pPrev = prev;newNode->_pNext = cur;prev->_pNext = newNode;cur->_pPrev = newNode;++_size;return newNode;
}template<typename T>
typename my::list<T>::iterator my::list<T>::erase(my::list<T>::iterator pos)
{PNode cur = pos._pNode;PNode prev = cur->_pPrev;PNode next = cur->_pNext;prev->_pNext = next;next->_pPrev = prev;--_size;delete cur;pos = nullptr;return next;
}

这篇关于(C++ STL)list类的简单模拟实现与源码展示的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

基于Python实现一个图片拆分工具

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片，默认是输出到项目文件夹中，可以自己选择其他的文件夹，选择需要拆分的行数和列数，可以通过
阅读更多...
Python中将嵌套列表扁平化的多种实现方法

Python中将嵌套列表扁平化的多种实现方法

《Python中将嵌套列表扁平化的多种实现方法》在Python编程中,我们常常会遇到需要将嵌套列表（即列表中包含列表）转换为一个一维的扁平列表的需求,本文将给大家介绍了多种实现这一目标的方法,需要的朋... 目录python中将嵌套列表扁平化的方法技术背景实现步骤1. 使用嵌套列表推导式2. 使用itert
阅读更多...
Python使用pip工具实现包自动更新的多种方法

Python使用pip工具实现包自动更新的多种方法

《Python使用pip工具实现包自动更新的多种方法》本文深入探讨了使用Python的pip工具实现包自动更新的各种方法和技术,我们将从基础概念开始,逐步介绍手动更新方法、自动化脚本编写、结合CI/C... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核
阅读更多...
在Linux中改变echo输出颜色的实现方法

在Linux中改变echo输出颜色的实现方法

《在Linux中改变echo输出颜色的实现方法》在Linux系统的命令行环境下,为了使输出信息更加清晰、突出,便于用户快速识别和区分不同类型的信息,常常需要改变echo命令的输出颜色,所以本文给大家介... 目python录在linux中改变echo输出颜色的方法技术背景实现步骤使用ANSI转义码使用tpu
阅读更多...
Python使用python-can实现合并BLF文件

Python使用python-can实现合并BLF文件

《Python使用python-can实现合并BLF文件》python-can库是Python生态中专注于CAN总线通信与数据处理的强大工具,本文将使用python-can为BLF文件合并提供高效灵活... 目录一、python-can 库：CAN 数据处理的利器二、BLF 文件合并核心代码解析1. 基础合
阅读更多...
Python使用OpenCV实现获取视频时长的小工具

Python使用OpenCV实现获取视频时长的小工具

《Python使用OpenCV实现获取视频时长的小工具》在处理视频数据时,获取视频的时长是一项常见且基础的需求,本文将详细介绍如何使用Python和OpenCV获取视频时长,并对每一行代码进行深入解析... 目录一、代码实现二、代码解析1. 导入 OpenCV 库2. 定义获取视频时长的函数3. 打开视频文
阅读更多...
golang版本升级如何实现

golang版本升级如何实现

《golang版本升级如何实现》：本文主要介绍golang版本升级如何实现问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录golanwww.chinasem.cng版本升级linux上golang版本升级删除golang旧版本安装golang最新版本总结gola
阅读更多...
SpringBoot中SM2公钥加密、私钥解密的实现示例详解

SpringBoot中SM2公钥加密、私钥解密的实现示例详解

《SpringBoot中SM2公钥加密、私钥解密的实现示例详解》本文介绍了如何在SpringBoot项目中实现SM2公钥加密和私钥解密的功能,通过使用Hutool库和BouncyCastle依赖,简化... 目录一、前言1、加密信息(示例)2、加密结果(示例)二、实现代码1、yml文件配置2、创建SM2工具
阅读更多...
Mysql实现范围分区表(新增、删除、重组、查看)

Mysql实现范围分区表(新增、删除、重组、查看)

《Mysql实现范围分区表(新增、删除、重组、查看)》MySQL分区表的四种类型（范围、哈希、列表、键值）,主要介绍了范围分区的创建、查询、添加、删除及重组织操作,具有一定的参考价值,感兴趣的可以了解... 目录一、mysql分区表分类二、范围分区（Range Partitioning1、新建分区表：2、分
阅读更多...
MySQL 定时新增分区的实现示例

MySQL 定时新增分区的实现示例

《MySQL定时新增分区的实现示例》本文主要介绍了通过存储过程和定时任务实现MySQL分区的自动创建,解决大数据量下手动维护的繁琐问题,具有一定的参考价值,感兴趣的可以了解一下... mysql创建好分区之后，有时候会需要自动创建分区。比如，一些表数据量非常大，有些数据是热点数据，按照日期分区MululbU
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2