C++模拟实现——list

一、成员变量及其基本结构

1.基本结构模型

本质是一个带头双向循环列表，将节点进行封装，并且为了方便使用，进行重定义

2.节点的封装定义

	template<class T>//定义节点struct list_node{list_node<T>* _prev;list_node<T>* _next;T _data;list_node(const T& x = T()) :_prev(nullptr),_next(nullptr),_data(x){}};

在定义节点时，要注意将初始化一起进行封装完成，提供默认构造函数

3.成员变量的定义

成员变量是一个哨兵位的头结点

typedef list_node<T> node;//对节点重命名，方便使用
private:list_node<T>* _head;

二、迭代器（重点）

1.介绍

list的迭代器用原生指针无法实现，需要对原生指针进行封装，然后对顺序表指针的行为操作进行模拟实现，是list模拟实现中最大的重点难点，此时从使用者的角度上看，依然能将iterator看作为指针去使用，但设计者的角度上看，其本质是一个指针的封装，是个自定义类型。

2.对指针的基本封装

template<class T>
struct __list_iterator
{typedef list_node<int> node;//将节点重定义方便使用typedef __list_iterator<int> self;//将类型重定义方便使用//成员变量node* _node;//初始化__list_iterator(node* n):_node(n){}//模拟实现指针操作...
}

以上对节点指针进行了封装处理，之后逐一实现常用的功能，例如：++ 、--、* 、 -> 、== 、!= 等等

3.++和--

要提供迭代器++和--的操作，需要对运算符进行重载，链表迭代器的++本质上是获得下一个节点的地址，--则是前一个节点的地址，并且要区分前置和后置

        //++slef& operator++(){_node = _node->_next;return *this;}slef operator++(int)//后置{slef tmp(*this);_node = _node-> _next;return tmp;}//--self& operator--(){_node = _node->_prev;return *this;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}

4.== 和 !=

迭代器的比较，本质是要比较其封装在内部的指针是否同一个

bool operator!=(const self& n)
{return _node != n._node;
}bool operator==(const self& n)
{return _node == n._node;
}

5. * 和 ->

对解引用操作符的重载，则需要考虑到常量迭代器的调用，常量迭代器去本质是对迭代器所指向的内容进行常量化，因此在这里，const_iterator 和 iterator 的核心区别在于解引用后返回的值是否常量，其他功能相同，因此可以使用类模板去控制这两个运算符重载返回值的区别，在定义部分加上两个新的模板参数即可。

template<class T,class Ref,class Ptr>
strucr __list_iterator
{...//定义和重命名等等Ref operator*()//  Ref == T&（迭代器） / const T&（常量迭代器）{return _node->_data;}//对于->的重载，存在特殊处理，只需要返回Ptr operator->()// Ptr == T*（迭代器）/ const T*（常量迭代器）{return& _node->_data;}
}// 迭代器定义部分，在list类内定义
// typedef __list_iterator<T,T&,T*> iterator;
// typedef __list_con_iterator<T,const T&,const T*>;

三、构造与析构

1.默认构造函数

默认构造需要初始化出一个哨兵位的头结点，并且让节点指针指向自己，为了方便其他构造函数初始化哨兵位的头结点，可以单独写一个函数进行复用

		void empty_init(){_head = new node;_head->_next = _head;_head->_prev = _head;}list()//直接的初始化{empty_init();}

2.用迭代器区间去构造

迭代器区间构造需要借助函数模板，任意类型的迭代器都可以将值拷贝到容器中

template<class Iterator>
list(Iterator first,Iterator last)
{//先得初始化容器empty_init();while(first != last){push_back(*first); // 底层是++first;}
}

3.拷贝构造

拷贝构造这里选择对上面的构造函数进行复用，深拷贝出一个tmp，在进行交换

		void swap(list<T>& lt){std::swap(_head, lt._head);}list(const list<T>& lt)//拷贝构造{empty_init();list<T> tmp(lt.begin(), lt.end());swap(tmp);}

4.赋值重载

赋值重载的底层实现，也是在传参的时候，调用了拷贝构造实现深拷贝后，在进行交换

		list<T>& operator=(list<T> lt)//赋值重载{swap(lt);return *this;}

5.析构函数

可以先实现clear，然后复用，底层就是将所有节点全部逐一释放，用迭代器遍历释放即可

		void clear(){iterator it = begin();while (it != end()){it = erase(it);}}~list()//析构{clear();delete _head;_head = nullptr;}

四、增删操作

对应增删操作，只需要实现insert和erase，其余的头插头删等等都可以对其进行复用，这里是用迭代器去实现的。

		void insert(iterator pos, const T& x){node* cur = pos._node;node* prev = cur->_prev;node* new_node = new node(x);//链接new_node->_prev = prev;prev->_next = new_node;new_node->_next = cur;cur->_prev = new_node;}iterator erase(iterator pos){assert(pos != end());node* cur = pos._node;node* prev = cur->_prev;node* next = cur->_next;delete cur;//链接prev->_next = next;next->_prev = prev;return iterator(next);}

需要注意的是，erase后迭代器会失效，因此为了部分场景下的方便，erase是有一个返回值的，返回的是下一个节点的迭代器；

总结

本章通过自行模拟实现了list，加深了类和对象以及list的相关知识，其中很重要的一个知识点就是对与list迭代器的封装和实现，本篇博客整理了整个实现过程的思路，方便今后复习和其他同学参考学习