【C++】list模拟实现

🔥个人主页： Forcible Bug Maker
🔥专栏： STL || C++

前言

本篇博客主要内容：STL库中list的模拟实现。

实现list就和之前的vector和string大不相同了，vector和string的底层结构是顺序表，而list的底层是链表，学习list的底层实现，了解顺序表和链表的区别是至关重要的，如果对这部分内容不太了解，可以参考这篇博客：初阶数据结构-顺序表和链表（C语言）
本篇的list实现中，迭代器的实现是重难点，它不再和以前的实现一样，只是单纯的原生指针，而是一个迭代器模板类。希望大家在了解list迭代器的实现之后，能对STL库中容器的迭代器有着更深的认识。

🌈list需要实现的结构和接口函数

list建议在vector的实现基础上进行，同样涉及到了模板的使用，而且更为复杂。本篇list的模拟实现并不会将接口函数的声明和定义分离，函数体统一实现在模板类内部。我们在定义链表list之前需要两个结构体内容，一个是结点Node，另一个是迭代器ListIterator。
先来看看需要实现的接口函数：

#pragma once
#include
#include
using namespace std;

namespace ForcibleBugMaker
{
    // List的结点类
    template<class T>
    struct ListNode
    {
        ListNode(const T& val = T());
        ListNode<T>* _pPre;
        ListNode<T>* _pNext;
        T _val;
    };

    //List的迭代器类
    template<class T, class Ref, class Ptr>
    class ListIterator
    {
        typedef ListNode<T>* PNode;
        typedef ListIterator<T, Ref, Ptr> Self;
    public:
        ListIterator(PNode pNode = nullptr);
        ListIterator(const Self& l);
        Ref operator*();
        Ptr operator->();
        Self& operator++();
        Self operator++(int);
        Self& operator--();
        Self& operator--(int);
        bool operator!=(const Self& l);
        bool operator==(const Self& l);
        PNode _pNode;
    };

    //list类
    template<class T>
    class list
    {
    	// typedef结点为Node
    	// 不然每次类型都写ListNode会比较麻烦
        typedef ListNode<T> Node;
        typedef Node* PNode;
    public:
    	// 下面两个typedef使编译器分别构造了两个类型的迭代器
    	// iterator和const_iterator
        typedef ListIterator<T, T&, T*> iterator;
        typedef ListIterator<T, const T&, const T*> const_iterator;
    public:
        // List的默认成员函数
        list();
        list(int n, const T& value = T());
        
        template <class Iterator>
        list(Iterator first, Iterator last);
        
        list(const list<T>& l);
        list<T>& operator=(list<T> l);
        ~list();
        
        // List Iterator
        iterator begin();
        iterator end();
        const_iterator cbegin();
        const_iterator cend();

        // List Capacity
        size_t size()const;
        bool empty()const;
        
        // List Access
        T& front();
        const T& front()const;
        T& back();
        const T& back()const;

        // List Modify
        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()); }
        // 在pos位置前插入值为val的节点
        iterator insert(iterator pos, const T& val);
        // 删除pos位置的节点，返回该节点的下一个位置
        iterator erase(iterator pos);
        void clear();
        void swap(list<T>& l);
    private:
        PNode _pHead;
    };
};

整个list可以被分为三个部分，List结点类（用于构造List类的结点），List的迭代器类（用于构造和操作List类的迭代器）以及List类（维护list链表，支持对链表的一系列操作）。
接下来我们将它们一一实现：

🔥List结点类

此结点类是一个模板类，模板参数T表示结点的数据类型。主要是实现其构造函数，便于后面List类中结点的创建。

// List的节点类
template<class T>
struct ListNode
{
    ListNode(const T& val = T())
        :_pPre(nullptr)
        , _pNext(nullptr)
        , _val(val)
    {}
    ListNode<T>* _pPre;
    ListNode<T>* _pNext;
    T _val;
};

构造函数部分初始化变量使用了初始化列表，并在参数列表中提供了了缺省值，同时实现了无参和传参的结点构造。

🔥List迭代器类

此迭代器类同样是一个模板类，包含三个模板参数，T（表示迭代器指向元素的数据类型），Ref（类型为T&或const T&，表示operator*()操作符重载的返回值类型），Ptr（类型为T*或const T*，表示operator->()操作符重载的返回值类型）。

