STL——list的介绍和模拟实现

前言

本篇博客我们将要开始介绍list这个容器，list是带头双向循环链表，STL标准模板库中实现了list这样方便我们去使用，那么本篇博客我们将脱下list的神秘外衣，介绍它的使用以及模拟实现。

list的介绍

list的底层是带头双向循环链表，可以在任意位置完成插入删除的功能，了解其迭代器我们将更加深入了解C++封装的特性。与vector相比，list的最大缺陷是不支持随机访问，但由于其底层封装了迭代器，因此list是可以通过迭代器访问的。同时，由于list的结构是链状的，所以它在一定程度上可以节省空间

下面我们来看一下list为我们提供的接口：

首先来看list的构造函数：

list与其他容器一样都提供了一个迭代器构造，initializer构造以及拷贝构造 

接下来是迭代器：

 容量操作：

修改操作：

list的模拟实现

这是这篇博客的重点，通过模拟实现list我们将更加深入了解list的底层结构，以及如何使用

节点：

首先我们提供一个节点的类，这个类里面包含了prev指针，next指针以及我们要存储的数据data，如下所示：

template<class T> 
struct ListNode
{
	ListNode<T>* _next;
	ListNode<T>* _prev;
	T _data;
	ListNode(const T& data = T()) :_next(nullptr), _prev(nullptr), _data(data);
	{}
};

分析上述代码，我们看到，我们将这个类声明为struct而不是class，这是为什么呢？因为在后续的操作过程中我们将频繁访问 节点当中的数据，如果声明成class，那么如果我们要访问内部的数据就要声明成友元或者内部类，这样会对阅读代码的人造成困扰，同时也不方便我们去操作，所以在实际操作过程中，如果看见了需要频繁操作的数据，那么我们尽可能的让它声明成struct

同时，我们在这个节点类中提供了一个构造函数，这样可以使我们的程序更加安全可靠。

list类

有了节点后我们将用这个节点去创建一个list，因此我们此时需要一个list类，里面封装我们要实现list的各种操作，其代码如下所示：

template<class T>
class list
{
	typedef ListNode<T> Node;
public:

private:
	Node* _head;
};

首先我们搭建出list的框架，里面封装了一个头节点，其后续要实现的各种功能我们将在public中实现。同时，我们将ListNode<T>重新命名为了Node，这样是为了可读性考虑

迭代器的实现

我们知道，迭代器为容器提供了一种统一的访问形式，从而屏蔽了底层细节，方便人们使用和学习。前面我们实现了vector，它的迭代器是一个指针，那么对于list而言我们能用指针实现吗？答案是否定的，因为它的结构不是连续的，所以我们不能这么做，那么为了保证我们有一种统一的访问方式我们必须提供一个类去封装iterator，这个类里面得重载前置++，前置--，后置++，后置--，迭代器，解引用等功能，其结构如下所示：

	template<class T>
	struct ListIterator
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T> Self;
		Node* _node;

		ListIterator(Node*node):_node(node)
		{}


	};

分析上述代码，我们可以看到，在这个迭代器类中我们保存了一个节点，以便访问节点中的数据，从而实现对节点的操作，由于后续要频繁访问数据，所以我们同样将ListIterator声明为公有。

前置++/--

Self& operator++()
{
	_node = _node->_next;
	return *this;
}
Self& operator--()
{
	_node = _node->_prev;
	return *this;
}

后置++/--

Self operator++(int)
{
	Self tmp(_node);
	_node = _node->_next;
	return tmp;
}
Self operator--(int)
{
	Self tmp(_node);
	_node = _node->_prev;
	return tmp;
}

重载*

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

重载->

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

重载==/!=

bool operator==(const Self&it)
{
	return _node == it._node;
}
bool operator!=(const Self& it)
{
	return _node != it._node;
}

 由此，我们就完成了一个iterator，但是这样的代码显然移至性是很低的，为什么呢？因为在实际操作过程中，我们常常会遇见const修饰的对象，那么对于其而言我们应该使用const迭代器去完成，那这该怎么办呢？有两种解决方法，一种是重新实现一个const类型的迭代器；另一种通过调用不同的模板参数去完成，显然第一种方法虽然很简单，但是有很多重复的代码，所以我们在实际操作中更多的是用第二种解决方法。

仔细观察上述代码，我们发现只有函数可以用const修饰，一个是T&，一个是T*，那么我们可以再加两个模板参数，一个负责T&，一个负责T*，那么我们就得到了下面的代码：

template<class T,class Ref,class Ptr>
struct ListIterator
{
	typedef ListNode<T> Node;
	typedef ListIterator<T,T&,T*> Self;
	Node* _node;

	ListIterator(Node*node):_node(node)
	{}

	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	Self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}

	Self operator++(int)
	{
		Self tmp(_node);
		_node = _node->_next;
		return tmp;
	}
	Self operator--(int)
	{
		Self tmp(_node);
		_node = _node->_prev;
		return tmp;
	}

	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &_node->_data;
	}

	bool operator==(const Self&it)
	{
		return _node == it._node;
	}
	bool operator!=(const Self& it)
	{
		return _node != it._node;
	}
};

begin()与end()

当我们将list的迭代器类实现出来后我们就可以用迭代器访问这个类，因此我们应该在list这个类中提供一个接口，这个接口就是begin与end，其代码如下所视：

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

list的插入/删除

list最常见的插入删除就是在头部和尾部的插入删除，其中插入的步骤是：

1.创建新节点

2.获取目标位置的节点及其前驱节点

3.让新节点的头指向目标位置节点的头节点，让新节点的尾节点指向目标位置节点

4.让前驱节点的尾指向新节点，目标位置节点的头指向新节点

