C++list的模拟实现

🕗 发布于 2024-10-20 08:29 c++ list 开发语言

基本结构

首先明确一个问题，list是带头双向循环链表，既然是链表，那么我们就需要定义一个节点的结构体，然后既然是list的模拟实现，就需要定义一个list的类，根据带头双向循环链表的特点，还需要一个头节点，所以list的成员变量中必有一个头节点

下面是基本结构

namespace bit
{
    template<class T>
    struct ListNode
    {
        ListNode<T>* _next;
        ListNode<T>* _prev;
        T _Date;
        ListNode(const T x=T())
        {
            _next=nullptr;
            _prev=nullptr;
            _Date=x;
        }
    };


    
    template<class T>
    calss list
    {
     public:
     list()
     {
        _head=new Node;
        _head->_next=_head;
        _head->_prev=_head;
     }

     private:
     typedef ListNode<T> Node;
     Node* _head;
        
    };


}

上面有一个问题，上面的那个定义节点要用struct,而不用class,原因就是上面的节点里面的任何元素随时都需要访问，而struct里面的是默认共有的，当然在这里你也可以用calss,只是需要把所有的元素置成公有的

push_back()

向节点的尾部添加一个节点，基本的思路就是找到尾节点，申请新的节点，然后将新的节点连接就行了

void push_back(const T x)
{
Node* tail = _head->_prev;
Node* newnode = new Node(x);
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
}

迭代器

今天的这个迭代器会有一点特别，以前在string,vector里面的模拟实现里面，定义一个迭代器都是都是直接typedef一个int*,或者一个char*,让后直接对迭代器进行++或者--，但是，今天的这个是链表，结构在物理上都不是连续的，如何进行++或者--操作，这是不行的，唯一的方法就是对定义一个迭代器的类，然后对++或者--进行操作符的重载


template<class T>
class ListIterator
{

typedef ListNode<T> Node;
typedef ListIterator<T> self;
Node* _node;

public:
ListIterator(Node* node)
:_node(node)
{}


self&operator++()
{
_node = _node->_next;
return *this;
}

self operator++(int)
{
self temp(_node);
_node = _node->_next;
return temp;
}

        self&operator--()
{
_node = _node->_prev;
return *this;
}

self operator--(int)
{
self temp(_node);
_node = _node->_prev;
return temp;
}


bool operator==(const self& s)
{
return _node == s._node;
}
bool operator!=(const self& s)
{
return _node != s._node;
}

T& operator*()
{
return _node->_Date;
}

T* operator->()
{
return &(_node->_Date);
}


};

这样就可以对链表进行遍历了，当然了，这里的的begin()和end()函数还没有实现，可以在下面完整代码的list里面去查看

上面代码还有一个问题，你迭代器里面去重载一个—>有什么用

主要是为下面的情况做准备的

上面又又同学问了，啊，->这个操作符得出不是pos的地址吗，你这个怎么好直接就能去的出pos里面的成员变量的，其实上面的写法和被注释掉的代码是一样的，这里编译器是为了增强代码的可读性和美观性才这样省略出这样的，

const迭代器

const迭代器和非const迭代器其实是相差不大的，有人可能认为，在iterator前面加上一个const让他变成const iterator不就成为const迭代器了吗，那你就大错特错了

const迭代器是什么？是迭代器里面指向的内容不能被修改，直接加const不久变成迭代器不能被修改了，这里其实代码和非const迭代器是差不多的，唯一有一个地方需要改的就是限制解引用的返回值，让他变成const

template<class T>
class ListConstIterator
{

typedef ListNode<T> Node;
typedef ListConstIterator<T> self;
Node* _node;

public:
ListConstIterator(Node* node)
:_node(node)
{}


self&operator++()
{
_node = _node->_next;
return *this;
}

self operator++(int)
{
self temp(_node);
_node = _node->_next;
return temp;
}

bool operator==(const self& s)
{
return _node == s._node;
}
bool operator!=(const self& s)    //记得参数里面加const，如果不加，会出现权限的放大问题
{
return _node != s._node;
}

const T& operator*()          //加const
{
return _node->_Date;
}

const T* operator->()        //加const
{
return &(_node->_Date);
}


};

两个迭代器合一块

两个迭代器写一块，那不是太麻烦了一点，能不能写一个模板？答案是可以的

只需要在模板参数里面添加两个参数

然后下面函数的返回值稍微改动一下

最后关键的一步来了

在list定义迭代器里面的时候给不同的模板参数就行了

析构函数


