C++list类模拟实现

• list类的基本结构
• 结点类
• • 成员变量
  • 成员函数
• 迭代器类
• • 成员函数
  • • 1、解引用运算符重载
    • 2、箭头运算符重载
    • 3、迭代器前置++
    • 4、迭代器后置++
    • 5、迭代器的比较
• 链表类
• • 成员变量
  • 成员函数
  • • 1、构造函数
    • 2、拷贝构造
    • 3、赋值重载
    • 4、析构函数
    • 5、clear
    • 6、begin（）、end（）
    • 7、insert
    • 8、erase
    • 其他小型接口

list类的基本结构

xxxxSTL中list是一个双向带头循环链表。除了头结点不存储有效信息外，其余node结点存储有效信息。同时，为了防止代码冗余，对于存储信息类型不同的问题，将采用模板的方式解决。

xxxxlist需要创建3个类：结点类、迭代器类和链表类。

结点类

成员变量

xxxx就像C语言中链表的创建，C++的链表也需要构建一个类（类似于C的结构体）包含节点中数据信息、下一节点地址和上一节点的地址三部分信息。

结点类成员变量如下：

template<class T>
struct _list_node_
{
	T _val;					//存储数据
	_list_node_<T>* _next;
	_list_node_<T>* _prev;
};
           

成员函数

xxxx分析我们需要写的成员函数：发现只有构造函数需要写，因为在new新的结点时，会自动调用它的构造函数，如果不写就会产生随机值。但是结点不会拷贝构造，不会赋值。并且节点的释放是list控制。所以不需要写拷贝构造、赋值运算法重载和析构函数。

结点类完整代码如下：

解释:由于结点类的成员变量需要被其他类直接访问，所以要将成员变量设置成公有，所以直接用struct（默认内容为公有public）。下面迭代器类同理

迭代器类

xxxx不同于string、vector两种容器，list的迭代器并不是原生的指针，而是封装结点指针成了一个类。

迭代器类代码如下：

template<class T, class Ref, class Ptr>
	struct _list_iterator_					//迭代器就是需要浅拷贝，不需要重新写拷贝构造或者复制
	{										//析构函数：迭代器只是存一下指针，指针指向的结点由链表管理，不需要迭代器去释放空间
		typedef _list_node_<T> node;
		typedef _list_iterator_<T, Ref, Ptr> self;

		_list_iterator_(node* pnode = nullptr)
			:_pnode(pnode)
		{}

		Ref operator*()				//不加引用就是返回一个临时变量，不可更改具有常属性
		{
			return _pnode->_val;
		}
		Ptr operator->()
		{
			return &_pnode->_val;				//it->->_year   it->获得T*，T*->获得T类中的内容
		}
		bool operator==(const self& s) const
		{
			return _pnode == s._pnode;
		}
		bool operator!=(const self& s) const
		{
			return _pnode != s._pnode;	
		}
		self& operator++()
		{
			_pnode = _pnode->_next;
			return *this;
		}
		self operator++(int)			//返回的是临时对象，所以不返回引用
		{
			self tmp(*this);
			_pnode = _pnode->_next;
			return tmp;
		}
		self& operator--()
		{
			_pnode = _pnode->_prev;
			return *this;
		}
		self operator--(int)			//返回的是临时对象，所以不返回引用
		{
			self tmp(*this);
			_pnode = _pnode->_prev;
			return tmp;
		}

		//成员变量
		node* _pnode;
	};

           

