【c++丨STL】list模拟实现（附源码）

与vector、string不同，由于list的底层是一个双向带头循环链表，所以它的实现上要更加复杂。vector和string的迭代器可以是原生指针，但是list的迭代器需要用一个类模板来实现，并且数据之间都是以节点的指针相连接，我们还需要定义其节点结构。当然，与vector一样，在接下来模拟实现list的过程中，我们也将采用类模板进行定义，并不会将声明和定义分离。

建议大家在掌握了双向带头循环链表以及vector、string的实现之后，再来阅读本文，否则其中部分内容可能较难理解。

一、节点、迭代器以及函数声明

首先是链表节点、迭代器和我们要实现接口的声明：

#include <iostream>
#include <cassert>
using namespace std;

//节点
template<class T>
struct list_node
{
T _data;//数据域
list_node<T>* _next;//指向后一个节点
list_node<T>* _prev;//指向前一个节点

//节点的默认构造
list_node(const T& x = T());
};

//迭代器
template<class T, class Ref, class Ptr>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T, Ref, Ptr> Self;

Node* ptr;//封装节点的指针

//迭代器构造
list_iterator(Node* node);

//解引用
Ref operator*();
//结构成员间接访问
Ref operator->();
//前置++
&Self operator++();
//前置--
&Self operator--();
//后置++
Self operator++(int);
//后置--
Self operator--(int);
//不等于
bool operator!=(const Self& it);
};

//容器
template<class T>
class List
{
typedef list_node<T> Node;
public:
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;

//迭代器接口
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;

//空链表的初始化
void empty_init();

//无参构造
List();
//n个val值构造
List(size_t n, const T& val = T());
//拷贝构造
List(const List<T>& l);
//赋值重载
List<T>& operator=(List<T> l);
//析构
~List();

//插入和删除
iterator insert(iterator pos, const T& x);
iterator erase(iterator pos);
void push_back(const T& x);
void push_front(const T& x);
void pop_back();
void pop_front();

//清空链表
void clear();

//交换两个链表
void swap(List<T> l);
private:
Node* _head;//头节点的指针
size_t _size;//节点个数
};

//交换两个链表--非成员函数版
template <class T>
void swap(List<T>& l1, List<T>& l2);

接下来，我们开始逐一实现这三个部分。

二、list功能实现

1. 节点

和传统的双向带头循环链表相同，节点当中有一个数据域用于存放数据；两个指针分别指向前驱节点和后继节点。我们需要实现节点的默认构造函数，便于容器构造节点。

代码实现：

//节点
template<class T>
struct list_node
{
T _data;//数据域
list_node<T>* _next;//指向后一个节点
list_node<T>* _prev;//指向前一个节点

//节点的默认构造
list_node(const T& x = T())
:_data(x)
, _next(nullptr)
, _prev(nullptr)
{}
};

可以看到，这里的节点我们也定义成了一个类模板，参数T表示的是传入的数据类型。对于构造函数，如果我们没有显式传参，则数据x就会调用其默认构造函数初始化。

2. 迭代器

迭代器也是一个类模板，我们模拟实现的迭代器具有三个模板参数：数据类型T，T的引用类型Ref（普通引用或const引用）、T的指针类型Ptr（普通指针或const指针）。为什么要这样设计呢？其实这样做的目的是为了提高代码复用率。如果我们创建了一个list普通对象和一个const对象，那么使用它们的迭代器时，相对应就会有普通迭代器和const迭代器。这样我们在实现迭代器时，就要将同样的接口写两遍。而当我们定义了三个模板参数后，容器内部就可以通过传参来定义对应的普通迭代器ef和const迭代器，减少了代码冗余。

//list容器内部定义迭代器
typedef list_iterator<T, T&, T*> iterator;//普通迭代器
typedef list_iterator<T, const T&, const T*> const_iterator;//const迭代器

其次，为了简化代码，我们typedef一下节点类型以及迭代器本身类型：

typedef list_node<T> Node;//节点
typedef list_iterator<T, Ref, Ptr> Self;//迭代器本身

除此之外，由于迭代器是将指针进行封装，所以我们要将其成员变量设置为一个指向链表节点的指针：

Node* _ptr;//封装节点的指针

