【C++笔记】C++ list类模拟实现

一、初始化和各种构造

C++的list类使用的模型是带头双向循环链表：

所以今天我们也是基于这个模型来实现一个list。

1.1、准备工作

在定义链表类之前，我们先要定义链表的节点类：

// list节点类
template <class T>
struct ListNode {
	// 构造函数
	ListNode(const T& val = T()) {
		_val = val;
		_pre = nullptr;
		_next = nullptr;
	}
	T _val;
	ListNode<T>* _pre; // 指向前一个节点
	ListNode<T>* _next; // 指向后一个节点
};
1
2
3
4
5
6
7
8
9
10
11
12
13

然后就是list类了：

template <class T>
class list {
	typedef ListNode<T> Node;
public :
private :
	Node* _head;
	size_t _size;
};
1
2
3
4
5
6
7
8

因为我们所写的是带头链表，所以在list类里就只需要顶一个头节点和size即可。

1.2、各种构造和析构

有了链表类，我们就要先来实现各种构造和析构了。
空初始化
但在开始实现构造之前，我们必须先得实现一个“空初始化”，因为我们设计的链表是带头结点的，并且这个头结点是不算入有效数据的。
所以我们要先将这个头结点申请出来，这也就是空初始化要做的事情：

// 空初始化
void emptyInit() {
	// 开辟一个头节点
	Node* newHead = new Node();
	_head = newHead;
	_head->_next = _head;
	_head->_pre = _head;
	_size = 0;
}
1
2
3
4
5
6
7
8
9

无参构造
无参构造的作用就是只创建一个链表对象，其他什么都不做，所以我们直接调用空初始化即可：

// 无参构造函数
list() {
	emptyInit();
}
1
2
3
4

以n个相同值构造
这个其实我们可以直接复用后面写的尾插，直接一直追加即可。
在正式插入之前，我们还是先要处理头节点，即调用空初始化：

// 以n个相同值构造
list(int n, const T& val = T()) {
	// 先空初始化
	emptyInit();
	//  插入
	for (int i = 0; i < n; i++) {
		push_back(val);
	}
}
1
2
3
4
5
6
7
8
9

以一段迭代器区间初构造
这个其实也和其他容器是一样的：

// 以一段迭代器区间初始化
template <class Iterator>
list(Iterator first, Iterator last) {
	// 先空初始化
	emptyInit();
	while (first != last) {
		push_back(*first);
		first++;
	}
}
1
2
3
4
5
6
7
8
9
10

拷贝构造
对于其他容器而言，链表的拷贝构造我想是最简单的了，因为它的空间本身就不连续，也就不必申请新的一段连续的空间再拷贝数据了。
其实我们直接将两个链表的哨兵位节点交换即可。
所以我们可以先实现一个交换函数：

// 交换
void Swap(list<T>& lt) {
	swap(_head, lt._head);
	swap(_size, lt._size);
}
1
2
3
4
5

然后我们在构造函数中创建一个临时对象，再将这个对象与我们要构造的对象交换即可：

// 拷贝构造
list(const list<T>& lt) {
	// 先空初始化
	emptyInit();

	// 创建一个临时对象
	list<T> temp(lt.begin(), lt.end());
	// 交换即可
	Swap(temp);
}
1
2
3
4
5
6
7
8
9
10

析构函数
析构函数，我这里并不想使用以前的方法依次删除节点，我这里打算复用其他的函数。
我们先得要实现一个清数据的函数——只清理有效数据，不清理哨兵头节点：

// 清除数据
void clear() {
	iterator it = begin();
	while (it != end()) {
		it = erase(it);
	}
}
1
2
3
4
5
6
7

这里用到的迭代器后面后讲到。

然后在析构函数中，我们只需要调用一次clear然后再将哨兵头节点释放掉即可：

// 析构函数
~list() {
	clear();
	delete _head;
}
1
2
3
4
5

二、插入和删除

2.1、插入

尾插
尾插其实就和我们以前写的带头双向循环链表一模一样了：

	// 尾插
void push_back(const T& val) {
	Node* tail = _head->_pre;
	// 申请一个新节点
	Node* newNode = new Node(val);
	tail->_next = newNode;
	newNode->_pre = tail;
	newNode->_next = _head;
	_head->_pre = newNode;
	_size++;
}
1
2
3
4
5
6
7
8
9
10
11

头插

	// 头插
	void push_front(const T& val) {
		// 申请新的头节点
		Node* newHead = new Node(val);
		// 原来的头节点
		Node* head = _head->_next;
		_head->_next = newHead;
		newHead->_pre = _head;
		newHead->_next = head;
		head->_pre = newHead;
		_size++;
	}
1
2
3
4
5
6
7
8
9
10
11
12

随机插入
在pos位置之前插入一个新节点，并返回新节点的位置：

iterator insert(iterator pos, const T& val) {
	// 申请一个新节点
	Node* newNode = new Node(val);
	Node* Pre = pos._node->_pre;
	Node* Next = pos._node;
	Pre->_next = newNode;
	newNode->_pre = Pre;
	newNode->_next = Next;
	Next->_pre = newNode;
	_size++;
	return newNode;
}
1
2
3
4
5
6
7
8
9
10
11
12

2.2、删除

尾删