typedef类型说明：PNode（表示一个结点的指针，简化书写），Self（表示此迭代器类型ListIterator的别名，简化书写）

下面来看看迭代器具体的代码实现，同时理解一下这些模板参数的用途。

//List的迭代器类
template<class T, class Ref, class Ptr>
class ListIterator
{
    typedef ListNode<T>* PNode;
    typedef ListIterator<T, Ref, Ptr> Self;
public:
	// 默认成员函数，初始化结点指针的指向
    ListIterator(PNode pNode = nullptr)
        :_pNode(pNode)
    {}
    ListIterator(const Self& l)
        :_pNode(l._pNode)
    {}
    // 解引用访问T类型的对象
    Ref operator*()
    {
        return _pNode->_val;
    }
    // 箭头实现访问T类型对象中的成员
    // 此处为C++特定语法，下面会展开讲
    Ptr operator->()
    {
        return &(_pNode->_val);
    }
    // 让迭代器指向下一结点
    Self& operator++()
    {
    	// 虽然外部重载的是++
    	// 但内部已经是链表的移动方式
        _pNode = _pNode->_pNext;
        return *this;
    }
    Self operator++(int)
    {
        Self tmp(*this);
        _pNode = _pNode->_pNext;
        return tmp;
    }
    // 让迭代器指向上一结点
    Self& operator--()
    {
        _pNode = _pNode->_pPre;
        return *this;
    }
    Self& operator--(int)
    {
        Self tmp(*this);
        _pNode = _pNode->_pPre;
        return tmp;
    }
    // 判断迭代器是否相等
    bool operator!=(const Self& l)
    {
        return _pNode != l._pNode;
    }
    bool operator==(const Self& l)
    {
        return _pNode == l._pNode;
    }
    
    // 唯一的成员变量，一个结点的指针
    PNode _pNode;
};

我们可以单独将operator->()重载拿出来看：

Ptr operator->()
{
    return &(_pNode->_val);
}

此接口函数返回值的类型为结点元素的地址，当你使用这样的重载访问元素成员的时候，本质上是这样的（it.operator->()->_a1）或这样的（it->->_a1）。很明显，这样的写法看起来太不美观，用起来也太不舒适了。所以，C++增加了语法规定，使编译器不支持it->->_a1这种写法，而单独支持it->_a1这种。提高了C++使用的方便性和代码的可读性。

🔥List类

进入到咱们的重头戏，List类，它也是一个模板类，包含一个模板参数T（表示List类的数据类型）。其中也是只有一个成员变量，指向链表头节点的指针_pHead。List类的链表为带头双向循环链表，可以很轻易的通过头节点访问到链表头和链表尾。

typedef类型说明：Node（链表的结点类型ListNode的别名），PNode（指向Node类型元素的指针），iterator（迭代器类型ListIterator的别名），const_iterator（迭代器类型ListIterator的别名）。

接下来我们逐一实现其成员函数：

默认成员函数

主要还是那几样，构造函数，拷贝构造，赋值运算符重载以及析构函数。

// List的构造函数
list()
{
	// 创建头节点
    _pHead = new Node;
    _pHead->_pNext = _pHead;
    _pHead->_pPre = _pHead;
}
list(int n, const T& value = T())
{
    _pHead = new Node;
    _pHead->_pNext = _pHead;
    _pHead->_pPre = _pHead;
    for (int i = 0; i < n; i++) {
    	// push_back，链表尾插，后面会实现
        push_back(value);
    }
}
// 迭代器区间构造
template <class Iterator>
list(Iterator first, Iterator last)
{
    _pHead = new Node;
    _pHead->_pNext = _pHead;
    _pHead->_pPre = _pHead;
    // 往链表中依次插入迭代器区间中的结点
    while (first != last) {
        push_back(*first);
        ++first;
    }
}
// 拷贝构造
list(const list<T>& l)
{
    _pHead = new Node;
    _pHead->_pNext = _pHead;
    _pHead->_pPre = _pHead;
    PNode pcur =  l._pHead->_pNext;
    while (pcur != l._pHead) {
        push_back(pcur->_val);
        pcur = pcur->_pNext;
    }
}
// 赋值运算符重载
list<T>& operator=(list<T> l)
{
	// swap交换链表函数，后面会实现
    swap(l);
    return *this;
}
// 析构函数，释放空间
~list()
{
	// clear，清空list对象结点，后面会实现
    clear();
    delete _pHead;
    _pHead = nullptr;
}

