C++ List底层实现

---

前言

我们都清楚c++中的容器list，本质上就是一个带头双向循环链表，接下来我们实现一下list的底层，帮助我们更深层次的了解list的结构和使用

成员变量

我们知道这个节点有三部分构成 _prev,_next,_val;每个节点看作list的一个元素，这又是一个双向带头循环链表，那么我们如果仅仅知道头节点，就可以访问遍历链表中的所有元素。

//类模板
template < class T>
struct ListNode
{
ListNode(const T& val=T()) //初始化
:_prev(nullptr)
,_next(nullptr)
,_data(val)
{ }
ListNode* _prev;//指向前一个元素
ListNode* _next;//指向后一个元素
T _data;//当前节点的值
};

有了这个结点之后，我们在实现list是创建一个头节点就可以控制这个链表了

template
class list
{
    //模板+类–》类型
    typedef ListNode Node;
private:
    Node* _head;
};

在class类中，默认为私有的，在struct中默认为公有，只有将这个节点定义为公有，我们才可以访问。

那这里采用内部类的方法不行吗？？
答案是不行的，如果我们吧struct定义在内部类中，外部list类就无法访问struct中的元素了。

成员函数

迭代器

我们在实现vector中，迭代器我们并没有实现，或者说我们不需要实现，因为vector容容器的结构很特殊，是一块连续的物理空间。加加，解引用等方式很容易实现。

我们看一下迭代器，是一个个地址不连续的指针

那我们怎末实现呢
我们很清楚迭代器的实质就是一个指针，在这个list中就是哟个listNode的指针。
我们要实现迭代器的操作，可以采用运算符重载的方式实现，但是这里又出现了新的问题，迭代器是一个内置类型，只有自定义类型才可以实现自定义类型重载，所以我们需要都这个指针进行封装，变成一个自定义类型

template< class T >
struct ___list_iterator
{
  typedef ListNode< T> Node;//方便我们使用
  typedef ___list_iterator< T> self;//方便使用，我们会用到
  ___list_iterator(Node* x)//初始化
    :_node(x)
    {}
  Node* _node;//成员变量
};

在这里面实现我们需要的功能，

list::const_iterator it = lt.begin();
while (it != lt.end())
{
std::cout << *it << " ";
++it;
}
std::cout << std::endl;

我们需要实现前置++,后置++,前置- -，后置- -，解引用，判断是否相等。我们依此来看一下

self& operator++()前置++

self& operator++()//++返回的是一个
{
   _node = _node->_next;//我们仅需要让指针往后移动一个节点就可以
  return *this;
}

self operator++(int)后置++

这里只能用self,不能用self&，因为返回的是一个临时对象
self operator++(int)//后置++也是返回一个节点，
{
  self tmp(*this);//首先拷贝一份
  _node = _node->next;//指针向后移动一个节点
  return tmp;//返回拷贝的值
}

self operator–()前置–

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

self operator–(int)后置–

self operator–(int)
{
  self tmp(*this);
   _node = _node->perv;
   return tmp;
}

bool operator!=(const self & tmp)判断是否相等

bool operator!=(const self & tmp)
{
   return _node != tmp._node;//判断两个指针是否指向同一块空间就可以
}

T* operator*() 解引用操作

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

list()初始化

list()
{
   我们初始化仅仅初始化头节点就可以
   empty_list();//我们可以通过调用这个函数创建头节点
}
void empty_list()
{
   _head = new Node;
   _head->_next = _head;
   _head->_prev = _head;
}

iterator begin()

iterator begin()
{
   return _head->_next;//第一个元素就是头节点后面的那个元素
}

iterator end()

iterator end()
{
   return _head;//最后一个元素的下一个就是head
}

const_iterator begin()const

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

const_iterator end()const

const_iterator end()const
{
   return _head;
}

iterator insert(iterator pos, const T& val)在pos位置插入val

iterator 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;
   return newnode;//返回新节点
}

我们来看一下这里的insert有没有迭代器失效的问题？？

void push_back(const T& val)在尾部位置后插入

void push_back(const T& val)
{
   insert(end(), val);//我们可以直接进行复用
}

void push_front(const T& val)在头部位置插入

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

iterator erase(iterator pos)

iterator erase(iterator pos)
{
   assert(pos != end());//断言一下，不是删除头节点
   Node* cur = pos._node;//取到迭代器中的元素
   Node* prev = cur->_prev;//记录前一个位置
   Node* next = cur->_next;//记录后一个位置
   delete cur;//释放当前元素
   prev->_next = next;//改变指向
   next->_prev = prev;
   return next;//返回删除元素的下一个位置
}

我们来看一下这里会不会有迭代器失效的问题??
我们发现这里存在迭代器失效的问题，并且很大，这个元素删除了之后，之后很可能还需要用到这个元素，继续删除，如果不及时更新，就会出现大问题。

void pop_back()//删除最后一个元素

void pop_back()
{
   erase(–end());//我们要注意end是哪个位置
}

void pop_front()删除第一个元素

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

list(list& tmp)拷贝构造

在这里我们有很多方式实现，我们来看一种比较简单的
list(list< T>& tmp)
{
   empty_list();//首先创建一个头节点
   //遍历
   for (const auto& e : tmp)
   {
   push_back(e);//取数据依次插入这个新的头结点中
   }
}

void swap(list&tmp)交换两个list

