STL库——list（类模拟实现）

ʕ • ᴥ • ʔ

づ♡ど

 🎉 欢迎点赞支持🎉

个人主页：励志不掉头发的内向程序员；

专栏主页：C++语言；

前言

通过我们上一章节对 list 的学习，我们已经知道了 list 的成员函数和 vector 的相似之处和不同之处，此章节我们来尝试模拟实现 list 类，比起 vector 的模拟实现会困难一些，但是大家肯定能够克服困难搞明白 list 的。接下来一起来看看吧。

一、基本框架

list是由我们一个节点一个节点相互连接所构成的逻辑层面上连续的一个容器，所以如果想要实现这一结构，我们还得多创建一个链表节点的类以供我们链表能够有节点去链接。

namespace zxl
{
    // 链表节点
	template <class T>
	struct list_node
	{
		T _data;
		list_node<T>* _next;
		list_node<T>* _prev;
	};

    // 链表的主体
	template <class T>
	class list
	{
		typedef list_node<T> Node;
	public:
		

	private:
		Node* _head;
		size_t _size;
	};
}

二、构造函数

我们的构造分为四种，分别是无参构造、带参构造、迭代器构造和拷贝构造。

我们的无参构造实现十分简单，就是创建一个节点的空间后，把我们节点的 next 和 prev 都指向自己即可。

list()
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;
    _size = 0;
}

同时我们也要注意，我们节点如果想要创建也得初始化，所以也得有构造函数。

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

这样我们在list中创建节点就会调用这个构造函数为我们节点初始化啦。

拷贝构造可以使用迭代器的循环遍历去实现，但是在这之前我们得先给我们的要赋值的对象创建一个头节点，也是哨兵位节点。

void empty_init()
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;
	_size = 0;
}

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

三、析构函数

析构主要就是从后往前一个节点一个节点的删除，但是这里为了方便就直接使用我们的函数复用，用迭代器去循环erase即可。

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

当然，我们上面的删除其实就是clear的操作，我们可以先实现clear后再来函数复用就会是这样。

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

四、赋值重载

我们直接把临时变量相互交换即可。

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

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

五、增删查改

5.1、push_front/push_back函数

头插和尾插都比较简单。

这就是尾插的方式，先创建出一个新的节点 newnode，然后再把它和 _head 的 prev 节点插入好，然后再和 _head 节点插入好即可。

void push_back(const T& x)
{
	Node* newnode = new Node(x);

	newnode->_next = _head;
	newnode->_prev = _head->_prev;
	_head->_prev->_next = newnode;
	_head->_prev = newnode;

	++_size;
}

当然，如果觉得这样麻烦，我们可以直接把尾部节点保存起来，这样就可以随便插入了。

void push_back(const T& x)
{
	Node* newnode = new Node(x);
	Node* tail = _head->_prev;

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

	++_size;
}

当然，如果我们实现了 insert 函数后可以直接函数复用也很方便。

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

我们头插和尾插差不多，只不过是我们把尾节点换成我们头节点的下一个罢了。

void push_front(const T& x)
{
	Node* newnode = new Node(x);

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

这里只展示一种，剩下的大家可以自己尝试。

5.2、pop_front/pop_back函数

头删和尾删也不困难，我们如果实现了 erase 可以尝试函数复用，但是如果没有实现，我们可以把这些节点都保存下来，然后直接连接后删除即可。

void pop_front()
{
	Node* cur = _head->_next;
	Node* next = cur->_next;
	_head->_next = next;
	next->_prev = _head;
	delete cur;
	--_size;
}

当然也可以直接函数复用。

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

尾删同理

void pop_back()
{
	Node* cur = _head->_prev;
	Node* prev = cur->_prev;
	_head->_prev = prev;
	prev->_next = _head;
	delete cur;
	--_size;
}

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

5.3、insert函数

任意位置的插入和我们头插和尾插没有任何的不同，只是把我们的节点变化一下而已，但是我们得先实现迭代器才行，因为我们头插的参数都是迭代器。

在这里我们直接保存 pos 的位置和它之前的位置的两个节点，然后直接把 pos 插入到其中即可。

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

	++_size;
}

5.4、erase函数

