【C++】list模拟实现&list迭代器失效问题

一，list模拟实现

在上节我们熟悉了list的底层结构和各个接口的含义后，下面我们来对list的主要接口进行模拟实现

1. list的主要框架接口模拟

list的底层是双向带头循环链表，所以我们先写一个节点的类，这个节点类也是一个类模板，由给定的数据类型生成相应的类

这个节点类可以写成结构体，用结构体是为了方便访问数据,不用单独写取数据接口

//list的节点
template<class T>
struct ListNode {
	ListNode* _prev;
	ListNode* _next;
	T _data;
	ListNode(const T& t = T())
		:_prev(nullptr)
		,_next(nullptr)
		,_data(t)
	{}

};
1
2
3
4
5
6
7
8
9
10
11
12
13

其次我们写list的基本框架，其成员变量我们可以用节点声明一个头结点，根据头结点的链接关系我们就可以知道其list存放的内容

template<class T>
class mylist {
	typedef ListNode<T> Node;//方便阅读
public:
	//....
private:
	Node* _head;
};

1
2
3
4
5
6
7
8
9

2. list构造&拷贝构造&析构

list的构造有无参的构造，用n个值初始化构造，迭代器区间构造

---

我们这里实现无参的构造，

void list_init() {
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;
}

mylist() {
	list_init();
}
1
2
3
4
5
6
7
8
9

初始化时其头指针和外指针指向自己：

---

现在我们来实现拷贝构造

拷贝构造的实现我们和vector一样依次去插入即可。

mylist(mylist<T>& ml) {
	list_init();
	for (const auto e : ml) {
		push_back(e);
	}
}
1
2
3
4
5
6

---

重载operator=，这里我们可以转变一下思路，当传入一个list对象时，发生了拷贝构造，用拷贝构造的这个对象和当前要调用operator=的对象进行交换，再返回交换后的这个对象。

mylist& operator=(mylist lt)//在类中时可以省略模板参数
	swap(lt);
	return *this;
}
1
2
3
4

3. list迭代器

由于list的底层空间的不连续性，所以不能像string和vector一样直接用原生指针，我们要对其进行封装，使其可以像指针那样可以进行++或者–那样去使用。

template<class T>
struct List_Iterator {
	typedef ListNode<T> Node;
	typedef List_Iterator<T> self;
	Node* _node;
	//..
};
1
2
3
4
5
6
7

对于迭代器的构造函数，比较简单，可写可不写

template<class T>
struct List_Iterator {
	typedef ListNode<T> Node;
	typedef List_Iterator<T> self;
	Node* _node;
	
	List_Iterator(Node* n)
		:_node(n)
	{}
	//..
};
1
2
3
4
5
6
7
8
9
10
11

3.1 普通迭代器

我们先实现普通迭代器
既然要对这个类进行封装，那么就是为了让其可以进行++或者–等运算，所以我们需要对这些操作进行重载

---

重载operator++，有前置++和后置++，

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

//后置++
self operator++(int) {
	self tmp(*this);//拷贝构造
	_node = _node->_next;
	return tmp;
}
1
2
3
4
5
6
7
8
9
10
11
12

注：拷贝构造我们后面会实现

---

重载operator--和operator++类似，我们直接上代码

//前置--
self& operator--() {
	_node = _node->_prev;
	return *this;
}
//后置--
self operator--(int) {
	self tmp(*this);
	_node = _node->_prev;
	return tmp;
}
1
2
3
4
5
6
7
8
9
10
11

---

重载operator->，这是因为当list中存储的是其他结构体时，可以通过 it->_data 来直接访问其内容。

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

这里来举个具体的场景，看下面的代码：

struct Exp {
	int _a1 = 1;
	int _a2 = 2;

	Exp(int a1 = 1,int a2 = 2)
		:_a1(a1)
		,_a2(a2)
	{}
};