void swap(list< int>&tmp)
{
   std::swap(_head, tmp._head);//我们仅仅改变两个list的指针就可以
}

list< T>& operator=(list< T> it)赋值

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

我们再来看一下这个过程，我们假设lt1=lt2;
因为list< T> it这里，lt2会产生一份临时拷贝it

我们swap(it)，本质就是将it与lt1的内容进行交换

it是临时变量，出了作用域就销毁了，我们就完成了赋值任务

int size()判断有多少元素

int size()
{
   int count = 0;//记录一个变量，一个个统计即可
   for (const auto& e : *this)
   {
   count++;
   }
   return count;
}

bool empty() 判断list是否为空

bool empty()
{
   return size() == 0;//我们只需要判断list是否有元素
}

T& front()取首元素

T& front()
{
   return _head->_next->_data;
}

T& back()取尾元素

T& back()
{
   return _head->_prev->_data;
}

void clear()清空元素

一个个删除元素即可
void clear()
{
   iterator it = begin();
   while (it != end())
   {
   it = erase(it);
   }
}

~list()析构

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

再谈迭代器

我们已经实现了普通迭代器，但是对于const都迭代器，我们还需要实现。
我们再来看一下const迭代器，并不是这个迭代器指针不可以修改，而是迭代器指针所指向的内容不可以修改。
那我们是不是可以在普通迭代器的基础上再新增一个const迭代器，我们仅需要修改解引用的那块操作就可以，其他实现的功能都是相同的。

template<class T >
struct ___list_const_iterator
{
	typedef ListNode<T>  Node;
	typedef ___list_const_iterator<T> self;
	___list_const_iterator(Node* x)
		:_node(x)
	{}
	//不等于
	bool operator!=(const self& tmp)
	{
		return _node != tmp._node;
	}
	//解引用
	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);
		_node = _node->perv;
		return tmp;
	}
	//需要返回一个地址
	T* operator->()
	{
		return &_node->_data;
	}

	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

虽然这样可以完成我们的功能，但是总感觉代码有点冗余，const迭代器和普通迭代器有太多重复内容，那我们可不可以通过一种方法将这两种迭代器进行合并呢？？

我们来看一下！！！
我们注意到，const T& operator*()和T& operator*()仅仅是返回值不同，我们又不能把两个方法放在同一个迭代器中，我们可以利用传参的方式进行解决，我们来看一下这种操作

模板传递的是类型，根据传参的不同调用自己合适的模板参数，这两个是完全不同的类型，我们这样就可以轻松完成我们的工作，仅仅使用一个迭代器就完成了两个功能

完整代码

namespace peng
{
	template <class T>
	struct ListNode
	{
		ListNode(const T& val=T())
			:_prev(nullptr)
			,_next(nullptr)
			,_data(val)
		{	}
		ListNode* _prev;
		ListNode* _next;
		T _data;
	};
	//
	//迭代器
	//不连续,
	template<class T,class Ref  >
	struct ___list_iterator
	{
		typedef ListNode<T>  Node;
		typedef ___list_iterator<T,Ref> self;
		___list_iterator(Node* x)
			:_node(x)
		{}
			//不等于
			bool operator!=(const self & tmp)
			{
				return _node != tmp._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);
				_node = _node->perv;
				return tmp;
			}
			//需要返回一个地址
			T* operator->()
			 {
				return &_node->_data;
				
			 }
		
	    Node* _node;
	};


	//默认私有
	template<class T>
	class list
	{
		//模板+类--》类型
		typedef ListNode<T> Node;
	public:
	//	typedef ___list_iterator<T, T&,T*> iterator;
	//	typedef ___list_iterator<T, const T&,const T*> const_iterator;

	 	typedef ___list_iterator<T,T&> iterator;
		typedef ___list_iterator<T,const T&>  const_iterator;

		list()
		{			empty_list();
		}
		void empty_list()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}
		//l1(l2)
		list(list<T>& tmp)
		{
			empty_list();
			//遍历
			for (const auto& e : tmp)
			{
				push_back(e);
			}
		}
		iterator begin()
		{
			return _head->_next;
		}
		iterator end()
		{
			return _head;
		}
		const_iterator begin()const
		{
			return _head->_next;
		}
		const_iterator end()const
		{
			return _head;
		}
		void swap(list<int>&tmp)
		{
			std::swap(_head, tmp._head);
		}
		list<T>&  operator=(list<T> it)
		{
			swap(it);
			return *this;
		}
		int size()
		{
			int count = 0;
			for (const auto& e : *this)
			{
				count++;
			}
			return count;
		}
		bool empty()
		{
			return size() == 0;
		}
		iterator 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;
			return newnode;
		}
		void push_back(const T& val)
		{
			insert(end(), val);
		}
		void push_front(const T& val)
		{
			insert(begin(), val);
		}
		iterator erase(iterator pos)
		{
			assert(pos != end());
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;
			delete cur;
			prev->_next = next;
			next->_prev = prev;
			return next;
		}
		T& front()
		{
			return _head->_next->_data;
		}
		T& back()
		{
			return _head->_prev->_data;
		}
		void pop_back()
		{
			erase(--end());
		}

		void pop_front()
		{
			erase(begin());
		}
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}
	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
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
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205

总结

以上就是今天要讲的内容，本文仅仅详细介绍了C++list的模拟实现，希望对大家的学习有所帮助，仅供参考 如有错误请大佬指点我会尽快去改正 欢迎大家来评论~~