C++语法	相关知识点	可以通过点击	以下链接进行学习	一起加油！
命名空间	缺省参数与函数重载	C++相关特性	类和对象-上篇	类和对象-中篇
类和对象-下篇	日期类	C/C++内存管理	模板初阶	String使用
String模拟实现	Vector使用及其模拟实现

本文将通过模拟实现List，从多个角度深入剖析其底层机制，详细讲解其内部实现原理和实际应用场景，帮助读者全面理解和掌握List的工作方式。

🌈个人主页：是店小二呀

🌈C语言专栏：C语言

🌈C++专栏： C++

🌈初阶数据结构专栏： 初阶数据结构

🌈高阶数据结构专栏： 高阶数据结构

🌈Linux专栏： Linux

🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅

文章目录

前文:List介绍一、搭建创建List武器库1.1 创建节点ListNode1.2 迭代器ListIterator 1.2.1 自定义类型迭代器1.2.2 交换语句1.2.3 迭代器运算符重载1.2.3.1 前置++与后置++1.2.3.2 前置--与后缀--1.2.3.4 *运算符重载1.2.3.5 ==与!=运算符重载

二、正式模拟实现List2.1 武器库使用2.2 获得List开头和结尾迭代器2.3 关于迭代器失效2.4 insert2.5 erase 2.6 复用insert与erase完成插入与删除2.7 operator->重载2.8 const_Iterator迭代器2.8.1 实现const_Iterator迭代器2.8.2 模板整合类型问题

2.9 打印链表元素

三、常规接口实现3.1 构造函数3.2 拷贝构造3.3 operator= 赋值运算符3.4 clear 清除3.5 ~list 析构函数3.6 size 查看当前链表元素个数3.7 empty 判空

List.h

前文:List介绍

list文档介绍

list是可以在常数范围内在任意位置插入和删除的序列式容器，并且该容器可以前后双向迭代list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前面一个元素和后一个元素list与forward_list非常相似:最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效与其他的序列式容器相比，list通常在任意位置进行插入，移除元素的执行效率更好与其他序列式容器相比，list和forward_list最大的缺陷式不支持任意位置的随机访问。

在模拟实现list过程中，为了避免跟库中list发生冲突，需要创建个命名空间，在命名空间中实现list。

<code>namespace ls

{ -- -->

class list

{

};

}

list的底层是双向链表结构，而链表是通过每个独立的节点利用指针连接在一起的数据结构。节点是组成链表基本单位。模拟实现带头双向循环链表，为了适应不同的数据类型，选择采用类模板。

一、搭建创建List武器库

1.1 创建节点ListNode

template<class T>

struct ListNode

{

ListNode<T>* _next;

ListNode<T>* _prev;

T _data;

//创建节点，是传数据创建的

ListNode(const T& x = T())

:_next(nullptr)

,_prev(nullptr)

,_data(x)

{ }

};

具体说明：为了适应不同类型的节点，将创建节点设计成类模板。访问限定符一般选用struct，由于默认访问权限是公开的，节点里面数据都是可以使用。当然使用class也是可以的，只需要将访问限定符设置为public。

节点对象实例化一般是传个数值，但是为了考虑类型和是否传参，可以设置一个全缺省构造函数

1.2 迭代器ListIterator

链表通过每个节点连接在一起，但这不能保证节点间地址是连续的。对此虽然原生指针是天然的迭代器，但是建立在物理空间连续的情况下

1.2.1 自定义类型迭代器

list<T> ::iterator it = lt.begin();

while (it != lt.end())

{

*it += 10;

cout << *it;

it++;

}

由于链表节点间物理空间不连续，使用原生指针作为迭代器不能满足++或–操作。节点间又是通过指针连接在一起的，那么可以将指针封装到类中，通过运算符重载重新定义运算符的行为，达成我们的需求。不采用内置类型迭代器，选择自定义类型迭代器，其中自定义类型迭代器内部是通过指针实现的。

template<class T>

struct ListIterator

{

typedef ListNode<T> Node;

typedef ListIterator<T> Self;

Node* _node;

ListIterator(Node* node)

:_node(node)

{ }

}

注意事项:

将通过ListIterator类模板模拟实现迭代器，通过采用struct公开迭代器里面的数据 ListIterator(Node* node)，这里迭代器的实现还是依赖指针，只是通过类封装改变运算符的行为，参数部分是传递指针类型（关键）其中迭代器是作为指向作用，申请资源不属于迭代器，而属于链表，不需要考虑析构的问题，迭代器就是玩数据数据公开意味着，内部数据可以被任意修改。没人会去跳过封装，使用内部的数据，没有意义。不同编译器中底层实现是不一样的(实现逻辑、名称)，这本身就是一种隐式设置为私有的作用