任意位置删除也很容易，但是同样得先实现迭代器才行。

void erase(iterator pos)
{
	assert(pos != end());
	Node* next = pos._node->_next;
	Node* prev = pos._node->prev;
	prev->_next = next;
	next->_prev = prev;
	delete pos._node;
	--_size;
}

六、其他成员函数

6.1、迭代器

我们 list 的迭代器实现起来较为复杂，首先 list 的物理逻辑上是不连续的，这也就意味着它的 ++/-- 不像原生指针那样方便，list 的一个节点 ++ 后并不是下一个节点。所以我们得去单独实现一个关于迭代器的类，我们可以通过对其类的内部进行函数重载去实现 ++ 后就到下一个类的效果。

我们此时在封装一个list_iterator 类。

	template <class>
	struct list_iterator
	{
		typedef list_node<T> Node;
		typedef list_iterator<T> Self;
        
        // 这个类的成员函数
		Node* _node;

        // 这个类的无参构造
        // 到时候list中返回begin时
        // 就得构造我们的iterator
		list_iterator(Node* node)
			: _node(node)
		{ }
	};

我们可以看出这个类的主要架构就是如此，因为这个类主要就是去函数重载我们的迭代器，所以用struct 即可。而且我们后面要返回 list_iterator<T> 的类型，所以提前 typedef 简化代码，另外一个也是如此。

我们的 ++ 重载主要就是让我们能够成功的找到 list 的下一个节点，所以只要返回我们 node 的下一个节点即可。

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

我们返回 Self 的原因是因为我们得连续的 ++，如果返回的是 Node 下一次就不能 ++ 了。因为不满足我们重载的参数，也就是隐藏的 this 指针。所以我们返回的就是 Self 了，引用则是可能有要修改的请求。

我们 -- 的重载也和 ++ 相似，就是把 next 变成 prev 即可。

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

解引用主要是返回我们的 data 的数据，而且要可以修改，所以我们就返回 T& 即可。

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

还有 == 和 != 的运算符重载，这两个是在循环时判断是不是到 end 时使用的。

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

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

这就是我们所需要的 list 迭代器的运算符重载，有了这个重载，我们就可以在我们 list 的类中实现我们的有关迭代器的函数了。

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

		iterator begin()
		{
			// 可以有名对象
			//iterator it(_head->_next);
			//return it;

			// 也可以匿名对象
			return iterator(_head->_next);
		}

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

这样就可以实现我们的迭代器了。

我们尝试着运行看看。

int main()
{
	zxl::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);

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

	return 0;
}

成功打印出来了。这里我们就可以看出来我们上层看上去循环遍历都是从 begin 一直 ++ 到 end，但是底层确实天差地别。

我们可以继续来完善这个迭代器，我们已经实现了前置 ++/-- 了，现在可以尝试来实现后置 ++/--。

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

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

在这里创建了 tmp，运用的是拷贝构造，但是我们没有实现拷贝构造，那我们的系统就会对我们的内置类型进行值拷贝，我们的成员函数是 Node* 的指针，那我们到底要不要去实现拷贝构造呢？其实我们这里没有必要去实现，如果我们不实现拷贝构造，我们的 tmp 和我们 *this 就是指向同一个 _node 空间的，但是由于我们的节点是由链表管理的，而不是我们 *this 管理，所以当我们_node 离开时并不会去销毁我们的空间，同时，我们的 tmp 所指向的空间本就是我们所希望的空间，所以在这里浅拷贝就好了。

我们迭代器所指向的资源并不是属于它的资源，也可以解释为什么这里可以用浅拷贝而不用实现拷贝构造。同时也不用写析构了。

我们接着来看下面这串代码。

struct AA
{
	int a1 = 1;
	int a2 = 1;
};

int main()
{
	zxl::list<AA> a;
	a.push_back(AA());
	a.push_back(AA());
	a.push_back(AA());
	a.push_back(AA());

	zxl::list<AA>::iterator it = a.begin();
	while (it != a.end())
	{
		cout << (*it).a1 << " " << (*it).a2 << endl;
		it++;
	}

	return 0;
}

