【STL】list的模拟实现

目录

1.list的介绍及使用

1.1 list的介绍

1.2 list的使用

1.2.1 list的构造

1.2.2 list iterator的使用

1.2.3 capacity

1.2.4 list element access

1.2.5 list modifiers 

1.2.6 list的迭代器失效问题

2.list的模拟实现

2.1 list的结构设计

2.2 list的结点设计

2.3 list的迭代器

关于三个模板参数的解释：

operator++前置

operator--前置

operator++后置

operator--后置

operator*

operator->

operator==

operator!=

2.4 list

 list的基本框架

begin

end

insert

erase

push_back

push_front

pop_back

pop_front

3. list和vector的区别 

---

1.list的介绍及使用

1.1 list的介绍

1）list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

2）list的底层是双向链表结构。

3）list和forward_list非常相似，最主要的不同在于forward_list是单链表，只能朝前迭代，以让其更简单高效。

4）与其他的序列容器相比(array, vector, deque)，list通常在任意位置进行插入、删除元素的执行效率更高。

5）与其他序列容器相比，list和forward_list的最大缺陷是不支持随机访问。另外list还需要额外的空间来保存前驱和后继指针。

1.2 list的使用

list的接口比较多，下面只列举一些常见的重要接口。

1.2.1 list的构造

代码演示：

list<int> first(4, 100);//用4个100来构造list
list<int> second();     //构造空的list
list<int> third(first); //拷贝构造函数，用first来构造third
list<int> fourth(first.begin(), first.end());//用区间来构造fourth

1.2.2 list iterator的使用

正向迭代器和反向迭代器的区别

1）begin()和end()是正向迭代器，从容器的第一个元素开始，遍历到容器的最后一个元素，对正向迭代器进行++操作，迭代器指向下一个元素

2）rbegin()和rend()为反向迭代器，从容器的最后一个元素开始，遍历到容器的第一个元素，对反向迭代器进行++操作，迭代器指向上一个元素

代码演示：

正向迭代器

#include 
#include 
using namespace std;
 
int main()
{
	int arr[] = { 1,2,3,4,5 };
	list<int> lt(arr, arr + 5);
	list<int>::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	return 0;
}

反向迭代器

#include 
#include 
using namespace std;
 