1.2.2 交换语句

void swap(list<T>& it)

{

std::swap(_head, it._head);

std::swap(_size, it._size);

}

1.2.3 迭代器运算符重载

1.2.3.1 前置++与后置++

//前缀++

Self& operator++()

{

_node = _node->_next;

return *this;

}

//后缀++

Self operator++(int)

{

//构造一个tmp临时变量

Self tmp(*this);

_node = _node->_next;

return tmp;

}

1.2.3.2 前置–与后缀–

Self& operator--()

{

_node = _node->_prev;

return *this;

}

//后缀--

Self operator--(int)

{

//构造一个tmp临时变量

Self tmp(*this);

_node = _node->_prev;

return tmp;

}

具体说明:有拷贝构造就需要考虑深浅拷贝的问题。这里需要使用到浅拷贝，指向同一块空间，并且不需要考虑重复析构的问题，也说明了浅拷贝并都是坏处。临时对象tmp同指向一块空间，调用完临时对象被销毁，指向空间资源保留。这也导致了返回类型是指针还是引用。

1.2.3.4 *运算符重载

T& operator* ()

{

return _node->_data;

}

1.2.3.5 ==与!=运算符重载

//通过指针指向的节点去判断是否相等

bool operator==(const Self& it)

{

return _node == it._node;

}

bool operator!=(const Self& it)

{

return _node != it._node;

}

具体说明：

关于形参部分使用const修饰，其一为了提醒对象顺序问题，其二在while(it != lt.end())中lt.end()调用返回临时对象具有常性，在参数部分进行接收将权限降低。迭代器间的比较并不是比较指向数据，而是比较迭代器指向的位置

二、正式模拟实现List

2.1 武器库使用

前面知识是为了我们实现List提供武器库

template<class T>

class list

{

typedef ListNode<T> Node;

public:

typedef ListIterator<T> Iterator;

private:

//创建哨兵位

Node* _head;

size_t _size;

};

武器使用:

关于<code>typedef ListNode<T> Node与typedef ListIterator<T> Iterator这两个类可以当作武器库，主要是为List类提供服务。那么对于ListIterator类来说ListNode<T> Node也是当作一个武器进行使用。对于带头双向循环链表，成员对象需要哨兵位和记录个数对象。

2.2 获得List开头和结尾迭代器

Iterator begin()

{ -- -->

//return Iterator(_head->_next);

return _head->_next;

}

Iterator end()

{

//return Iterator(_head);

return _head;

}

具体说明:

由于正在使用自定义类型的迭代器，返回类型为Iterator自定义类型。返回类型可以写成Node*类型，单参数的拷贝构造函数支持隐式类型转换。

需要注意:

返回值没有传引用返回，由于该接口功能是返回开头和节点迭代器，如果传引用返回，会影响下一次调用该节点。我们不需要拿到这个位置的迭代器，只需要拿到这个位置的信息。

小插曲:隐式类型转换

list<int> :: Iterator it = (lt._head->_next);

由于_ head属于list类中的私有对象，不能直接的访问私有成员，通过公共接口访问。不同编译器底层实现是不同的，这也体现了封装的重要性。

2.3 关于迭代器失效

关于vector学习，我们知道在扩容或缩容的时候，可能会出现迭代器失效的问题。在list这里insert不会出现迭代器失效，但是erase就会出现迭代器失效。

关于解决不同编译器下erase导致迭代器失效的问题。方法有两个：迭代器失效以后，不要直接使用，如何要使用按照规则重新更新使用，返回被删除数据的迭代器。

2.4 insert

<code>void insert(Iterator pos, const T& val)

{ -- -->

Node* newnode = new Node(val);

Node* cur = pos._node;

Node* prev = cur->_prev;

newnode->_next = cur;

newnode-> _prev = prev;

cur->_prev = newnode;

prev->_next = newnode;

_size++;

}

这里跟数据结构实现双向链表任意位置插入数据的逻辑是一样的，不同的地方就是这里使用迭代器。

2.5 erase

//这些需要使用迭代器作为返回类型，怕出现迭代器失效

Iterator& erase(Iterator pos)

{

Node* cur = pos._node;

Node* next = cur->_next;

Node* prev = cur->_prev;

delete cur;

next->_prev = prev;

prev->_next = next;

_size--;

//注意点

return Iterator(next);

}

具体说明:这里跟数据结构实现双向链表任意位置删除数据的逻辑是一样的。