当我们的list创建一个类类型的变量时，如果我们要打印就比较麻烦，因为我们 it 是类类型的指针，所以得先解引用在去用 . 来去打印。这里有2种优化方法，第一种就是给我们AA的流输出运算符重载一下，但是如果换一个类时又得重载，还有一个就是在迭代器中重载一个 -> 符。

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

这样就可以完成我们箭头的工作了。

while (it != a.end())
{
	cout << it->a1 << " " << it->a2 << endl;
	it++;
}

但是有人会觉得这里很奇怪，为什么箭头是这样实现的？其实我们这里少了一个箭头，它本质上是有两个箭头在这里的。把代码改成这样你就一定可以理解了。

while (it != a.end())
{
	cout << it.operator->()->a1 << " " << it.operator->()->a2 << endl;
	it++;
}

这个时候我们先返回类的指针后就可以用类的箭头的操作了，但是为了美观和可读性，我们便省略了后面的箭头，所以就是第一次那种样子啦。

实现了普通迭代器后，我们来尝试实现const迭代器。首先我们知道const迭代器的特点就是不能修改，所以我们只要对我们迭代器的 * 运算符和 -> 运算符重载时加入 const 即可。

template <class T>
struct list_const_iterator
{
	typedef list_node<T> Node;
	typedef list_const_iterator<T> Self;

	Node* _node;

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

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

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

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

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

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

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

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

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

这就是我们的反向迭代器，再在list中 typedef list_const_iterator const_iterator 即可。

这样确实可是实现我们的const，但是我们会发现有大量的代码重复，看上去就没必要，因为只有两个代码是不同的，其余的都是相同代码。那我们有没有什么办法把它们揉在一起呢？答案就是模板，模板可以让编译器去做重复的工作。那我们该怎么操作呢？

我们仔细观察可以发现我们const迭代器和普通迭代器的差别无非就是一个是 T*/T&，而另一个是 const T*/const T&，所以我们可以创建一个模板，它有3个模板变量，

template <class T, class Ref, class Ptr>
struct list_iterator
{

};

我们list是这样传参的

class list
{
public:
	typedef list_iterator<T, T&, T*> iterator;
	typedef list_const_iterator<T, const T&, const T*> const_iterator;
};

这就是我们模板的用法，此时我们传不同的参数进去就会实例化出不同的对象，本质上就是我们上面写两个的情况让我们编译器自己去做了。

我们只要把刚才用到 T/T&/T* 用我们 T/Ref/Ptr 替代即可。

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)
	{ }

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

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

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

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

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

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

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

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

这样就完成了我们的模板实现。

我们接着来看看我们迭代器失效的问题，我们现在在任意位置插入后修改数据会不会迭代器失效呢？

int main()
{
	zxl::list<int> a;
	a.push_back(1);
	a.push_back(2);
	a.push_back(3);
	a.push_back(4);

	zxl::list<int>::iterator it = a.begin();
	it++;
	it++;

	a.insert(it, 10);
	*it *= 10;

	for (auto x : a)
	{
		cout << x << ' ';
	}
	cout << endl;

	return 0;
}

我们来看看我们 it 的位置有没有改变，3有没有变成30。

很显然，迭代器没有失效，这是因为vector在插入数据时会平移数据而导致我们 it 所指向的空间数据发生了改变，但是我们list确实插入数据，它本身空间不连续，我们插入数据时 it 更不会改变了。所以迭代器不会失效。

我们erase删除数据会导致迭代器失效，这是因为它删除后所指向的空间已经给销毁了，是野指针了，所以会失效。

我们可以让我们的erase函数返回我们下一个迭代器，这样我们用一个值记录下来就可以实现连续的删除了。

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

所以迭代器到底失不失效得看容器的结构，我们默认它失效即可。

6.2、size函数

size_t size()
{
	return _size;
}

6.3、empty函数

bool empty()
{
	return _size == 0;
}

6.4、clear函数

它和析构函数很像，也是把所有节点都销毁。

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

总结

以上便是我们list的主要内容啦，其实模拟实现并不难，主要的难点就在于实现迭代器，它和之前直接用原生指针的容器有很大的区别。大家可以慢慢研究了解，大家加油。

🎇坚持到这里已经很厉害啦，辛苦啦🎇

ʕ • ᴥ • ʔ

づ♡ど