list的模拟实现（一）

嗨喽大家好，时隔许久阿鑫又给大家带来了新的博客，list的模拟实现（一），下面让我们开始今天的学习吧！

list的模拟实现（一）

1.list splice接口的使用

2.list尾插的实现

3.list的迭代器模拟实现

4.const迭代器

5.insert和erase的模拟实现

1.list splice接口的使用

int main()
{
    std::list<int> mylist1;
    mylist1.push_back(1);
    mylist1.push_back(2);
    mylist1.push_back(3);
    mylist1.push_back(4);

    auto it = find(mylist1.begin(), mylist1.end(), 3);
    mylist1.splice(++mylist1.begin(), mylist1, it);//1324
    for (auto ch: mylist1)
    {
        cout << ch << " ";

    }
    cout << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.list尾插的实现

3.list的迭代器模拟实现

原生指针的++是连续的物理空间的++。
因为类能进行运算符重载，我直接对节点进行++达不到我的要求，所以我就将节点指针封装成一个类，这个类的行为就是遍历双向循环列表。
每一个类都有自己需要完成的事情，也可以是几个类互相搭配完成一件事情。

模板是不会被编译的，只有实例化的时候才会被编译
按需实例化，调用哪个函数才会实例化哪个函数
每个template定义的模板参数T都只能供当前类用

	template<class T>
	struct ListNode
	{
		ListNode<T>* _next;
		ListNode<T>* _prev;
		T _date;

		ListNode(const T& date = T())
		:_next(nullptr)
		,_prev(nullptr)
		,_date(date)
		{}
	};

	template<class T>
	class ListIterator
	{
		typedef ListNode<T> Node;//此处传T的时候就相当于实例化
		typedef ListIterator<T> self;
	public:
		ListIterator(Node* node)//用一个节点的指针来构造
			:_node(node)
		{}
		//++it
		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;
}



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

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


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

	private://成员是一个节点的指针，将指针封装成类来达到我们想要实现的操作
		Node* _node;
	};



	template<class T>
	class list
	{
		
	public:

		typedef ListNode<T> Node;
		typedef ListIterator<T> iterator;//若T为int相当于实例化了一个int类型的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* newnode = new Node(x);
			Node* tail = _head->_prev;
			//head  2  3   tail  newnode
			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;
		}

	private:
		Node* _head;

	};
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

iterator类不需要写析构函数，构造函数。节点是由链表管理的。（一般一个类不写析构函数，就不用写拷贝构造和赋值）

在C、C++等语言中，指针访问结构体（struct）或联合体（union）的成员时，我们使用箭头（->）操作符。而当我们**直接访问结构体或联合体的成员（即不通过指针）时，我们使用点（.）**操作符。

注意：对于->操作符，可以得到一个指向节点有效数据的指针（下图pos坐标（中存储的是行和列）类似于节点中的_date），应该如下图注释所进行调用，但是编译器为了可读性，强行省略了一个箭头

struct pos
{
	int _row;
	int _col;

	pos(int row = 0,int col = 0 )
		:_row(row)
		,_col(col)
	{}

};


void list_test2()
{

	list<pos> it1;
	it1.push_back(pos(100,200));
	it1.push_back(pos(200,300));
	it1.push_back(pos(300,400));

	list<pos>::iterator it = ++it1.begin();
	while (it != it1.end())
	{
		cout << it->_col << ":" << it->_row <<endl;
		it++;
	}
	cout << endl;
}
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

匿名对象的临时对象可以调用非const的成员函数

4.const迭代器

const迭代器不能是普通迭代器前加const
const迭代器目标本身可以修改，指向的内容不能修改，类似const T* p

注意：不能在模板参数T前加上const

第一种方式：

template<class T>
class ListConstIterator
{
	typedef ListNode<T> Node;//此处传T的时候就相当于实例化
	typedef ListConstIterator<T> self;
public:
	ListConstIterator(Node* node)//用一个节点的指针来构造
		:_node(node)
	{}
	//++it
	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;
	}



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

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


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

private://成员是一个节点的指针，将指针封装成类来达到我们想要实现的操作
	Node* _node;
};


template<class T>
class list
{
	
public:

	typedef ListNode<T> Node;
	typedef ListIterator<T> iterator;//若T为int相当于实例化了一个int类型的iterator
	typedef ListConstIterator<T> const_iterator;


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

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

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

	const_iterator end()const
	{
		return iterator(_head);
	}
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

第二种方式：不同的模板参数表达的是不同的类，正如vector< int>和vector< double>表达的是两个不同的类

template<class T,class Ref,class Ptr>
class ListIterator
{
	typedef ListNode<T> Node;//此处传T的时候就相当于实例化
	typedef ListIterator<T,Ref,Ptr> self;
public:
	ListIterator(Node* node)//用一个节点的指针来构造
		:_node(node)
	{}
	//++it
	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;
	}



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

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


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

private://成员是一个节点的指针，将指针封装成类来达到我们想要实现的操作
	Node* _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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

5.insert和erase的模拟实现

链表的insert没有迭代器失效，erase迭代器有失效

void push_back(const T& x)//尾插
{
	//Node* newnode = new Node(x);
	//Node* tail = _head->_prev;
	head  2  3   tail  newnode
	//tail->_next = newnode;
	//newnode->_prev = tail;
	//newnode->_next = _head;
	//_head->_prev = newnode;
	insert(--end(), x);
}

iterator insert(iterator pos, const T& x)//插入
{
	//在pos位置之前插入节点
	//随机插入,先获得这个位置的指针
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* newnode = new Node(x);

	//prev  newnode cur  
	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = cur;
	cur->_prev = newnode;
	//匿名对象
	//返回x的下一个节点的迭代器
	return iterator(newnode);
}

iterator erase(iterator pos)//删除
{//删除pos位置的节点
	assert(pos != end());//为1就不断言
	Node* cur = pos._node;
	//prev  cur  next
	Node* prev = cur->_prev;
	Node* next = cur->_next;
	 
	//prev cur next
	prev->_next = next;
	next->_prev = prev;
	delete cur;

	//返回删除位置的下一个迭代器
	return iterator(next);
}
//头插，尾删
//_head(end()) begin()
void pop_back()//尾删
{
	erase(--end());
}

void push_front(const T& x)//头插
{
	insert(begin(), x);
}
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
52
53
54
55
56
57

好啦，今天的内容我们就学习到这里，如果大家觉得阿鑫写的不错的话，记得留下你的一键三连哦，期待我们的下一次相遇！