list的模拟实现

一、节点类

1、代码

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

2、实现原理

• 因为这里模拟实现的是带头双向链表，所以定义两个类类型的指针_pPre和_pNext，用来指向节点的前一个和后一个节点，用_val存储数据。
• 为了方便开辟空间和初始化节点，需要实现一个无参的构造函数，而构造出来的节点的前后节点我们是不知道的，所以都置为空即可。
• 因为节点类的成员变量与成员函数在节点类外需要用到，所以定义类时使用struct而不用class，因为struct的默认限定符是public。

3、注意

• 构造函数的形参val的缺省值需用T()，如果传入的val需要的是自定义类型时，编译器会直接调用它的构造函数去构造变量。

二、迭代器类

1、基本框架

（1）代码

template<class T, class Ref, class Ptr>
class ListIterator
{
    typedef ListNode<T>* PNode;
    typedef ListIterator<T, Ref, Ptr> Self;
public:
	PNode _pNode;
1
2
3
4
5
6
7

（2）实现原理

• 因为迭代器类中的其他函数要使用到引用和指针，所以模板参数需要有三个，第一个为类型，第二个为类型的引用，第三个为类型的指针。
• 因为在迭代器类外可能需要使用到本节点的指针变量，所以_pNode需用public限定符限定。
• 因为迭代器类中的内容都是要对外开放的，所以定义类时可以使用struct而不是class，因为class默认的限定符是private，而struct的默认限定符是public。

2、*运算符重载

（1）代码

Ref operator*()
{
    return _pNode->_val;
}
1
2
3
4

（2）作用

• 当我们用迭代器时，需要对迭代器进行解引用进而获得它所指向的数据，例如*it（it为迭代器变量）就可以获得它所指向的数据。

（3）注意

• 返回值需为_pNode->_val而不能是_pNode，因为_pNode只是一个指针而不是数据，链表的数据存储在节点的成员变量_val中。

3、->运算符重载

（1）代码

Ptr operator->()
{
    return &_pNode->_val;
}
1
2
3
4

（2）作用

• 当链表的元素是一个自定义类型，并且它的内部有成员变量而我们想访问它时，就需要使用到->，如果迭代器中没有重载->运算符，访问时只能是先对迭代器进行解引用再访问成员变量，即(*it)->成员变量名，这样操作会显得比较麻烦。
• 当重载了->运算符时，就可以直接访问成员变量，即it->成员变量名。

（3）注意

• 返回的是_val，而不是指针_pNode。
• 虽然写代码时是写成it->成员变量名，但编译器实际调用时是省略了一个->，即实际代码是it.operator->()->成员变量名。

4、自增与自减运算符重载

（1）代码

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

（2）实现原理

• 自增运算符分为前置自增和后置自增，前置自增返回自增完的变量，而后置自增需要返回自增前的变量值，再将变量自增。
• 所以前置自增只需将节点移动到下一个节点处，在返回本对象即可。
• 后置自增需要先构造一个对象，保存自增前的节点，再将本对象的_pNode移动到下一个节点处，最后返回保存自增前的节点的对象。
• 后置自增需要加一个占位符作为形参，作为前置自增和后置自增的区分。
• 自减和自增类似，这里不再过多说明。

（3）注意

• 自增和自减的返回类型为Self，即ListIterator，即需要返回本类的对象。
• 后置自增与自减的返回类型不能加引用，要使用值传递的方式。因为tmp是在该函数的内部创建的，出了作用域将会调用析构函数进行析构。

5、判断运算符重载

（1）代码

bool operator!=(const Self& l)
{
    return _pNode != l._pNode;
}
bool operator==(const Self& l)
{
    return _pNode == l._pNode;
}
1
2
3
4
5
6
7
8

（2）实现原理

• 判断两个迭代器对象是否相等，本质上就是判断它们指向的_pNode是否是同一个。
• 因为只是进行判断不做修改，所以形参采用引用和用const修饰，减少拷贝，使代码的效率更高。

三、list类

1、基本框架

（1）代码

template<class T>
class list
{
    typedef ListNode<T> Node;
    typedef Node* PNode;
    typedef ListIterator<T, T&, T*> iterator;
    typedef ListIterator<T, const T&, const T*> const_iterator;
private:
    void CreateHead()
    {
        _pHead = new Node;
        _pHead->_pPre = _pHead;
        _pHead->_pNext = _pHead;
    }
    PNode _pHead;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

（2）实现原理

• 使用typedef 将一些类型进行重定义，方便下方的代码书写。
• 迭代器的对象可能被const修饰，这时，它将无法调用没被const修饰的迭代器的函数，解决这个问题的方法可以是重载一个迭代器类，但重载的迭代器类和原先的迭代器模板类的函数只有返回类型不同，其他的都一样，这样就会显得代码很冗余。所以，使用模板的三个参数就可以解决这个问题，只不过传的实参不同而已。
• 由于此处实现的链表是一个带头的循环链表，所以需要一个头节点，则定义_pHead作为头节点并用private限定符限定起来，因为在list类的外部无需使用到它。
• 实现一个CreateHead函数，使它具有创建头节点的功能，这样在其他函数中要创建头节点时只需要调用这个函数即可。其次，这个函数可以用private限定符限定起来，因为在list类的外部无需使用到它。

（3）注意

• 为了具有被const修饰的迭代器的类，需要用模板参数的方法或者重载一个迭代器类。而不能在list类内部使用const iterator实现，因为此处的const是修饰迭代器本身，即迭代器本身不能修改，而它指向的内容可以修改，即迭代器的自增与自减等等操作将无法使用。

2、insert函数

（1）代码

iterator insert(iterator pos, const T& val)
{
    /*PNode newNode = new Node;
    newNode->_val = val;*/

    PNode newNode = new Node(val);

    PNode posNode = pos._pNode;
    PNode prev = posNode->_pPre;
    newNode->_pNext = posNode;
    newNode->_pPre = prev;
    posNode->_pPre = newNode;
    prev->_pNext = newNode;

    return iterator(newNode);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

（2）实现原理

• 因为insert函数的作用是在pos位置前插入值为val的节点，所以，首先应该创建一个节点。因为ListNode类中有构造函数，所以，直接用val构造一个节点即可。当然，可以自己创建节点并赋值为val，即代码中被注释的部分。
• 因为是插入节点，即需要在pos和pos的前一个节点之间插入一个节点。所以，对pos和pos的前一个节点的_pPre 和_pNext 进行修改即可，最后再返回新插入的节点的迭代器即可。

（3）注意

• 因为返回类型是iterator ，即迭代器。所以，不能直接返回新创建出来的节点，即newNode，需要用newNode作为实参去创建一个迭代器，再将这个迭代器返回。

3、erase函数

（1）代码

iterator erase(iterator pos)
{
    assert(pos != end());
    PNode prev = pos._pNode->_pPre;
    PNode next = pos._pNode->_pNext;
    prev->_pNext = next;
    next->_pPre = prev;
    delete pos._pNode;

    return iterator(next);
}
1
2
3
4
5
6
7
8
9
10
11

（2）实现原理

• 因为erase是删除存有数据的链表节点，而头节点不属于这个范畴，所以，使用assert对pos进行断言，当删除的位置是头节点时，直接进行报错而不进行下面的操作。
• 因为是删除pos节点，所以，需要对pos的前一个节点和后一个节点进行处理，即对节点的_pPre 和_pNext 进行修改。
• 然后再释放掉pos节点的空间，最后再返回用下一个节点作为实参创建出来的迭代器。

4、迭代器函数

（1）代码

iterator begin()
{
    return iterator(_pHead->_pNext);
}
iterator end()
{
    return iterator(_pHead);
}

const_iterator begin() const
{
    return const_iterator(_pHead->_pNext);
}
const_iterator end() const
{
    return const_iterator(_pHead);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

（2）实现原理

• 因为有头节点的存在，所以头节点的下一个节点就是存储数据的链表节点中的第一个节点，头节点的位置就是存储数据的链表节点中的最后一个节点的下一个节点。所以，各函数就返回对应节点的迭代器即可。
• 为了让被const修饰的链表对象也能调用对应的函数，所以需要重载对应的函数，即重载this指针被const修饰，返回类型也被const修饰的函数。

（3）注意

• 因为返回类型是迭代器，所以返回的不能是节点本身，即_pHead->_pNext和_pHead，而是要用该节点去构造一个迭代器对象，再将这个迭代器对象作为返回值返回。

5、clear函数和析构函数

（1）代码

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

    _pHead->_pPre = _pHead;
    _pHead->_pNext = _pHead;
}

~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

（2）实现原理

• 因为clear函数是清理链表的元素，对头节点不做处理。所以，使用迭代器的方法遍历链表并释放它们的空间。对迭代器的自增可以在调用erase函数后更新迭代器it的值，因为erase函数返回的是被删除节点的下一个节点，即代码中被注释的部分；也可以在调用erase函数时，使用后置自增的方法，即传入的实参是没自增之前的迭代器，在这个时候erase函数还没调用，但迭代器it已经完成了自增。
• 因为clear函数不对头节点做处理，所以在最后需要对头节点_pHead的前后指针进行修改，不然它指向的空间已经被释放，而对它们进行访问将是非法的操作。
• 因为clear函数可以清理链表的元素，所以，析构函数可以复用clear函数，然后再对头节点的空间进行释放即可。最后，为了安全，可以将头节点置为空。

6、swap函数、构造函数、拷贝构造函数和赋值运算符重载

（1）代码

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

template <class Iterator>
list(Iterator first, Iterator last)
{
    CreateHead();
    while (first != last)
    {
        push_back(*first++);
    }
}
list(const list<T>& l)
{
    CreateHead();
    list<T> tmp(l.begin(), l.end());
    swap(tmp);
}

list<T>& operator=(list<T> l)
{
    swap(l);
    return *this;
}
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

（2）实现原理

• 因为链表头节点的作用是访问其他节点，所以，交换两个链表只需交换它们的头节点即可。
• 迭代器方式的构造函数只需用迭代器遍历链表并将对应的元素尾插在本链表里即可，而尾插函数实际上就是复用insert函数在end()位置进行插入元素操作的函数。
• 因为有了迭代器方式的构造函数，所以拷贝构造函数可以直接复用它，最后再将本链表和构造出来的链表tmp进行交换即可。
• 赋值运算符重载函数可以采用形参传值拷贝的方式， 即形参是拷贝出来的链表，此时，再将本链表和形参链表进行交换即可。

四、模拟实现list的代码

#pragma once

#include
#include
using namespace std;

namespace snow
{
    //List的节点类
    template<class T>
    struct ListNode
    {
        ListNode(const T& val = T())
            :_val(val)
            ,_pPre(nullptr)
            ,_pNext(nullptr)
        {}
        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)
            :_pNode(pNode)
        {}

        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;
    };


    //list类
    template<class T>
    class list
    {
        typedef ListNode<T> Node;
        typedef Node* PNode;
        typedef ListIterator<T, T&, T*> iterator;
        typedef ListIterator<T, const T&, const T*> const_iterator;
    public:
        list()
        {
            CreateHead();
        }
        list(int n, const T& value = T())
        {
            CreateHead();
            for (size_t i = 0; i < n; ++i)
            {
                push_back(value);
            }
        }
        template <class Iterator>
        list(Iterator first, Iterator last)
        {
            CreateHead();
            while (first != last)
            {
                push_back(*first++);
            }
        }
        list(const list<T>& l)
        {
            CreateHead();
            list<T> tmp(l.begin(), l.end());
            swap(tmp);
        }
        list<T>& operator=(list<T> l)
        {
            swap(l);
            return *this;
        }
        ~list()
        {
            clear();
            delete _pHead;
            _pHead = nullptr;
        }
        
        iterator begin()
        {
            return iterator(_pHead->_pNext);
        }
        iterator end()
        {
            return iterator(_pHead);
        }
        const_iterator begin() const
        {
            return const_iterator(_pHead->_pNext);
        }
        const_iterator end() const
        {
            return const_iterator(_pHead);
        }
        
        size_t size()const
        {
            size_t size = 0;
            const_iterator start = begin();
            while (start != end())
            {
                ++size;
                ++start;
            }
            return size;
        }
        bool empty()const
        {
            return size() == 0;
        }

        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;
        }

        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());
        }