接下来，我们开始实现迭代器的操作函数。

迭代器的默认构造

//迭代器构造
list_iterator(Node* node)
    :_ptr(node)
{}

对于构造函数，我们将传入的指针赋值给成员指针即可。

operator*

//解引用
Ref operator*()
{
return _ptr->_data;
}

解引用用于访问指针所指对象的数据，所以函数返回迭代器指向节点的数据域。

operator->

//结构成员间接访问
Ref operator->()
{
return &_ptr->_data;
}

正常来讲，该函数的作用应该是用于访问指针所指向数据的成员，但是它并没有参数，而且返回值却是数据地址。这是为什么呢？这其实和c++的语法规定有关。当我们使用该运算符重载时，要访问到数据的成员，原本应该这样写：迭代器 ->-> 成员。但是连续两个“->”看起来并不美观，并且难以理解，所以c++语法在这里省略了一个“->”。所以我们在实现该重载时，要返回数据的地址，编译器就会默认根据这个地址找到指定成员（成员名写在->后即可，不传参）。

前置++和--

由于链表底层结构并非连续，所以不能直接使指针++/--来改变指向，而应该使用类似链表遍历的方式。实现如下：

//前置++
Self& operator++()
{
_ptr = _ptr->next;
return *this;
}
//前置--
Self& operator--()
{
_ptr = _ptr->prev;
return *this;
}

后置++和--

后置++/--的实现方法与前置++/--类似。这里创建一个临时迭代器来保存未移动时的指向。

//后置++
Self operator++(int)
{
Self tmp(*this);
_ptr = _ptr->next;
return tmp;
}
//后置--
Self operator--(int)
{
Self tmp(*this);
_ptr = _ptr->prev;
return tmp;
}

operator!=

//不等于
bool operator!=(const Self& it)
{
return _ptr != it._ptr;
}

这里判断它们的成员指针是否相等即可。

3. 容器

为了简化代码，还是先typedef一下节点类型：

typedef list_node<T> Node;

接下来，我们开始实现list容器的常用接口。

交换两个容器的内容

还是老套路，我们仅需交换它们的成员变量，就可以完成容器的交换。代码实现：

//交换两个链表
void swap(List<T> l)
{
std::swap(_head, l.head);//交换头节点指针
std::swap(_size, l._size);//交换size
}

//交换两个链表--非成员函数版
template <class T>
void swap(List<T>& l1, List<T>& l2)
{
l1.swap(l2);//直接调用成员函数版
}

迭代器接口

首先是普通迭代器和const迭代器的定义：

typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;

迭代器接口实现：

//迭代器接口
iterator begin()
{
return iterator(_head->next);
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return iterator(_head->next);
}
const_iterator end() const
{
return _head;
}

这里要注意一下它们的返回值：begin的返回值是指向首元素的迭代器，由于我们的链表头部有一个哨兵节点，所以首元素是哨兵节点的下一个节点；end的返回值是指向尾元素的“下一个元素”的迭代器，比较抽象，这里刚好可以定义为哨兵节点。

空链表初始化

该函数用于创建哨兵节点并且初始化链表的各项属性，便于后续构造函数调用。

//空链表的初始化
void empty_init()
{
_head = new Node();
_head->next = _head->prev = _head;
_size = 0;
}

构造函数

这里我们实现一下无参构造和n个val值构造：

//无参构造
List()
{
empty_init();
}

//n个val值构造
List(size_t n, const T& val = T())
{
empty_init();
for (size_t i = 0; i < n; i++)
{
push_back(val);//循环尾插
}
}

拷贝构造函数

拷贝构造函数的逻辑与n个val值构造相同，遍历源链表内容，循环尾插给当前链表即可。

//拷贝构造
List(const List<T>& l)
{
empty_init();
for (auto& e : l)
{
push_back(e);
}
}

赋值重载

这里我们仍然使用新式写法，构造新对象然后交换，完成赋值操作。代码如下：

//赋值重载
List<T>& operator=(List<T> l)
{
swap(l);
return *this;//支持连续赋值
}

析构函数

对于析构函数，我们首先释放掉所有的节点空间，然后删除哨兵节点。

//析构
~List()
{
clear();//调用clear函数清空链表
delete _head;
_head = nullptr;
}

