C++ [STL之list模拟实现]

本文已收录至《C++语言》专栏！
作者：ARMCSKGT

STL之list模拟实现

前言

list的底层与vector和string不同，实现也有所差别，特别是在迭代器的设计上，本节将为大家介绍list简单实现，并揭开list迭代器的底层！
list-出自STL源码剖析

正文

本文介绍list部分简单接口，以list迭代器的介绍为主！

基本框架

list底层是一个带头双向循环链表，在节点上变化不大，主要是操作！

list整体由三个类组成：

节点类(封装一个节点)

迭代器类

list类

节点类

list节点类是一个模板类以适合于任何类型的list对象，封装了一个节点需要的基本成员：

成员变量 – 前驱指针 _prev – 后继指针 _next – 数据存储 _data

成员函数：只有一个构造函数，用于初始化节点data数据和置空指针，构造函数的value参数是缺省参数，适应不同场景注意：节点类不需要拷贝构造和析构函数，对于节点的拷贝构造在list中只需要浅拷贝即可，节点的释放也不在节点类中进行！
//节点类template<classT>structlist_node{
    list_node<T>* _prev,* _next;
    T _data;list_node(const T& value =T()):_prev(nullptr)//指针置空,_next(nullptr),_data(value)//初始化data{}};
迭代器类

迭代器类也是封装节点，但是迭代器类不会创造节点，只会利用现有节点构造一个迭代器，在迭代器内部通过各种运算符重载对节点的状态做修改！

其次，我们在使用迭代器时，会涉及返回节点指针或数据data的引用，所以需要在构造对象时将list数据类型的指针和引用类型传给迭代器对象！

