C++从零开始的打怪升级之路(day31)

这是关于一个普通双非本科大一学生的C++的学习记录贴

在此前，我学了一点点C语言还有简单的数据结构，如果有小伙伴想和我一起学习的，可以私信我交流分享学习资料

那么开启正题

今天分享的是关于list的模拟实现，今天只实现一部分基础函数

1.结点以及构造函数

template<class T>
struct __list_node
{
	__list_node* _next;
	__list_node* _prev;
	T _data;
 
	__list_node(const T& x = T())
		:_data(x)
		,_next(nullptr)
		,_prev(nullptr)
	{}
};
 
class list
{
	typedef __list_node<T> Node;
public:
	list()
	{
		_head = new Node;
		_head->_next = _head;
		_head->_prev = _head;
	}
 
private:
	Node* _head;
};

list是一个双向带头循环的链表，所以在初始化时需要初始化哨兵位

2.尾插 

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

list的尾插比较简单，因为他的结构很完善

3.迭代器

template<class T>
struct __list_iterator
{
	typedef __list_node<T> Node;
	Node* _node;
 
	__list_iterator(Node* node)
		:_node(node)
	{}
 
	T& operator*()
	{
		return _node->_data;
	}
 
	__list_iterator operator++()
	{
		_node = _node->_next;
 
		return *this;
	}
 
	bool operator!=(const __list_iterator<T>& it)
	{
		return _node != it._node;
	}
};

因为迭代器要像指针一样去使用，所以我们必须对list的结点进行一些处理，而对于像vector的容器，他的原生指针就可以达到要求，我们没必要再打工干戈，但是对于list，我们就得动一些非常的手段

我们创造一个iterator的类，他存放结点的指针，再重载他的*   ++   --   ==   !=   等操作符，即可完成我们的要求 

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

当然，在begin()和end()函数调用时，就得用结点来创造迭代器再进行返回

 4.使用

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

将以上代码串起来，就可以简单模拟并验证list的实现了

下面是完整代码

namespace wkl
{
	template<class T>
	struct __list_node
	{
		__list_node* _next;
		__list_node* _prev;
		T _data;
 
		__list_node(const T& x = T())
			:_data(x)
			,_next(nullptr)
			,_prev(nullptr)
		{}
	};
 
	template<class T>
	struct __list_iterator
	{
		typedef __list_node<T> Node;
		Node* _node;
 
		__list_iterator(Node* node)
			:_node(node)
		{}
 
		T& operator*()
		{
			return _node->_data;
		}
 
		__list_iterator operator++()
		{
			_node = _node->_next;
 
			return *this;
		}
 
		bool operator!=(const __list_iterator<T>& it)
		{
			return _node != it._node;
		}
	};
 
	template<class T>
	class list
	{
		typedef __list_node<T> Node;
	public:
		typedef __list_iterator<T> iterator;
 
		iterator begin()
		{
			return iterator(_head->_next);
		}
 
		iterator end()
		{
			return iterator(_head);
		}
 
		list()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}
 
		void push_back(const T& x)
		{
			Node* tail = _head->_prev;
			Node* newnode = new Node(x);
 
			tail->_next = newnode;
			newnode->_next = _head;
			newnode->_prev = tail;
			_head->_prev = newnode;
		}
 
	private:
		Node* _head;
	};
 
	void test_list1()
	{
		list<int> l;
		l.push_back(1);
		l.push_back(2);
		l.push_back(3);
		l.push_back(4);
		l.push_back(5);
 
		list<int>::iterator it = l.begin();
		while (it != l.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}
}
 
int main()
{
	wkl::test_list1();
	return 0;
}

新手写博客，有不对的位置希望大佬们能够指出，也谢谢大家能看到这里，让我们一起学习进步吧！！