(C++) list底层模拟实现

个人主页：Lei宝啊

愿所有美好如期而遇

首先，list底层是一个带头双向循环链表，再一个，我们还要解决一个问题，list的迭代器，vector和string的迭代器可以直接++，是因为他们的地址空间是连续的，而链表不是，所以链表的迭代器封装的不是原生指针，我们需要想办法解决这个问题。

我们要解决list<T>::iterator可以++，既然我们不能封装原生指针，那么我们就对他进行运算符重载，但是在我们模拟的list类里，是不应该有这样的用法：list<int> lt, lt.operater++()，我们想要的是迭代器的运算符重载，即: list<int>::iterator it = lt.begin(); it++ 这样的用法，那么我们就写一个迭代器的类，在这个类里重载++运算符。

首先是链表，我们先写出带头双向循环链表的结构，以及他的构造函数，至于为什么不用class类，是因为这样做后续可直接使用他的成员变量，如果写成类，还需要get set函数，比较麻烦，我们模拟实现理解原理即可，所以为了省事，不使用class。

template<class T>
struct ListNode
{
	ListNode<T>* next;
	ListNode<T>* prev;
	T data;

	ListNode(const T& x = T())
		:next(nullptr)
		,prev(nullptr)
		,data(x)
	{}
};

接下来是list类的实现，第一个typedef是将链表的类型重命名，第二个typedef是将迭代器类进行重命名，第三个typedef也是将迭代器类进行重命名，并且这两个迭代器是为了区分const和非const，模版参数我们也可以看得出来。

template<class T>
class list
{
	typedef ListNode<T> Node;
public:
	typedef __list_iterator<T, T&, T*> iterator;
	typedef __list_iterator<T, const T&, const T*> const_iterator;

    //empty_init方法是初始化一个哨兵位， 接着就是构造函数，也就是初始化一个哨兵位；
	void empty_init()
	{
		_head = new Node();
		_head->prev = _head;
		_head->next = _head;
	}

	//构造函数
	//list<int> lt(); &lt  this
	list<T>()
	{
		empty_init();
	}

	void swap(list<T>& x)
	{
		std::swap(_head, x._head);
	}

	//拷贝构造
    //对于拷贝构造，我们需要进行深拷贝，先初始化一个哨兵位，然后遍历被拷贝的链表，             
    //用push_back方 法不断尾插节点，完成深拷贝；
	list(list<T>& copy)
	{			 
		empty_init();

		iterator it = copy.begin();
		while (it != copy.end())
		{
			push_back(it._node->data);
			it++;
		}
	}

    //最后就是赋值运算符重载，我们传参不传引用，就是为了在传参时拷贝构造出一个链表，           
    //然后我们只需要交换_head，就可以完成赋值，这里我们写一个swap方法。
	list<T>& operator=(list<T> tmp)
	{
		swap(tmp);
		return *this;
	}
    
    //push_back方法，只需要理清楚插入节点newnode和_head的关系就好；
	void push_back(const T& x = T())
	{
		//_head->prev newnode _head

		//Node* newnode = new Node(x);
		//Node* tail = _head->prev;
		//
		//tail->next = newnode;
		//newnode->prev = tail;
		//_head->prev = newnode;
		//newnode->next = _head;
		insert(end(), x);

	}

    //insert方法也是类似于push_back方法，我们写出insert方法后，                     
    //push_back完全可以复用insert方法，链表的insert没有迭代器失效问题；
	iterator insert(iterator pos, const T& x = T())
	{
		//pos->prev newnode pos
		Node* cur = pos._node;
		Node* prev = cur->prev;
	
		//prev newnode cur
		Node* newnode = new Node(x);
		newnode->next = cur;
		cur->prev = newnode;
		prev->next = newnode;
		newnode->prev = prev;

		return newnode;
	}

    //begin和end方法，也就是返回链表的开始位置和尾部位置，注意，                             
    //开始位置是_head->next，尾部位置是_head->prev；
	iterator begin()
	{
		return iterator(_head->next);
	}

	const_iterator begin() const
	{
		return _head->next;
	}

	iterator end()
	{
		return iterator(_head);
	}

	const_iterator end() const
	{
		return _head;
	}

    //erase方法我们使用时还是要注意迭代器失效问题，删除一个节点后，                          
    //迭代器就是一个野指针，也就失效了；
	iterator erase(iterator pos)
	{
		Node* cur = pos._node;
		Node* prev = cur->prev;
		Node* next = cur->next;

		prev->next = next;
		next->prev = prev;

		return iterator(next);
	}

    //clear方法，我们需要遍历链表释放所有节点，我们这里可以复用erase方法；
	void clear()
	{
		iterator it= begin();
		while (it != end())
		{
			erase(it++);
		}
	}

    //析构函数，我们调用clear释放掉其他节点后，我们再单独释放掉哨兵位；
	~list()
	{
		clear();

		delete _head;
		_head = nullptr;
	}

private:
	Node* _head;

};

__list_iterator类的实现

模版参数有三个，因为我们要明白，iterator是有解引用操作的，非const对象可以对值修改，但是const对象不可以，当然，我们可以写他的重载，但是有了这样一个模板参数，只需要修改返回值即可，并且我们重载了->运算符，这个返回值时一个指针，我们仍然需要区分是否是const对象。

template<class T, class ref, class ptr>
struct __list_iterator
{
	typedef ListNode<T> Node;
	
public:

	//构造函数
	__list_iterator(Node* node)
		:_node(node)
	{}

	//前置++
	__list_iterator& operator++()
	{
		_node = _node->next;
		return *this;
	}

	//后置++
	__list_iterator& operator++(int)
	{
		//auto tmp = __list_iterator(this->_node);
		auto tmp = __list_iterator(*this);
		_node = _node->next;
		return tmp;
	}

	//前置--
	__list_iterator& operator--()
	{
		_node = _node->prev;
		return *this;
	}

	//后置--
	__list_iterator& operator--(int)
	{
		//auto tmp = __list_iterator(this->_node);
		auto tmp = __list_iterator(*this);
		_node = _node->prev;
		return tmp;
	}

	ref operator*()
	{
		return _node->data;
	}

	ptr operator->()
	{
		return &_node->data;
	}

	bool operator!=(const __list_iterator& x)
	{
		return _node != x._node;
	}
	
	Node* _node;
};

那么我们是如何使用的呢？

list<int>::iterator it = lt.begin()，lt是list<int>类型，非const，则调用非const begin方法，但是我们的begin返回值是_head->next，是个Node*类型的指针，我们返回值类型可是iterator，封装的是__list_iterator类，但是这个类的构造函数所传的参数是单参数，而且也是Node*，也就是说，会进行隐式类型转换，_head->next会构造出一个__list_iterator临时对象，然后进行返回，然后这个临时对象再拷贝构造it，如果编译器进行优化，也就变成了直接进行拷贝构造。

我们的主要问题，对++运算符的重载也就不是问题了，唯一需要注意的是前置和后置++，区分它们只能是通过参数了，我们一般是给后置++的参数加上int。

最后一个问题就是->的重载，如果我们使用是不是这样使用：

假设我们有一个结构体，AA{int a; int b},list<AA> lt; 我们要通过iterator访问他的成员变量，list<AA>::iterator it = lt.begin(),返回值就是AA的地址，那么我们如何访问他的成员变量呢？

it.operator->()->a，或者是it->->a?