list简单模拟实现

发布于：2025-05-17 ⋅ 阅读:(16) ⋅ 点赞:(0)

由于前面已经模拟实现了vector，所以这里关于一些函数实现就不会讲的过于细致。

成员变量

template<class T>
struct ListNode
{
	ListNode<T>* _next;
	ListNode<T>* _prev;
	T _data;
	ListNode(const T& x = T())
		:_next(nullptr)
		,_prev(nullptr)
		,_data(x)
	{}
};

template<class T>
class list
{
	typedef ListNode<T> Node;
public:
	list()
	{
		_head = new Node;
		_head->_next = _head->_prev = _head;
		_size = 0;
	}
	size_t size()const
	{
		return _size;
	}
private:
	Node* _head;
	size_t _size;
};

迭代器（重点）

我们想要迭代器能实现以下的功能：

void test_1()
{
	list<int>lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	list<int>::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << ' ';
		++it;
	}
	cout << endl;
}

实际上迭代器模拟的是指针的功能，然而链表的指针++并不会得到下一个元素的指针。但我们却希望迭代器++能得到下一个元素的迭代器。

那么我们是不是需要对++进行一个修改，也就是运算符重载。

再仔细想想，重载后的运算符是对这一个类生效的，但我们只需要对迭代器生效。那是不是意味着我们的迭代器需要是一个独立的类：

ListIterator

template<class T>
struct ListIterator
{
	typedef ListNode<T> Node;
	typedef ListIterator<T, Ref, Ptr> Self;
	Node* _node;//内置类型指针
	ListIterator(Node* node)
	:_node(node)
	{}
}

注意不需要析构函数，实际上我们的迭代器就是原数组结点指针的一个类，怎么可以用过一次后就析构掉呢？

运算符重载

前置++：

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

后置++：

Self operator++(int)//后置++
{
	Self tmp(*this);//浅拷贝
	_node = _node->_next;
	return tmp; 
}

值得注意的是，前后++的重载函数名都是operator++，那么如何区分他们呢？

C++语法规定：后置++的函数参数里面需要有一个int。

此外，我这的tmp是一个浅拷贝，这样做有没有问题呢？
我们需要的是指针，那么对于指针自然应该采用浅拷贝。
事实上，我们一般有一个规律：如果类需要重载析构函数，那么一般就要深拷贝，反之一般就需要浅拷贝。

剩余运算符：

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

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

Self operator--(int)//后置--
{
	Self tmp(*this);//浅拷贝
	_node = _node->_prev;
	return tmp;
}

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

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

begin、end

注意到我们的begin是返回首元素迭代器，而end是返回最后一个元素的下一个位置的迭代器：

typedef ListIterator<T> iterator;
iterator begin() 
{
	return _head->_next;
}

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

注意到，begin这里我返回的是_head->_next，因为单参数会隐式类型转换：自动调用单参数的构造函数，也就是等价于iterator(_head->_next).

插入、删除

insert

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

	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = cur;
	cur->_prev = newnode;
	_size++;
}

erase

iterator erase(iterator pos)//返回iterator防止迭代器失效
{
	Node* cur = pos->_node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;

	prev->_next = next;
	next->_prev = prev;
	delete cur;
	_size--;

	return iterator(next);
}

值得注意的是，为了防止迭代器失效，我们这里要返回最后一个删除的元素的下一个元素的迭代。

头插、尾插、头删、尾删

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

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

void pop_back()
{
	erase(end()--);//没有重载-1，所以要用--
}

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

尾删这里需要注意一定要是end()–，而不能是end()-1.理由很简单，因为我们没有重载-。

operator->

对于非内置类型如下：

struct A
{
	int _a1;
	int _a2;

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

void test_2()
{
	list<A>lt;
	A aa1(1, 1);
	lt.push_back(aa1);
	lt.push_back(aa1);
	lt.push_back(A(2, 2));
	lt.push_back({ 3,3 });
	lt.push_back({ 4,4 });
	list<A>::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << ' ';//不支持流插入
		++it;
	}

}

不难发现cout << *it << ’ ';这里会报错，因为自定义类型没有重载<<。
因此我们需要改写为：

cout << (*it)._a1 << ' ' << (*it)._a2 << endl;

