【C++】STL之list容器的模拟实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了【C++】STL之list容器的模拟实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【C++】STL之list容器的模拟实现,C++,c++,list,windows,STL,容器

个人主页：🍝在肯德基吃麻辣烫
分享一句喜欢的话：热烈的火焰，冰封在最沉默的火山深处。

前言

本文章进入C++STL之list的模拟实现。

一、list的三个类的关系分析图

在STL标准库实现的list中，这个链表是一个== 双向带头循环链表==。
【C++】STL之list容器的模拟实现,C++,c++,list,windows,STL,容器

说明：
list是一个类，成员变量为_head
节点类node，是每一个节点。
list的迭代器也升级成了类，成员变量为node。

把迭代器升级成类是为了能够重载++，–，*，！=等可以用在vector迭代器上的操作。

vector和list的区别

	vector	list
底层结构	是一块连续的空间	不是连续的空间
随机访问	支持下标随机访问	不支持下标随机访问
插入和删除	如果是头插头删，效率为O(n) ，如果插入时需要扩容，会付出更高的代价	头插头删都很方便，O(1)的效率
空间利用情况	底层为连续的动态空间，内存碎片小，空间利用率高	底层是一块一块不连续的空间，内存碎片多，空间利用率较低
迭代器	使用天然的原生迭代器	将迭代器封装起来再对外开放
迭代器失效	在进行插入删除时，插入/删除位置及其之后，空间不再属于自己，由于空间是连续的，其之后的迭代器全部失效	在插入时迭代器不会失效，只有在删除时迭代器会失效，且不会影响其他迭代器
使用场景	需要进行大量随机访问，需要高效存储，不关心插入删除。	大量插入删除操作时，不关心随机访问

vector在内存中是一块连续的地址空间，vector下标就是天然的迭代器。
list在内存中并不连续，所以不支持随机访问。为了能够让list完成诸如vector的操作，比如：

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

我们对list的迭代器进行封装，重载各种操作符，以便完成上述的操作。

1.节点的成员变量以及构造函数

在数据结构之链表中，我们知道一个节点必须包含prev,next,val三个变量，在STL的list也是如此。

template<class T>
//class list_node 如果这样写，节点的所有成员都是私有的，无法直接访问
struct list_node
{
	list_node<T>* _prev;
	list_node<T>* _next;
	T _val;

	//节点的构造函数
	list_node(const T& val = T())
		:_prev(nullptr)
		, _next(nullptr)
		, _val(val)
	{}
};

注意：
1.在C++，struct升级成了类，但如果不标明，struct的所有成员都是公有的。
2.类名不是类型，不能使用list_node*来作为指针的类型。要使用模板来作为类型。

2.list的迭代器

需要注意的一个点：

list的迭代器是用来访问的，而不是用来管理节点的空间，所以list的空间是由自己管理和释放的，我们知道，程序崩溃主要就是同一块空间释放两次。
所以list的迭代器在进行拷贝构造时可以使用浅拷贝，不会造成程序的崩溃。

list<int>:: iterator it = lt1.begin();

对这行代码来说，迭代器不是直接赋值给it的，因为迭代器升级成了类，而不是一个指针。这里会调用迭代器的拷贝构造函数。

list迭代器代码如下：

//迭代器也封装起来，形成我们熟悉的*it,++it
template<class T, class Ref, class Ptr>
//class __list_iterator 如果这样写，迭代器是私有的，无法直接使用
//迭代器使用类模板，为了重载Ref，Ptr，设置3个模板参数
struct __list_iterator
{
	typedef list_node<T> Node;
	typedef __list_iterator<T, Ref, Ptr> self;
	//等价于：
	//typedef __list_iterator<T, T&, T*> self;

	Node* _node; //成员

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

	//返回引用，可读可写
	Ref operator*()
	{
		return _node->_val;
	}

	//返回地址
	Ptr operator->()
	{
		return &_node->_val;
	}

	//返回迭代器本身
	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;
	}

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

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

};

