【C++】list的模拟实现

个人主页<—请点击
C++专栏<—请点击

一、list的基础框架确立

我们要实现的list的结构是带头结点的双向循环链表，和我们STL库中的一致。

如图，这样的话，我们的节点就需要存储三个变量，其中一个_data存储数据，另外_prev存储前一个节点的地址，_next存储后一个节点的地址。

而在STL库中的list模板类，它可以存储string等类型，所以结点的定义就需要使用模板进行实现。

接下来就是迭代器该如何实现，链表部分的迭代器就不能使用原生指针Node*（结点*）进行实现了，因为*iterator可不是存储的数据了，我们需要进行重载，而且想要完成链表的各个结点的遍历，靠原生指针++是行不通的，因为各个结点之间的地址是不确定的。所以考虑到种种因素，我们的迭代器部分的实现需要单独实现一个迭代器类，链表的功能不再是原生指针能够胜任的了。

list的基本框架实现也需要使用模板类，然后它的成员变量就是结点* _head，和迭代器中的成员变量类型相同。

上图就是我们list的模拟实现所需要的三件套。这里再次对迭代器进行总结：迭代器使用Node*无法达到预期行为，所以使用类封装Node*，重载运算符，达到控制迭代器的行为的目的。

注意：由于我们的list和库中的list名称相同，为了不产生冲突问题，我把它们都放在了一个命名空间namespace LI中。

二、模拟实现

2.1 结点类的构造函数

我们在上面定义出了结点类的成员变量，我们还差一个结点的构造函数。构造函数也比较容易编写，主要的点在于我们的缺省值不能在给出具体值，因为我们编写的是模板类，所以我们可以使用匿名对象T()。

template<class T>
struct list_node
{
	T _data;
	list_node<T>* _prev;
	list_node<T>* _next;

	list_node(const T& x = T())
		:_data(x)
		,_prev(nullptr)
		,_next(nullptr)
	{ }
};

如此，我们就把结点的模板类给完善好了。

2.2 迭代器类和list类中的构造函数

迭代器类中的需求是，我里面的_node指针需要指向需求的结点，仅此而已，所以我们需求的也就是将你给我的指针赋值给我迭代器类中的_node指针即可，这样我就能找到相关结点。

template<class T>
struct __list_iterator
{
	typedef list_node<T> Node;
	Node* _node;

	__list_iterator(Node* node)
		:_node(node)
	{ }
};

list类中是在刚开始构造的时候，list中只有一个结点，就是头结点，所以我们需要申请一个结点给_head，并且它的_prev和_next指针都指向它本身。

template<class T>
class list
{
public:
	typedef list_node<T> Node;
	typedef __list_iterator<T> iterator;

	list()
	{
		_head = new Node;
		_head->_next = _head;
		_head->_prev = _head;
	}
private:
	Node* _head;
};

2.3 push_back和范围for

在库中，我们拿到list想到的就是增删查改和遍历嘛，所以我们就先实现这两个功能。

push_back：
我们的尾插就比较简单了，就是申请一个结点，然后让新节点的_next指针指向头结点，_prev指针指向原来的尾结点，再更改一下头结点和原来尾节点的相关指针就好了。

void push_back(const T& x)
{
	//申请新节点
	Node* newnode = new Node(x);
	//储存旧的尾结点
	Node* tail = _head->_prev;

	//_head tail newnode
	tail->_next = newnode;
	newnode->_prev = tail;
	newnode->_next = _head;
	_head->_prev = newnode;
}

我们现在已经有了push_back，所以我们可以尝试把测试点写出来，针对测试点的需求，我们也可以更好的完善范围for。

void test1()
{
	LI::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	LI::list<int>::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << endl;
		++it;
	}
	cout << endl;
}

这是尝试写出来的测试点1，其中我们尾插了4个数据，并且想使用迭代器遍历，如今我们的begin和end没有实现，解引用it和++it也都不能满足要求，因为不再是原生指针了。

首先的问题就是begin和end要写在哪里？分析如下，它们需要获取链表中具体的结点信息，应当实现在list类中，因为只有list类才知道它实例化后的对象中的实际结点信息，迭代器类只能通过list类实例化对象获取具体结点的地址。

那在分析具体函数，其中链表为空时就是只剩下一个头结点，所以begin函数应当返回头结点的_next指针，因此end函数我们也就知道了，它应该返回头结点，因为end指向的是尾部的下一个位置，这样符合左闭右开。

iterator begin()
{
	return iterator(_head->_next);
}

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

注意：iterator已经升级为类了，不能再单纯的返回。

解引用和++部分都是针对迭代器，所以应该在迭代器类中重载它们。解引用重载时就返回结点的数据，重载前置++时就返回结点的下一个指针。