需要注意：返回类型需要使用迭代器类型，怕出现迭代器失效，返回下一个位置的迭代器

2.6 复用insert与erase完成插入与删除

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());

}

具体说明：

在vector实现push_back和pop_back时，通过begin和end得到迭代器指向的位置。返回变量为具有常性的临时变量，不能通过++或–对其修改。在List中迭代器可以进行++或–操作，由于不是对临时对象本身进行修改，而是在运算符重载中改变了运算符的行为，修改是临时对象指向的内容。在vector中修改是对象本身当然是不信的。

2.7 operator->重载

给出场景:关于之前类模板实例化中模板参数为内置类型，这次将T改为自定义类型，注意A是自定义类型。

struct A

{

int a1 = 0, a2 = 0;

A(int a1,int a2)

:a1(1)

,a2(2)

{ }

};

list<A> lt;

list<A> ::Iterator it = lt.begin();

lt.push_back(A(1,2));

lt.push_back({ 3,3});

while (it != lt.end())

{

cout << *it;

it++;

}

在进行cout << *it中得到该类对象，并没有得到内部数据，对此有两个解决措施:

(*it).a1直接访问成员流插入的运算符重载

我们希望得到的效果是第二种写法，第一种感觉会冗余

第一种:(*it).a1

第二种:it->_a1

重点梳理:

先梳理思路list<A> ::Iterator it代表了it属于Iterator类对象。这里将it看成迭代器，其中*被运算符重载为_node->_data，其中_data类型就是自定义类型A。那么*it行为就是得到自定义类型A对象，通过A对象.内部成员变量方式进行访问。对于第二种:也是想通过->运算符重载得到A类型对象，但是很奇怪，得到了A类型对象怎么去访问A类型对象中成员变量呢？对此编译器为了可读性，省略了一个->，实际上是这样子的it.operator->()->_a1,编译器省略之后it->_a1就可以了，提高了可读性。

//返回A类型对象指针，很合理啦

T* operator->()

{

return &_node->_data;

}

2.8 const_Iterator迭代器

2.8.1 实现const_Iterator迭代器

关于迭代器相关接口已经实现完毕，如果我们需要实现个指向内容不可以被修改的迭代器呢？

思考问题：

我们为什么要用const_Iterator而不是const Iterator呢？const修饰迭代器，是迭代器本身不能被修改，还是迭代器指向内容不能被修改呢？

<code>const Iterator begin() const

{ -- -->

return _head->_next;

}

const Iterator end() const

{

return _head;

}

我们实现const版本迭代器目的就是为了指向内容不被修改。

分析过程：

Iterator是一个类，如果在前面加const，它表示的意思是这个类对象本身不能被修改，而不是指向内容不能被修改。实现链表的迭代器不是内置类型，而是自定义类型，在自定义类型前面使用const修饰代表本身不能被修改，会导致++或–运算符之类的运算符重载会失效。指出问题:迭代器指向内容是否被修改，需要对实现迭代器的类里面解引用运算符重载进行const修饰

template<class T>

struct ListConIterator

{

typedef ListNode<T> Node;

typedef ListConIterator<T> Self;

//只针对解引用 修改了迭代器的行为 但是++ --是将迭代器位置改变，迭代器指向的内容不能被修改

Node* _node;

//迭代器还是依赖指针，通过类来改变运算符的行为

//这里是浅拷贝 拷贝构造函数

ListIterator(Node* node)

:_node(node)

{ }

Self& operator++()

{

_node = _node->_next;

return *this;

}

//后缀++

Self operator++(int)

{

//构造一个tmp临时变量

Self tmp(*this);

_node = _node->_next;

return tmp;

}

//这里需要判断空

Self& operator--()

{

_node = _node->_prev;

return *this;

}

//

//后缀--

Self operator--(int)

{

//构造一个tmp临时变量

Self tmp(*this);

_node = _node->_prev;

return tmp;

}

const T& operator* ()

{

return _node->_data;

}

//通过指针指向的节点去判断是否相等

bool operator==(const Self& it)

{

return _node == it._node;

}

bool operator!=(const Self& it)

{

return _node != it._node;

}

const T* operator->()

{

return &_head->_data;

}

};

具体说明:将解引用操作符重载的返回值用const修饰，保证返回的数据不能被修改。这里没有对++和–的返回值进行修饰，因为++和–并不直接影响迭代器的内容，是针对迭代器（it）本身。

2.8.2 模板整合类型问题