1.使用三个模板参数的原因：
- 要求返回指针，如：用指针->访问成员的情况；或者返回迭代器本身的情况，如 ++ ，–操作。
2.在重载operator->()时，返回的是val的地址，所以我们在调用该函数时，需要进行两次->操作才能访问成员变量。
比如：

struct A
{

	A(int a1 = 0, int a2 = 0)
		:_a1(a1)
		, _a2(a2)
	{}

	int _a1;
	int _a2;
};

bit::list<A>lt2;
lt2.insert(lt2.begin(), A(1, 1));
lt2.insert(lt2.begin(), A(2, 2));
list<A>::iterator it = lt2.begin();
while (it != lt2.end())
{
	//迭代器重载了*，返回T&,也就是A本身
	cout << it->_a1 << " " << it->_a1 << endl;
	++it;
}
cout << endl;

本质上，应该需要 it->->_al，it->->_a2才能够访问成员。
第一个it->是调用operator->重载，返回val的地址，第二个->是通过地址访问成员。
编译器为了简化操作，以及看起来没有那么别扭，对it->->_a1进行简化成了it->_a1。

3.类模板中的Ref是Reference，是引用的意思，Ptr是Pointer，是指针的意思。通过这两个模板名可以知道迭代器需要支持&，和*的操作。
4.迭代器被重命名成self，也就是迭代器本身，在++，–操作时，需要返回迭代器本身。

二、list的增删查改工作

2.1insert()

在pos位置之前插入val值。

首先要获取pos位置的前一个节点，记为posprev。
将新的节点插入即可。

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

	newnode->_next = inspos;
	inspos->_prev = newnode;

	newnode->_prev = posprev;
	posprev->_next = newnode;

	++_size;
	return posprev;

}

list的插入没有迭代器的失效问题。

2.2erase()

删除pos位置的节点，并返回pos位置的下一个位置的迭代器。

iterator erase(iterator pos)
{
	assert(pos != end());
	Node* erapos = pos._node;
	Node* eraprev = erapos->_prev;
	Node* eranext = erapos->_next;

	eraprev->_next = eranext;
	eranext->_prev = eraprev;

	erapos->_prev = erapos->_next = nullptr;
	delete erapos;

	--_size;
	return eranext;
}

erase后pos位置的迭代器会失效，我们需要返回下一个位置的迭代器来防止继续访问出现失效的情况。

删除后如果迭代器不更新，继续访问会出现野指针问题。

2.3 push_back(),pop_back(),push_front(),pop_front()

这几个函数分别是：尾插，尾删，头插，头删，我们复用insert和erase即可完成。

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

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

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

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

2.4clear()

该函数是将链表的所有节点全部释放，哨兵位头节点除外。

//把所有的节点都释放了，除了哨兵位的头节点
void clear()
{
	iterator it = begin();
	while (it != end())
	{
		//为防止迭代器失效，erase后会返回pos位置的下一个位置，所以it不需要++
		it = erase(it);
	}

	_size = 0;
}

注意：erase（）删除pos节点后，会返回pos位置的下一个位置，所以这里不需要++it

三、list的默认成员函数

3.1 构造函数

首先申请一个哨兵位的头节点。

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

//构造函数，构造出一个链表
list()
{
	empty_init();
}

2.2 拷贝构造

由于我们将迭代器进行了封装升级，现在可以使用++it等操作。
拷贝构造是深拷贝，先new一个_head哨兵位的头节点，再逐个节点进行尾插。

list(list<T>& lt)
{
	empty_init();
	list<T>::iterator it = lt.begin();
	while (it != lt.end())
	{
		push_back(*it);
		++it;
		++_size;
	}

}

2.3析构

调用clear函数释放所有空间，再释放头节点。

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

完整代码

namespace bit
{
	//c++不喜欢使用内部类，所以把节点类放在list外面
	//节点封装成类
	template<class T>
	//class list_node 如果这样写，节点的所有成员都是私有的，无法直接访问
	struct list_node
	{
		list_node<T>* _prev;
		list_node<T>* _next;
		T _val;

