【C++】—— list的模拟实现

🕗 发布于 2024-11-17 07:39 c++ list

一、list节点

list是一个双向循环带头的链表，所以链表节点结构如下：

template<class T>
struct ListNode
{
T val;
ListNode* next;
ListNode* prve;
ListNode(int x)
{
val = x;
next = prve = this;
}
};

二、list迭代器

2.1、list迭代器与vector迭代器区别

list迭代器与vector迭代器不一样，不能使用简单的原生指针了；

vector中迭代器可以使用原生指针，因为vector的存储空间是连续的，可以通过指针+/-/++/–找到下一个（上一个）位置；而list(链表)我们知道存储空间是不连续的，不能通过指针++/—找到下一个（上一个）节点；那我们就不能使用原生指针。

2.2、list迭代器实现

既然原生指针不能满足我们的需求，那我们就要用其他的方法来实现迭代器，这时候类的封装的意义就体现出来了；我们只需要对原生指针进行封装，然后使用运算符重载来修改迭代器++/–这些行为，这样就可以满足我们的需求了。

具体代码如下：

template<class T, class Ref, class Str>
class list_iterator
{
typedef ListNode Node;
typedef list_iterator iterator;
public:
list_iterator(Node* node)
{
_node = node;
}
//前置++
iterator operator++()
{
Node tmp(_node);
_node = _node->_next;
return tmp;
}
//后置++
iterator operator++(int)
{
_node = _node->_next;
return *this;
}
//前置--
iterator operator--()
{
Node tmp(_node);
_node = _node->_prve;
return tmp;
}
iterator operator++(int)
{
_node = _node->_prve;
return *this;
}
bool operator==(const iterator& it)
{
return _node == it._node;
}
bool operator!=(const iterator& it)
{
return _node != it._node;
}
Ref operator*()
{
return _node->val;
}
Ptr operator->()
{
return &(_node->_val);
}
private:
Node* _node;
};

三、list实现

3.1、构造函数

在这里插入图片描述

先看一下list构造函数的接口

构造函数	接口说明
list()	默认构造函数，构造一个空的list
list (size_type n, const value_type& val =value_type())	用n个val值构造list
list (InputIterator first, InputIterator last)	还有一段迭代器区间初始化
list (const list& x)	拷贝构造函数

这里我们实现的list是带头双向循环链表，具体结构与之前的双向链表相同。

在构造之前，我们需要先构造一个头结点，这里就写一个函数 empty_init 来构造这个头结点。

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

默认构造函数

list()
{
empty_init();
_size = 0;
}

用n个val值构造

list(size_t n, const T& val)
{
/*_head = new Node();
_head->_next = _head;
_head->_prve = _head;*/
empty_init();
for (size_t i = 0; i < n; i++)
{
Node* newnode = new Node(val);

newnode->_next = _head->_next;
newnode->_prve = _head->_next;
_head->_next->_prve = newnode;
_head->_next = newnode;
}
_size = n;
}

迭代器区间构造

使用迭代器区间构造，这里复用一下后面的push_back直接尾插来构造。

template<class InputIterator>
list(InputIterator first, InputIterator last)
{
empty_init();
_size = 0;
while (first != last)
{
push_back(*first);
_size++;
}
}
void push_back(const T& val)
{
Node* newnode = new Node(val);
newnode->_next = _head;
    newnode->_prve = _head->_prve;
_head->_prve->_next = newnode;
_head->_prve = newnode;
}

拷贝构造函数

拷贝构造，这里直接复用上面迭代器构造即可。

list(const list& l)
{
empty_init();
list(l.begin(), l.end());
_size = l.size();
}

3.2、迭代器

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

这里迭代器返回值，可以直接返回节点指针（因为单参数的构造函数支持隐式类型转换）。

3.3、Capacity

在这里插入图片描述

主要就是empty和size（判断空和数据个数）

