文章目录

• 1、前提说明
• 2、构造与析构接口模拟
• • 2.1 构造相关
  • • 2.1.1默认的无参构造
    • 2.1.2 n个值为value的构造
    • 2.1.3 拷贝构造
    • 2.1.4 通过迭代器实现的区间构造
  • 2.2 析构相关
  • 2.3 赋值运算符重载
• 3、迭代器接口模拟
• • 3.1 list中的迭代器是什么？
  • 3.2 list中的迭代器实现方法
  • • 3.2.1 正向迭代器实现
    • 3.2.2反向迭代器实现
• 4、容量相关的接口模拟
• • 4.1 获取链表有效元素个数
  • 4.2 判断链表是否为空
  • 4.3 调整链表有效元素个数
• 5、元素访问相关接口模拟
• • 5.1 访问链表第一个元素
  • 5.2 访问链表的最后一个元素
• 6、链表修改相关接口
• • 6.1 尾插&&尾删
  • 6.2 头插&&头删
  • 6.3 任意位置插入
  • 6.4任意位置删除
• 7、其他接口
• • 7.1 清除有效元素
  • 7.2 交换两个链表
• 8、接口测试
• • 8.1 构造&&析构的测试
  • 8.2 迭代器的测试
  • 8.3 容量&&元素访问测试
  • 8.4 修改相关接口测试

1、前提说明

本文只是对list容器中相关的基础、常用接口进行模拟。
为了避免与STL中的list存在冲突，本次模拟的所有接口均在自定义的命名空间下
list是一个带头结点的双向循环链表，我们可以通过以下一个类来描述list容器中存放的每个结点的形式

template<class T>class ListNode{public:ListNode<T>* next;//下一个结点的地址ListNode<T>* prev;//前一个结点的地址T data;//数据域ListNode(const T& value = T()):next(nullptr), prev(nullptr), data(value){}};

🆗，接下来我们开始实现相关接口并进行测试

2、构造与析构接口模拟

2.1 构造相关

由于list是一个带头节点的双向循环链表。对于每一个链表，即使是空链表，也会有一个头节点。因此将头节点的创建封装为一个方法，属性设置为私有。不暴露给外部，仅供内部成员使用。

2.1.1默认的无参构造

list();

2.1.2 n个值为value的构造

list(size_t n,const T& value);

注意：此处的第一个参数如果为size_t类型，在调用该接口进行构造的时候会并不会调用到该接口，而是会调用区间构造的接口，进而引发程序错误。
因此，在实现该接口的时候有两种方式避免该错误：
①将该接口的第一个参数类型改为int
②新增一个第一个参数为in类型的相同接口

2.1.3 拷贝构造

list(const list& L);

上图中还有一个致命性的错误：const对象调用了非const的成员函数。图中方框的begin和end应该换为cbegin和cend

对于上图中的思考题，我们在下面的迭代器部分会详细展开，读者们稍安勿躁~

2.1.4 通过迭代器实现的区间构造

llist(Iterator first,Iterator last);

2.2 析构相关

主要的工作就是对资源进行释放

2.3 赋值运算符重载

为了方便我们后期的代码测试容易看到结果，这里我们实现一个打印链表的接口

template<class T>class PrintList(list<T>& L){auto iter = L.begin();while (iter != L.end()){cout << *iter << " ";++iter;}cout << endl;};

3、迭代器接口模拟

好的，带着上面的问题，我们一起来揭开list迭代器的神秘面纱！

3.1 list中的迭代器是什么？

list中的迭代器与之前学过的string、vector等有着本质的区别。

string、vector中的迭代器其实就是一个原生态的指针，因为这两个容器底层空间是连续的这一特性，原生态的指针具有的操作也就能够满足容器的需求

list中的迭代器“追根溯源”，其实也是一个原生态的指针，但是不能直接将其设置为原生态的指针，而是应该将原生态的指针重新包装一下，封装成为一个类，在该类中提供一些方法，使得用户在使用该迭代器访问元素的时候是透明的（也就是说不需要考虑底层的数据结构）

看完这段话是否有点懵逼？不急，图解带你理清思路！
①观察下面的双向链表图解，理清需求：通过迭代器遍历打印结点中的值

②分别分析迭代器为原生态指针和原生态指针的封装的可行性

对于原生态指针的分析如下图：

结论1：lis中的迭代器一定不是原生态的指针

对于原生态指针的封装 进行分析

结论2：list的迭代器是通过对原生态指针进行封装，并提供相关操作接口这样的方式实现的

3.2 list中的迭代器实现方法

好的，下面我们就着手来模拟实现list的迭代器！
有了上面的知识的过渡，现在直接给出迭代器实现的相关内容

3.2.1 正向迭代器实现

//正向迭代器template<class T,class Ref,class Ptr>class ListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;public:ListIterator(Node* pNode = nullptr):_pNode(pNode){}//解引用Ref operator*(){return _pNode->data;}//->操作（只有当T是自定义类型才有意义）Ptr operator->(){return &_pNode->data;}//前置++Self& operator++(){_pNode = _pNode->next;return *this;}//后置++Self operator++(int){Self tmp(*this);_pNode = _pNode->next;return tmp;}//前置--Self& operator--(){_pNode = _pNode->prev;return *this;}//后置--Self operator--(int){Self tmp(*this);_pNode = _pNode->prev;return tmp;}//比较bool operator==(const Self& it){return _pNode == it._pNode;}bool operator!=(const Self& it){return _pNode != it._pNode;}public:Node* _pNode;};

3.2.2反向迭代器实现

//反向迭代器（就是对正向迭代器的一种重新包装）template<class Iterator>class ListReverseIterator{public:typedef typename Iterator::Reference Reference;typedef typename Iterator::Pointer Pointer;typedef ListReverseIterator<Iterator> Self;ListReverseIterator(Iterstor it):_it(it){}Reference operator*(){auto tmp = _it;--tmp;return *tmp;}Pointer operator->(){return &(operator*());}Self& operator++(){--_it;return *this;}Self operator++(int){Self tmp(*this);--_it;return tmp;}Self& operator--(){++_it;return *this;}Self operator--(int){Self tmp(*this);++_it;return tmp;}bool operator==(const Self& rit){return _it == rit._it;}bool operator!=(const Self& rit){return _it != rit._it;}public:Iterator _it;//正向迭代器};

4、容量相关的接口模拟

4.1 获取链表有效元素个数

size_t size()const;

4.2 判断链表是否为空

bool empty()const;

4.3 调整链表有效元素个数

void resize(size_t newsize,const T& value = T());

5、元素访问相关接口模拟

5.1 访问链表第一个元素

T& front(); | const T& front()const;

5.2 访问链表的最后一个元素

T& back(); | const T& back()const;

6、链表修改相关接口

6.1 尾插&&尾删

void push_back(const T& value);
void pop_back();

6.2 头插&&头删

void push_front(const T& value);
void pop_front();

6.3 任意位置插入

iterator insert(iterator Insertpos,const T& value);

6.4任意位置删除

iterator erase(iterator Erasepos);

iterator erase(iterator first,iterator last);

7、其他接口

7.1 清除有效元素

void clear();

7.2 交换两个链表

void swap(list& L);

8、接口测试

8.1 构造&&析构的测试

8.2 迭代器的测试

1、正向迭代器

2、反向迭代器

8.3 容量&&元素访问测试

8.4 修改相关接口测试

欧克~感谢大家能够看到文末，在这里附上list模拟实现的源代码，大家戳这里获取

下篇总结栈和队列，我们下篇再见！