【c++】:list模拟实现“任意位置插入删除我最强ƪ(˘⌣˘)ʃ“

 

 

文章目录

• 前言
• 一.list的基本功能的使用
• 二.list的模拟实现
• 总结

 

---

前言

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。

4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。

5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

下面我们可以看一下list的实现图：

---

 

 

一、list的基本功能的使用

我们先看看list有哪些接口：

其实list的接口并不多，对于链表而言我们在数据结构中就学过，无非就是头插尾插，头删尾删以及任意位置的插入删除等，下面我们就讲解一下一些常用的接口该如何使用：

首先要注意包list的头文件#include <list>

void test1()
{list<int> ls;ls.push_back(1);ls.push_back(2);ls.push_back(3);ls.push_back(4);list<int>::iterator it = ls.begin();while (it != ls.end()){cout << *it << " ";++it;}cout << endl;
}
int main()
{test1();return 0;
}

 上面是尾插push_back接口的使用和迭代器的使用，迭代器还是与前面的容器一样都是这样的用法，但是他们的底层实现已经天差万别了，我们模拟的时候会详细的介绍。

接下来我们头插一个99.

 size是链表中的元素个数，empty是判断链表是否为空：

front返回链表中第一个节点值的引用，back返回链表中最后一个节点的引用。

void test2()
{list<int> ls;ls.push_back(1);ls.push_back(2);ls.push_back(3);ls.push_back(4);for (auto e : ls){cout << e << " ";}cout << endl;ls.pop_back();ls.pop_front();for (auto e : ls){cout << e << " ";}cout << endl;
}
int main()
{//test1();test2();return 0;
}

 pop_back是尾删，pop_front是头删。接下来我们再演示一下插入，删除，清空就结束。

clear():将list中的有效元素清空：

 insert():

 我们已经学过vector，可以发现这里insert接口参数都是一样的用迭代器进行插入：

erase也是同理：

 在这里我们为什么--了一下end()才删掉最后一个元素呢？因为end()是哨兵位的头结点，我们不能将头结点删除：

 由于list底层是双向带头循环链表，所以头结点的前一个就是最后一个元素。

 我们之前讲过vector的迭代器失效问题，那么erase会导致迭代器失效吗？答案是一定会失效，因为pos位置都被删掉了，要解决这个办法我们只需要把pos后的迭代器给it即可，如下图：

void test3()
{list<int> ls;ls.push_back(1);ls.push_back(2);ls.push_back(3);ls.push_back(4);list<int>::iterator it = ls.begin();while (it != ls.end()){ls.erase(it);++it;}cout << endl;
}
int main()
{//test1();//test2();test3();return 0;
}

我们的目的是依次删除链表中的元素，然后当我们运行起来：

这时候我们像刚刚将的那样解决一下：

 这也证明了在erase一个pos位置后，这个位置的迭代器会失效。

当然还有一些功能对我们刷题很有用，如下：

 这些功能有链表的拼接，合并，反转等大家刷题的时候想用可直接查看原文档。

接下来我们就进入模拟list的环节。

 二、list的模拟实现

同样我们先看一下STL源码：

 我们可以看到对于单个节点的实现源码中用了struct，对于c++中是用struct还是用class是视情况而定的，如果你想要这个类里面的东西全部公开那就用struct，因为struct中的成员默认就是公有的。

下面的迭代器我们可以看到很复杂，这就与我们刚开始所说的迭代器的底层实现已经发生了巨大改变，我们讲到迭代器会详细的介绍，这里就先讲解list中的成员：

 我们可以看到库中对于list也是用空间配置器开空间的与vector一样，然后在list中有一个node的成员，这个是什么呢？看下图：

 link_type其实就是list_node*的重命名，也就是说实际上是一个链表节点的指针。然后通过我们之前对双向带头循环链表的知识不难判断这里就是哨兵位头结点，接下来我们看一下list的构造函数：

这个empty_initialize是什么呢？看下图：

原来这就是一个对头节点进行初始化的函数，先开一个头结点，然后让这个头结点的前后指针都指向自己。

看完了源码现在我们就正式的开始模拟实现：

#pragma once
#include <iostream>
using namespace std;
#include <assert.h>namespace sxy
{template<class T>struct list_node{list_node<T>* _prev;list_node<T>* _next;T _data;};template<class T>class list{public:typedef list_node<T> node;void empty_init(){_head = new node;_head->_next = _head;_head->_prev = _head;}private:node* _head;};void test1(){}
}

 首先我们为了防止和库中命名冲突将要写的list放入命名空间，因为list要容纳任意类型所以我们必须用模板参数，对于一个链表节点我们和库中一样都用struct，有一个该类型的prev指针和一个next指针，然后还有一个模板类型的data变量。接下来我们创建list类，由于要经常用到节点指针所以我们直接将节点重命名为node，然后创建一个哨兵位的头结点_head，我们也像库中实现的那样专门用一个函数去初始化这个头节点，初始化头结点的步骤是：先给_head指针开一个节点空间，然后将这个节点的前后两个指针都指向自己。