        iterator insert(iterator pos, const T& val)
        {
            /*PNode newNode = new Node;
            newNode->_val = val;*/

            PNode newNode = new Node(val);

            PNode posNode = pos._pNode;
            PNode prev = posNode->_pPre;
            newNode->_pNext = posNode;
            newNode->_pPre = prev;
            posNode->_pPre = newNode;
            prev->_pNext = newNode;
            
            return iterator(newNode);
        }
        iterator erase(iterator pos)
        {
            assert(pos != end());

            PNode prev = pos._pNode->_pPre;
            PNode next = pos._pNode->_pNext;
            prev->_pNext = next;
            next->_pPre = prev;
            delete pos._pNode;

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

            _pHead->_pPre = _pHead;
            _pHead->_pNext = _pHead;
        }
        void swap(list<T>& l)
        {
            ::swap(_pHead, l._pHead);
        }
    private:
        void CreateHead()
        {
            _pHead = new Node;
            _pHead->_pPre = _pHead;
            _pHead->_pNext = _pHead;
        }
        PNode _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
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250

• 本文只是对list的一些常用与常见的函数模拟实现与讲解，一些比较简单的函数没有讲解但在上方的代码中都有模拟实现的代码。

本文到这里就结束了，如有错误或者不清楚的地方欢迎评论或者私信
创作不易，如果觉得博主写得不错，请务必点赞、收藏加关注💕💕💕