~list()
{
list<T>::iterator it = begin();
while (it != end())
{
it = erase(it);
}

delete _head;
_head = nullptr;
}

拷贝构造和赋值重载

void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}


list<T>& operator=(const list<T> l1)
{
empty_init();                //这里记着要初始化
swap(_head, l1._head);
return *this;
}

上面的赋值运算符重载设计得很巧妙，首先明确的一个问题是要使用传值传参，后面直接交换两个_head的指向，因为传值传参会引发拷贝构造函数，后面把_head的指向给l1的拷贝构造了之后函数结束直接析构，这里就有点像让你干活，最后把你给杀了

list(const list<T>& l1)
{
empty_init();
for (const auto &e : l1)
{
push_back(e);
}


}

这里记得拷贝构造函数需要使用深拷贝，如果你不写拷贝构造函数得话，编译器生成的默认构造函数默认的是浅拷贝，函数调用结束了之后会发生同一块空间析构两次的问题，导致程序崩溃

写代码时的一个易错点

这里写代码的时候老是出现下面的问题：函数匹配问题，这一般都是由于权限的放大缩小问题

还有就是写范围for的时候尽量写引用，因为范围for实际上时赋值给e,赋值的话会拷贝产生一个临时对象，如果auto是自定义类型的话，拷贝量太大了，效率比较低

常规函数

void erase(iterator pos)            //迭代器失效，因为被释放了
{
Node* prev = pos._node->_prev;
Node* next = pos._node->_next;
prev->_next = next;
next->_prev = prev;
delete pos._node;
pos._node = nullptr;
}

void insert(iterator&pos, T x)       //迭代器没有失效
{
Node* newnode = new Node(x);
Node* prev = pos._node->_prev;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = pos._node;
pos._node->_prev = newnode;
}

void pop_back()
{
Node* cur = _head->_prev;
Node* prev = cur->_prev;
prev->_next = _head;
_head->_prev = prev;
delete cur;
}

完整代码

#include<iostream>
using namespace std;
namespace bit
{
template<class T>
struct ListNode
{
ListNode<T>* _next;
ListNode<T>* _prev;
T _Date;

ListNode(const T date = T())
:_Date(date)
,_prev(nullptr)
,_next(nullptr)
{

}

};


template<class T,class ref,class ptr>
class ListIterator
{

typedef ListNode<T> Node;
typedef ListIterator<T,ref,ptr> self;
public:
Node* _node;
public:
ListIterator(Node* node)
:_node(node)
{

}

self& operator++()
{
_node = _node->_next;
return *this;

}

self operator++(int)
{
self temp(_node);
_node = _node->_next;
return temp;
}

self& operator--()
{
_node = _node->_prev;
return *this;
}

bool operator==(const self& s)
{
return _node == s._node;
}

bool operator!=(const self& s)
{
return _node != s._node;
}

ref&operator*()
{
return _node->_Date;
}

ptr operator->()
{
return &(_node->_Date);
}

};

/*template<class T>
class ListConstIterator
{

typedef ListNode<T> Node;
typedef ListConstIterator<T> self;
Node* _node;

public:
ListConstIterator(Node* node)
:_node(node)
{}


self&operator++()
{
_node = _node->_next;
return *this;
}

self operator++(int)
{
self temp(_node);
_node = _node->_next;
return temp;
}

bool operator==(const self& s)
{
return _node == s._node;
}
bool operator!=(const self& s)
{
return _node != s._node;
}

const T& operator*()
{
return _node->_Date;
}

T* operator->()
{
return &(_node->_Date);
}


};*/


template<class T>
class list
{
public:
typedef ListIterator<T, T&,T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;
//typedef ListConstIterator<T> const_iterator;
iterator begin()
{
return iterator(_head->_next);
}

const_iterator begin()const
{
return const_iterator(_head->_next);
}

        const_iterator end()const
{
return const_iterator(_head);
}

iterator end()
{
return iterator(_head);
}

void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}


list<T>& operator=(const list<T> l1)
{
empty_init();
swap(_head, l1._head);
return *this;
}

list()
{
empty_init();
}
void push_back(const T x)
{
Node* tail = _head->_prev;
Node* newnode = new Node(x);
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
}

iterator erase(iterator pos)
{
Node* prev = pos._node->_prev;
Node* next = pos._node->_next;
prev->_next = next;
next->_prev = prev;
delete pos._node;
pos._node = nullptr;

return iterator(next);
}

list(const list<T>& l1)
{
empty_init();
for (const auto &e : l1)
{
push_back(e);
}


}

~list()
{
list<T>::iterator it = begin();
while (it != end())
{
it = erase(it);
}

delete _head;
_head = nullptr;
}

bool empty()
{
return _head->_next == _head;
}
void insert(iterator&pos, T x)
{
Node* newnode = new Node(x);
Node* prev = pos._node->_prev;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = pos._node;
pos._node->_prev = newnode;
}

void pop_back()
{
Node* cur = _head->_prev;
Node* prev = cur->_prev;
prev->_next = _head;
_head->_prev = prev;
delete cur;
}
private:
typedef ListNode<T> Node;
Node* _head;
};