		//节点的构造函数
		list_node(const T& val = T())
			:_prev(nullptr)
			, _next(nullptr)
			, _val(val)
		{}
	};

	//迭代器也封装起来，形成我们熟悉的*it,++it
	template<class T, class Ref, class Ptr>
	//class __list_iterator 如果这样写，迭代器是私有的，无法直接使用
	//迭代器使用类模板，为了重载Ref，Ptr，设置3个模板参数
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> self;
		//等价于：
		//typedef __list_iterator<T, T&, T*> self;

		Node* _node; //成员

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

		//返回引用，可读可写
		Ref operator*()
		{
			return _node->_val;
		}

		//返回地址
		Ptr operator->()
		{
			return &_node->_val;
		}

		//返回迭代器本身
		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;
		}

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

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

	};
    
	template<class T>
	class list
	{
		//节点不希望对外开发,把节点封装起来。
		typedef list_node<T> Node;
	public:
		//迭代器对外开放即可访问节点
		//这个迭代器是给链表用的。
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;

		iterator begin()
		{
			//return iterator(_head->_next);
			return _head->_next; // 单参数的构造函数可以进行隐式类型转换，从节点的指针转换成一个类
		}

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

		const_iterator begin() const
		{
			return const_iterator(_head->_next);
			//return _head->_next; // 单参数的构造函数可以进行隐式类型转换，从节点的指针转换成一个类
		}

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

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

		//构造函数，构造出一个链表
		list()
		{
			empty_init();
		}

		//拷贝构造
		//lt2(lt1)
		list(list<T>& lt)
		{
			empty_init();
			list<T>::iterator it = lt.begin();
			while (it != lt.end())
			{
				push_back(*it);
				++it;
				++_size;
			}

		}

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

		//把所有的节点都释放了，除了哨兵位的头节点
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				//为防止迭代器失效，erase后会返回pos位置的下一个位置，所以it不需要++
				it = erase(it);
			}

			_size = 0;
		}

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

		//赋值运算符重载
		//先调用拷贝构造，再调用赋值重载
		//lt3 = lt1
		//lt1先拷贝构造给tmp
		list<T>& operator=(list<T> tmp)
		{
			swap(tmp);
			//出了作用域，调用析构
			return *this;
		}

		size_t size() const
		{
			return _size;
		}



		//尾插传过来的是一个数据，而不是一个节点
		void push_back(const T& x)
		{
			//Node* tail = _head->_prev;
			调用构造
			//Node* newnode = new Node(x);
			//tail->_next = newnode;
			//newnode->_prev = tail;

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

			insert(end(), x);
		}

		void pop_back()
		{
			//Node* del = _head->_prev;
			//_head->_prev = del->_prev;
			//del->_prev->_next = _head;

			//del->_next = del->_prev = nullptr;
			//delete del;
			//左闭右开，需要--
			erase(--end());
		}

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

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

		//在pos位置之前插入val
		//不会出现迭代器失效问题
		iterator insert(iterator pos, const T& val)
		{
			Node* newnode = new Node(val);
			Node* inspos = pos._node;
			Node* posprev = inspos->_prev;

			newnode->_next = inspos;
			inspos->_prev = newnode;

			newnode->_prev = posprev;
			posprev->_next = newnode;

			++_size;
			return posprev;

		}
		//迭代器封装成了类，所以需要通过迭代器找到节点
		//防止迭代器失效，返回删除节点的下一个
		iterator erase(iterator pos)
		{
			assert(pos != end());
			Node* erapos = pos._node;
			Node* eraprev = erapos->_prev;
			Node* eranext = erapos->_next;

			eraprev->_next = eranext;
			eranext->_prev = eraprev;

			erapos->_prev = erapos->_next = nullptr;
			delete erapos;

			--_size;
			return eranext;
		}

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