不足之处:对于Ierator类与const_Ierator类的解引用运算符重载大体功能相同，主要区别在于不同情况下需要使用返回值类型不同，实现两个类显得有点冗余。如果问题是在于类型上差异导致的，可以将两个封装到同一个类中，使用模板实现。

typedef ListIterator<T, T&, T*> Iterator;

typedef ListIterator<T, const T&, const T*> const_Iterator;

template<class T,class Ref, class Ptr>

struct ListIterator

{

typedef ListNode<T> Node;

typedef ListIterator<T,Ref,Ptr> Self;

Node* _node;

//迭代器还是依赖指针，通过类来改变运算符的行为

//这里是浅拷贝 拷贝构造函数

ListIterator(Node* node)

:_node(node)

{ }

//Self& operator++()

Self& operator++()

{

_node = _node->_next;

return *this;

}

//后缀++

Self operator++(int)

{

//构造一个tmp临时变量

Self tmp(*this);

_node = _node->_next;

return tmp;

}

Self& operator--()

{

_node = _node->_prev;

return *this;

}

//后缀--

Self operator--(int)

{

//构造一个tmp临时变量

Self tmp(*this);

_node = _node->_prev;

return tmp;

}

// T& operator* ()

Ref operator* ()

{

return _node->_data;

}

//通过指针指向的节点去判断是否相等

bool operator==(const Self& it)

{

return _node == it._node;

}

bool operator!=(const Self& it)

{

return _node != it._node;

}

//T* operator->()

Ptr operator->()

{

return &_head->_data;

}

};

2.9 打印链表元素

void PrintList(const list<int>& clt)

{

list<int> ::Iterator it = clt.begin();

while (it != clt.end())

{

*it += 10;

cout << *it << " ";

++it;

}

cout << endl;

}

三、常规接口实现

3.1 构造函数

void empty_init()

{

_head = new Node;

_head->_next = _head;

_head->_prev = _head;

_size = 0;

}

构造和拷贝构造都需要一份节点，那么可以复用一份

这里不需要对_data进行初始化，在new Node时已经完成

list()

{

empty_init();

}

3.2 拷贝构造

list(const list<T>& lt)

{

empty_init();

for (auto e : lt)

{

push_back(e);

}

}

3.3 operator= 赋值运算符

list<T>& operator=(list<T> it)

{

swap(it);

return *this;

}

3.4 clear 清除

void clear()

{

Iterator it = begin();

while (it != end())

{

it = erase(it);

}

}

说明:

这里是简单的资源清除，没有删除哨兵位同时在使用erase时，需要将下一个位置迭代器返回

3.5 ~list 析构函数

~list()

{

clear();

delete _head;

_head = nullptr;

}

3.6 size 查看当前链表元素个数

//获得基本信息

size_t size()

{

return _size;

}

3.7 empty 判空

bool empty()

{

return _size == 0;

}

---

List.h

#include <iostream>

using namespace std;

//链表 任意位置插入 不怕迭代器失效

//链表 任意位置删除 怕迭代器失效 对此需要传下一个位置的迭代器

namespace bit

