STL容器-- list的模拟实现（附源码）

List的实现主要考察我们对list这一容器的理解，和代码的编写能力，通过上节对list容器的使用，我们对list容器已经有了一些基本的了解·，接下来就让我们来实现一些list容器常见的功能函数来加深我们对c++工程的理解：

在这里插入图片描述

一、基本框架的搭建

首先我们需要将基本的框架搭建好， 从之前我们学数据结构时，对list的一些认识并结合c++ stl标准可以得出：

定义节点的构造
明确指针的指向
list的封装
根据c++中的标准我们可以得知，list时一个双向迭代器，所以对应的，我们需要定义的双向循环链表：

1.1节点的构造

template <class T>
struct ListNode
{
    T _data;
    ListNode<T>* _next;
    ListNode<T>* _prev;
    // 节点的构造函数
    ListNode(const T& val)
    :_data(val)
    ,_next(nullptr)
    ,_prev(nullptr)
    {}
};

在定义一个节点的时候，我们先让这个节点的_next and _prev指针为空

1.2 list的封装

    
template <class T>
struct ListNode
{
    T _data;
    ListNode<T>* _next;
    ListNode<T>* _prev;
    // 节点的构造函数
    ListNode(const T& val = T())
    :_data(val)
    ,_next(nullptr)
    ,_prev(nullptr)
    {}
};

template<class T>
class list
{
public:
    typedef ListNode<T> node;
    void empty_init()
    {
        // zdl :: 在初始化一个空链表时， 先定义一个哨兵位
        _head = new node();
        _head->_next = _head;
        _head->_prev = _head;
    }
    list()
    {
    	empty_init();
    }
    // functon define:
    }

private:
        node* _head;
};

同时为了防止访问冲突，我们可以将我们自己实现的类，放在我们自己定义的命名域中：

namespace zdl
{
	template <class T>
	struct ListNode
	{
	    T _data;
	    ListNode<T>* _next;
	    ListNode<T>* _prev;
	    // 节点的构造函数
	    ListNode(const T& val)
	    :_data(val)
	    ,_next(nullptr)
	    ,_prev(nullptr)
	    {}
	};
	    
	template <class T>
	struct ListNode
	{
	    T _data;
	    ListNode<T>* _next;
	    ListNode<T>* _prev;
	    // 节点的构造函数
	    ListNode(const T& val = T())
	    :_data(val)
	    ,_next(nullptr)
	    ,_prev(nullptr)
	    {}
	};
	
	template<class T>
	class list
	{
	public:
	    typedef ListNode<T> node;
	    void empty_init()
	    {
	        // zdl :: 在初始化一个空链表时， 先定义一个哨兵位
	        _head = new node();
	        _head->_next = _head;
	        _head->_prev = _head;
	    }
	    list()
	    {
	    	empty_init();
	    }
	    // functon define:
	    }
	
	private:
	        node* _head;
	};
}

这样list的基本框架就搭建好了！！

二、节点的尾插和头插

2.1 节点的头插 (push_back)

在这里插入图片描述

通过前面数据结构的学习。我们已经清楚了链表的结构，在进行数据尾插时, 就只是在改变指针的指向罢了：

void push_back(const T& val)
    {
        node* creat = new node(val);
        node* tail = _head->_prev;
        tail->_next = creat;
        creat->_prev = tail;
        creat->_next = _head;
        _head->_prev = creat; 
    }

2.2 节点的头插(push_front)

节点的头插和尾插十分的相似，
这里我们就直接展示一下代码：

void push_front(const T& val)
    {
        node* fnode = new node(val);
        fnode->_next = _head->_next;
        fnode->_prev = _head;
        _head->_next->_prev = fnode;
        _head->_next = fnode;
    }

2.3 数据插入验证

为了方便起见，我这里再再这个类里面定义一个打印链表的函数：

 void Print_list()
        {
            node* cur = _head->_next;
            while (cur != _head)
            {
                cout << cur->_data << " ";
                cur = cur->_next;
            }
            cout << endl;
        }

完成了list容器的头插和尾插操作接下来我们可以来验证一下，我们的函数实现是否有问题：

#include"list.h"

int main()
{
    zdl::list<int> l1;
    l1.push_back(1);
    l1.push_back(2);
    l1.push_front(3);
    l1.Print_list();
    return 0;
}

通过运行可知，这里的函数没有问题：

在这里插入图片描述

三、list迭代器的实现

