(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。

相关文章

如何使用Java实现请求deepseek

如何使用Java实现请求deepseek

《如何使用Java实现请求deepseek》这篇文章主要为大家详细介绍了如何使用Java实现请求deepseek功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1.deepseek的api创建2.Java实现请求deepseek2.1 pom文件2.2 json转化文件2.2
阅读更多...
python使用fastapi实现多语言国际化的操作指南

python使用fastapi实现多语言国际化的操作指南

《python使用fastapi实现多语言国际化的操作指南》本文介绍了使用Python和FastAPI实现多语言国际化的操作指南,包括多语言架构技术栈、翻译管理、前端本地化、语言切换机制以及常见陷阱和... 目录多语言国际化实现指南项目多语言架构技术栈目录结构翻译工作流1. 翻译数据存储2. 翻译生成脚本
阅读更多...
C++初始化数组的几种常见方法(简单易懂)

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化（推荐方式）1.2、初始化部分列表1.3、使用std::
阅读更多...
C++ Primer 多维数组的使用

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没
阅读更多...
如何通过Python实现一个消息队列

如何通过Python实现一个消息队列

《如何通过Python实现一个消息队列》这篇文章主要为大家详细介绍了如何通过Python实现一个简单的消息队列,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录如何通过 python 实现消息队列如何把 http 请求放在队列中执行1. 使用 queue.Queue 和 reque
阅读更多...
Python如何实现PDF隐私信息检测

Python如何实现PDF隐私信息检测

《Python如何实现PDF隐私信息检测》随着越来越多的个人信息以电子形式存储和传输,确保这些信息的安全至关重要,本文将介绍如何使用Python检测PDF文件中的隐私信息,需要的可以参考下... 目录项目背景技术栈代码解析功能说明运行结php果在当今，数据隐私保护变得尤为重要。随着越来越多的个人信息以电子形
阅读更多...
使用 sql-research-assistant进行 SQL 数据库研究的实战指南(代码实现演示)

使用 sql-research-assistant进行 SQL 数据库研究的实战指南(代码实现演示)

《使用sql-research-assistant进行SQL数据库研究的实战指南(代码实现演示)》本文介绍了sql-research-assistant工具,该工具基于LangChain框架,集... 目录技术背景介绍核心原理解析代码实现演示安装和配置项目集成LangSmith 配置（可选）启动服务应用场景
阅读更多...
使用Python快速实现链接转word文档

使用Python快速实现链接转word文档

《使用Python快速实现链接转word文档》这篇文章主要为大家详细介绍了如何使用Python快速实现链接转word文档功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 演示代码展示from newspaper import Articlefrom docx import
阅读更多...
前端原生js实现拖拽排课效果实例

前端原生js实现拖拽排课效果实例

《前端原生js实现拖拽排课效果实例》：本文主要介绍如何实现一个简单的课程表拖拽功能,通过HTML、CSS和JavaScript的配合,我们实现了课程项的拖拽、放置和显示功能,文中通过实例代码介绍的... 目录1. 效果展示2. 效果分析2.1 关键点2.2 实现方法3. 代码实现3.1 html部分3.2
阅读更多...
redis群集简单部署过程

redis群集简单部署过程

《redis群集简单部署过程》文章介绍了Redis,一个高性能的键值存储系统,其支持多种数据结构和命令,它还讨论了Redis的服务器端架构、数据存储和获取、协议和命令、高可用性方案、缓存机制以及监控和... 目录Redis介绍1. 基本概念2. 服务器端3. 存储和获取数据4. 协议和命令5. 高可用性6.
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2