void test() {
	mylist<Exp> ex;
	ex.push_back(Exp(1, 2));
	mylist<Exp>::iterator it = ex.begin();
	while (it != ex.end()) {
		cout << (*it)._a1 << " " << (*it)._a2 << endl;
		cout << it->_a1 << " " << it->_a2 << endl;
		++it;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

看到这段代码，你可能会一头雾水，为啥 it->_a1可以直接访问struct的成员变量，it->不是返回的是这个结构体的指针吗？

其实这里是省略了一个->，我们可以加一句代码来解释

struct Exp {
	int _a1 = 1;
	int _a2 = 2;

	Exp(int a1 = 1,int a2 = 2)
		:_a1(a1)
		,_a2(a2)
	{}
};

void test() {
	mylist<Exp> ex;
	ex.push_back(Exp(1, 2));
	mylist<Exp>::iterator it = ex.begin();
	while (it != ex.end()) {
		cout << (*it)._a1 << " " << (*it)._a2 << endl;
		cout << it->_a1 << " " << it->_a2 << endl;
		cout << it.operator->()->_a1 << it.operator->()->_a2 << endl;
		++it;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

it->_a1中，it->取到的是结构体对象的地址，其后面应该再用一个->访问到其中的变量，但是后面的箭头被省略了，这里也是C++为了方便使用而做的处理。

---

operator*返回的是T& 减少拷贝

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

3.2 const迭代器

实现了普通迭代器，现在我们终于要实现const迭代器了，现在思考一下，普通迭代器和const迭代器区别在哪，其实const迭代器的区别就是operator*和operator->的返回值加上const。

试想一下，如果我们像vector一样只在普通迭代器前面直接加一个const。我们直接再将普通迭代器的代码拷贝一份，在operator*和operator->返回值前加上const，其余代码不变，也可以实现const迭代器。但是这样写代码难免有些冗余，如果相同的场景下要拷贝的代码有上千万行呢，难道也要拷贝吗？

所以这里我们只需在模板参数中添加两个参数Ref，Ptr。分别代表 operator和operator->的返回值，当传入的是const T或者const T&时，迭代器类会返回相应的类型。具体在list的类中再对const迭代器进行封装。

template<class T,class Ref,class Ptr>
struct List_Iterator {//
	typedef ListNode<T> Node;
	typedef List_Iterator<T,Ref,Ptr> self;
	Node* _node;

	List_Iterator(Node* n)
		:_node(n)
	{}

	//前置++
	self& operator++() {
		_node = _node->_next;
		return  *this;
	}
	//后置++
	self operator++(int) {
		self 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;
	}

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

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

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

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

};


template<class T>
class mylist {
	typedef ListNode<T> Node;//方便阅读
		
public:
	typedef List_Iterator<T,T&,T*> iterator;//写成公有,类外也可以访问
	typedef List_Iterator<T,const T&,const T*> const_iterator;
	//....
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

---

在list类中如何用用到iterator类呢，下面我们来实现一下：

iterator begin() {
	return _head->_next;//单参数的构造函数支持隐式类型转换,
}

iterator end() {
	return _head;//迭代器区间是左闭右开,end指向最后一个元素的下一个位置
}
1
2
3
4
5
6
7

4. 增删查改

list的插入删除比较简单，因为不用考虑数据挪动的问题，只要创建或者删除新的节点，改变前后节点的指针即可。

---

insert

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

	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = cur;
	cur->_prev = newnode;

	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

erase可能会造成迭代器失效的问题，具体原因和解决办法我们在下面讲解。

iterator erase(iterator pos) {
	assert(pos != end());//会发生隐式类型转换,将指针类型转换成iterator类

	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;

	prev->_next = next;
	next->_prev = prev;

	delete cur;
	cur = nullptr;

	return next;//迭代器失效,返回删除位置的下一个位置
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

push_back()和push_front和pop_back()和pop_front的实现可以直接复用insert，在末尾位置插入即可

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

void push_front(const T& t) {
	insert(begin(), t);
}
void pop_back() {
	erase(--end());
}

void pop_front() {
	erase(begin());
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

二，迭代器失效问题

1. list的迭代器失效原因

list的插入不会像vector造成迭代器失效，因为vector一旦发生扩容，其所有位置的迭代器都会失效，但是list不用扩容，当有元素插入时才创建节点，再链接到链表中。
但是list的删除会造成迭代器失效，因为删除一个节点后，这个节点的迭代器位置实际上已经不存在了，再继续使用则会出错，除非下次使用时再给其赋值。

2. 解决办法

解决办法就是让删除后返回被删除节点的下一个节点的迭代器，下面是正确的使用场景，

void Test()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array+sizeof(array)/sizeof(array[0]));
	auto it = l.begin();
	while (it != l.end())
	{
		l.erase(it++); // it = l.erase(it);
	}
}
1
2
3
4
5
6
7
8
9
10

---

list的模拟实现部分我们讲解完了，希望大家看了后会有所收获，期待更多的C++相关的知识请大家三连一波哦