operator*：

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

operator++：

__list_iterator<T>& operator++()
{
	_node = _node->_next;
	return *this;
}

现在我们依旧无法测试，漏掉了!=，所以我们还要重载它。其内部就是比较两个结点是否相同。
operator!=：

bool operator!=(const __list_iterator<T>& it)
{
	return _node != it._node;
}

好了，现在就可以进行测试了：

我们实现的代码没有问题，此时，我们已经满足了使用范围for的所有条件，我们可以使用范围for了。

测试点：

void test2()
{
	LI::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	for (auto& it : lt)
	{
		cout << it << endl;
	}
	cout << endl;
}

没有问题。

2.4 const_iterator

我们已经实现了普通迭代器，我们还需要实现一个const迭代器，这样普通链表调用普通迭代器，const链表调用const迭代器。

我们在之前进行模拟实现的时候，都是使用原生指针，所以直接typedef const T* const_iterator即可，以vector而言，这样就能保证const迭代器指向的内容不能被修改，因为T*被const修饰了，而const迭代器可以被修改，所以可以使用++操作。

有人有这样的想法，简单嘛，不是实现了普通迭代器嘛，直接typedef const 普通迭代器 const_iterator就可以了呀，那这样一来迭代器本身都不能修改了，还如何++呢，所以它行不 通。

const_iterator的需求是它指向的内容不能被修改，所以关键点在于operator*函数，它的返回值不能再是T&，而需要是const T&，这样const_iterator指向的内容就不能被修改了，而它本身依旧能够修改，所以可以使用++。

知道关键点之后，就来到了另一个问题，我们不能在原来迭代器类的基础上直接修改，如果直接修改了，我们的iterator指向的内容也就不能修改了，所以这就让我们不得不重新定义一个迭代器模板类，这样才能解决这个问题。

template<class T>
struct __list_const_iterator
{
	typedef list_node<T> Node;
	Node* _node;

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

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

	__list_const_iterator<T>& operator++()
	{
		_node = _node->_next;
		return *this;
	}

	bool operator!=(const __list_const_iterator<T>& it)
	{
		return _node != it._node;
	}
};

这样我们的const迭代器才算弄好了，但我们发现我们相比于普通迭代器类只修改了operator*函数，重复的部分太多了，所以我们等下会做出改进。

2.5 const begin、const end及合并迭代器类

const begin、const end：

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

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

测试点3：