有链表和顺序表基础的话，还是没什么难度的。

Iterators迭代器获取

由于迭代器不再是原生指针，而是一个ListIterator迭代器类，所以并不能直接返回元素的指针，而是构造出来的迭代器对象。
如下：

// List Iterator
iterator begin()
{
    return iterator(_pHead->_pNext);
}
iterator end()
{
    return iterator(_pHead);
}
const_iterator cbegin()
{
    return const_iterator(_pHead->_pNext);
}
const_iterator cend()
{
    return const_iterator(_pHead);
}

其中，迭代器类型使用匿名对象简化书写。当我们重载了这样几个迭代器接口之后，就可以像STL库里那样顺利的获取和使用迭代器了。

容量接口

获取当前List对象所包含的元素个数（size）或者是否为空（empty）。

// List Capacity
size_t size()const
{
    size_t digit = 0;
    PNode pcur = _pHead->_pNext;
    while (pcur != _pHead) {
        ++digit;
        pcur = pcur->_pNext;
    }
    return digit;
}
bool empty()const
{
    if (_pHead == _pHead->_pNext)return true;
    else return false;
}

这里的size()接口函数我实现的相对草率，通过遍历List对象计算元素的个数，时间复杂度O(N)。当然，如果你有想法，完全可以实现一个复杂度为O(1)的size()接口。

List Access元素获取

List对象中的元素获取不存在下标访问这一说，只提供了获取头元素和尾元素的接口函数。

// List Access
T& front()
{
    assert(!empty());
    return _pHead->_pNext->_val;
}
const T& front()const
{
    assert(!empty());
    return _pHead->_pNext->_val;
}
T& back()
{
    assert(!empty());
    return _pHead->_pPre->_val;
}
const T& back()const
{
    assert(!empty());
    return _pHead->_pPre->_val;
}

同时重载了const类型和非const类型的两种接口。

List对象修饰接口

主要包含，List对象插入删除，头插头删，尾插尾删，链表元素的清空。在list对象的修饰中，统统使用迭代器来确定修饰位置及元素，大家需要慢慢习惯迭代器修饰方式。
我们可以先来实现结点的插入和删除：

// 在pos指向元素位置前插入值为val的节点
iterator insert(iterator pos, const T& val)
{
	// 创建并初始化新结点
    PNode newnode = new Node(val);
    // 以下插入方式大家应该不陌生
    newnode->_pNext = pos._pNode;
    newnode->_pPre = pos._pNode->_pPre;
    pos._pNode->_pPre->_pNext = newnode;
    pos._pNode->_pPre = newnode;
    // 返回指向插入元素的迭代器
    return iterator(newnode);
}
// 删除pos位置的节点，返回该节点的下一个位置
iterator erase(iterator pos)
{
	// 保存被删除结点下一位置，作为返回值
    iterator tmp(pos._pNode->_pNext);
    pos._pNode->_pPre->_pNext = pos._pNode->_pNext;
    pos._pNode->_pNext->_pPre = pos._pNode->_pPre;
    delete pos._pNode;
    pos._pNode = nullptr;
    return tmp;
}

头插头删，尾插尾删其实就是对以上两个接口函数的复用，如下：

// 头插
void push_front(const T& val) { insert(begin(), val); }
// 头删
void pop_front() { erase(begin()); }
// 尾插
void push_back(const T& val) { insert(end(), val); }
// 尾删
void pop_back() { erase(--end()); }

List对象结点的清除，创建一个迭代器依次删除元素，同时判断是否删除到尾就可以了：

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

swap

交换两个List对象只需要交换它们的头节点指针变量_pHead。

void swap(list<T>& l)
{
    std::swap(_pHead, l._pHead);
}

结语

本篇博客主要讲了list的模拟实现，可以简单将其分成三部分，List结点类，List迭代器类以及List类，最终将它们集合在一起组成了我们模拟实现的list。实现的功能还是元素插入元素删除，构造和析构那几套，但list相对于vector和string已经完全抛弃了下标访问，只支持迭代器区间了，我们需要渐渐习惯迭代器的使用。
博主后续还会分享更多有趣的内容，感谢大家的支持。♥