list迭代器的功能和vetor的功能有很多相似的地方，但是二者在底层实现时，使用的不同的方法：
基于，list迭代器的特殊性质，我们会采用类封装的方式来满足list_iterator的特殊性质：

3.1迭代器基本功能的实现和封装处理

template<class T>
    struct list_iterator
    {
        typedef ListNode<T> node;
        typedef list_iterator<T> self;
        node* _nd;
        list_iterator(node* nd)
        :_nd(nd)
        {}
        // zdl:: 实现迭代器的基本功能：
        // 解引用数值
        T& operator*()
        {
            return _nd->_data;
        }
        // zdl:: 前置++ / --
        self& operator++()
        {
            _nd = _nd->_next;
            return *this;
        }
        self& operator--()
        {
            _nd = _nd->_prev;
            return *this;
        }
        // zdl:: 后置 ++ / --
        self operator++(int)
        {
            self tmp = _nd;
            _nd = _nd->_next;
            return tmp;
        }
        self operator--(int)
        {
            self tmp = _nd;
            _nd = _nd->_prev;
            return tmp;
        }
        // zdl:: != 运算
        bool operator!=(const self& s)
        {
            return _nd != s._nd;
        }
    };

实现了list_iterator的功能后，我们就只需要将他封装道list类中就可以正常使用了：
使用typedef 封装迭器
在这里插入图片描述
基本的逻辑都是十分的简单的接下来我们来简单的验证一代码是否可行：

3.2 对结构体(类）的解引用

对 ->运算符的重载

大家现在可以想象一下这样的场景，假设我现在在llist中存储的不是基础类型的元素，而是类等较为复杂的对象时,我们应当怎么正常的使用这个类对象的成员呢？
这时，我们就可以考虑对->运算符重载， 通过返回对象的地址，来访问成员变量和成员函数等！
下面我们就来举个例子：
假设我现在我要在list中存储pos类：

struct pos
{
	int row;
	int col;
	//构造函数
	pos(const int& x = 0, const int& y = 0)
	:row(x)
	,col(y)
	{}
	//成员函数
	void pos_show()
	{
		printf("(%d, %d) ",row, col);
	}
};

我们就只需要重载->运算符：

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

运行后可以得到：
在这里插入图片描述
但是大家可能会觉得很奇怪，通过->重载，返回的只是_data的地址，为什么能直接访问到元素呢？不应该使用it->->解引用两次才行啊？
这个其实就只是c++便准下为我们提供的特殊语法，通过这样的规定使我们能够直接访问到元素，当然c++也是支持这样的写法的：
在这里插入图片描述
但是不支持这样的写法：

3.3`const`迭代器的实现与模板参数的巧用

前面我们已经实现了，可读可写的迭代器，现在我们就来实现一下只读迭代器:
const iterator,
其实从功能上看，这个迭代器与原来的迭代器十分的相似，只是不能对指向对象的值进行修改，因此我们就只需要对* 和 ->运算符重载的时候稍加修改就可以得到我们想要的结果，即再创建一个类：
在这里插入图片描述
其他的共同功能粗需要改动，只需要改动下面两个重载函数：

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

紧接着我们还需要在llist类中实现const对象专用的begin()、end()
在这里插入图片描述

接下来我们来验证一下效果：
在这里插入图片描述
现在consr iterator也实现好了，但是这里依然还存在问题，这样我们将相当于为迭代器实现了两个类，这两个类的攻击能还高度重合，这并没有，体现出模板函数的简洁性，因此我们还可以通过其他的方式来优化我们现在的代码。
通过对源码的分析，参照我们或许可以从中得到一些启发，从源码中可知我们可以得知，通过对模板参数的巧用就可以的实现代码的简化：

在这里插入图片描述
接下来我们就只需要将代码稍加改动就可以实现我们的目的：

接下来，我们再次运行看看是否可以达到简化代码的效果：

可以发现现在的代码依然有效，代码简化成功！！

四、丰富构造函数、list增删查改的实现

现在我们已经完成了list的简单构造函数，现在我们就可以参照 c++ library完成其他的构造函数：

4.1 `list(size_t n, const T& x = T())`

我们要实现的这个函数和标准库中的一样，并且直接复用我峨嵋你已经实现的函数就好了：

list(size_t n, const T& x = T())
{
   for (int i = 0; i < n; i++)
   {
       push_back(x);
   }
}

直接来演示一下的效果：
在这里插入图片描述

4.2 拷贝构造

我们就只需要将被拷贝链表的元素一个一个的拷贝进链表就行了：

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

我们来测试一下效果：
在这里插入图片描述

4.3 插入函数的实现（insert)