值得注意的是：list的插入/删除伴随着迭代器失效的问题，即：插入新节点后无法访问插入位置的数据

那么解决方法是什么呢？很简单，就是返回插入位置的数据，因此list的插入和删除都要传迭代器接收目标位置的数据，代码如下：

iterator insert(iterator pos, const T& x)
{
	Node* newnode = new Node(x);
	Node* cur = pos._node;
	Node* prev = cur->_prev;

	newnode->_next = cur;
	newnode->_prev = prev;
	prev->_next = newnode;
	cur->_prev = newnode;
	return iterator(newnode);
}
iterator erase(iterator pos)
{
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;

	prev->_next = next;
	next->_prev = prev;
	delete cur;
	return iterator(next);
}

有了插入删除的接口，那么我们就可以很轻松实现list的头部插入删除，尾部插入删除，其代码如下：

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

void push_back(const T& x)
{
	insert(begin(), x);
}
void push_front(const T& x)
{
	insert(end, x);
}

构造/析构函数

list的C++标准库中提供了很多的构造方式，我们在这里只着重介绍其中的无参构造，initializer_list构造以及拷贝构造，在实现构造函数之前，我们应该先写一个初始化函数，这个初始化函数是将头节点的next和prev都指向自己从而实现初始化，我们在写构造函数时，主要用这个初始化函数来构造，其代码如下：

void empty_init()
{
	_head = new Node();
	_head->_next = _head;
	_head->_prev = _head;
}
list()
{
	empty_init();
}
list(const list<T>& il)
{
	empty_init();
	for (const auto& e : il)
	{
		push_back(e);
	}
}
list(initializer_list<T> il)
{
	empty_init();
	for (const auto& e : il)
	{
		push_back(il);
	}
}

析构函数与构造函数类似，提供了一个clear接口，通过调用clear接口逐个删除list的节点，最后再将头节点释放，这样就实现了一个简单的析构函数，其代码如下所示：

void clear()
{
	auto it = begin();
	while (it != end())
	{
		it = erase(it);
	}
}
~list()
{
	clear();
	delete _head;
	_head = nullptr;
}

重载=

list的重载=是通过传值传参然后调用swap来实现的，其代码如下所示：

list<T>& operator=(const list<T> lt)
{
	swap(_head, lt._head);
	return *this;
}

分析上述代码，我们可以看到，不同于传统的重载operator=我们这里采用了传值传参，然后交换头节点，这样做的好处显而易见，传值传参调用拷贝构造产生一个临时对象，临时对象具有常量属性因此要加const修饰，在出作用域之后就析构销毁。

list模拟实现代码如下

template<class T> 
struct ListNode
{
	ListNode<T>* _next;
	ListNode<T>* _prev;
	T _data;
	ListNode(const T& data = T()) :_next(nullptr), _prev(nullptr), _data(data)
	{}
};

template<class T,class Ref,class Ptr>
struct ListIterator
{
	typedef ListNode<T> Node;
	typedef ListIterator<T,T&,T*> Self;
	Node* _node;

	ListIterator(Node*node):_node(node)
	{}

	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	Self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}

	Self operator++(int)
	{
		Self tmp(_node);
		_node = _node->_next;
		return tmp;
	}
	Self operator--(int)
	{
		Self tmp(_node);
		_node = _node->_prev;
		return tmp;
	}

	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &_node->_data;
	}

	bool operator==(const Self&it)
	{
		return _node == it._node;
	}
	bool operator!=(const Self& it)
	{
		return _node != it._node;
	}
};

template<class T>
class list
{
	typedef ListNode<T> Node;
public:
	typedef ListIterator<T, T&, T*> iterator;
	iterator begin()
	{
		return iterator(_head->_next);
	}
	iterator end()
	{
		return iterator(_head);
	}
	typedef ListIterator<T, const T&,const T*> const_iterator;
	const_iterator begin()const
	{
		return const_iterator(_head->_next);
	}
	const_iterator end()const
	{
		return const_iterator(_head);
	}
	void empty_init()
	{
		_head = new Node();
		_head->_next = _head;
		_head->_prev = _head;
	}
	list()
	{
		empty_init();
	}
	list(const list<T>& il)
	{
		empty_init();
		for (const auto& e : il)
		{
			push_back(e);
		}
	}
	list(initializer_list<T> il)
	{
		empty_init();
		for (const auto& e : il)
		{
			push_back(il);
		}
	}

	list<T>& operator=(const list<T> lt)
	{
		swap(_head, lt._head);
		return *this;
	}
	void clear()
	{
		auto it = begin();
		while (it != end())
		{
			it = erase(it);
		}
	}
	~list()
	{
		clear();
		delete _head;
		_head = nullptr;
	}

	iterator insert(iterator pos, const T& x)
	{
		Node* newnode = new Node(x);
		Node* cur = pos._node;
		Node* prev = cur->_prev;

		newnode->_next = cur;
		newnode->_prev = prev;
		prev->_next = newnode;
		cur->_prev = newnode;
		return iterator(newnode);
	}
	iterator erase(iterator pos)
	{
		Node* cur = pos._node;
		Node* prev = cur->_prev;
		Node* next = cur->_next;

		prev->_next = next;
		next->_prev = prev;
		delete cur;
		return iterator(next);
	}

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

	void push_back(const T& x)
	{
		insert(begin(), x);
	}
	void push_front(const T& x)
	{
		insert(end, x);
	}
private:
	Node* _head;
};

小结

本篇博客介绍了list的使用和模拟实现，通过对list的模拟实现，我们介绍了迭代器失效的问题以及迭代器的封装。

感谢您在百忙之中能够看完本篇文章，如果本篇文章对您有所帮助的话，希望您能留下点赞评论加关注，您的支持就是我创作的最大动力。