迭代器在不访问data的情况下返回的都是迭代器，为了书写简洁，我们事先声明本迭代器类型self(即实例的类型)，在函数操作完成时返回self(迭代器)即可！
template<classT,classRef,classPtr>struct__list_iterator{typedef list_node<T> node;//节点指针typedef __list_iterator<T, Ref, Ptr> self;//迭代器对象(方便返回迭代器)

    node* _node;//节点__list_iterator(node* n)//默认构造函数:_node(n){}};
注意，迭代器对象不会凭空创造节点，只会利用现有的节点(迭代器节点类型与list节点类型相同)，所以不需要拷贝构造和析构函数，浅拷贝足以！

list类

list类中包含一个头节点和迭代器以及各种操作函数！
template<classT>classlist{typedef list_node<T> node;//node节点类型public:typedef T& reference;//T&引用类型typedefconst T& const_reference;//const T&引用类型private:
    node* _head;//头节点};
这里有些类型为了见名知意，进行了 typedef ！

迭代器类功能实现

在介绍list之前，我们先介绍list迭代器部分！

list迭代器

list迭代器是一个单独的struct类，使用struct是为了公开成员供用户使用！
虽然list不支持下标随机访问，但是我们希望list仍然像vector一样使用++和 - - 访问每一个节点，对于list对象，我们是无法实现的，因为对list定义的对象重载运算符++和 - - 操作会丢失节点，因为list要保存完整的节点信息，所以只能把这个功能外包给迭代器类！

list的是双向链表，就可以往后走也可以往前走，所以list迭代器是双向迭代器，但是list迭代器不支持随机访问，也就是只支持begin++和begin - -，不支持加整数(begin+3等)随机访问 (不支持随机访问) ，毕竟不是连续的空间！

迭代器分类：

单向迭代器：只支持 ++ 或 - - 一个方向上的遍历(即正向或反向)

双向迭代器：支持++和 - - 前后遍历

随机迭代器：支持通过加上一个整数的方式跳跃式随机访问(例如begin+3，只有随机迭代器才能使用库函数sort)

迭代器设计思想

我们规定list迭代器begin指向头节点所指向的下一个节点(链表中的第一个有效节点)，end指向头节点，返回的都是迭代器对象，遍历时从第一个节点开始遍历一直到头节点结束！

首先，我们的迭代器需要list实例化的数据类型，list精华在于迭代器类的设计，而迭代器类中的精华在于多参数模板，这种传多模板参数的方法，巧妙的解决了 普通对象 与 const对象 的冗余设计问题！

迭代器分为 iterator 和 const_iterator，不同的对象调用不同的迭代器类型，如果不用多参数模板，就需要写两份相差不大的迭代器类，造成代码冗余！

多参数模板：

T：节点值数据类型

Ref：节点值数据类型引用类型

Ptr：节点值数据类型指针类型

使用不同的参数组合可以实例化出不同的迭代器，这正是 泛型编程 思想之一！

因为返回类型都为迭代器对象，所以可以使用匿名对象进行构造！
list迭代器定义：
template<classT>classlist{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(){returniterator(_head->_next);} 
    iterator end(){returniterator(_head);}//普通迭代器const重载版本    
    const_iterator begin()const{returnconst_iterator(_head->_next);}
    const_iterator end()const{returnconst_iterator(_head);}//const迭代器
    const_iterator cbegin()const{returnconst_iterator(_head->_next);} 
    const_iterator cend()const{returnconst_iterator(_head);}private:
    node* _head;};
在某些场景下，使用const引用list对象传参，在内部定义迭代器或使用范围for，编译器默认范围for使用begin和end迭代器，而我们加上const而编译器无法匹配迭代器，所以普通迭代器我们提供const版本去适应不同场景！
// 例如该场景，如果没用const普通迭代器则报错voidPrint(const list<int>& ls){for(constauto& x : ls)//内部范围for调用的是const普通迭代器begin和end
        cout << x <<" ";

    cout << endl;}
在后续涉及list对象打印所有节点参数的时候会调用此函数！
迭代器操作设计
迭代器遍历：
对于迭代器的遍历，无非是前置++和 - - 以及后置++和 - - ！
对于vector，是一片连续的空间，++相当于走到下一个元素，- - 相当于回到上一个元素！
但是list是一个一个的节点，并非连续的空间，对于list迭代器的++和 - - 只能手动走向下一个节点，即_node = _node->_next !

注意： 我们直接对list迭代器中的_node进行++和 - - ，因为不是连续空间，直接进行++和 - - 会造成野指针问题；而且我们迭代器在切换节点后需要返回一个迭代器，所以返回self类型(当前迭代器类型)即可！
//返回__list_iterator对象引用
self&operator++()//前置++{
    _node = _node->_next;return*this;}//返回__list_iterator对象
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;}
对于前置操作： 我们只需要将当前迭代器节点走到下一个节点即可，然后返回迭代器！
对于后置操作： 我们需要先构造一个临时对象保存当前的节点，然后让迭代器走到下一个节点上，返回临时对象的节点即可完成后置操作！

注意： 虽然我们可以通过某些手段实现随机访问，但是效率极低，为了跟库保持一致不进行实现！
其他操作：
对于迭代器，如果我们list实例化的是指针，则需要
*
运算符解引用取值，以及因为我们嵌套了一层迭代器，在使用
->
运算符时需要返回data的地址！

因为我们在使用迭代器遍历时需要有遍历条件作为终止条件，不妨会涉及迭代器的比较，所以还需要 != 和 == 的比较操作！
//迭代器比较booloperator!=(const self& n)const{return _node != n._node;}booloperator==(const self& n)const{return _node == n._node;}//返回T&——解引用访问数据
Ref operator*(){return _node->_data;}//返回T*——自定义类型需要->访问成员(其_data可能是一个自定义类型)
Ptr operator->(){return&_node->_data;}
voidtest(){int arr[]={1,2,3,4,5,6,7,8,9,10};
    my_list::list<int>ls(arr, arr +10);//迭代器区间构造auto it = ls.begin();while(it != ls.end()){
        cout <<*it <<" ";++it;}
    cout << endl;//当然，支持迭代器就支持范围forfor(constauto& x : ls){
        cout << x <<" ";}
    cout << endl;}
迭代器中每时每刻只有一个节点指针，当我们进行遍历操作时内部改变即可，外部迭代器还是同一个迭代器对象！

list类功能实现

默认成员函数

对于list默认采成员函数无非就是我们常见的四种类默认采用函数：

构造函数(默认构造和迭代器区间构造)