//Capacity
bool empty()
{
return _head == _head->_next;
}
size_t size()
{
/*size_t ret = 0;
Node* ptail = _head->_next;
while (ptail != head)
{
ret++;
ptail = ptail->_next;
}
return ret;*/
return _size;
}

这里遍历链表来计算数据个数，代价太大了，我们直接写一个成员变量，在初始化，插入和删除时修改，会方便很多。

3.4、增删查改

在这里插入图片描述

这里增删查改就实现其中的一部分，其他的不太常用。

3.4.1、push_back、push_front、pop_back、pop_front

头插尾插，头删尾删，对于list而言，只需要修改指针的指向；

void push_back(const T& val)
{
Node* newnode = new Node(val);
newnode->_next = _head;
newnode->_prve = _head->_prve;
_head->_prve->_next = newnode;
_head->_prve = newnode;
}
void push_front(const T& val)
{
Node* newnode = new Node(val);
newnode->_next = _head->_next;
newnode->_prve = _head;
_head->_next->_prve = newnode;
_head->_next = newnode;
}

//删
void pop_back()
{
if (!empty())
{
Node* del = _head->_prve;
_head->_prve->_prve->_next = _head;
_head->_prve = _head->_prve->_prve;
delete del;
}
}
void pop_front()
{
if (!empty())
{
Node* del = _head->_next;
_head->_next->_next->_prve = _head;
_head->_next = _head->_next->_next;
delete del;
}
}

3.4.2、insert

在这里插入图片描述

insert在指定位置插入数据，看它的参数列表，大概就知道，要在迭代器position 迭代器位置（之前）插入数据（1个或者n个），或者插入一段迭代器区间的数据。

//insert
void insert(iterator pos, const T& val)
{
Node* newnode = new Node(val);
Node* tmp = pos._node;
newnode->_next = tmp;
newnode->_prve = tmp->_prve;

tmp->_prve->_next = newnode;
tmp->_prve = newnode;
    ++_size;
}
void insert(iterator pos, size_t n, const T& val)
{
for(size_t i = 0; i < n; i++)
{
Node* newnode = new Node(val);
Node* tmp = pos._node;
newnode->_next = tmp;
newnode->_prve = tmp->_prve;

tmp->_prve->_next = newnode;
tmp->_prve = newnode;
}
    _size+=n;
}
void insert(iterator pos, int n, const T& val)
{
for(size_t i = 0; i < n; i++)
{
Node* newnode = new Node(val);
Node* tmp = pos._node;
newnode->_next = tmp;
newnode->_prve = tmp->_prve;

tmp->_prve->_next = newnode;
tmp->_prve = newnode;
}
}

这里需要注意：

看到这里可能会疑惑，为什么实现了两个插入n个数据的insert函数；

因为，当数据类型是int时，下面模版实例化出的函数（iterator , int , int）比这里实现的(iterator , size_t , int)更加匹配；编译器就会去调用更加匹配的函数，就会出错。这里就是为了防止这种出错。

插入迭代器的数据，与使用迭代器区间构造初始化相似，list只需改变指针指向即可。

template<class InputIterator>
void insert(iterator pos, InputIterator first, InputIterator last)
{
while (first != last)
{
Node* newnode = new Node(*first);
Node* tmp = pos._node;
newnode->_next = tmp;
newnode->_prve = tmp->_prve;

tmp->_prve->_next = newnode;
tmp->_prve = newnode;
++first;
}
}

3.4.3、erase

erase删除一个节点，我们要修改前后节点的指针指向。

iterator erase(iterator pos)
{
assert(pos != end());
Node* del = pos._node;
Node* next = del->_next;
Node* prve = del->_prve;
next->_prve = prve;
prve->_next = next;
delete del;
return next;
}

在我们删除节点之后，之前的迭代器就会失效，为了解决迭代器失效问题，我们就使用返回值，返回新的迭代器。

3.4.4、swap

这里实现的list只有一个成员函数（头结点的指针），直接交换即可。

void swap(list& l)
{
std::swap(_head, l._head);
}

