List 模拟实现

前言

本文将会向你介绍如何模拟实现list、iterator迭代器

模拟实现

引入

迭代器是一种用于访问容器中元素的对象，它封装了对容器中元素的访问方式。迭代器提供了一组操作接口，可以让我们通过迭代器对象来遍历容器中的元素。（iterator迭代器内部成员变量和成员函数都是与节点有关的）

先举一个例子，以下是迭代器++成员函数的实现
Self看不懂没关系，我们现在只要知道它是迭代器类名typedef过来的就好了，_pNode是一个指向ListNode结构体的指针。在ListIterator类中，_pNode用于指向链表中的某个节点，通过该指针可以访问节点的成员变量和成员函数。本质上还是对节点做操作，那我们为什么要大费周章还要套一个迭代器类呢？为什么不能大大方方的直接使用节点指针呢？
原因是：虽然写的人麻烦了，但却能方便使用者，使用者直接对迭代器对象++就能完成遍历

我们接下来就要做这个事情了。

        Self& operator++()
        {
            _pNode = _pNode->_pNext;    //让节点指针指向下一个节点    
            //返回迭代器对象
            return *this;
        }
1
2
3
4
5
6

迭代器对象和指向节点的指针之间有以下关系： 迭代器对象封装了指向节点的指针，提供了一组操作接口，使得我们可以通过迭代器对象来访问节点中的元素。 迭代器对象可以通过指针的方式来访问节点中的元素，可以使用指针运算符来获取元素的值，或者使用指针递增/递减来移动到下一个/上一个节点。 迭代器对象可以隐藏底层容器的具体实现细节，使得我们可以通过统一的接口来访问不同类型的容器，提高了代码的可复用性和灵活性。

整体结构