拷贝构造函数

赋值重载函数

析构函数
构造函数
因为我们是带头的链表，所以在实例化时必须事先申请一个头节点，所以所有的构造函数都会在操作前申请一个头节点，为了避免代码的冗余，我们将头节点的创建封装为一个private函数，在构造函数初始化时调用创建头节点！
private:
    node* _head;voidEmpty_Init()//申请一个头节点初始化链表{
        _head =new node;
        _head->_next = _head->_prev = _head;
        _head->_data =T();}
默认构造函数需要支持构造一个空链表，也可以构造有n个value值节点的链表！
当我们需要构造空链表时，直接调用 Empty_Init 函数即可！
list(){Empty_Init();}//默认构造list(int n, const_reference value =T())//构造有n个value值节点的链表！{Empty_Init();while(n--){push_back(value);}}
但我们发现，构造有n个T类型值的链表的构造函数可以包含默认构造的功能，只需要一个缺省参数0即可；如果需要插入数据，调用push_back即可(库中没有这样实现，需要给定n指定的节点数)！
list(int n =0, const_reference value =T()){Empty_Init();while(n--){push_back(value);}}list(size_t n =0, const_reference value =T());//避免因为list(size_t,size_t)匹配上迭代器区间构造//实现与以上函数一样，但因为迭代器区间构造冲突问题不进行实现
这里的
const_reference
相当于
const T&
!

迭代器区间构造也是调用push_back进行尾插！
template<classInputIterator>//迭代器区间构造list(InputIterator first, InputIterator last){Empty_Init();while(first != last){push_back(*first);++first;}}
实例演示：
voidtest(){
    list<int> l1;//构造空的list对象
    list<int>l2(3,1);//构造有3个节点为1的list对象int arr[]={1,2,3,4,5,6,7,8,9,10};
    list<int>l3(arr, arr +10);//迭代器区间构造
    cout <<"l1:";Print(l1);
    cout <<"l2:";Print(l2);
    cout <<"l3:";Print(l3);}
Print函数是打印list对象节点的函数，在上面迭代器部分介绍过！
拷贝构造
拷贝构造需要注意深拷贝问题，当然对于自定义类型会调用其自带的拷贝构造，，其次就是对象参数需要引用，否则会引起无穷递归问题！

拷贝构造采用现代写法，构造临时对象使用swap交换，在此之前，因为是构造函数所以需要创造头节点，调用 Empty_Init() 函数，再进行拷贝！
list(const list<T>& l)//拷贝构造{Empty_Init();
    list<T>tmp(l.begin(), l.end());swap(tmp);}
实例演示：
voidtest(){
    list<int>l1(3,1);//构造有3个节点为1的list对象
    list<int>l2(l1);Print(l2);}
赋值重载
对于赋值重载，与拷贝构造相似，但是赋值重载在传递参数时使用传值传参，这样就自动帮我们构造了一个临时对象，我们只需要swap取下临时对象的头节点即可，将我们现有的链表交给临时对象销毁，这样就完成了赋值；因为我们可能会连等(l1=l2=l3等等)，所以需要返回对象的引用！
list<T>&operator=(list<T> l)//赋值重载{swap(l);return*this;}
实例演示：
voidtest(){
    list<int>l1(5,668); 
    list<int>l2(3,2); 

    cout <<"赋值前:";Print(l2);
    l2 = l1;
    cout <<"赋值后:";Print(l2);}
析构函数
析构函数需要释放所有节点以及头节点，在释放前需要判断当前链表是否为空，如果为空直接是否头节点即可！
~list(){if(!empty())//判断是否为空clear();//clear函数会清空所有节点(除了头节点)delete _head;//释放头节点
    _head =nullptr;//头节点指针置空}
容量查询

关于容量的查询，一共是查询节点数，另一个是判断链表是否为空！

节点数size：只需要全部遍历一次计数即可

判空empty：只需要判断头节点_head的_next指针是否指向自己即可
size_t size()const//获取节点数{
    size_t sz =0;
    const_iterator it =begin();while(it !=end()){++sz;++it;}return sz;}boolempty()const{return _head->_next == _head;}//判空，为空返回true
