C++|list的模拟实现

前言

我们模拟实现的list是带头双向循环链表，list的成员变量有指向头节点的指针。所以在实现list之前我们应该实现节点这个类型

ListNode

这个是双向链表的节点的结构

template<class T>
	struct ListNode
	{
		
		ListNode<T>* _prev;
		ListNode<T>* _next;
		T _data;
		ListNode(const T& val = T())
			:_prev(nullptr),
			_next(nullptr),
			_data(val)
		{}
	};
1
2
3
4
5
6
7
8
9
10
11
12
13

list

class list 
{
	typedef ListNode<T> Node;
	Node* _head;
public:
	list() 
	{
		_head = new Node;
		_head->_prev = _head;
		_head->_next = _head;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

list的尾插操作

void push_back(T val =T()) 
{
	Node* tail = _head->_prev;
	Node * newnode = new ListNode(val);
	tail->_next = newnode;
	newnode->_prev = tail;
	newnode->_next = _head;
	_head->_prev = newnode;
}
	
1
2
3
4
5
6
7
8
9
10

list的尾删

		void pop_back() 
		{
			Node* tail = _head->_prev;
			Node* pr = tail->_prev;
			_head->_prev = pr;
			pr->_next = _head;
			delete tail;
		}
1
2
3
4
5
6
7
8

因为我们想实现list的任意位置的插入的删除都要实现list的迭代器，所以我们先实现迭代器。

list的迭代器

vector中我们直接把指针当成迭代器，这是因为vector支持随机访问。但是链表的指针++ 就变成野指针了。我们想要控制这个指针的行为，就要把这个指针封装成类。类决定了行为

代码实现

	template<class T>
	class Iterator
	{

	public:
		
		typedef ListNode<T> Node;
		typedef Iterator<T> Self;
		Node* _node;
		Iterator(Node* node)
		:_node(node)
		{}
		Self& operator++()
		{
			_node = _node->_next;
			//why
			return *this; // this 指针指向当前的iterator
			// 返回的就是iterator
		}
		Self& operator--()
		{
			_node = _node->_prev;
			return *this; 
		}
		Self operator++(int) 
		{
			Iterator tmp(*this);
			_node = _node->_next;
			return tmp; // 出了作用域tmp就被销毁了所以不能引用tmp

		}
		T& operator*()
		{
			return _node->_data;
		}
		bool operator != ( const Self &it) // 引用的是 return 回来的值 
			//因为return 回来的值本质是拷贝的一份临时变量 具有常性
		{
			return _node != it._node;
		}
		
		

	};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

list的其他操作

insert

void insert( iterator pos, T val = T()) // 缺省参数只能从右边缺省！
{
	Node *newnode = new Node(val);
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	prev->_next = newnode;
	newnode->_prev = prev;

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

}
1
2
3
4
5
6
7
8
9
10
11
12
13

erase

	void erase(iterator pos) 
	{
		Node* cur = pos._node;
		Node* prev = cur->_prev;
		Node* next = cur->_next;
		prev->_next = next;
		next->_prev = prev;
		delete cur;
		_size--;
	}
1
2
3
4
5
6
7
8
9
10

	void empty_list() 
	{
		_head = new Node;
		_head->_prev = _head;
		_head->_next = _head;
		_size = 0;
	}
	List()
	{
		empty_list();
	}
	List(const List<T> &It) 
	{
		empty_list();
		for (auto e : It) 
		{
			push_back(e);
		}
	}
	List(initializer_list<T> il)
	{
		empty_list();

		for (auto& e : il)
		{
			push_back(e);
		}
	}
	~List() 
	{
		clear();
		delete _head;
		_head = nullptr;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

const迭代器

	class constlistiterator
	{
		typedef  listnode<t>  node; //内嵌类型
		typedef  constlistiterator<t> self;
	public:
		node* _node;
		constlistiterator(node* node)
			:_node(node)
		{}
	public:
		const t& 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);
			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;
		}
		 const t* operator->() 
		{
			return &_node->_data;
		}
	};
	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

我们发现大部分内容都是一样的只是返回值不一样！
我们可以用模板把const迭代器和普通迭代器和成一个模板，当需要的时候编译器再现生成一个

class ListIterator
{
	typedef  ListNode<T>  Node; //内嵌类型
	typedef  ListIterator<T,Ref,Ptr> Self;

public:
	Node* _node;
	ListIterator(Node* node)
		:_node(node)
	{}
	Ref 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);
		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;
	}
	Ptr operator->() 
	{
		return &_node->_data;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50