对于构造函数，我们直接初始化一下头结点即可：

        list(){empty_init();}

 接下来我们直接写一个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;}

 对于尾插来说，就是将最后一个节点的next连接新节点，新节点的prev连上前一个节点，然后再将新节点与头结点相连形成循环即可。我们可以看到给newnode开空间的时候我们初始化为x，那么这个时候一定要想到list_node的构造函数是否写了，因为我们没写所以给list_node写一个带缺省值的构造函数：

    struct list_node{list_node(const T& x = T()):_data(x),_next(nullptr),_prev(nullptr){}list_node<T>* _prev;list_node<T>* _next;T _data;};

在这里缺省值一定是T类型的匿名对象，因为list是针对任何类型的，用匿名对象做缺省值会去调用其类型的默认构造。 

这样我们的尾插应该是成功了，如下图：

 下面我们开始实现迭代器：

如上图，对于list的迭代器我们不能再像vector一样简单的让指针加加减减了，因为链表中每个节点的地址是不连续的，指针++并不是下一个节点的地址，这个时候我们看看库中是如果搞定迭代器的：

 通过源码我们发现list迭代器的++实际上是让此节点变成下一个节点，这个时候我们应该能明白，我们直接用一个节点指针就能搞定迭代器了，用这个指针我们就可以让节点变成下一个节点或者上一个节点。

    template<class T>struct list_iterator{typedef list_node<T> node;typedef list_iterator<T> self;node* _node;list_iterator(node* n):_node(n){}T& operator*(){return _node->_data;}self& operator++(){_node = _node->_next;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const self& it){return _node != it._node;}bool operator==(const self& it){return _node == it._node;}};

 我们首先从迭代器的构造函数开始讲解：

        list_iterator(node* n):_node(n){}

 因为我们的迭代器本质是一个链表的节点，所以我们的构造函数的参数也是一个节点，初始化就是用这个节点初始化即可。

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

 解引用符号本质就是找到其节点所保存的数据，所以返回data即可，返回类型用T&可以减少拷贝。

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

 前置加加就比较简单了，对于迭代器的++其实就是指向下一个节点，所以我们让节点变成next即可，由于这里++后还是个迭代器我们必须返回其迭代器，而迭代器类型为list_iterator<T>太过繁琐我们直接typedef为self，所以返回self&即可。

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

对于后置++而言我们要用一个tmp变量，tmp是此迭代器的拷贝构造，虽然我们没有写拷贝构造但是编译器默认生成的拷贝构造完全可以完成拷贝一个节点的任务，对于一个节点浅拷贝就刚好满足我们的需求。

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

 前置--和后置--与++同理。

对于迭代器来说，我们需要判断两个迭代器是否相等是否不相等：

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

 判断是否相等很简单，直接判断两个迭代器所在的节点是否相等。

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

 解决完迭代器后一定要在list类中重新定义一下迭代器，不然名字太长了，如下：

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

 因为我们的迭代器实现是用struct重新创建的，所以返回的时候我们不能像之前那样直接返回头结点，我们返回的类型必须是迭代器，所以对于begin我们返回一个匿名对象并且用头结点的下一个节点初始化。而end就用头结点即可，如下图：

下面我们试试迭代器是否能正常使用：

 很明显是可以使用的，我们之前实现过string，vector，迭代器都有相应的const版本，那么我们这个迭代器如何实现const版本呢？

 我们看到对于const对象现在确实不能使用迭代器，我们可以这样吗？

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

 我们看到确实能正常编译了，但是对于const迭代器而言我们的目的是不可以修改迭代器所指向的内容，而迭代器本身可以++ --等，那么现在符合我们的预期吗，如下图：

 对于const对象来讲现在竟然可以修改其内容了，所以上面我们写的const迭代器一定是错误的，那么该怎么办呢？

 同样上图中对于const迭代器的使用也是不正确的，如果将const位于迭代器之前这样迭代器就无法++ --了，也是达不到我们的预期的。

所以我们给出第一种解决办法：

    template<class T>struct list_const_iterator{typedef list_node<T> node;typedef list_const_iterator<T> self;node* _node;list_const_iterator(node* n):_node(n){}const T& operator*(){return _node->_data;}self& operator++(){_node = _node->_next;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const self& it){return _node != it._node;}bool operator==(const self& it){return _node == it._node;}};

const迭代器的不同点就是对于*解引用的内容不可以被修改，所以我们将operator*的返回值设为const T&,这样是可以的。

        typedef list_node<T> node;typedef list_iterator<T> iterator;typedef list_const_iterator<T> const_iterator;iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}