当然，这里的实现是与库中统一，我们也可以单独定义一个 _n 整型变量进行计数！

实例演示：
voidtest(){int arr[]={1,2,3,4,5,6,7,8,9,10};
    list<int>l1(arr, arr+10); 
    cout <<"size:"<< l1.size()<< endl;
    cout <<"empty:"<< l1.empty()<< endl;
    l1.clear();//清空节点
    cout <<"empty:"<< l1.empty()<< endl;}
数据访问

list常用迭代器进行数据访问，也提供了头尾节点的访问！
这里为了减少拷贝，返回的是data值的引用；当然，在访问前需要判断链表是否为空！
reference front()//访问头节点返回其data值的引用{assert(!empty());return _head->_next->_data;}

const_reference front()const//访问头节点返回其data值的const引用{assert(!empty());return _head->_next->_data;}

reference back()//访问尾节点返回其data值的引用{assert(!empty());return _head->_prev->_data;}

const_reference back()const//访问尾节点返回其data值的const引用{assert(!empty());return _head->_prev->_data;}
实例演示：
voidtest(){int arr[]={1,2,3,4,5,6,7,8,9,10};
    list<int>l1(arr, arr+10); 
    cout <<"l1:";Print(l1);
    cout <<"front node data:"<< l1.front()<< endl;
    cout <<"back node data:"<< l1.back()<< endl;}
节点插删相关

插入删除是list的优点，只要我们拿到对应的节点，就可以立即对其进行插入和删除操作！

头尾插删

头尾插删的操作主要是对头节点_head的_next节点和_prev节点进行操作！
头插
头插主要是修改原来的第一个有效节点与_head节点的链接关系，在其中链入一个新的节点！

先根据参数构建一个新节点 newnode

找到原第一个有效节点 frontnode

修改 _head 和 frontnode 链接关系，将 newnode 链入到两节点中
voidpush_front(const_reference val)//头插{
    node* newnode =newnode(val);//新节点
    node* frontnode = _head->_next;//当前第一个有效节点//修改 _head 和 frontnode 链接关系，将 newnode 链入到两节点中
    _head->_next = newnode;//头节点指向新节点
    newnode->_prev = _head;//新节点的前驱指向头节点
    newnode->_next = frontnode;//新节点指向原第一个有效节点
    frontnode->_prev = newnode;//向原第一个有效节点的前驱更新为新节点}
头删
头删也是修改原来的第一个有效节点与_head节点的链接关系，删除第一个有效节点转而让_head指向第二个有效节点！

在删除前检查是否存在有效节点

记录当前第一个有效节点frontnode

记录第二个有效节点frontnext

修改 _head 与第二个有效节点链接关系，将 frontnode 节点剥离链表

删除 frontnode 节点
voidpop_front()//头删{assert(!empty());//检查是否为空链表
    node* frontnode = _head->_next;//当前第一个有效节点
    node* frontnext = frontnode->_next;//记录第二个有效节点//让_head与第二个有效节点链接 - 剥离第一个有效节点
    _head->_next = frontnext;
    frontnext->_prev = _head;//删除原第一个有效节点delete frontnode;
    frontnode =nullptr;}
尾插
尾插节点与头插一样，修改
_head
与
backnode
的链接关系，链入新节点！

根据参数创建一个新节点 newnode

记录原尾节点 backnode

关系 _head 与 backnode 之间的链接关系，在其中链入 newnode
voidpush_back(const_reference val)//尾插{
    node* newnode =newnode(val);//新节点
    node* backnode = _head->_prev;//尾节点//更新链接关系
    _head->_prev = newnode;
    newnode->_next = _head;
    newnode->_prev = backnode;
    backnode->_next = newnode;}
尾删
尾删与头删一样，剥离尾节点，修复链接关系即可！

在删除前检查是否存在有效节点

记录原尾节点 backnode

记录尾节点的前驱节点 backprev

更新 _head 与 backprev 节点的链接更新，剥离尾节点 backnode