想要在这个双向链表中插入节点，我们就需要

待插入的值
待插入位置

所以，insert函数定义为： void insert(iterator pos, const T& val = T())

iterator insert(iterator pos, const T& val = T())
{
     node* cur = pos._nd;
     node* prev = pos._nd->_prev;
     node* insrt = new node(val);
     prev->_next = insrt;
     insrt->_prev = prev;
     insrt->_next = cur;
     cur->_prev = insrt;
     return iterator(cur->_prev);
 }

这个函数也十分的简单如果，有的uu还没有接触过链表，或者是已经忘了链表的增删查改，可以移步去看看我之前的博客：链表的介绍

4.4链表的删除(earse)

关于erase和函数的定义，我们就只需要拿到需要删除的位置就可以了，所以定义为：void erase(iterator pos)

iterator erase(iterator pos)
{
     assert(pos != end()); //! 注意不能够将哨兵位删除！！
     node* cur = pos._nd;
     node* prev = cur->_prev;
     prev->_next = cur->_next;
     cur->_next->_prev = prev;
     delete cur;
     return iterator(prev->_next);
 }

现在我们就直接来测试一下这个函数是否可以满足我们的要求：
在这里插入图片描述
由此可知我们实现的都没有问题。

4.5链表元素的查找(find)

定义find函数时，我们就只需要给函数一个特定的需要查找到的值，然后使这个函数返回这个元素的位置（迭代器）

iterator find(const T& val)
{
     auto it = begin();
     while (it != end() && *it != val)
     {
         it++;
     }
     if (*it == val) return it;
     return nullptr;
 }

在这里插入图片描述

4.6 头删和尾删操作

前面我们已经实现了earse 现在我们就只需要对这个和拿书尽心你给复用就好了：

void pop_front()
{
    erase(++end());
}
void pop_back()
{
    erase(--end());
}

接下来我们就直接来演示这个函数是否有用：

在这里插入图片描述

五、析构函数与clear函数

最后我们就来实现一下list的析构函数，我们还是继续函数的复用：

// zdl:: 析构类函数的实现：
        ~list()
        {
            // ! 不仅要将所有的数值删除还需要将哨兵位也清除！
            clear();
            delete _head;
            _head = nullptr;            
        }
        void clear()
        {
            // !! 不能删除哨兵位，就只是将所有的数值清空。
            auto it = begin();
            while (it != end()) it = erase(it);
        }

现在我们就将已有的链表清空试试：
在这里插入图片描述

六、代码展示

list.h

#pragma once 

#include<iostream>
#include<cassert>
using  namespace std;
namespace zdl
{
    
    template <class T>
    struct ListNode
    {
        T _data;
        ListNode<T>* _next;
        ListNode<T>* _prev;
        // 节点的构造函数
        ListNode(const T& val = T())
        :_data(val)
        ,_next(nullptr)
        ,_prev(nullptr)
        {}
    };
    template<class T, class Ref, class Ptr>
    struct list_iterator
    {
        typedef ListNode<T> node;
        typedef list_iterator<T, Ref, Ptr> self;
        node* _nd;
        list_iterator(node* nd)
        :_nd(nd)
        {}
        // zdl:: 实现迭代器的基本功能：
        // 解引用数值
        Ref operator*()
        {
            return _nd->_data;
        }
        Ptr operator->()
        {
            return &_nd->_data;
        }
        // zdl:: 前置++ / --
        self& operator++()
        {
            _nd = _nd->_next;
            return *this;
        }
        self& operator--()
        {
            _nd = _nd->_prev;
            return *this;
        }
        self& operator+(size_t n)
        {
            while (n--)
            {
                _nd = _nd->_next;
            }
            return *this;
        }
        self& operator-(size_t n)
        {
            while (n--)
            {
                _nd = _nd->_prev;
            }
            return *this;
        }
        // zdl:: 后置 ++ / --
        self operator++(int)
        {
            self tmp = _nd;
            _nd = _nd->_next;
            return tmp;
        }
        self operator--(int)
        {
            self tmp = _nd;
            _nd = _nd->_prev;
            return tmp;
        }
        // zdl:: != 运算
        bool operator!=(const self& s)
        {
            return _nd != s._nd;
        }
    
    };
    