xxxx问题一：为什么要这样做呢？因为由于list并不是序列型容器，而是一个一个结点通过地址连接起来的。而为了保证所有容器迭代器使用方法的统一性，都要有对迭代器++/–/*等操作。++/–会直接访问上一个结点或者下一个结点的数据；解引用操作则会直接访问当前结点存储的数据。如果我们使用原生指针（结点的指针），则无法达到迭代器所要求的结果。因此，我们需要将结点的指针包装成类，通过运算符重载改变它的行为。达到这样的目的。

xxxx问题二：为什么迭代器类不写拷贝构造、赋值重载和析构函数呢？因为迭代器在拷贝构造和赋值的时候，就是希望做到浅拷贝，就是将值进行拷贝，让他们指向同一块空间，而不是将指向的内容进行深拷贝。因此编译器自动生成的浅拷贝就够了。其次，由于迭代器并没有自己开辟空间，因此无空间的释放，所以不需要析构函数。结点的释放是链表的任务

xxxx问题三:迭代器的模板中，为何需要三个模板参数？三个模板参数分别代表什么意思？。我们都知道，list的迭代器不同于string和vector的原生指针类型的迭代器，他是一个类。对于原生指针来说。被const修饰和不被const修饰的两种指针就是两种类型。因此对于正常的思维来说，迭代器就应该实现成两种类，一个是iterator，一个是const_iterator，两种分开写。因为如果还是想string、vector一样单纯把const和非const两种迭代器看作一种，在list类里typedef成const和非const类型的迭代器。这样就会导致const无效，还是可以更改内容。因为，迭代器仍然是非const，你只是把迭代器的类型名改成了const_iterator，并没有改变迭代器的实质。所以当调用解引用的操作符重载时，还是会返回T&，还是可以更改。所以第一种解决方法就是将iterator和const_iterator两种迭代器类型分成两个类来写，这样const修饰的链表就会去调用const_iterator的类，非const链表就会调用iterator的类。但是这样就会造成大量代码的冗余。

xxxx于是，就出现了利用模板的方法，来区分两种迭代器。

xxxx第一个参数模板class T：代表的是数据的类型。

xxxx第二个参数模板class Ref：代表的是结点中数据的引用。

xxxx第三个参数模板class Ptr：代表的是结点中数据的指针。

具体如下图：

如果还是有不理解可以通过下面成员函数的解析再次加深理解。

成员函数

1、解引用运算符重载

Ref operator*()				//不加引用就是返回一个临时变量，不可更改具有常属性
{
	return _pnode->_val;
}
           

xxxx对于string、vector迭代器是原生指针的容器来说。他们的迭代器就是数据的地址，因此解引用可以直接拿到数据。而list并不是，所以需要运算符重载来改变它的行为。可以通过对迭代器解引用直接获取数据。所以return _pnode->val

xxxx同时，对于返回值，我们需要返回的是一个引用，否则，返回的就是一个临时变量，具有常属性，不可改变。并且，如果迭代器是const_iterator所以它的Ref就是const T&就不能对数据进行写，只能读。const类型迭代器返回的是T&，就可读可写了。

2、箭头运算符重载

Ptr operator->()
{
	return &_pnode->val;
}
           

xxxx若迭代器为原生指针，则it->就可以直接获取it的内容，但是list的迭代器不可以，所以就需要运算符重载改变行为。

xxxx值得注意的是

3、迭代器前置++

typedef _list_iterator_<class T, class Ref, class Ptr> self
self& operator++()
{
	_pnode = _pnode->_next;
	return *this;
}
           

xxxxself是一个类型，返回的就是迭代器自己。self是typedef出来的。前置–类似就是将_next换成_prev。

4、迭代器后置++

self operator++(int)
{
	self tmp(*this);
	_pnode = _pnode->_next;
	return tmp;
}
           

xxxx因为返回的是tmp，是临时变量，所以不能返回引用。因为返回的值是改变之前的值，所以要报错原来的值，返回再将*this改变。后置–类似，就是将_next换成_prev。

5、迭代器的比较

xxxx迭代器的比较比较简单，所以就不细说了。

链表类

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;


	list()
	{
		_head = (node*)malloc(sizeof(node));
		_head->_next = _head;
		_head->_prev = _head;
	}

	list(const list<T>& lt)
	{
		_head = new node;
		_head->_next = _head;
		_head->_prev = _head;
		for (const T& e:lt)
		{
			push_back(e);
		}

	}
		
	list<T>& operator=(list<T> lt)		//现代写法
	{
		swap(_head, lt._head);
		return *this;
	}

	~list()
	{
		clear();
		delete _head;
		_head = nullptr;
	}
			
	void clear()
	{
		iterator it = begin();
		while (it != end())
		{
			it = erase(it);
		}
	}
	iterator begin()
	{
		return _head->_next;
	}
	const_iterator begin() const
	{
		return _head->_next;
	}
	iterator end()
	{
		return _head;
	}
	const_iterator end() const
	{
		return _head;
	}
	void push_back(const T& x)
	{
		node* tail = _head->_prev;
		node* newnode = new node(x);		//调用node的构造函数
		tail->_next = newnode;
		newnode->_next = _head;
		_head->_prev = newnode;
		newnode->_prev = tail;
	}
	void insert(iterator pos, const T& x)
	{
		assert(pos._pnode);
		node* cur = pos._pnode;
		node* prev = cur->_prev;
		node* newnode = new node(x);
		prev->_next = newnode;
		newnode->_next = cur;
		cur->_prev = newnode;
		newnode->_prev = prev;
	}
	iterator erase(iterator pos)
	{
		assert(pos._pnode);
		assert(pos != end());
		node* prev = pos._pnode->_prev;
		node* next = pos._pnode->_next;
		delete pos._pnode;		
		prev->_next = next;
		next->_prev = prev;
		return iterator(next);
	}
	size_t size()
	{
		size_t sz = 0;
		iterator it = begin();
		while (it != end())
		{
			it++;
			sz++;
		}
		return sz;
	}
	bool empty()
	{
		return begin() == end();
	}
private:
	node* _head;
};
           

成员变量

xxxx成员变量就是一个头结点。同时还需要typedef出结点、const_iterator和iterator

成员函数

1、构造函数

list()
{
	_head = (node*)malloc(sizeof(node));
	_head->_next = _head;
	_head->_prev = _head;
}
           

xxxx注意_head需要使用malloc来开辟空间，因为头结点不需要存储数据，所以不需要初始化。如果用new的话存在一个问题，就是如果出现数据类型T也是list，那么用new开辟头结点空间时，就会自动迪调用构造函数初始化，初始化就要调用构造函数，调用构造函数就要new并且初始化，就会出现一个无限循环。所以就需要malloc来开辟空间。

xxxx对于空链表来说，应该是头结点的next和prev都指向自己。

2、拷贝构造

list(const list<T>& lt)
{
	_head = (node*)malloc(sizeof(node));
	_head->_next = _head;
	_head->_prev = _head;
	for(const auto& e : lt)
	{
		push_back(e);
	}
}
           

xxxx可以复用代码，使用push_back。但是push_back之前，必须是规范的空链表，必须初始化。

3、赋值重载

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

xxxx这是一种现代写法，很简单，先利用拷贝构造，构造出一个完全相同的，这样把*this的_head与拷贝构造出来的_head一换，这样就直接把拷贝构造出来的内容的给了this

4、析构函数

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

xxxx同样的道理，也是复用，先用clear，将链表置空（所有的结点都被释放掉），然后再释放掉头结点。

5、clear

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

xxxx挨个释放所有结点就是复用erase，同时，因为释放结点后，就无法找到该结点后的结点，所以it要接受erase的返回值（即：被释放结点后结点的迭代器）

6、begin（）、end（）

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

7、insert

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

xxxxprev、cur、next三个结点的链接关系搞清楚即可，由于是带头双向循环，所以，不需要考虑结点之间连接的顺序，也不需要考虑多种情况。需要考虑的就是pos除是否为空，空的位置不能操作，断言一下。提高安全性。

8、erase

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

xxxx删除后，为了防止迭代器失效，所以要把下一位置的的迭代器当做返回值返回。这是STL中容器的普遍做法。

其他小型接口

xxxx其余的接口都比较比较简单，直接看代码就能明白，代码在上面的list类完整版部分。

xxxx

xxxx

xxxx

xxxx

xxxx如果读者还有任何疑问，可以评论留言，或者私信我，我们一起探讨，一起进步