{

//节点

template<class T>

struct ListNode

{

ListNode<T>* _next;

ListNode<T>* _prev;

T _data;

//创建节点，是传数据创建的

ListNode(const T& x = T())

:_next(nullptr)

,_prev(nullptr)

,_data(x)

{ }

};

//template<class T>

//

template<class T,class Ref, class Ptr>

struct ListIterator

{

typedef ListNode<T> Node;

typedef ListIterator<T,Ref,Ptr> Self;

Node* _node;

//迭代器还是依赖指针，通过类来改变运算符的行为

//这里是浅拷贝 拷贝构造函数

ListIterator(Node* node)

:_node(node)

{ }

//Self& operator++()

Self& operator++()

{

_node = _node->_next;

return *this;

}

//后缀++

Self operator++(int)

{

//构造一个tmp临时变量

Self tmp(*this);

_node = _node->_next;

return tmp;

}

Self& operator--()

{

_node = _node->_prev;

return *this;

}

//后缀--

Self operator--(int)

{

//构造一个tmp临时变量

Self tmp(*this);

_node = _node->_prev;

return tmp;

}

// T& operator* ()

Ref operator* ()

{

return _node->_data;

}

//通过指针指向的节点去判断是否相等

bool operator==(const Self& it)

{

return _node == it._node;

}

bool operator!=(const Self& it)

{

return _node != it._node;

}

//T* operator->()

Ptr operator->()

{

return &_head->_data;

}

};

//template<class T>

//struct ListConIterator

//{

//typedef ListNode<T> Node;

//typedef ListConIterator<T> Self;

////只针对解引用 修改了迭代器的行为 但是++ --是将迭代器位置改变，迭代器指向的内容不能被修改

//Node* _node;

////迭代器还是依赖指针，通过类来改变运算符的行为

////这里是浅拷贝 拷贝构造函数

//ListIterator(Node* node)

//:_node(node)

//{}

//Self& operator++()

//{

//_node = _node->_next;

//return *this;

//}

////后缀++

//Self operator++(int)

//{

////构造一个tmp临时变量

//Self tmp(*this);

//_node = _node->_next;

//return tmp;

//}

////这里需要判断空

//Self& operator--()

//{

//_node = _node->_prev;

//return *this;

//}

////

//

////后缀--

// Self operator--(int)

//{

////构造一个tmp临时变量

//Self tmp(*this);

//_node = _node->_prev;

//return tmp;

//}

//

// T& operator* ()

//{

//return _node->_data;

//}

////通过指针指向的节点去判断是否相等

//bool operator==(const Self& it)

//{

//return _node == it._node;

//}

//bool operator!=(const Self& it)

//{

//return _node != it._node;

//}

// T* operator->()

//{

//return &_head->_data;

//}

//};

template<class T>

class list

{

typedef ListNode<T> Node;

public:

//typedef ListIterator<T> Iterator;

typedef ListIterator<T, T&, T*> Iterator;

typedef ListIterator<T, const T&, const T*> const_Iterator;

//不要传引用，不要修改这些位置

Iterator begin()

{

//return Iterator(_head->_next);

//单参数的拷贝构造函数支持隐式类型转换

return _head->_next;

}

Iterator end()

{

//return Iterator(_head);

return _head;

}

const Iterator begin() const

{

return _head->_next;

}

const Iterator end() const

{

return _head;

}

const_Iterator begin() const

{

//return Iterator(_head->_next);

//单参数的拷贝构造函数支持隐式类型转换

return _head->_next;

}

const_Iterator end() const

{

//return Iterator(_head);

return _head;

}

//构造-->同时拷贝需要也需要一份节点 那么就可以复用同一份

void empty_init()

{

_head = new Node;

_head->_next = _head;

_head->_prev = _head;

//不需要 newndoe->date 在实例化时，data已经是0了

_size = 0;

}

list()

{

empty_init();

}

//拷贝构造

list(const list<T>& lt)

{

empty_init();

for (auto e : lt)

{

push_back(e);

}

}

list<T>& operator=(list<T>& it)

{

swap(it);

return *this;

}

void swap(list<T>& it)

{

std::swap(_head, it._head);

std::swap(_size, it._size);

}

//通过迭代器来实现

void insert(Iterator pos, const T& val)

{

Node* newnode = new Node(val);

Node* cur = pos._node;

Node* prev = cur->_prev;

newnode->_next = cur;

newnode-> _prev = prev;

cur->_prev = newnode;

prev->_next = newnode;

_size++;

}

//这些需要使用迭代器作为返回类型，怕出现迭代器失效

Iterator& erase(Iterator pos)

{

Node* cur = pos._node;

Node* next = cur->_next;

Node* prev = cur->_prev;

delete cur;

next->_prev = prev;

prev->_next = next;

_size--;

//注意点

return Iterator(next);

}

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());

}

void clear()

{

Iterator it = begin();

while (it != end())

{

it = erase(it);

}

}

~list()

{

clear();

delete _head;

_head = nullptr;

}

//获得基本信息

size_t size()

{

return _size;

}

bool empty()

{

return _size == 0;

}

private:

//创建哨兵位

Node* _head;

size_t _size;

};

struct A

{

int a1 = 0, a2 = 0;

A(int a1 , int a2)

:a1(1)

,a2(2)

{ }

};

void PrintList(const list<int>& clt)

{

list<int> ::Iterator it = clt.begin();

while (it != clt.end())

{

*it += 10;

cout << *it << " ";

++it;

}

cout << endl;

}

void list_test()

{

//list<int> it;

先插入

//it.push_back(1);

//it.push_back(2);

//list<int> :: Iterator lt = it.begin();

//A* ptr = &a1

// (*ptr).a1;

// ptr->_a1

//返回的是临时变量 是一份临时拷贝 具有常性

list<A> lt;

list<A> ::Iterator it = lt.begin();

lt.push_back(A(1,2));

lt.push_back({ 3,3});

while (it != lt.end())

{

cout << *it;

it++;

}

}

}

---

---

以上就是本篇文章的所有内容，在此感谢大家的观看！这里是店小二呀C++笔记，希望对你在学习C++语言旅途中有所帮助！