template<class T>
void print(const LI::list<T>& lt)
{
	//类模板此时未实例化，编译器分不清 const_iterator 是嵌套内类还是静态成员变量
	// 所以要加上 typename 告诉编译器它是类型
	//typename LI::list<T>::const_iterator it = lt.begin();
	auto it = lt.begin();//等价于上面
	while (it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
}

void test3()
{
	LI::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

	print(lt);
}

这里我又实现了一个打印函数，让它接受const list<T>。

此时我们的迭代器的两种类型就解决了，但我们发现，这两个迭代器类重复的地方太多了，只有一处地方不一样，简直就是一个模子生成的，诶，模子！我们定义迭代器类不就是模板类吗，所以我们可以在模板中再添加一个模板参数，让它们实例化的时候一个传递T&，一个传递const T&不就好了。

合并的模板类：

template<class T,class Ref>
struct __list_iterator
{
	typedef list_node<T> Node;
	Node* _node;

	typedef __list_iterator<T, Ref> Self;

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

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

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

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

这里我嫌改动太麻烦，所以进行了typedef __list_iterator<T, Ref> Self;。


运行依旧符合预期，至此我们的迭代器最大的问题就解决了。

2.6 operator->

我们知道除了使用*it的方式获取数据我们还有it->的方式，当它的结点结构比较特殊时，我们就会用到->，所以我们也要进行重载。既然是要重载到迭代器类中的，而迭代器分为两种，所以它和operator*一样也需要重载两种类型，一个返回T*,一个返回const T*，所以我们需要再次增加一个模板参数控制它。

operator->

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

看着有些奇怪，其实就是取出结点数据的结构_data的地址。

迭代器类：

template<class T, class Ref, class Ptr>
struct __list_iterator
{
	typedef list_node<T> Node;
	typedef __list_iterator<T, Ref, Ptr> Self;
	Node* _node;

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

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

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

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

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

测试点4：

struct pos
{
	int _x;
	int _y;
	pos(int x = 0, int y = 0)
		:_x(x)
		,_y(y)
	{ }
};

void test4()
{
	LI::list<pos> lt;
	lt.push_back({ 1,1 });
	//{1，1}这样传，用到了隐式类型转换
	lt.push_back({ 2,2 });
	lt.push_back({ 3,3 });
	lt.push_back({ 4,4 });

	auto it = lt.begin();
	while (it != lt.end())
	{
		cout << it->_x << " " << it->_y << endl;
		//it->_x等价于it.operator->()->_x 
		++it;
	}
}

我定义了一个结构体来使结点复杂，这样就有了使用->的场景。

注意：在我们看来，不应该使用两个->吗，一个->调用函数，另一个->指向结点存储数据的结构_data中的成员，但是为了可读性编译器就省略了一个->。

符合我们的预期。

2.7 迭代器类的完善

后置++：

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;
}

operator==：

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

2.8 insert和erase

insert：


我们只实现第一个，insert的实现内部就是申请一个结点，然后给它要给的值，在进行插入即可。

它的返回值是指向最新插入的结点的迭代器。

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

	//pre newnode cur
	pre->_next = newnode;
	newnode->_prev = pre;
	newnode->_next = cur;
	cur->_prev = newnode;

	return iterator(newnode);
}

测试点5：

void test5()
{
	LI::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	print(lt);

	lt.insert(lt.begin(), 81);
	lt.insert(lt.end(), 10);
	print(lt);
}

erase：


我们只实现第一种。它的返回值指向的是原结点的下一个结点的位置。

iterator erase(iterator pos)
{
	Node* cur = pos._node;
	Node* pre = cur->_prev;
	Node* next = cur->_next;

	//pre cur next
	pre->_next = next;
	next->_prev = pre;
	delete cur;

	return iterator(next);
}

测试点6：

void test6()
{
	LI::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.insert(lt.begin(), 81);
	lt.insert(lt.end(), 10);
	print(lt);
	lt.erase(++lt.begin());
	lt.erase(--lt.end());
	print(lt);
}

注意：永远不要对end()迭代器调用erase()，会导致程序错误。

2.9 尾插尾删和头插头删

push_back()：
我们前面实现过了push_back()，但我们实现了insert所以我们可以再改进一下。

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

pop_back()：

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

push_front()：

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

pop_front()：

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

测试点7：

void test7()
{
	LI::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	print(lt);
	lt.push_back(10);
	lt.push_front(53);
	print(lt);
	lt.pop_front();
	lt.pop_back();
	print(lt);
}

2.10 拷贝构造和赋值重载

由于这里会频繁用到构造函数里面的语句：

_head = new Node;
_head->_next = _head;
_head->_prev = _head;

所以我把它们封装在了empty_init中。

拷贝构造：

list(const list<T>& lt)
{
	empty_init();
	for (auto& x : lt)
	{
		push_back(x);
	}
}

测试点8：

void test8()
{
	LI::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	print(lt);
	LI::list<int> lt1(lt);
	print(lt1);
}

赋值重载：
这里将会使用现代写法，就是将目标和新生成的list类对象交换使它变成自己的。
swap：

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

operator=：

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

这里返回引用的目的是支持连续赋值操作。

测试点9：

void test9()
{
	LI::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	print(lt);
	LI::list<int> lt1;
	lt1 = lt;
	print(lt1);
}

2.11 initializer_list构造

list(initializer_list<T> il)
{
	empty_init();
	for (auto& e : il)
	{
		push_back(e);
	}
}

测试点10：

void test10()
{
	LI::list<int> lt = { 98,1,2,3,4,99 };
	print(lt);
}

2.12 析构函数和clear函数

clear()：
清空之后链表就会只剩下头结点。

void clear()
{
	auto it = begin();
	while (it != end())
	{
		it = erase(it);
	}
}

~list()：

~list()
{
	clear();
	delete _head;
	_head = nullptr;
}

再次执行代码，没有发生报错。

2.13 size函数

为了处理计数问题，我们可以进行一个一个遍历计数操作，但这样它的时间复杂度就会变成O(n)，这不是我们想要的。

还有一个很好的解决方法就是定义一个成员变量_size来进行计数，进行插入删除时就修改它，而且我们的插入删除全是依靠insert和erase完成的，所以我们将++_size放入insert中，--_size放入erase中就可以了。

额外修改的点：

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

size()：

size_t size() const
{
	return _size;
}

测试点11：

void test11()
{
	LI::list<int> lt = { 98,1,2,3,4,998,666,777,256,99 };
	print(lt);
	cout << lt.size();
}

至此，我们list的模拟实现就完成了。

总结：
以上就是本期博客分享的全部内容啦！如果觉得文章还不错的话可以三连支持一下，你的支持就是我前进最大的动力！
技术的探索永无止境! 道阻且长，行则将至！后续我会给大家带来更多优质博客内容，欢迎关注我的CSDN账号，我们一同成长！
(～￣▽￣)～