但是这样实现会不会太浪费了呢？const与普通迭代器的区别只是operator的返回值不同，其他的函数都是一样的，有什么办法可以只用普通迭代器就能既完成普通的又完成const迭代器呢？答案是有的，我们之前看源码可以看到源码中的迭代器的模板参数比我们多了两个，这就是解决这类问题的。如下：

    template<class T,class Ref>struct list_iterator{typedef list_node<T> node;typedef list_iterator<T,Ref> self;node* _node;list_iterator(node* n):_node(n){}Ref operator*(){return _node->_data;}self& operator++(){_node = _node->_next;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const self& it){return _node != it._node;}bool operator==(const self& it){return _node == it._node;}};

        typedef list_node<T> node;typedef list_iterator<T,T&> iterator;typedef list_iterator<T,const T&> const_iterator;iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}

 我们直接多给一个模板参数Ref，让operator *的返回值为Ref，然后我们在list中typedef的时候将list_iterator<T,T&>为普通迭代器，list_iterator<T,const T&>为const迭代器，这样一来一旦有const对象调用迭代器就会调用这个const T&的参数，然后普通迭代器中operator *的返回值就变成了constT&.对于迭代器来说，要么是原生指针，要么是自定义类型对原生指针的封装，模拟指针的行为。

 对于上图中这样的自定义类型我们是无法去直接打印链表中的值的，如下图：

当然也确实可以打印，但是会比较麻烦，比如下面这样：

 所以我们想要让自定义类型的访问也方便应该让迭代器重载->操作符，不然就会像上图中圈出来的那样访问太过麻烦，而库中对于这方面的解决办法也是多加一个模板参数，如下：

    template<class T,class Ref,class Ptr>struct list_iterator{typedef list_node<T> node;typedef list_iterator<T,Ref,Ptr> self;node* _node;list_iterator(node* n):_node(n){}Ref operator*(){return _node->_data;}self& operator++(){_node = _node->_next;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}Ptr operator->(){return &_node->_data;}bool operator!=(const self& it){return _node != it._node;}bool operator==(const self& it){return _node == it._node;}};

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

这样就解决了上述我们所说的问题。

接下来我们实现insert接口：

        void insert(iterator pos, const T& x){node* cur = pos._node;node* prev = cur->_prev;node* newnode = new node(x);newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;prev->_next = newnode;}

对于插入我们并不陌生，只需要将新节点插入到pos的前一个节点和pos位置中间即可，让新节点的next连接pos位置的节点，pos位置的节点的prev连接新节点，再将新节点与prev节点相连即可。

实现了insert，我们就可以复用实现头插尾插了：

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

 接下来我们实现erase接口：

        iterator erase(iterator pos){assert(pos!=end());node* prev = pos._node->_prev;node* tail = pos._node->_next;prev->_next = tail;tail->_prev = prev;delete pos._node;return iterator(tail);}

 对于erase，首先我们是不可以删除哨兵位的头结点的，所以我们断言一下，end()的位置就是头结点的位置。删除pos位置就是将pos 的前一个节点和pos的后一个节点相互连接即可。然后delete掉pos位置的节点，前面我们讲过为了防止erase后迭代器失效我们要返回pos位置节点的下一个节点，所以我们返回一个迭代器的匿名对象，用pos的下一个节点初始化即可。

有了erase接口我们就可以复用头删，尾删了：

        void pop_front(){erase(begin());}void pop_back(){erase(_head->_prev);}

下面实现一下clear()接口：

        void clear(){iterator it = begin();while (it != end()){it = erase(it);}}

在这个接口就体现出我们实现erase让其返回下一个节点的重要性了，如果不这样做这里迭代器失效是无法持续删除的。

        void clear(){iterator it = begin();while (it != end()){//it = erase(it);erase(it++);}}

 当然我们也可以用后置++，也可以完成c连续删除的任务。

接下来是析构函数：

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

 析构函数和clear的区别在于析构函数要释放哨兵位的头结点，释放后将头结点置为空。

接下来是用迭代器区间构造：

        template<class Iterator>list(Iterator first, Iterator last){empty_init();while (first != last){push_back(*first);++first;}}

 首先我们用迭代器区间构造是一个个push_back，而我们要用push_back()必须得有哨兵位的头结点，所以我们先对空初始化然后依次push_back()即可。对于迭代器区间构造我们之前说过，这里的迭代器可以是任意类型的比如string，vector，所以我们必须用一个模板参数Iterator。

拷贝构造函数：

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

 对于拷贝构造函数，我们先讲头结点初始化，然后依次尾插ls的节点即可。

当然还有一种现代写法的拷贝构造函数：

        list(const list<T>& ls){empty_init();list<T> tmp(ls.begin(), ls.end());swap(tmp);}void swap(list<T>& ls){std::swap(_head, ls._head);}

 我们先开一个头结点然后初始化，用迭代器区间构造一个与ls对象一样的tmp链表，然后再将tmp和*this交换交换指针指向即可。

接下来是赋值重载：

        list<T>& operator=(list<T> ls){swap(ls);return *this;}

赋值重载就很简单了，首先我们是传值传参，ls是一份临时拷贝，我们直接用这个临时变量和*this交换即可，然后返回*this.

 以上就是list的完整模拟实现了。

下面我们放一张vector与list的对比图：

 

 

---

总结

list的模拟实现中最难理解的就是迭代器的构造，对于list的迭代器我们一定要多练习才能真正的掌握。