3.4.5、clear

clear函数，清理数据，（保留头结点）。

//清除数据
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}

3.5、析构函数

析构函数相对就比较简单了，我们清理完数据，再释放头结点即可。

~list()
{
clear();
delete _head;
}

到这里，list的模拟实现就完成了；这里只是实现了其中的一部分内容，感兴趣的可以继续深入了解学习。

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws
ear函数，清理数据，（保留头结点）。

//清除数据
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}

3.5、析构函数

析构函数相对就比较简单了，我们清理完数据，再释放头结点即可。

~list()
{
clear();
delete _head;
}

到这里，list的模拟实现就完成了；这里只是实现了其中的一部分内容，感兴趣的可以继续深入了解学习。

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws

原文地址：https://blog.csdn.net/LH__1314/article/details/143823752

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

上一篇：React Native 全栈开发实战班 - 用户界面进阶之自定义组件开发
下一篇：ISP是什么？

分布式系统学习笔记
除了分布式爬虫系统，还有许多分布式系统值得学习和实践，它们在不同领域有广泛应用，积累相关经验对找工作非常有帮助。
阅读更多2024-11-18
SQL初步注入
基于时间的延迟，构造一个拼接语句： vince' and if(substr(database(),1,1)='X' (猜测 vince' and if(substr(database(),1,1)=
阅读更多2024-11-18
跨平台WPF框架Avalonia教程十一
这个例子展示了如何覆盖Panel元素的默认布局行为，并创建从Panel派生的自定义布局元素。该例子定义了一个简单的自定义Panel元素，称为PlotPanel，它根据两个硬编码的x和y坐标来定位子元素
阅读更多2024-11-18
【MySQL】MySQL数据库入门：构建你的数据基石
🦅数据库基础🍑个人主页：Jupiter.🚀 所属专栏：MySQL初阶探索：构建数据库基础。
阅读更多2024-11-18
如何查看python源代码
众所周知，Python内建了许多函数模块，并且我们可能还会安装许多第三方模块等等。在该类或方法上按住“ctr+鼠标左键”可以快速查看源代码。想要查看每个功能的解释，用help(type(对象名))输入
阅读更多2024-11-18
基于java的健身馆网站
项目编号：springbootA063随着网络科技的不断发展以及人们经济水平的逐步提高，网络技术如今已成为人们生活中不可缺少的一部分，而信息管理系统是通过计算机技术，针对用户需求开发与设计，该技术尤其
阅读更多2024-11-18
WebLogic 介绍
WebLogic 支持完整的 Java EE 规范，包括 JSP、Servlet、EJB（Enterprise JavaBeans）、JMS（Java Message Service）、JNDI（Ja
阅读更多2024-11-18
简单学点位运算（Java）
【代码】简单学点位运算（Java）
阅读更多2024-11-18
使用MATLAB进行随机信号处理
MATLAB是一款强大的数学计算软件，广泛应用于工程、科学和经济等领域。其中，随机信号处理是MATLAB其中一个重要的应用领域。本文将探讨随机信号的基本概念、生成方法以及MATLAB中如何处理随机信号
阅读更多2024-11-18
CSP/信奥赛C++语法基础刷题训练（11）：洛谷P5743：猴子吃桃
CSP/信奥赛C++语法基础刷题训练（11）：洛谷P5743：猴子吃桃
阅读更多2024-11-18

【C++】—— list的模拟实现

一、list节点

二、list迭代器

2.1、list迭代器与vector迭代器区别

2.2、list迭代器实现

三、list实现

3.1、构造函数

默认构造函数

用n个val值构造

迭代器区间构造

拷贝构造函数

3.2、迭代器

3.3、Capacity

3.4、增删查改

3.4.1、push_back、push_front、pop_back、pop_front

3.4.2、insert

3.4.3、erase

3.4.4、swap

3.4.5、clear

3.5、析构函数

3.5、析构函数

相关文章