删除尾节点 backnode
voidpop_back()//尾删{assert(!empty());//检查是否为空链表
    node* backnode = _head->_prev;//尾节点
    node* backprev = backnode->_prev;//尾节点前驱//更新链接更新-剥离尾节点
    _head->_prev = backprev;
    backprev->_next = _head;//删除尾节点delete backnode;
    backnode =nullptr;}
实例演示：
voidtest(){int arr[]={1,2,3,4,5,6,7,8,9,10};
    list<int> l1;for(constauto& x : arr){
        l1.push_front(x);
        l1.push_back(x);}while(!l1.empty()){Print(l1);
        l1.pop_front();
        l1.pop_back();}}
任意位置插删

任意位置插删，我们约定使用迭代器指定插入位置，在当前迭代器节点前插入一个节点！

注意： 无论是任意位置删除还是任意位置插入，在操作后都需要返回一个迭代器！

对于任意位置插入，返回的是新插入节点的迭代器

对于任意位置删除，返回的是删除节点的下一个节点的迭代器
任意位置插入
任意位置插入是在pos迭代器位置前插入一个节点，并返回这个节点的迭代器！

检查pos迭代器中节点是否正常

根据参数申请一个新节点 newnode

获取pos位置节点的前驱节点 posprev

将新节点 newnode 链入 pos节点 与 pos前驱节点 之间

链入成功后返回新插入节点的迭代器
iterator insert(iterator pos, const_reference val){assert(pos._node);//确保节点非空
    node* newnode =newnode(val);//创建新节点
    node* posprev = pos._node->_prev;//获取pos节点的前驱//更新链接关系 - 将新节点链入pos节点与pos前驱节点之间
    newnode->_next = pos._node;
    newnode->_prev = posprev;
    posprev->_next = newnode;
    pos._node->_prev = newnode;//返回新节点迭代器    returniterator(newnode);}
任意位置删除
任意位置删除是删除pos迭代器位置的节点，并返回删除节点的下一个节点的迭代器！

检查链表是否为空且pos迭代器中节点是否正常且pos节点不为_head头节点

获取 pos节点 的 前驱节点posprev

获取 pos节点 的 后继节点posnext

链接 posprev 和 posnext 节点，剥离pos节点

删除pos节点

返回 posnext节点 的 迭代器(即pos的下一个节点的迭代器)
iterator erase(iterator pos){//链表非空&确保节点非空&不为头节点_headassert(!empty()&& pos._node && pos._node != _head); 

    node* posprev = pos._node->_prev;//pos的下一个节点
    node* posnext = pos._node->_next;//pos的上一个节点
    node* freenode = pos._node;//链接posprev和posnext 剥离 pos 节点
    posprev->_next = posnext;
    posnext->_prev = posprev;delete freenode;//释放pos节点returniterator(posnext);//返回pos节点的下一个节点的迭代器}
当我们实现了任意位置插入和删除，头尾插删就可以简化代码复用任意位置插删函数了！
//头插voidpush_front(const_reference val){insert(begin(), val);}//尾插voidpush_back(const_reference val){insert(end(), val);}//头删voidpop_front(){erase(begin());}//尾删voidpop_back(){erase(--end());}
实例演示：
voidtest(){int arr[]={1,2,3,4,5,6,7,8,9,10};
    list<int>l1(arr,arr+10);Print(l1);
    l1.insert(++l1.begin(),668);//在2前插入668Print(l1);
    l1.erase(--(--l1.end()));//删除9Print(l1);}
其他函数

剩余一些常用的函数有：

交换swap – 使用库函数交换头节点即可

清空函数clear – 遍历节点，逐一删除即可，但是保留头节点_head，如果链表为空则不执行

调整函数resize – 调整节点个数，只能在尾部增加节点个数，增加的节点data可以指定值
//交换voidswap(list<T>& l){ std::swap(_head, l._head);}//清空voidclear(){if(empty())return;//如果为空则不执行
    iterator it =begin();//获取迭代器//迭代器遍历逐一删除(后置++返回上一个迭代器)while(it !=end()){erase(it++);}}//调整voidresize(size_t n, const_reference val =T()){if(n >size())while(size()< n){push_back(val);}}