C++的list

首先我们要理清list的结构,库里面的list是双向链表,我们要模拟实现时要特别注意链表的迭代器,因为链表的底层结构空间是不连续的,所以不像vector那样直接++就能找到下一个数据存放的地址。我们要想实现++或–这种,就要求我们要对迭代器进行重载,因此我们在实现时不仅要定义一个list类,还要定义一个迭代器类。此外,list中的成员变量是每一个节点,我们也要对定义一个节点类,节点中就存放对应的数据,以及前后指针。

节点类

template<class T>
struct list_node
{
	list_node* _prev;
	list_node* _next;
	T _val;

	list_node(const T& val = T())
		:_next(nullptr)
		,_prev(nullptr)
		,_val(val)
	{

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

节点类中存放的是数据,以及每一个节点的前后指针。
注意这里的构造函数给的默认值为val = T(),给了一个匿名对象,如果是自定义类型,它就会调用对应的自定义类型的构造函数,当它为内置类型时也会调用它对应的构造函数,这里你可能会有疑问,内置类型不是没有默认构造函数吗?这是因为C++11对这里进行了特殊处理,内置类型也给了默认构造函数。

迭代器类

//迭代器对象
//template 
template <class T, class Ref, class Ptr>
struct __list_iterator
{
	typedef list_node<T> Node;
	//typedef __list_iterator iterator;
	//typedef __list_iterator 		const_iterator;
	typedef __list_iterator<T, Ref, Ptr> self;
	
	Node* _node;

	__list_iterator(Node* node)
		:_node(node)
	{

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

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

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

	self& operator++()
	{
		_node = _node->_next;
		return *this;
	}

	self& operator++(int)
	{
		__list_iterator<T> tmp(*this);
		_node = _node->_next;
		return tmp;
	}

	self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}

	self& operator--(int)
	{
		__list_iterator<T> tmp(*this);
		_node = _node->_prev;
		return tmp;
	}

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

	bool operator==(const self& it) const
	{
		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
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

初次看到这个迭代器类,你会感到很茫然,为什么要给三个模板参数,并且这三个模板参数,在学习后你发现这三个模板参数T都是相同的,不过是T,T*,T&,直接返回函数对应的这三个类型之一不就行了吗?为什么要给三个呢?
这是因为我们在定义const对象迭代器时,如果只给一个模板参数就不能达到我们的要求

typedef __list_iterator<T> iterator;
typedef const __list_iterator<T> const_iterator;
1
2

我们期望的是这个迭代器指向的内容不能发生改变,这样设计是让迭代器本身不能被修改,与我们的要求不符。
1.const T* p;
2.T* const p;
我们期望得到的是第一种结果,迭代器指针还要进行++或–等操作,如果直接在前面加const就是让这个指针的指向不能被改变,我们要做的是让p指向的内容不被改变,即*this不被改变。
因此我们在设计const迭代器时就要直接给参数列表,作为对应的返回类型。

list类的实现

定义节点为Node

typedef list_node<T> Node;
1

定义const迭代器和普通迭代器

typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
1
2

在定义对应类型的变量时,自动调用并实例化对应的迭代器类

template<class T>
class list
{
	typedef list_node<T> Node;
public:
	//typedef __list_iterator iterator;
	typedef __list_iterator<T, T&, T*> iterator;
	typedef __list_iterator<T, const T&, const T*> const_iterator;
	//下面这样设计const迭代器是不行的,因为const迭代器期望指向的内容不能被修改,迭代器本身能被修改
	//typedef const list_node const_iterator;

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

		_size = 0;
	}

	list()
	{
		empty_init();
	}

	/*list(list& lt)
	{
		empty_init();

		for (auto e : lt)
		{
			push_back(e);
		}
	}*/

	list(const list<T>& lt)
	{
		empty_init();

		for (auto& e : lt)
		{
			push_back(e);
		}
	}

	void swap(list<T> lt)
	{
		::swap(_head, lt._head);
		::swap(_size, lt._size);
	}

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

	~list()
	{
		clear();

		delete _head;
		_head = nullptr;
	}

	void clear()//清数据但不清哨兵位
	{
		iterator it = begin();
		while (it != end())
		{
			it = erase(it);
		}

		_size = 0;
	}

	iterator begin()
	{
		//return _head->_next;//两种都可以,这种属于单参数支持隐式类型转换
		return iterator(_head->_next);
	}

	iterator end()
	{
		//return _head->_prev;
		return iterator(_head);
	}

	const_iterator begin() const
	{
		//return _head->_next;//两种都可以,这种属于单参数支持隐式类型转换
		return const_iterator(_head->_next);
	}

	const_iterator end() const
	{
		//return _head->_prev;
		return const_iterator(_head);
	}

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

		newnode->_val = val;*/

		insert(end(), x);
	}

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

	void pop_back()
	{
		erase(--end());
	}

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

	//在pos之前插入
	iterator insert(iterator pos, const T& x)
	{
		Node* cur = pos._node;
		Node* prev = cur->_prev;
		Node* newnode = new Node(x);

		prev->_next = newnode;
		newnode->_next = cur;

		cur->_prev = newnode;
		newnode->_prev = prev;

		++_size;

		return newnode;
	}

	iterator erase(iterator pos)
	{
		assert(pos != end());
		Node* cur = pos._node;
		Node* prev = cur->_prev;
		Node* next = cur->_next;

		prev->_next = next;
		next->_prev = prev;

		--_size;

		delete cur;
		return next;
	}

	size_t size()
	{
		return _size;
	}


private:
	Node* _head;//指向头结点
	size_t _size;
};

//template
void Print(const list<int>& lt)
{
	sw::list<int>::const_iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		++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
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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186

迭代器失效

前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

总结

list中成员变量是头节点指针以及节点个数_size,因此我们要声明一个节点类,每个节点中放的是当前节点的数据值和前后指向的指针,在对list成员函数进行实现时要用到迭代器,以往我们的迭代器不需要再单独实现,因为那时的数据结构底层的地址是连续的,可以对指针进行直接++或–,因此我们要额外实现迭代器,而迭代器分为const迭代器和普通迭代器,如果我们直接选择在迭代器本身前加const,就是让迭代器本身不能进行++或–,而我们想要的是迭代器这个指针指向的内容不被改变,而不是这个迭代器指针指向不能被改变,因此这样是行不通的,所以我们选择多个模板参数,且这些模板参数有const的和普通的,再把这些类typedef成const_iterator和_iterator,在选择对应的类时,就会去实例化出相应的类。