// 尾删
void pop_back() {
	assert(!empty());
	Node* tail = _head->_pre;
	Node* Pre = tail->_pre;
	// 释放尾节点
	delete tail;
	Pre->_next = _head;
	_head->_pre = Pre;
	_size--;
}
1
2
3
4
5
6
7
8
9
10
11

头删

// 头删
void pop_front() {
	assert(!empty());
	// 旧的头节点
	Node* head = _head->_next;
	// 新的头节点
	Node* newHead = head->_next;
	// 释放旧的头节点
	delete head;
	_head->_next = newHead;
	newHead->_pre = _head;
	_size--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

随机删除
删除pos位置的节点，并返回被删除节点的下一个节点的位置：

iterator erase(iterator pos) {
	assert(!empty());
	Node* cur = pos._node;
	Node* Pre = cur->_pre;
	Node* Next = cur->_next;
	// 释放原来的节点
	delete cur;
	Pre->_next = Next;
	Next->_pre = Pre;
	_size--;
	return Next;
}
1
2
3
4
5
6
7
8
9
10
11
12

三、迭代器

因为链表的哨兵头节点是私有的，并且链表也不支持随机访问(不能实现方括号重载)，所以我们遍历链表的方式就只剩一种——迭代器。

3.1、正向迭代器

因为链表的空间不是连续的，所以我们就不能直接用原生指针来模拟了。我们需要对原生指针再进行封装。
并且迭代器的++和–也要通过运算符重载的方式达到：

// list迭代器类
template <class T, class ref, class ptr>
struct ListIterator {
	typedef ListNode<T> Node;
	typedef ListIterator<T, ref, ptr> iterator;
public :
	// 构造函数
	ListIterator(Node* node = nullptr) {
		_node = node;
	}

	// 拷贝构造
	ListIterator(const iterator& it) {
		_node = it._node;
	}

	// 星号解引用运算符重载
	ref operator*() {
		return _node->_val;
	}

	// 箭头解引用运算符重载
	ptr operator->() {
		return &_node->_val;
	}
	// 前置++运算符重载
	iterator& operator++() {
		_node = _node->_next;
		return *this;
	}

	// 后置++运算符重载
	iterator& operator++(int) {
		iterator* temp = new iterator(this->_node);
		++(*this);
		return *temp;
	}

	

	// 前置--运算符重载
	iterator& operator--() {
		_node = _node->_pre;
		return *this;
	}

	// 后置--运算符重载
	iterator& operator--(int) {
		iterator* temp = new iterator(this->_node);
		--(*this);
		return *temp;
	}

	// 等于运算符重载
	bool operator==(const iterator& it) {
		return _node == it._node;
	}

	// 不等于运算符重载
	bool operator!=(const iterator& it) {
		return !((*this) == it);
	}
public :
	Node* _node;
};
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
64
65

3.2、反向迭代器

实现反向迭代器我们其实只需要适配正向迭代器即可，因为反向迭代器的逻辑几乎和正向迭代器是一样的，只是在对反向迭代器进行++和–的时候需要和正向迭代器相反：

// list反向迭代器类
template <class Iterator, class Ref, class Ptr>
struct Reverse_iterator
{
	Iterator _it;
	typedef Reverse_iterator<Itertor, Ref, Ptr> Self;

	Reverse_iterator(Iterator it)
		: _it(it)
	{}

	Ref operator*()
	{
		Iterator tmp = _it;
		return *(--tmp);
	}

	Ptr operator->()
	{
		return &(operator*());
	}

	Self& operator++()
	{
		--_it;
		return *this;
	}

	Self& operator--()
	{
		++_it;
		return *this;
	}

	bool operator!=(const Self& s)
	{
		return _it != s._it;
	}
};
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

3.3、提供迭代器位置

// 正向const迭代器起始位置
const_iterator begin() const
{
	return const_iterator(_head->_next);
}
// 正向const迭代器结束位置
const_iterator end() const
{
	return const_iterator(_head);
}
 // 正向迭代器起始位置
iterator begin()
{
	return iterator(_head->_next);
}
 // 正向迭代器结束位置
iterator end()
{
	return iterator(_head);
}
 // 反向const迭代器起始位置
const_reverse_iterator rbegin() const
{
	return const_reverse_iterator(end());
}
 // 反向const迭代器结束位置
const_reverse_iterator rend() const
{
	return const_reverse_iterator(begin());
}
 // 反向迭代器起始位置
reverse_iterator rbegin()
{
	return reverse_iterator(end());
}
 // 反向迭代器结束位置
reverse_iterator rend()
{
	return reverse_iterator(begin());
}
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

四、其他一些接口

4.1、链表的长度和判空

// 返回长度
	size_t size() {
		return _size;
	}
	// 判断是否为空
	bool empty() {
		return _size == 0;
	}
1
2
3
4
5
6
7
8

4.2、返回链表的头尾结点

// 返回链表的头一个节点(第一个有效节点的值)
	T& front() {
		assert(!empty());
		return _head->_next->_val;
	}

	// const版本的头节点
	const T& front() const {
		assert(!empty());
		return _head->_next->_val;
	}

	// 返回链表的尾节点(最后一个有效节点的值)
	T& back() {
		assert(!empty());
		return _head->_pre->_val;
	}

	// const版本尾节点
	const T& back() const {
		assert(!empty());
		return _head->_pre->_val;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23