首先先让你熟悉一下整个结构

	//节点类
    template<class T>
    struct ListNode
    {
    
    }
    //迭代器类
    template<class T, class Ref, class Ptr>
    class ListIterator
    {
		  //...
		  //利用结构体指针对节点结构体进行管理
	      PNode _pNode;   //成员变量：结构体指针
     };
	//list类
    template<class T>
    class list
    {
		
		private:		
        PNode _pHead;	//哨兵位头节点（结构体指针）
        size_t _size;	//节点个数
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

节点类

定义了一个节点结构体，在链表类中，我们需要能够直接访问节点的指针 _pPre 和 _pNext，以及节点的值 _val。如果将节点类定义为class，则需要在节点类中将这些成员变量和成员函数声明为public，或者在链表类中添加友元关系，以便链表类可以访问和操作节点的私有成员。

  template<class T>
  struct ListNode
  {
      //构造函数
      ListNode(const T& val = T())
          : _val(val) //节点的值
          , _pPre(nullptr)
          , _pNext(nullptr)
          {}
      ListNode<T>* _pPre; //节点的前驱
      ListNode<T>* _pNext; //节点的后继
      T _val;
  };
1
2
3
4
5
6
7
8
9
10
11
12
13

迭代器类

定义一个ListIterator类，在这个迭代器类中使用节点的指针，底层还是使用节点指针，迭代器类可以看作对节点类的封装，它提供了对节点的操作和访问的接口，使得用户可以通过迭代器来遍历和操作链表中的节点。 这里有一个点需要注意一下 这里的Ref指的是reference（引用）， Ptr指的是pointer（指针），当然这里用T&、T*替换Ref和Ptr也是可以的 我们可以看到实例化部分，T&就传给了Ref，T * 就传给了Ptr

那么我们为什么要多传递两个模板参数呢？原因这两个模板参数可以助我们区分const迭代器类和普通迭代器类


值得一提的是重载->
当我们定义一个AA类型的对象的时候，并传入二元的数据，但是<<是不支持的(cout << *it << endl;) 我们可以想到用 cout << (*it)._a1 << " " << (*it)._a2 << endl, 这当然可以
但是迭代器模拟的是指针的行为，用->似乎更恰当一些，于是我们就重载了->运算符
operator->() 返回了 &_pNode->_val，这是什么意思呢？
&_pNode->_val这是一个指向AA类型数据的指针（AA *），对象指针再加上一个->就可以访问成员变量啦
cout << it.operator->() ->_a1 << " " << it.operator->()->_a2 << endl;

    struct AA
    {
        AA(int a1 = 0, int a2 = 0)
            :_a1(a1)
            ,_a2(a2)
        {}
        int _a1;
        int _a2;
    };
    void test_list4()
    {
        Fan::list<AA> lt;
        lt.push_back(AA(1, 1));
        lt.push_back(AA(2, 2));
        lt.push_back(AA(3, 3));
        Fan::list<AA>::iterator it = lt.begin();
        while (it != lt.end())
        {
            //AA对象不支持流插入
          	//error:cout << *it << endl;
            //cout << (*it)._a1 << " " << (*it)._a2 << endl;
            cout << it->_a1 << " " << it->_a2 << endl;
            //cout << it.operator->() ->_a1 << " " << it.operator->()->_a2 << endl;
            it++;
        }
        cout << endl;
    }
    ```

 ```c
 template<class T, class Ref, class Ptr>
    class ListIterator
    {
        //typedef结点类
        typedef ListNode<T>* PNode;
        //typedef迭代器类
        typedef ListIterator<T, Ref, Ptr> Self;
    public:
        //构造函数
        ListIterator(PNode pNode = nullptr)
            :_pNode(pNode) //初始化指向节点的指针
        {}
        //拷贝构造函数
        //l2(l1)
        ListIterator(const Self& l)
        {
            _pNode = l._pNode;  
        }
        //重载*
        //从泛型的角度来说我们并不知道operator*()的返回值是什么
        Ref operator*()
        {
            return _pNode->_val;   //节点指针指向的值
        }
        //重载->（为自定义类型的数据准备）
        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;   //成员变量：节点指针
    };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

list类

实例化类模板

用typedef重命名，隐藏底层的细节，提供统一的访问修改方式

 //list类
    template<class T>
    class list
    {
    	//实例化节点类模板
        typedef ListNode<T> Node;   
        typedef Node* PNode;        //重命名Node*指针类型
    public:
    	//实例化类模板
        typedef ListIterator<T, T&, T*> iterator;   
        //实例化const版本
        typedef ListIterator<T, const T&, const T&> const_iterator;
1
2
3
4
5
6
7
8
9
10
11
12

默认成员函数

// List的构造
        list()
        {
        	//初始化头节点
            CreateHead();
        }
        //n个value的构造
        list(int n, const T& value = T())
        {
            CreateHead();  
            while (n--)
            {
                push_back(value);   //尾插
            }
        }
        template <class Iterator>
        //一段迭代器空间的构造
        list(Iterator first, Iterator last)
        {
            CreateHead(); 
            while (first != last)
            {
                push_back(*first);  //尾插    
                first++;
            }
        }
        //拷贝构造
        //lt2(lt1)
        list(const list<T>& l)
        {
            CreateHead();   
            for (auto e : l)
            {
                push_back(e);
            }
        }
        //赋值重载
        //lt2 = lt1
        list<T>& operator=(list<T> l)
        {
            clear();    //清除数据(不包括头节点)
            for (auto e : l)
            {
                push_back(e);
            }
            return *this;
        }
        //析构函数
        ~list()
        {
            clear();
            //释放头节点
            delete _pHead;
            _pHead = nullptr;
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

获取指向头尾节点的指针

 // List Iterator
        //返回第一个节点的指针（不是头节点）
        iterator begin()
        {
            //return iterator(_pHead->_pNext);
            return _pHead->_pNext;
        }
        //返回最后一个节点的下一个位置的节点指针
        iterator end()
        {
            //return iterator(_pHead)
            return _pHead;
        }
        //const：返回第一个节点的指针（不是头节点）
        const_iterator begin()  const
        {
            return const_iterator(_pHead->_pNext);
            //return _pHead->_pNext;  
        }
        //const：//返回最后一个节点的下一个位置的节点指针
        const_iterator end()  const
        {
            return const_iterator(_pHead);
                //return _pHead;
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

容量

        // List Capacity
        size_t size()
        {
            return _size;
        }
        bool empty()const
        {
            return _size == 0;
        }
1
2
3
4
5
6
7
8
9

获取头尾结点的值

        //返回第一个节点的值（不是头节点）
        T& front()
        {
            return _pHead->_pNext->_val;
        }
        //const版本：返回第一个节点的值（不是头节点）
        const T& front()const
        {
            return _pHead->_pNext->_val;
        }
        //返回最后一个节点的值（注意与end()区别）
        T& back()
        {
            return _pHead->_pPre->_val;
        }
        //const版本：返回最后一个节点的值
        const T& back()const
        {
            return _pHead->_pPre->_val;
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

修改

  // 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)
        {
            ++_size;
            //结构体指针
            PNode cur = pos._pNode;
            PNode prev = cur->_pPre;

            PNode newnode = new Node(val);
            prev->_pNext = newnode;
            cur->_pPre = newnode;
            newnode->_pPre = prev;
            newnode->_pNext = cur;
            //返回新节点位置处的迭代器
            return iterator(newnode);
        }
        // 删除pos位置的节点，返回该节点的下一个位置
        iterator erase(iterator pos)
        {
            --_size;
            PNode cur = pos._pNode;
            PNode prev = cur->_pPre;
            PNode next = cur->_pNext;

            prev->_pNext = next;
            next->_pPre = prev;
            delete cur;
            return iterator(next);
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

测试

void test_list1()
{
   Fan::list<int> lt;
   lt.push_back(1);
   lt.push_back(2);
   lt.push_back(3);
   lt.push_back(4);
   lt.push_back(5);
   lt.push_back(6);
   Fan::list<int>::iterator it = lt.begin();
   while (it != lt.end())
   {
       cout << *it << " ";
       ++it;
   }
   cout << endl;
   for (auto e : lt)
   {
       cout << e << " ";
   }
   cout << endl;
}
void test_list2()
{
   Fan::list<int> lt1;
   lt1.push_back(1);
   lt1.push_back(2);
   lt1.push_back(3);
   lt1.push_back(4);
   lt1.push_back(5);
   Fan::list<int>::iterator it1 = lt1.begin();
   while (it1 != lt1.end())
   {
       cout << *it1 << " ";
       ++it1;
   }
   cout << endl;
   Fan::list<int> lt2(lt1.begin(), lt1.end());
   Fan::list<int>::iterator it2 = lt2.begin();
   while (it2 != lt2.end())
   {
       cout << *it2 << " ";
       ++it2;
   }
   cout << endl;
   Fan::list<int> lt3(lt2);
   Fan::list<int>::iterator it3 = lt3.begin();
   while (it3 != lt3.end())
   {
       cout << *it3 << " ";
       ++it3;
   }
}
//打印const对象
   void print_list(const Fan::list<int>& lt)
   {
       Fan::list<int>::const_iterator it = lt.begin();
       while (it != lt.end())
       {
           cout << *it << " ";
           ++it;
       }
       cout << endl;
       for (auto e : lt)
       {
           cout << e << " ";
       }
   }
   void test_list3()
   {
       Fan::list<int> lt;
       lt.push_back(1);
       lt.push_back(2);
       lt.push_back(3);
       lt.push_back(4);
       lt.push_back(5);
       lt.push_back(6);
       print_list(lt);
   }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

小结

本篇文章对于初步接触模板的朋友们是有一定难度的，看完这篇文章，希望你能有所收获，在对模板的理解上更进一步，如果本文存在疏漏或错误的地方，还请您能够指出！