void test01()
{
list<int> l1;
l1.push_back(10);
l1.push_back(20);
l1.push_back(30);
l1.push_back(40);
l1.push_back(50);
l1.push_back(60);
list<int>::iterator it = l1.begin();
while (it != l1.end())
{
cout << *it << " ";
it++;
}
cout << endl;

}

void func(const list<int>&s)
{
list<int>::const_iterator it = s.begin();
while (it != s.end())
{
//(*it)++;
cout << *it << " ";
it++;
}
}

void test02()
{
list<int> l1;
l1.push_back(10);
l1.push_back(20);
l1.push_back(30);
l1.push_back(40);
func(l1);
}

struct pos
{
int _x;
int _y;
pos(int x=0,int y=0)
:_x(x)
,_y(y)
{}
};

void test03()
{
list<pos> p;
p.push_back(pos(1,2));
p.push_back(pos(3,4));
p.push_back(pos(5,6));
list<pos>::iterator it = p.begin();
//cout << it.operator->()->_x << " " << it.operator->()->_y << endl;
cout << it->_x << " " << it->_y << endl;

}

void test04()
{
list<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
for (auto &e : l1)
{
cout << e << " ";
}
cout << endl;

list<int> l2 = l1;
for (auto& e : l2)
{
cout << e << " ";
}
cout << endl;


}


void test05()
{
list<int> l1;
l1.push_back(10);
l1.push_back(20);
l1.push_back(30);
l1.push_back(40);

}
}

原文地址：https://blog.csdn.net/lihaolihao111111/article/details/142970777

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：[LeetCode] 542. 01矩阵
下一篇：Python 基础语法

leetcode289:生命游戏
根据，简称为，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。给定一个包含m × n个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1即为（live），或0即为
阅读更多2024-10-20
MongoDB数据恢复
注意：两个MongoDB的版本要一致，本文使用的是mongo:4.2.24。先把K8S上面的MongoDB 容器停止（可以把副本改成0）。1、将容器挂载MongoDB的数据目录备份到本地。经常是数据文
阅读更多2024-10-20
C#中实现事务
C#中实现事务
阅读更多2024-10-20
【LeetCode每日一题】——560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。
阅读更多2024-10-20
「漏洞复现」满客宝智慧食堂系统 selectUserByOrgId 未授权访问漏洞
请勿利用文章内的相关技术从事非法测试，由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失，均由使用者本人负责，作者不为此承担任何责任。工具来自网络，安全性自测，如有侵权请联系删除。本次
阅读更多2024-10-20
React面试题目（从基本到高级）
React前端面试常见题目涵盖了React的基础概念、组件、状态管理、生命周期、性能优化等多个方面。
阅读更多2024-10-20
12.个人博客系统（Java项目基于spring和vue）
1 在校学习的学生，可用于日常学习使用或是毕业设计使用 2 毕业一到两年的开发人员，用于锻炼自己的独立功能模块设计能力，增强代码编写能力。 3 亦可以部署为商化项目使用。 4 需要完整资料及源码
阅读更多2024-10-20
YoloV8改进策略：注意力改进|DeBiFormer，可变形双级路由注意力|引入DeBiLevelRoutingAttention注意力模块（全网首发）
本次改进的核心在于将DeBiLevelRoutingAttention模块嵌入到YoloV8的主干网络中，具体位置是在SPPF（Spatial Pyramid Pooling Fast）模块之后。这一
阅读更多2024-10-20
word取消自动单词首字母大写
情况说明：在word输入单词后首字母会自动变成大写取消单词首字母大写步骤：（1）点击菜单栏文件（2）点击“更多”——>“选项”（3）点击“校对”——>“自动更正选项”（4）取消“句首字母大
阅读更多2024-10-20
web前端网页用户注册页面
【代码】web前端网页用户注册页面。
阅读更多2024-10-20