C++ list 模拟实现

1. 基本结构的实现

2. list()

3. void push_back(const T& val)

4. 非 const 迭代器

4.1 基本结构

4.2 构造函数

4.3 T& operator*()

4.4 __list_iterator& operator++()

4.5 bool operator!=(const __list_iterator& it)

4.6 T* operator->()

5. const 迭代器

6. begin() && end()

编辑

7. iterator insert(iterator pos, const T& val)

8. iterator erase(iterator pos)

9. void push_front(const T& val)

10. void pop_front()

11. void pop_back()

12. size_t size() const

13. void clear()

14. ~list()

1. 基本结构的实现

在 list 的使用部分，我们已经知道了 list 其实就是一个带头的双向循环链表 (以下简称双链表)。结合我们在 C 语言写过的双链表的实现：C语言数据结构初阶(4)----带头双向循环链表_姬如祎的博客-CSDN博客

第一步要做的就是定义出链表的节点。和 C 语言不一样的是，list 可以存储任意类型的数据，因此必须定义成模板。老规矩为了与库中的 list 做区分，我们还是会把自己模拟实现的 list 放到一个命名空间里面。

namespace Tchey
{template<class T>struct ListNode{T _val;ListNode<T>* _prev;ListNode<T>* _next;ListNode(const T& val = T()):_val(val),_prev(nullptr),_next(nullptr){}};
}

在 C++ 中结构体被提升成了类，因此在定义双链表的节点的时候，我们可以写一个节点的构造函数，这样在堆上申请节点的时候，就能够直接初始化节点的 val 值啦！

OK，既然双链表的节点定义好了，list 类中的成员变量应该如何定义呢？起始很简单，list 类想要维护一个双链表只需要维护头结点的指针就可以了。因为 list 是带头的双链表，因此，list 的成员变量就是那个哨兵位的头结点的指针。

namespace Tchey
{template<class T>class list{private:ListNode<T>* _head;};
}

2. list()

这个是 list 的无参构造函数，他的任务就是做好初始化哨兵位的头结点的工作。你还记得双向带头循环链表的初始化应该怎么做吗？看下面的图你应该就会记得了吧！

因为哨兵位的头结点是不需要存储任何有效的数据的，他的 val 值填多少都无所谓！索性就不填了，用默认的 val 就行。

list()
{_head = new ListNode<T>;_head->_next = _head;_head->_prev = _head;
}

3. void push_back(const T& val)

这个是双链表的尾插，双链表的尾节点，就是哨兵位的头结点的 _prev。开辟新节点，找到尾节点，做好链接工作就行啦！不知道如何链接，请看 C 语言实现的双向链表中的 push_back 函数：

C语言数据结构初阶(4)----带头双向循环链表_姬如祎的博客-CSDN博客

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

4. 非 const 迭代器

list 的迭代器是我们遇到的第一个不是原生指针的迭代器，我们来看看他的迭代器和 vector 迭代器的差别：

对于 vector 来说，他的迭代器是 int 类型的指针 (假设vector存储 int 数据)，解引用就直接能访问到真实的数据。如果 list 也是原生指针，那只能是结构体的指针，解引用得到的就是一个结构体，无法拿到真实的数据。list 拿到数据需要通过访问结构体的 _val 成员得到。

对于 vector 来说，他的迭代器是 int 类型的指针 (假设vector存储 int 数据)，并且 vector 的存储空间是连续的。迭代器加加就能直接跳过一个整形的空间，直接指向下一个有效的数据。

list 呢，物理空间不连续，如果 list 迭代器是结构体指针，加加之后访问到的空间并一定不属于你，可能会发生内存错误。实际上 list 的迭代加加之后，应该是指向节点的下一个节点，即需要通过 _next 找到下一个节点。

综上所述，list 的迭代器不可能是原生指针，需要对节点的指针进行封装。封装时，我们需要重载 *，++，等运算符，这样才能正确实现迭代器的效果。