容量接口size

容量接口size用于获取链表数据个数。我们在函数当中返回成员变量_size的值。

//容量接口
size_t size()
{
return _size;
}

插入和删除

和之前实现vector时的逻辑相同，我们首先实现insert和erase函数，这两个函数分别用于在任意位置进行插入和删除操作。然后，其他的插入和删除函数可以直接调用它们，能确保代码的高效性和复用性。

insert和erase

insert的逻辑和我们c语言实现双向链表时大体相同（在pos位置之前插入），注意插入元素后，pos指向的不再是原本需要插入的位置，迭代器失效，所以函数要返回新插入的节点的迭代器。

//插入
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._ptr;
Node* newnode = new Node(x);
newnode->_next = cur;
newnode->_prev = cur->_prev;
cur->_prev->_next = newnode;
cur->_prev = newnode;
_size++;
return iterator(newnode);
}

erase负责删除pos指向的节点。注意删除节点之后，该节点的迭代器会失效，所以函数返回指向被删除节点的后一个节点的迭代器。

iterator erase(iterator pos)
{
assert(pos != end());//避免删除哨兵节点
Node* del = pos._ptr;
Node* next = del->_next;
Node* prev = del->_prev;
next->_prev = del->_prev;
prev->_next = del->_next;
delete del;
_size--;
return iterator(next);
}

push_back、push_front、pop_back、pop_front

尾插、头插、尾删、头删直接调用insert和erase函数即可。注意尾删节点时，end指向的前一个位置才是尾节点。

void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}

清空链表

清空链表的操作类似于我们c语言实现的销毁链表，这里循环调用erase函数来完成数据的清除。注意不要删除哨兵节点。

//清空链表
void clear()
{
auto it = begin();//从首元素开始，一个个删除
while (it != end())
{
it = erase(it);
}
}

三、程序全部代码

关于list模拟实现的全部代码如下：

#include <iostream>
#include <cassert>
using namespace std;

//节点
template<class T>
struct list_node
{
T _data;//数据域
list_node<T>* _next;//指向后一个节点
list_node<T>* _prev;//指向前一个节点

//节点的默认构造
list_node(const T& x = T())
:_data(x)
, _next(nullptr)
, _prev(nullptr)
{}
};

//迭代器
template<class T, class Ref, class Ptr>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator<T, Ref, Ptr> Self;

Node* _ptr;//封装节点的指针

//迭代器构造
list_iterator(Node* node)
:_ptr(node)
{}

//解引用
Ref operator*()
{
return _ptr->_data;
}
//结构成员间接访问
Ref operator->()
{
return &_ptr->_data;
}
//前置++
Self& operator++()
{
_ptr = _ptr->next;
return *this;
}
//前置--
Self& operator--()
{
_ptr = _ptr->prev;
return *this;
}
//后置++
Self operator++(int)
{
Self tmp(*this);
_ptr = _ptr->next;
return tmp;
}
//后置--
Self operator--(int)
{
Self tmp(*this);
_ptr = _ptr->prev;
return tmp;
}
//不等于
bool operator!=(const Self& it)
{
return _ptr != it._ptr;
}
};

//容器
template<class T>
class List
{
typedef list_node<T> Node;
public:
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;

//迭代器接口
iterator begin()
{
return iterator(_head->next);
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return iterator(_head->next);
}
const_iterator end() const
{
return _head;
}

//空链表的初始化
void empty_init()
{
_head = new Node();
_head->next = _head->prev = _head;
_size = 0;
}

//无参构造
List()
{
empty_init();
}
//n个val值构造
List(size_t n, const T& val = T())
{
empty_init();
for (size_t i = 0; i < n; i++)
{
push_back(val);//循环尾插
}
}
//拷贝构造
List(const List<T>& l)
{
empty_init();
for (auto& e : l)
{
push_back(e);
}
}
//赋值重载
List<T>& operator=(List<T> l)
{
swap(l);
return *this;//支持连续赋值
}
//析构
~List()
{
clear();//调用clear函数清空链表
delete _head;
_head = nullptr;
}

//容量接口
size_t size()
{
return _size;
}

//插入和删除
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._ptr;
Node* newnode = new Node(x);
newnode->_next = cur;
newnode->_prev = cur->_prev;
cur->_prev->_next = newnode;
cur->_prev = newnode;
_size++;
return iterator(newnode);
}
iterator erase(iterator pos)
{
assert(pos != end());//避免删除哨兵节点
Node* del = pos._ptr;
Node* next = del->_next;
Node* prev = del->_prev;
next->_prev = del->_prev;
prev->_next = del->_next;
delete del;
_size--;
return iterator(next);
}
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}