int main()
{
	int arr[] = { 1,2,3,4,5 };
	list<int> lt(arr, arr + 5);
	list<int>::reverse_iterator rit = lt.rbegin();
	while (rit != lt.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;
	return 0;
}

 

1.2.3 capacity

1.2.4 list element access

代码演示：

#include 
#include 
using namespace std;
 
int main()
{
	int arr[] = { 1,2,3,4,5 };
	list<int> lt(arr, arr + 5);
	cout << lt.front() << endl;
	cout << lt.back() << endl;
	return 0;
}

1.2.5 list modifiers 

以上这些操作这里就不演示了，需要时可以参考文档~

1.2.6 list的迭代器失效问题

迭代器失效，归根结底就是野指针问题，也就是说迭代器指向的空间不再合法。因此我们可以很容易联想到什么情况下会出现迭代器实现的问题——如果容器的底层空间发生改变，就可能会导致迭代器失效。例如vector的扩容行为，就可能导致迭代器失效。在list中，插入操作是不会导致迭代器失效的，只有在删除的时候才会导致迭代器失效。原因在于该节点被删除了，迭代器所指向的空间不属于list了，但其他的迭代器不受影响。下面演示一下这种情况。

#include 
#include 
using namespace std;
 
int main()
{
	int arr[] = { 1,2,3,4,5 };
	list<int> lt(arr, arr + 5);
	list<int>::iterator it = lt.begin();
	while (it != lt.end())
	{
		lt.erase(it);
		it++;
	}
	return 0;
}

删除了it对应的结点后，it就变成了野指针，指向的空间已经不合法了，因此导致迭代器失效。

正确的做法：

#include 
#include 
using namespace std;
 
int main()
{
	int arr[] = { 1,2,3,4,5 };
	list<int> lt(arr, arr + 5);
	list<int>::iterator it = lt.begin();
	while (it != lt.end())
	{
		lt.erase(it++);// 等价于it = lt.erase(it);
	}
	return 0;
}

这里解释一下，list中erase的返回值是被删除元素的下一个元素的迭代器，到了list的模拟实现部分就更加明白了。

2.list的模拟实现

list是一个双向循环链表，所以只需要一个指针就可以完整的表现整个链表。在list的模拟实现中，最精华部分在于迭代器的模拟实现。至于要不要带上哨兵位的头结点，先明确这样一个规范，在传迭代器区间时，采用的都是“左闭右开”的方式——这是list的一个规范，如果带上哨兵位的头结点，我们将整个链表作为迭代区间时，就很好的符合规范了。所以，list是要带上哨兵位的头结点的。

2.1 list的结构设计

设计过list的人都知道，list本身和list的节点是不同的结构，需要分开设计。list结点的设计需要一个类，list本身需要一个类，list的迭代器需要一个类，所以一共需要三个类。

2.2 list的结点设计

以下是list结点的结构：

	template <class T>
	struct __list_node
	{
		__list_node* prev;
		__list_node* next;
		T data;
 
		__list_node(const T& val = T()) : prev(nullptr), next(nullptr), data(val){}
	};

这里提供构造函数是为了创建节点的时候方便，直接new。

2.3 list的迭代器

迭代器，作为最精华的部分。list不能再像vector一样以普通指针作为迭代器，因为list的结点在空间上是不连续的，当结点Node++是，并不能满足我们的需求，Node++后指向的位置未必就是我们想要的，我们的需要的是：Node++后指向它的下一个结点next。所以这里就不得不用一个类来对普通指针进行封装，通过运算符重载来达到我们的需求。

迭代器的主要结构如下：

template <class T, class Ref, class Ptr>
	struct ListIterator
	{
		typedef __list_node Node;
		typedef ListIterator Self;
		Node* _node;
		ListIterator(Node* node) :_node(node) {}
        //……
	};

首先，迭代器这个类里面是肯定要有一个指向结点的指针的，这样才能维护链表。最大的以后可能是：为什么需要三个模板参数？

关于三个模板参数的解释：

 如果只考虑普通迭代器，一个模板参数就够了，但是考虑到常量迭代器，也就是const迭代器，需要加上这两个模板参数——Ref(引用)、Ptr(指针)。首先理解一下const的迭代器的功能——只能遍历链表，但不能修改链表的内容。有了这个共识之后，我们再谈引入的原因。

上面已经说到引入Ref和Ptr的原因——为了适配const迭代器。那么有没有其他方法来解决这一问题？答案是有的，无非再写一个只需要一个模板参数的迭代器类，然后修改返回值为const T&和const T*(原先为T& 、T*)。请看代码：

 
	template <class T>
	struct ListIterator
	{
		typedef __list_node Node;
		typedef ListIterator Self;
		Node* _node;
		ListIterator(Node* node) :_node(node) {}
 
		T& operator*()
		{
			return _node->data;
		}
		T* operator->()
		{
			return &_node->data;
		}
		//……
 
	};

再对比const迭代器的代码：

template <class T>
	struct ListIterator
	{
		typedef __list_node Node;
		typedef ListIterator Self;
		Node* _node;
		ListIterator(Node* node) :_node(node) {}
 
		const T& operator*()
		{
			return _node->data;
		}
		const T* operator->()
		{
			return &_node->data;
		}
		//……
	};

 只是返回值变了，其余一样，但也可以行得通。但是两份几乎完全一样的代码，SGI STL的大佬嫌麻烦，所以就并没有采用这种做法，而是添加了两个模板参数Ref、Ptr（这里我参考的是《STL源码剖析》一书）。好了，为什么有三个模板参数这一问题解释完毕。下面说说它为什么可以做到。以下是const迭代器：

typedef ListIterator const_iterator;

 就是在模板实例化时也实例化出一份const版本的，也就是说，生成了两个迭代器类，一个是普通迭代器类，另一个是常量迭代器类。从本质上来看，我们只是把活交给了编译器干，和我们自己再写一个const迭代器的类无本质区别。

operator++前置

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

因为迭代器里就有指向链表节点的指针_node，所以要实现指向下一个结点的功能很简单，更新一下_node就可以。又因为考虑到可能会有连续赋值，所以返回了当前结点的迭代器。

operator--前置

Self& operator--()
{
    _node = _node->prev;
   	return *this;
}

operator++后置

Self operator++(int)
{
	Self tmp = *this;
	_node = _node->next;
	return tmp;
}

后置++，先使用再++，返回的是++之前的内容。 

operator--后置

Self operator--(int)
{
	Self tmp = *this;
	_node = _node->prev;
	return tmp;
}

后置--，先使用再--，返回的是--之前的内容。 

operator*

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

 解引用操作，返回的是数据的引用。

operator->

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

返回数据的地址。 

operator==

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

operator!=

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

2.4 list

 list的基本框架

template <class T>
	class list
	{
		typedef __list_node Node;
	public:
		typedef ListIterator iterator;
		typedef ListIteratorconst T&, const T*> const_iterator;
 
		//哨兵位
		list()
		{
			_head = new Node();
			_head->prev = _head;
			_head->next = _head;
		}
 
		//……
 
	protected:
		Node* _head;
	};

begin

哨兵位头结点的下一个结点。

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

end

哨兵位头结点本身就是。

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

insert

在指定位置之前插入数据。因为传的是迭代器，迭代器里有指向链表节点的指针，所以插入操作就只需把新节点正确的连接上去就好。

iterator insert(iterator pos, const T& val)
{
	Node* cur = pos._node;
	Node* prev = cur->prev;
	Node* newnode = new Node(val);
		
	prev->next = newnode;
	newnode->prev = prev;
	cur->prev = newnode;
	newnode->next = cur;
 
	return iterator(newnode);
}

erase

删除指定结点，根据前面讲的，这里会有迭代器失效的问题，所以要返回被删除结点的下一个节点的迭代器。

iterator erase(iterator pos)
{
	assert(pos != end());
 
	Node* cur = pos._node;
	Node* prev = cur->prev;
	Node* next = cur->next;
 
	prev->next = next;
	next->prev = prev;
	delete cur;
 
	return iterator(next);
}

push_back

复用insert。

void push_back(const T& val)
{
	insert(end(), val);
}

push_front

复用insert。

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

pop_back

复用erase。

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

pop_front

复用erase。

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

3. list和vector的区别 

---

完~