• 【C++】模拟实现STL容器：list

    需要云服务器等云产品来学习Linux的同学可以移步/-->腾讯云<--/-->阿里云<--/-->华为云<--/官网，轻量型云服务器低至112元/年，新用户首次下单享超低折扣。

     目录

    一、list的介绍

    二、list的排序

    三、迭代器

    1、list的迭代器失效问题

    2、迭代器的功能分类

    3、list迭代器的模拟实现

    3.1普通迭代器

    3.2const迭代器

    3.3反向迭代器

    4、迭代器价值

    5、迭代器operator->的重载

    四、模拟实现时遇到的困惑及注意点

    1、调用拷贝构造时，链表内节点数据为什么已经是深拷贝了？

    2、类名和类型的区别

    五、vector和list的优缺点

    1、vector

    2、list

    六、模拟实现list整体代码

    一、list的介绍

    列表是一种顺序容器，它允许在序列中的任何位置执行常量时间插入和删除操作，并允许在两个方向上进行迭代。

    它的底层是一个带头双向循环链表。附一篇博主用C语言写的带头双向循环链表：【数据结构】带头双向循环链表的实现

    二、list的排序

    list不能用算法库的sort进行排序。算法库中的sort的底层是一个快排，需满足三数取中，需要传入随机访问迭代器，所以list并不适用。

    当然list中提供了一个自己的sort，它的底层是一个归并排序。但是这个sort比vector使用算法库的sort还慢，甚至比list的数据先push_back到vector到再用算法库的sort还要慢。

    三、迭代器

    1、list的迭代器失效问题

    insert，迭代器不失效

    earse失效

    2、迭代器的功能分类

    1、单向迭代器：只能++，不能--。例如单链表，哈希表；

    2、双向迭代器：既能++也能--。例如双向链表；

    3、随机访问迭代器：能++--，也能+和-。例如vector和string。

    迭代器是内嵌类型（内部类或定义在类里）

    3、list迭代器的模拟实现

    3.1普通迭代器

    迭代器的实现需要支持解引用（为了取数据），支持++--。

    博主模拟实现string和vector时，直接将原生指针typedef成迭代器，是因为数组的结构正好满足迭代器的行为（注：string和vector可以用原生指针实现，但是vs中采用自定义类型封装的方式实现），但是list中的节点地址是不连续的，不能使用原生指针，需要使用类进行封装+运算符重载实现。

    1. //用类封装迭代器
    2. template <class T>
    3. struct __list_iterator
    4. {
    5.     typedef list_node node;
    6.     //用节点的指针进行构造
    7.     __list_iterator(node* p)
    8.         :_pnode(p)
    9.     {}
    10.     //迭代器运算符的重载
    11.     T& operator*()
    12.     {
    13.         return _pnode->_data;
    14.     }
    15.     __list_iterator& operator++()//返回值不要写成node* operator++()，因为迭代器++肯定返回迭代器啊，你返回节点指针类型不对
    16.     { 
    17.         //return _pnode->_next;
    18.         _pnode=_pnode->_next;
    19.         return *this;//返回的是迭代器
    20.     }
    21.     bool operator!=(const __list_iterator& it)
    22.     {
    23.         return _pnode != it._pnode;
    24.     }
    25. public:
    26.     node* _pnode;//封装一个节点的指针
    27. };

    3.2const迭代器

    const迭代器的错误写法：

    1. typedef __list_iterator iterator;
    2. const list::iterator it=lt.begin();

    因为typedef后，const修饰的是迭代器it，只能调用operator*(),调不了operator++()。（重载operator++()为const operator++()也不行,因为const版本++还是改变不了）

    正确写法：想实现const迭代器，不能在同一个类里面动脑筋，需要再写一个const版本迭代器的类。

    1. //用类封装const迭代器
    2. template <class T>
    3. struct __list_const_iterator
    4. {
    5.     typedef list_node node;
    6.     //用节点的指针进行构造
    7.     __list_const_iterator(node* p)
    8.         :_pnode(p)
    9.     {}
    10.     //迭代器运算符的重载
    11.     const T& operator*()const
    12.     {
    13.         return _pnode->_data;
    14.     }
    15.     __list_const_iterator& operator++()//返回值不要写成node*，因为迭代器++肯定返回迭代器啊，你返回节点指针类型不对
    16.     {
    17.         //return _pnode->_next;//返回类型错误的
    18.         _pnode = _pnode->_next;
    19.         return *this;//返回的是迭代器
    20.     }
    21.     __list_const_iterator& operator--()
    22.     {
    23.         _pnode = _pnode->_prev;
    24.         return *this;
    25.     }
    26.     bool operator!=(const __list_const_iterator& it)const
    27.     {
    28.         return _pnode != it._pnode;
    29.     }
    30. public:
    31.     node* _pnode;//封装一个节点的指针
    32. };
    33.  
    34. typedef __list_const_iterator const_iterator;

    当然，这样写__list_iterator和__list_const_iterator这两个类会出现代码重复。STL库中是通过类模板多给一个参数来实现，这样，同一份类模板就可以生成两种不同的类型的迭代器（以下为仿STL库的模拟实现）： 

    1. //用类封装普通/const迭代器
    2. template <class T,class Ref>
    3. struct __list_iterator
    4. {
    5.     typedef list_node node;
    6.     typedef __list_iterator Self;
    7.     //用节点的指针进行构造
    8.     __list_iterator(node* p)
    9.         :_pnode(p)
    10.     {}
    11.     //迭代器运算符的重载
    12.     Ref operator*()
    13.     {
    14.         return _pnode->_data;
    15.     }
    16.     Self& operator++()//返回值不要写成node*，因为迭代器++肯定返回迭代器啊，你返回节点指针类型不对
    17.     { 
    18.         //return _pnode->_next;//返回类型错误的
    19.         _pnode=_pnode->_next;
    20.         return *this;//返回的是迭代器
    21.     }
    22.     Self& operator--()
    23.     {
    24.         _pnode = _pnode->_prev;
    25.         return *this;
    26.     }
    27.     bool operator!=(const Self& it)
    28.     {
    29.         return _pnode != it._pnode;
    30.     }
    31. public:
    32.     node* _pnode;//封装一个节点的指针
    33. };
    34.  
    35. typedef __list_iterator iterator;
    36. typedef __list_iteratorconst T&> const_iterator;

    3.3反向迭代器

    1、反向迭代器的底层

    反向迭代器的本质就是对正向迭代器的封装，它是一个适配器。

    STL源码中的反向迭代器的实现：反向迭代器用正向迭代器进行构造。

    1. reverse_iterator rbegin(){return reverse_iterator(end());}
    2. reverse_iterator rend(){return reverse_iterator(begin());}

    画个图，其实正向迭代器和反向迭代器的位置是对称的。

    通过图示，rbegin()迭代器是最后一个数据的下一个位置，但是通过rbegin()访问的数据应该是4，这是通过运算符重载operator*()来解决。

    1. template <class Iterator, class Ref, class Ptr>
    2. Ref operator*()
    3. {
    4.     Iterator tmp = _it;
    5.     return *--(tmp);
    6. }
    7. typedef ReserveIterator reverse_iterator;
    8. typedef ReserveIteratorconst T&, const T*> const_reverse_iterator;

    2、反向迭代器的实现 

    1. namespace jly
    2. {
    3. 	template <class Iterator, class Ref, class Ptr>
    4. 	class ReserveIterator
    5. 	{
    6. 	public:
    7. 		ReserveIterator(Iterator it)//使用正向迭代器构造反向迭代器
    8. 			:_it(it)
    9. 		{
    10.  
    11. 		}
    12. 		Ref operator*()
    13. 		{
    14. 			Iterator tmp = _it;
    15. 			return *--(tmp);
    16. 		}
    17. 		Ptr operator->()//operator->()返回数据的地址
    18. 		{
    19. 			return &(operator*());
    20. 		}
    21. 		ReserveIterator& operator++()//返回值不要写成Iterator，因为反向迭代器++返回的是反向迭代器，不是传入的迭代器类型
    22. 		{
    23. 			--_it;
    24. 			return *this;
    25. 		}
    26. 		ReserveIterator& operator--()
    27. 		{
    28. 			++_it;
    29. 			return *this;
    30. 		}
    31. 		bool operator!=(const ReserveIterator& rit)const
    32. 		{
    33. 			return _it != rit._it;
    34. 		}
    35. 	private:
    36. 		Iterator _it;//底层是传入类型的迭代器
    37. 	};
    38. }

    4、迭代器价值

    1、封装底层实现，不暴露底层实现的细节；

    2、多种容器提供统一的访问方式，降低使用成本；

    C语言没有运算符重载和引用等语法，是实现不了迭代器的。

    5、迭代器operator->的重载

    迭代器的用法就是模拟指针的行为，如果现在有一个指向结构的指针，那么就需要用到->来解引用。

    1. //*的重载：返回节点的数据
    2. Ref operator*()
    3. {
    4.     return _pnode->_data;
    5. }
    6. //->的重载：返回数据的指针
    7. T* operator->()
    8. {
    9.     return &_pnode->_data;
    10. }

    但是operator->使用T*做返回值类型，这样无论是普通迭代器和const迭代器都能修改，所以operator->的返回值类型应该改为泛型：

    1. template <class T, class Ref,class Ptr>
    2. Ptr operator->()
    3. {
    4.     return &_pnode->_data;
    5. }
    6. typedef __list_iterator iterator;
    7. typedef __list_iteratorconst T&, const T*> const_iterator;

    四、模拟实现时遇到的困惑及注意点

    1、调用拷贝构造时，链表内节点数据为什么已经是深拷贝了？

    2、类名和类型的区别

    普通类：类名等于类型

    类模板：类名不等价于类型，例如list类模板类名是list,类型list等。

    所以我们平常写函数形参和返回值时，总会带上形参和返回值的类型：

    1. // 赋值运算符重载
    2. list& operator=(list lt)
    3. {
    4.     swap(lt);
    5.     return *this;
    6. }

    但是C++在类模板里面可以用类名代替类型： 

    1. // 赋值运算符重载写法2(赋值运算符重载都可以这么干)
    2. list& operator=(list lt)
    3. {
    4.     swap(lt);
    5.     return *this;
    6. }

    建议写代码的时候严格区分类型和类名，让自己和别人能够看的很明白。（了解下C++有这种坑语法即可）

    五、vector和list的优缺点

    vector和list像左右手一样，是互补关系，缺一不可。vector的优点正是list的缺点，list的优点也是vector的缺点，实际选用容器时，按照需求择优选用。

    1、vector

    vector的优点（结构牛逼）：

    1、支持下标的随机访问；

    2、尾插尾删效率高（当然扩容的那一次尾插会较慢）；

    3、CPU高速缓存命中高（数据从缓存加载至CPU中，会加载连续的一段数据，vector因为结构连续，高速缓存命中高）。

    vector的缺点：

    1、非尾插尾删效率低；

    2、扩容有消耗，并存在一定的空间浪费。

    vector迭代器失效问题：

    insert/erase均失效。（如果string的insert和erase形参是迭代器，那么也会失效，但是大部分接口是下标传参，不考虑失效问题，只有几个接口是迭代器传参，需要注意迭代器失效问题）

    2、list

    list的优点：

    1、按需申请释放，无需扩容；

    2、任意位置插入删除时间O(1)；（这里说的是插入删除，不要加上查找的时间）

    list的缺点：

    1、不支持下标的随机访问；

    2、CPU高速缓存命中率低；

    3、每一个节点除了存储数据外，还需要额外存储两个指针。

    list迭代器失效问题：

    insert不失效，erase失效。

    六、模拟实现list整体代码

    1. #pragma once
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. using std::cout;
    7. using std::endl;
    8. namespace jly
    9. {
    10. 	//链表节点的类
    11. 	template <class T>
    12. 	struct list_node
    13. 	{
    14. 		list_node(const T& x = T())//给一个缺省值，变成默认构造函数
    15. 			:_next(nullptr)
    16. 			, _prev(nullptr)
    17. 			, _data(x)
    18. 		{}
    19.  
    20. 		list_node* _next;
    21. 		list_node* _prev;
    22. 		T _data;
    23. 	};
    24. 	//用类封装普通/const迭代器
    25. 	template <class T, class Ref,class Ptr>
    26. 	struct __list_iterator
    27. 	{
    28. 		typedef list_node node;
    29. 		typedef __list_iterator Self;
    30. 		//用节点的指针进行构造
    31. 		__list_iterator(node* p)
    32. 			:_pnode(p)
    33. 		{}
    34. 		//迭代器运算符的重载
    35. 		Ref operator*()
    36. 		{
    37. 			return _pnode->_data;
    38. 		}
    39. 		Ptr operator->()
    40. 		{
    41. 			return &_pnode->_data;
    42. 		}
    43. 		Self& operator++()//返回值不要写成node*，因为迭代器++肯定返回迭代器啊，你返回节点指针类型不对
    44. 		{
    45. 			//return _pnode->_next;//返回类型错误的
    46. 			_pnode = _pnode->_next;
    47. 			return *this;//返回的是迭代器
    48. 		}
    49. 		Self operator++(int)//后置++
    50. 		{
    51. 			_pnode = _pnode->_next;
    52. 			return Self(_pnode->_next);
    53. 		}
    54. 		Self& operator--()
    55. 		{
    56. 			_pnode = _pnode->_prev;
    57. 			return *this;
    58. 		}
    59. 		Self operator--(int)//后置--
    60. 		{
    61. 			_pnode = _pnode->_prev;
    62. 			return Self(_pnode->_prev);
    63. 		}
    64. 		bool operator!=(const Self& it)const
    65. 		{
    66. 			return _pnode != it._pnode;
    67. 		}
    68. 		bool operator==(const Self& it)const
    69. 		{
    70. 			return _pnode == it._pnode;
    71. 		}
    72. 	public:
    73. 		node* _pnode;//封装一个节点的指针
    74. 	};
    75. 	//用类封装const迭代器
    76. 	//template 
    77. 	//struct __list_const_iterator
    78. 	//{
    79. 	//	typedef list_node node;
    80. 	//	//用节点的指针进行构造
    81. 	//	__list_const_iterator(node* p)
    82. 	//		:_pnode(p)
    83. 	//	{}
    84. 	//	//迭代器运算符的重载
    85. 	//	const T& operator*()const
    86. 	//	{
    87. 	//		return _pnode->_data;
    88. 	//	}
    89. 	//	__list_const_iterator& operator++()//返回值不要写成node*，因为迭代器++肯定返回迭代器啊，你返回节点指针类型不对
    90. 	//	{
    91. 	//		//return _pnode->_next;//返回类型错误的
    92. 	//		_pnode = _pnode->_next;
    93. 	//		return *this;//返回的是迭代器
    94. 	//	}
    95. 	//	__list_const_iterator& operator--()
    96. 	//	{
    97. 	//		_pnode = _pnode->_prev;
    98. 	//		return *this;
    99. 	//	}
    100. 	//	bool operator!=(const __list_const_iterator& it)const
    101. 	//	{
    102. 	//		return _pnode != it._pnode;
    103. 	//	}
    104. 	//public:
    105. 	//	node* _pnode;//封装一个节点的指针
    106. 	//};
    107. 	//用正向迭代器封装反向迭代器
    108. 	template <class Iterator, class Ref, class Ptr>
    109. 	class ReserveIterator
    110. 	{
    111. 	public:
    112. 		ReserveIterator(Iterator it)//使用正向迭代器构造反向迭代器
    113. 			:_it(it)
    114. 		{
    115.  
    116. 		}
    117. 		Ref operator*()
    118. 		{
    119. 			Iterator tmp = _it;
    120. 			return *--(tmp);
    121. 		}
    122. 		Ptr operator->()//operator->()返回数据的地址
    123. 		{
    124. 			return &(operator*());
    125. 		}
    126. 		ReserveIterator& operator++()//返回值不要写成Iterator，因为反向迭代器++返回的是反向迭代器，不是传入的迭代器类型
    127. 		{
    128. 			--_it;
    129. 			return *this;
    130. 		}
    131. 		ReserveIterator& operator--()
    132. 		{
    133. 			++_it;
    134. 			return *this;
    135. 		}
    136. 		bool operator!=(const ReserveIterator& rit)const
    137. 		{
    138. 			return _it != rit._it;
    139. 		}
    140. 	private:
    141. 		Iterator _it;//底层是传入类型的迭代器
    142. 	};
    143.  
    144. 	//链表类（控制哨兵位）
    145. 	template <class T>
    146. 	class list
    147. 	{
    148. 	public:
    149. 		typedef list_node node;
    150. 		typedef __list_iterator iterator;
    151. 		typedef __list_iteratorconst T&,const T*> const_iterator;
    152. 		typedef ReserveIterator reverse_iterator;
    153. 		typedef ReserveIteratorconst T&, const T*> const_reverse_iterator;
    154.  
    155. 		//typedef __list_const_iterator const_iterator;
    156. 		//构造函数
    157. 		void empty_initialize()//用于初始化哨兵位
    158. 		{
    159. 			_head = new node;
    160. 			_head->_next = _head;
    161. 			_head->_prev = _head;
    162. 			_size = 0;
    163. 		}
    164. 		list()
    165. 		{
    166. 			empty_initialize();
    167. 		}
    168. 		template <class InputIterator>
    169. 		list(InputIterator first, InputIterator last)//迭代器区间构造
    170. 		{
    171. 			empty_initialize();
    172. 			while (first != last)
    173. 			{
    174. 				push_back(*first);
    175. 				++first;
    176. 			}
    177. 		}
    178. 		//析构函数
    179. 		~list()
    180. 		{
    181. 			clear();
    182. 			delete _head;
    183. 			_head = nullptr;
    184. 		}
    185. 		//拷贝构造
    186. 		list(const list& lt)
    187. 		{
    188. 			先初始化*this
    189. 			//empty_initialize();
    190. 			//for (const auto& e : lt)//取lt的数据给e
    191. 			//{
    192. 			//	push_back(e);
    193. 			//}
    194.  
    195. 			//工具人写法
    196. 			list tmp(lt.begin(),lt.end());
    197. 			empty_initialize();
    198. 			swap(tmp);
    199. 		}
    200. 		void swap(list& lt)
    201. 		{
    202. 			std::swap(_head, lt._head);//交换头指针
    203. 			std::swap(_size,lt._size);
    204. 		}
    205. 		赋值运算符重载写法1
    206. 		//list& operator=(const list& lt)
    207. 		//{
    208. 		//	//防止自己给自己赋值
    209. 		//	if (this != <)
    210. 		//	{
    211. 		//		clear();
    212. 		//		for (const auto& e : lt)
    213. 		//		{
    214. 		//			push_back(e);
    215. 		//		}
    216. 		//	}
    217. 		//	return *this;
    218. 		//}
    219. 		// 赋值运算符重载写法2(赋值运算符重载都可以这么干)
    220. 		list& operator=(list lt)
    221. 		{
    222. 			swap(lt);//直接交换
    223. 			return *this;
    224. 		}
    225. 		//插入删除
    226. 		void push_back(const T& x)
    227. 		{
    228. 			/*node* newNode = new node(x);
    229. 			node* tail = _head->_prev;
    230. 			newNode->_prev = tail;
    231. 			newNode->_next = _head;
    232. 			tail->_next = newNode;
    233. 			_head->_prev = newNode;*/
    234. 			insert(end(), x);
    235. 		}
    236. 		void pop_back()
    237. 		{
    238. 			erase(--end());
    239. 		}
    240. 		void push_front(const T& x)//头插
    241. 		{
    242. 			insert(begin(), x);
    243. 		}
    244. 		void pop_front()
    245. 		{
    246. 			erase(begin());
    247. 		}
    248. 		iterator insert(iterator pos, const T& x)
    249. 		{
    250. 			node* newNode = new node(x);
    251. 			node* prev = pos._pnode->_prev;
    252. 			node* cur = pos._pnode;
    253. 			newNode->_prev = prev;
    254. 			newNode->_next = cur;
    255. 			prev->_next = newNode;
    256. 			cur->_prev = newNode;
    257. 			//return iterator(newNode);
    258. 			pos._pnode = newNode;
    259. 			++_size;
    260. 			return pos;
    261. 		}
    262. 		iterator erase(iterator pos)
    263. 		{
    264. 			assert(!empty());
    265. 			node* prev = pos._pnode->_prev;
    266. 			node* next = pos._pnode->_next;
    267. 			prev->_next = next;
    268. 			next->_prev = prev;
    269. 			delete pos._pnode;
    270. 			--_size;
    271. 			//return iterator(next);
    272. 			pos._pnode = next;
    273. 			return pos;
    274. 		}
    275. 		//链表小接口
    276. 		bool empty()const
    277. 		{
    278. 			return _head->_next == _head;
    279. 		}
    280. 		void clear()
    281. 		{
    282. 			/*assert(!empty);
    283. 			node* cur = _head->_next;
    284. 			while (cur != _head)
    285. 			{
    286. 				node* next = cur->_next;
    287. 				delete cur;
    288. 				cur = next;
    289. 			}*/
    290. 			iterator it = begin();
    291. 			while (it != end())
    292. 			{
    293. 				it = erase(it);//erase返回删除元素的下一个
    294. 			}
    295. 		}
    296. 		size_t size()const
    297. 		{
    298. 			return _size;
    299. 		}
    300. 		//普通begin(),end()迭代器
    301. 		iterator begin()
    302. 		{
    303. 			//return iterator(_head->_next);
    304. 			return __list_iterator(_head->_next);
    305. 		}
    306. 		iterator end()
    307. 		{
    308. 			return __list_iterator(_head);
    309. 		}
    310. 		//const begin(),end()迭代器
    311. 		const_iterator begin()const
    312. 		{
    313. 			//return const_iterator(_head->_next);
    314. 			return __list_iteratorconst T&,const T*>(_head->_next);
    315. 		}
    316. 		const_iterator end()const
    317. 		{
    318. 			return __list_iteratorconst T&,const T*>(_head);
    319. 		}
    320. 		reverse_iterator rbegin()
    321. 		{
    322. 			return reverse_iterator(end());
    323. 		}
    324. 		reverse_iterator rend()
    325. 		{
    326. 			return reverse_iterator(begin());
    327. 		}
    328. 	private:
    329. 		node* _head;//哨兵位
    330. 		size_t _size;//用于统计节点个数，空间换时间
    331. 		//不加这个私有变量，统计节点个数时间O(N),有这个私有变量，时间O(1),但是每个节点的体积变大
    332. 	};
    333.  
    334.  
    335. 	//测试函数
    336. 	struct Pos
    337. 	{
    338. 		int _row;
    339. 		int _col;
    340.  
    341. 		Pos(int row = 0, int col = 0)
    342. 			:_row(row)
    343. 			, _col(col)
    344. 		{}
    345. 	};
    346. 	void test()
    347. 	{
    348. 		list i;
    349. 		i.push_back(Pos(1, 2));
    350. 		i.push_back(Pos(2, 5));
    351. 		i.push_back(Pos(4, 3));
    352. 		list::iterator it = i.begin();
    353. 		while (it != i.end())
    354. 		{
    355. 			cout << (&( * it))->_row;//*it取数据，再取地址、解引用得到_row,多此一举
    356. 			cout << it->_row;//同第三种写法，编译器为了可读性，省略了一个->
    357. 			cout << it.operator->()->_row;//it.operator->()是显示调用，->_row是解引用得到_row
    358. 			it++;
    359. 		}
    360. 	}
    361. 	void test1()
    362. 	{
    363. 		list<int> i;
    364. 		i.push_back(1);
    365. 		i.push_back(2);
    366. 		i.push_back(3);
    367. 		list<int>::iterator it = i.begin();
    368. 		while (it != i.end())
    369. 		{
    370. 			cout << *it << " ";
    371. 			++it;
    372. 		}
    373. 		cout << endl;
    374. 		list<int>::reverse_iterator rit = i.rbegin();
    375. 		while (rit != i.rend())
    376. 		{
    377. 			cout << *rit << " ";
    378. 			++rit;
    379. 		}
    380. 	}
    381. }
  • 相关阅读:
    2022北京国际养老产业展览会/北京养老展/养老用品展11月
    LiteOS-M内核
    我不建议你使用SELECT *
    css基本样式之字体样式
    Linux的权限管理操作
    【Linux】Linux 之用户管理
    Oracle数据库基础
    Mac电脑idea中配置nodejs前端环境
    toRefs
    Acwing 2944. 回家的路
  • 原文地址：https://blog.csdn.net/gfdxx/article/details/128195342