4.1 基本结构

我们已经知道了，list 的迭代器就是对原生的结构体指针进行封装。然后通过运算符重载实现迭代器应有的功能。那这个迭代器的成员变量当然就是一个节点的指针啦！

namespace Tchey
{template<class T>struct __list_iterator{public:private:ListNode<T>* _node;};
}

4.2 构造函数

在 list 类里面，有 begin()，end() 之类的函数，用来返回一个迭代器对象，那么我们实现的迭代器就需要提供构造函数，支持使用节点的指针构造出来一个迭代器对象。

__list_iterator(ListNode<T>* node):_node(node)
{}

4.3 T& operator*()

我们都使用过迭代器遍历一个容器，知道了迭代器的解引用解释返回真实有效的数据，因此 operator 就是返回节点的 _val 值。

T& operator*()
{return _node->_val;
}

4.4 __list_iterator<T>& operator++()

对于 list 来说迭代器加加实际上就是让迭代器的成员变量 _node 指向当前节点的下一个节点。

__list_iterator<T>& operator++()
{_node = _node->_next;return *this;
}

4.5 bool operator!=(const __list_iterator<T>& it)

这个函数就是判断两个迭代器是否是一样的嘛，判断的逻辑就是判断两个迭代成员的节点指针是否相同。不能不写 const 因为 list 中的 begin()，end() 返回的都是一个迭代器的拷贝，当我们自己定义的迭代器变量与 end() 的返回值做 != 判断时就会调用 operator!= 如果没有 const，因为 end 的返回值具有常性，是无法用非 const 的迭代器类型来接收的。

bool operator!=(__list_iterator<T>& it)
{return _node != it._node;
}

4.6 T* operator->()

为什么要重载这种解引用的方式呢？emm，如果 list 容器存储的是一个结构体类型，或者其他自定义类型，那么重载了 -> 就能较为方便拿到我们的数据！

如果我没有重载 -> 那么当我们用迭代器区访问一个存储自定义类型的 list 的时候，你就需要这么写：

struct info
{int a;int b;
};int main()
{info in = { 10,20 };list<info> lt;lt.push_back(in);auto it = lt.begin();while (it != lt.end()){cout << (*it).a << " " << (*it).b << endl;it++;}return 0;
}

但是如果你重载了 -> 这个运算符，你就可以这么写：

struct info
{int a;int b;
};int main()
{info in = { 10,20 };list<info> lt;lt.push_back(in);auto it = lt.begin();while (it != lt.end()){cout << it->a << " " << it->b << endl;it++;}return 0;
}

我们下来看看怎么重载 -> 这个吧，其实重载 -> 就是返回 list 中的成员变量的 _val 的地址：

T* operator->()
{return &(_node->_val);
}

上面的例子中在使用迭代器遍历 list 的时候，it->a，本质上应该是先调用 operator-> 得到结构体的指针，再通过 -> 拿到数据，因此实际上应该这么写的：it->->a。但是这样写着实奇怪，因此编译器会进行处理，我们只需要这么写就可以：it->a。

5. const 迭代器

首先，我们要理解 const 迭代器和非 const 迭代器的区别：

在 const 迭代器中解引用返回的数据是不能够更改的。

在 const 迭代器中 operator-> 返回的指针解引用得到的数据也是不能修改的！

也就是说在 const 迭代器中 operator* 的返回值应该是 const T&，operator-> 的返回值应该是 const T* 。然后，你一拍脑袋说，这好办哇！我们把非 const 迭代器的代码 copy 一份，改成 const 迭代器不就行了嘛！是的这样做完全没问题，但是，既然我们学了模板，这样的脏活累活自然得交给我们的编译器去做啦！

我们来看看怎么把 const 迭代器和非 const 迭代器融合成一个模板吧！const 迭代器和非 const 迭代器的不同就是右两个函数的返回值类型不同嘛，因此我们可以将函数的返回值的类型参数化，通过外部实例化的传递来决定是 const 迭代器还是非 const 迭代器！