    template<class T>
    class list
    {
    public:
        typedef ListNode<T> node;
        typedef list_iterator<T, T&, T*> iterator;
        typedef list_iterator<T, const T&, const T*> const_iterator;
        void empty_init()
        {
            // zdl :: 在初始化一个空链表时， 先定义一个哨兵位
            _head = new node();
            _head->_next = _head;
            _head->_prev = _head;
        }
        list()
        {
            empty_init();
        }
        list(const list<T>& l1)
        {
            empty_init();
            for (auto& e : l1) push_back(e);
        }
        list(size_t n, const T& x = T())
        {
            empty_init();
            for (size_t i = 0; i < n; i++)
            {
                push_back(x);
            }
        }
        void push_back(const T& val)
        {
            node* creat = new node(val);
            node* tail = _head->_prev;
            tail->_next = creat;
            creat->_prev = tail;
            creat->_next = _head;
            _head->_prev = creat; 
        }
        void push_front(const T& val)
        {
            node* fnode = new node(val);
            fnode->_next = _head->_next;
            fnode->_prev = _head;
            _head->_next->_prev = fnode;
            _head->_next = fnode;
        }
        void Print_list()
        {
            node* cur = _head->_next;
            while (cur != _head)
            {
                cout << cur->_data << " ";
                cur = cur->_next;
            }
            cout << endl;
        }
        // zdl:: 增删查改的实现
        iterator insert(iterator pos, const T& val = T())
        {
            node* cur = pos._nd;
            node* prev = pos._nd->_prev;
            node* insrt = new node(val);
            prev->_next = insrt;
            insrt->_prev = prev;
            insrt->_next = cur;
            cur->_prev = insrt;
            return iterator(cur->_prev);
        }
        iterator erase(iterator pos)
        {
            assert(pos != end()); //! 注意不能够将哨兵位删除！！
            node* cur = pos._nd;
            node* prev = cur->_prev;
            prev->_next = cur->_next;
            cur->_next->_prev = prev;
            delete cur;
            return iterator(prev->_next);
        }
        iterator find(const T& val)
        {
            auto it = begin();
            while (it != end() && *it != val)
            {
                it++;
            }
            if (*it == val) return it;
            return nullptr;
        }
        void pop_front()
        {
            erase(begin());
        }
        void pop_back()
        {
            erase(--end());
        }
        // zdl:: 析构类函数的实现：
        ~list()
        {
            // ! 不仅要将所有的数值删除还需要将哨兵位也清除！
            clear();
            delete _head;
            _head = nullptr;            
        }
        void clear()
        {
            // !! 不能删除哨兵位，就只是将所有的数值清空。
            auto it = begin();
            while (it != end()) it = erase(it);
        }
// zdl:: 使用类来模拟迭代器的行为
    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);
    }
    private:
            node* _head;
    };
}

test.cpp


#include"list.h"
#include<list>
struct pos
{
	int row;
	int col;
	//构造函数
	pos(const int& x = 0, const int& y = 0)
	:row(x)
	,col(y)
	{}
	//成员函数
	void pos_show()
	{
		printf("(%d, %d) ",row, col);
	}
};
int main()
{
    // zdl::list<pos> l1;
    // pos p[] = {{1, 2}, {3, 4}, {5, 6}};
    // for (int i = 0; i < 3; i++) l1.push_back(p[i]);
    // auto it = l1.begin();
    // while (it != l1.end())
    // {
    //     it->pos_show();
    //     it++;
    //     cout << endl;
    // }
    // cout << endl;

    // zdl::list<int> l2(5, 4);
    // for (auto&i : l2) cout << i << " ";
    // cout << endl;

    // zdl::list<int> l4(3, 3);
    // l4.Print_list();
    // l4.insert(l4.begin() + 2, 2);
    // l4.Print_list();
    // l4.erase(l4.begin() + 2);
    // l4.Print_list();

    // zdl::list<int>l5;
    // for (int i = 1; i <= 10; i++) l5.push_back(i);
    // cout << "原数组：" << endl;
    // l5.Print_list();
    // // zdl:: 现在我们要借助 find + erase函数来删除元素：5
    // l5.erase(l5.find(5));
    // cout << "删除后：" << endl;
    // l5.Print_list();
    //  zdl:: 进行头删和尾删
    // cout << "进行尾删和头删后:" << endl;
    // l5.pop_back();
    // l5.pop_front();
    // l5.Print_list();
    // cout << "现在将所有的元素都删除！" << endl;
    // l5.clear();
    // l5.Print_list();
    zdl::list<int> l1(10, 10);
    cout <<"l1:" << endl;
    l1.Print_list();
    zdl::list<int> l2(l1);
    cout << "l2:" << endl;
    l2.Print_list();
    return 0;
}