(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实现网页表格转换为markdown

使用Python实现网页表格转换为markdown

《使用Python实现网页表格转换为markdown》在日常工作中,我们经常需要从网页上复制表格数据,并将其转换成Markdown格式,本文将使用Python编写一个网页表格转Markdown工具,需... 在日常工作中，我们经常需要从网页上复制表格数据，并将其转换成Markdown格式，以便在文档、邮件或
阅读更多...
Python使用pynput模拟实现键盘自动输入工具

Python使用pynput模拟实现键盘自动输入工具

《Python使用pynput模拟实现键盘自动输入工具》在日常办公和软件开发中,我们经常需要处理大量重复的文本输入工作,所以本文就来和大家介绍一款使用Python的PyQt5库结合pynput键盘控制... 目录概述：当自动化遇上可视化功能全景图核心功能矩阵技术栈深度效果展示使用教程四步操作指南核心代码解析
阅读更多...
SpringBoot实现文件记录日志及日志文件自动归档和压缩

SpringBoot实现文件记录日志及日志文件自动归档和压缩

《SpringBoot实现文件记录日志及日志文件自动归档和压缩》Logback是Java日志框架,通过Logger收集日志并经Appender输出至控制台、文件等,SpringBoot配置logbac... 目录1、什么是Logback2、SpringBoot实现文件记录日志，日志文件自动归档和压缩2.1、
阅读更多...
Python实现pdf电子发票信息提取到excel表格

Python实现pdf电子发票信息提取到excel表格

《Python实现pdf电子发票信息提取到excel表格》这篇文章主要为大家详细介绍了如何使用Python实现pdf电子发票信息提取并保存到excel表格,文中的示例代码讲解详细,感兴趣的小伙伴可以跟... 目录应用场景详细代码步骤总结优化应用场景电子发票信息提取系统主要应用于以下场景：企业财务部门：需
阅读更多...
基于Python实现智能天气提醒助手

基于Python实现智能天气提醒助手

《基于Python实现智能天气提醒助手》这篇文章主要来和大家分享一个实用的Python天气提醒助手开发方案,这个工具可以方便地集成到青龙面板或其他调度框架中使用,有需要的小伙伴可以参考一下... 目录项目概述核心功能技术实现1. 天气API集成2. AI建议生成3. 消息推送环境配置使用方法完整代码项目特点
阅读更多...
spring-gateway filters添加自定义过滤器实现流程分析(可插拔)

spring-gateway filters添加自定义过滤器实现流程分析(可插拔)

《spring-gatewayfilters添加自定义过滤器实现流程分析(可插拔)》：本文主要介绍spring-gatewayfilters添加自定义过滤器实现流程分析(可插拔),本文通过实例图... 目录需求背景需求拆解设计流程及作用域逻辑处理代码逻辑需求背景公司要求，通过公司网络代理访问的请求需要做请
阅读更多...
使用Python获取JS加载的数据的多种实现方法

使用Python获取JS加载的数据的多种实现方法

《使用Python获取JS加载的数据的多种实现方法》在当今的互联网时代,网页数据的动态加载已经成为一种常见的技术手段,许多现代网站通过JavaScript（JS）动态加载内容,这使得传统的静态网页爬取... 目录引言一、动态 网页与js加载数据的原理二、python爬取JS加载数据的方法（一）分析网络请求1
阅读更多...
Spring Security介绍及配置实现代码

Spring Security介绍及配置实现代码

《SpringSecurity介绍及配置实现代码》SpringSecurity是一个功能强大的Java安全框架,它提供了全面的安全认证(Authentication)和授权(Authorizatio... 目录简介Spring Security配置配置实现代码简介Spring Security是一个功能强
阅读更多...
SpringCloud使用Nacos 配置中心实现配置自动刷新功能使用

SpringCloud使用Nacos 配置中心实现配置自动刷新功能使用

《SpringCloud使用Nacos配置中心实现配置自动刷新功能使用》SpringCloud项目中使用Nacos作为配置中心可以方便开发及运维人员随时查看配置信息,及配置共享,并且Nacos支持配... 目录前言一、Nacos中集中配置方式？二、使用步骤1.使用$Value 注解2.使用@Configur
阅读更多...
Python中合并列表(list)的六种方法小结

Python中合并列表(list)的六种方法小结

《Python中合并列表(list)的六种方法小结》本文主要介绍了Python中合并列表(list)的六种方法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋... 目录一、直接用 + 合并列表二、用 extend() js方法三、用 zip() 函数交叉合并四、用
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2