//清空链表
void clear()
{
auto it = begin();//从首元素开始，一个个删除
while (it != end())
{
it = erase(it);
}
}

//交换两个链表
void swap(List<T> l)
{
std::swap(_head, l.head);//交换头节点指针
std::swap(_size, l._size);//交换size
}
private:
Node* _head;//头节点的指针
size_t _size;//节点个数
};

//交换两个链表--非成员函数版
template <class T>
void swap(List<T>& l1, List<T>& l2)
{
l1.swap(l2);//直接调用成员函数版
}

总结

本篇文章，我们在掌握list使用方法及其底层原理的基础上，模拟实现出了list容器。由于底层数据内存的非连续性，它的迭代器实现与vector、string有较大差异。之后博主会和大家一起开始stack和queue的学习。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤

原文地址：https://blog.csdn.net/2301_80955819/article/details/143781614

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

上一篇：【学习教程】如何利用有限数据发表更多SCI论文？利用ArcGIS探究环境和生态因子对水体、土壤和大气污染物
下一篇：MongoDB：数据迁移

Windows电脑本地部署llamafile并接入Qwen大语言模型远程AI对话实战
Windows电脑本地部署llamafile并接入Qwen大语言模型远程AI对话实战
阅读更多2024-11-23
解决vm虚拟机中ctrl键粘滞问题（一直处于按下状态）
虚拟机中点击鼠标左键没有问题，单独按下键盘也没有问题，但是如果按下键盘的同时在按下鼠标左键就会卡住。而且100%稳定复现。发现问题原因：vm版本的问题，我的版本是17.5.0，升级成17.5.2 bu
阅读更多2024-11-23
第十章 JavaScript的应用
10.1.1 JavaScript简介1 简单性JavaScript 设计之初就考虑到了非专业程序员的使用，因此它的语法相对简单，容易上手。2 动态性JavaScript 是一种解释型语言，代码可以在
阅读更多2024-11-23
非root用户安装CUDA
4.下载完成后执行.run文件，需要添加两个参数，一个是--override，用于跳过某些检查或限制；另一个是--toolkitpath，它表示安装路径，必须是自己目录下面的路径，如果是根目录就会安装
阅读更多2024-11-23
Python操作neo4j库py2neo使用之py2neo 删除及事务相关操作（三）
【代码】## Python操作neo4j库py2neo使用之py2neo 删除及事务相关操作（三）
阅读更多2024-11-23
【通俗理解】Jensen不等式与变分分布q(z)在积分计算中的应用
Jensen不等式 #变分分布 #积分计算 #期望 #凸函数 #优化问题 #下界估计 #机器学习。
阅读更多2024-11-23
「Mac玩转仓颉内测版27」基础篇7 - 字符串类型详解
本篇将介绍 Cangjie 中的字符串类型，包括字符串的定义、字面量形式、插值表达、常用操作及应用场景，帮助开发者熟练掌握字符串的使用。
阅读更多2024-11-23
数据科学与SQL：组距分组分析 | 区间分布问题
绝对值分布分析也可以理解为组距分组分析。对于某个指标而言，一个记录对应的指标值的绝对值，肯定落在所有指标值的绝对值的最小值和最大值构成的区间内，根据一定的算法，在把这个区间划分为等距离的几个小区间，，
阅读更多2024-11-23
c++编译报C1004错误的原因及解决办法
可能是你的代码文件最后没有正确的结束符，或者是缺少了一些必要的头文件或语句。默认磁盘驱动器没有足够的空间用于临时文件，需要大约两倍于源文件的空间。编译器到达了源文件尾但未解析构造。计算结果为假的 #i
阅读更多2024-11-23
mysql 去重补全取出重复变量函数和存储过程
mysql 去重补全取出重复变量函数和存储过程
阅读更多2024-11-23