因为有两个函数的返回值不相同，所以我们需要为我们封装的迭代器增加两个模板参数！

当我们传入 T&，T* 就是非 const 的 iterator，当我们传入 const T&，const T* 就是 const 的 iterator。是不是美妙绝伦！

__list_iterator 的模板参数改了，其他的函数也相应地改改嘛！因为给 __list_iterator 加上模板参数之后呢，这个类型写起来就比较复杂，我们可以使用 typedef 给他重新去一个名字

template<class T, class Ref, class Ptr>
struct __list_iterator
{
public:typedef __list_iterator<T, Ref, Ptr> self;__list_iterator(ListNode<T>* node):_node(node)
{}self& operator++()
{_node = _node->_next;return *this;
}bool operator!=(const self& it)
{return _node != it._node;
}Ref operator*()
{return _node->_val;
}Ptr operator->()
{return &(_node->_val);
}private:
ListNode<T>* _node;
};

6. begin() && end()

上面的那张图已经解释了如何定义 const 迭代器和非 const 迭代器啦！那么 begin() 与 end() 的 const 版本和非 const 版本就是信手拈来了！

begin 对应的迭代器起始就是用 _head->_next 构造一个迭代器返回！

typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;iterator begin()
{return _head->_next;
}iterator end()
{return _head;
}const_iterator begin() const
{return _head->_next;
}const_iterator end() const
{return _head;
}

为啥可以直接返回节点的指针呢？因为单参数的构造函数支持隐式类型转化嘛！

其实 list 的模拟实现，难的就是迭代器的部分，好的，我们的迭代器就已经实现完毕了！懂的都懂嘛！

7. iterator insert(iterator pos, const T& val)

我们先通过 pos 拿到节点的指针，申请节点，链接就行了，相当简单呢！最后返回新插入的节点的迭代器。

void insert(iterator pos, const T& val)
{ListNode<T>* cur = pos._node;ListNode<T>* prev = cur->_prev;ListNode<T>* newNode = new ListNode<T>(val);prev->_next = newNode;newNode->_prev = prev;newNode->_next = cur;cur->_prev = newNode;return newNode;
}

8. iterator erase(iterator pos)

在 list 的使用哪一节，我们观察到了，erase 是不能删除 end() 位置的节点的，即不能删除哨兵位的头结点。我们可以使用断言检查。为了解决迭代器失效的问题呢，我们可以给 erase 增加一个返回值。

iterator erase(iterator pos)
{ListNode<T>* cur = pos._node;ListNode<T>* prev = cur->_prev;ListNode<T>* next = cur->_next;delete cur;prev->_next = next;next->_prev = prev;return next;
}

9. void push_front(const T& val)

在我们完成了 insert 接口和 erase 接口的实现之后，下面的插入删除可以完全复用啦！

void push_front(const T& val)
{insert(begin(), val);
}

10. void pop_front()

void pop_front()
{erase(begin());
}

11. void pop_back()

这里的 -- 需要在迭代器里面重载，原理和 ++ 差不多，就交给你来实现啦！

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

12. size_t size() const

遍历一遍出结果，或者呢，你也可以在 list 里面维护一个表示 list 长度的变量。

size_t size() const
{int sz = 0;auto it = begin();while (it != end()){sz++;++it;}return sz;
}

13. void clear()

这个函数是清空 list 存储有效数据的节点，也就是说 clear 之后呢，哨兵位的头结点还在！

切记不可以 ++it，因为迭代器失效的问题嘛！我们通过 erase 的返回值来清除节点就行啦。

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

14. ~list()

主打的就是一个复用。我们写完 clear 之后析构函数直接复用，然后再释放掉 _head 就可以啦！

~list()
{clear();delete _head;_head = nullptr;
}