不难发现这有些许繁琐，正常来说对于类指针功能我们更希望用->这个操作符，也就是：

cout << it->_a1 << ' ' << it->_a2 << endl;

那就需要重载->：

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

这时候就有人发出疑问了，怎么返回值是一个指针，那要调用_a1，不应该是it->->_a1吗？
没错，这是原生写法，但是我们C++语法给他优化掉了，现在it->_a1等价于it.operator->()->_a1

const_iterator

const_iterator为什么不是const iterator?
这个问题其实前面学习类的时候已经解答过了，事实上我们的const_iterator是不能改变迭代器呢，还是不能改变迭代器指向的元素的值呢？
事实上const_iterator也是可以++的，否则怎么遍历数组元素。
那也就是说const_iterator只是不能改变指向的元素的值，而不是不能改变迭代器本身。

经过上述分析我们得知，我们只需要对*和->重载的返回值作出修改即可：

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

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

但是，只有返回值不同是无法重载函数的！！
那么我们是不是需要再多写一个const_iterator类呢？
可以，但有更好的方法。
注意到我们只有这两个函数不同，并且只有返回值不同，那是不是可以写一个模板将返回值不同分成不同的类呢？

template<class T,class Ref,class Ptr>
struct ListIterator
{
	typedef ListNode<T> Node;
	typedef ListIterator<T, Ref, Ptr> Self;
			
	Ref operator*()
	{
		return _node->_data;
	}
	
	Ptr operator->()
	{
		return &_node->_data;
	}
	
}
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;

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

const_iterator end() const
{
	return _head;
}

这样我们就省去了CV再写一个类的功夫。

拷贝构造

一样是复用push_back

void empty_init()
{
	_head = new Node;
	_head->_next = _head->_prev = _head;
	_size = 0;
}
list(const T& lt)// 复用push_back来深拷贝
{
	empty_init();
	for (auto& e : lt)
	{
		push_back(e);
	}
}

operator=

一样是复用拷贝构造：

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

析构函数

同样复用erase

void clear()//没清除头结点
{
	iterator it = begin();
	while (it != end())
	{
		it = erase(it);
	}

}

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

}

完整代码

template<class T>
struct ListNode
{
	ListNode<T>* _next;
	ListNode<T>* _prev;
	T _data;
	ListNode(const T& x = T())
		:_next(nullptr)
		,_prev(nullptr)
		,_data(x)
	{}
};

template<class T,class Ref,class Ptr>
struct ListIterator
{
	typedef ListNode<T> Node;
	typedef ListIterator<T, Ref, Ptr> Self;
	
	Node* _node;//内置类型指针

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

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

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

	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)
	{
		return _node != it._node;
	}

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

};

template<class T>
class list
{
	typedef ListNode<T> Node;
public:

	typedef ListIterator<T, T&, T*> iterator;
	typedef ListIterator<T, const T&, const T*> const_iterator;

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

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

	//const_iterator而不是const iterator，因为是指向内容不能被修改，而非迭代器本身不能被修改。如果是const iterator就不能it++
	const_iterator begin() const
	{
		return _head->_next;
	}

	const_iterator end() const
	{
		return _head;
	}

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

	list()
	{
		empty_init();
	}

	list(const T& lt)// 复用push_back来深拷贝
	{
		empty_init();
		for (auto& e : lt)
		{
			push_back(e);
		}
	}

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

	void clear()//没清除头结点
	{
		iterator it = begin();
		while (it != end())
		{
			it = erase(it);
		}

	}

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

	}

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

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

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

	void pop_back()
	{
		erase(end()--);//没有重载-1，所以要用--
	}

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

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

		prev->_next = newnode;
		newnode->_prev = prev;
		newnode->_next = cur;
		cur->_prev = newnode;
		_size++;
	}

	iterator erase(iterator pos)//返回iterator防止迭代器失效
	{
		Node* cur = pos->_node;
		Node* prev = cur->_prev;
		Node* next = cur->_next;

		prev->_next = next;
		next->_prev = prev;
		delete cur;
		_size--;

		return iterator(next);
	}

	size_t size()const
	{
		return _size;
	}

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

private:
	Node* _head;
	size_t _size;
};

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布