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

2024-09-04 00:12

本文主要是介绍(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

相关文章

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time