devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【STL】list的模拟实现

作者：从前慢现在也慢 | 2024-04-15 11:33:23

赞

踩

【STL】list的模拟实现

目录

前言 

list概述

list的节点

list的迭代器 

list的结构 

构造与析构

拷贝构造与赋值

list的元素操作 

insert()

push_back() 

 push_front()

erase() 

pop_back()

pop_front()

clear()

swap()

size()

完整代码链接 

前言 

如果你对链表还不熟悉或者忘了的话，建议你可以回去复习一下或者看一下这篇文章：双向链表

如果你没看过前几篇vector的模拟实现和string的模拟实现也建议可以去看看，因为这里有些内容在前面讲过了，所以解释的篇幅就比较少了。

如果内容有错，还望指出

希望本篇文章能对你学习STL有所帮助。

list概述

相较于vector，list就显得复杂许多，它的好处是每次插入或删除一个元素，就配置或释放一个元素空间。list的底层其实是一个双向链表的结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素，所以list是可以在常数范围内的任意位置进行插入和删除的序列式容器，并且可以前后迭代。但是list的最大的缺陷是不支持任意位置的随机访问。

list的节点

list本身和list节点的结构是不同的，所以我们需要分开写，下面是list的节点结构，很明显它是个双向链表。

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

list的迭代器 

可以说list的精华就在这迭代器上。list的迭代器的设计不能再向vector一样用个普通指针作为迭代器，因为对于链表来每个节点之间空间是不连续的，并且我们必须要让list的迭代器正确的指向list的节点，并且能够完成迭代器的一系列操作（取值、++、--等）。

所以我们的list迭代器初步设计如下

  1.     template <class T>
  2. 	struct __list_iterator
  3. 	{
  4. 		typedef list_node<T> Node;
  5. 		typedef __list_iterator<T> iterator;
  6.  
  7. 		Node* _node;
  8.  
  9.         //初始化
  10. 		__list_iterator(Node* node)
  11. 			:_node(node)
  12. 		{}
  13.  
  14. 		bool operator!=(const iterator& it)const
  15. 		{
  16. 			return _node != it._node;
  17. 		}
  18.  
  19. 		bool operator==(const iterator& it)const
  20. 		{
  21. 			return _node == it._node;
  22. 		}
  23.  
  24. 		//*it
  25. 		T& operator*()
  26. 		{
  27. 			return _node->_data;
  28. 		}
  29.  
  30. 		//it->
  31. 		T* operator->()
  32. 		{
  33. 			return &(operator*());
  34. 		}
  35.  
  36. 		//++it
  37. 		iterator& operator++()
  38. 		{
  39. 			_node = _node->_next;
  40. 			return *this;
  41. 		}
  42.  
  43. 		//it++
  44. 		iterator& operator++(int)
  45. 		{
  46. 			iterator tmp(*this);
  47. 			_node = _node->_next;
  48. 			return tmp;
  49. 		}
  50.  
  51. 		//--it
  52. 		iterator& operator--()
  53. 		{
  54. 			_node = _node->_prev;
  55. 			return *this;
  56. 		}
  57.  
  58. 		//it--
  59. 		iterator& operator--(int)
  60. 		{
  61. 			iterator tmp(*this);
  62. 			_node = _node->_prev;
  63. 			return tmp;
  64. 		}
  65. 	};

为了前置++和后置++、前置--和后置--之间能构成函数重载，所以我们需要在参数上动手脚，我这里在参数上就加了个int，包括源码中也是这样实现的。

对于->访问，源码里的实现并结合对应的场景来看，就有点让人难以看懂了

  1. struct Coord
  2. {
  3. 	Coord(int a1 = 0, int a2 = 0)
  4. 		:_a1(a1)
  5. 		,_a2(a2)
  6. 	{}
  7. 	int _a1;
  8. 	int _a2;
  9. };
  10.  
  11. int main()
  12. {
  13. 	hjx::list<Coord> lt;
  14. 	lt.push_back(Coord(10, 20));//匿名对象
  15. 	lt.push_back(Coord(21, 11));//匿名对象
  16. 	auto it = lt.begin();
  17. 	while (it != lt.end())
  18. 	{
  19. 		cout << it->_a1 << ":" << it->_a2 << endl;
  20. 		it++;
  21. 	}
  22. 	return 0;
  23. }

其实这里为了语言的可读性，编译器做了特殊处理，省略了一个->，所以没做特殊处理前应该是这样写的：it->->_a1，前一个->是调用了it.operator->()。

基于上面的迭代器的设计，对于const迭代器我们需要在operator*()和operator->()返回值加上const，但是这样写的话只有返回值不同不构成重载，当然你可以为const迭代器重新弄一个类出来。我们可以看看源码中是怎样设计的

源码中把T&和T*单领出来进行模板的实例化，如果模板实例化出const类型那这个迭代器就是const迭代器。

所以我们将迭代器重新设计如下

  1.     template<class T, class Ref, class Ptr>
  2. 	struct __list_iterator
  3. 	{
  4. 		typedef list_node<T> Node;
  5. 		typedef __list_iterator<T, Ref, Ptr> iterator;
  6.  
  7. 		Node* _node;
  8.  
  9. 		__list_iterator(Node* node)
  10. 			:_node(node)
  11. 		{}
  12.  
  13. 		bool operator!=(const iterator& it)const
  14. 		{
  15. 			return _node != it._node;
  16. 		}
  17.  
  18. 		bool operator==(const iterator& it)const
  19. 		{
  20. 			return _node == it._node;
  21. 		}
  22.  
  23. 		//*it
  24. 		Ref operator*()
  25. 		{
  26. 			return _node->_data;
  27. 		}
  28.  
  29. 		//it->
  30. 		Ptr operator->()
  31. 		{
  32. 			return &(operator*());
  33. 		}
  34.  
  35. 		//++it
  36. 		iterator& operator++()
  37. 		{
  38. 			_node = _node->_next;
  39. 			return *this;
  40. 		}
  41.  
  42. 		//it++
  43. 		iterator& operator++(int)
  44. 		{
  45. 			iterator tmp(*this);
  46. 			_node = _node->_next;
  47. 			return tmp;
  48. 		}
  49.  
  50. 		//--it
  51. 		iterator& operator--()
  52. 		{
  53. 			_node = _node->_prev;
  54. 			return *this;
  55. 		}
  56.  
  57. 		//it--
  58. 		iterator& operator--(int)
  59. 		{
  60. 			iterator tmp(*this);
  61. 			_node = _node->_prev;
  62. 			return tmp;
  63. 		}
  64. 	};

list的结构 

  1.     template<class T>
  2. 	class list
  3. 	{
  4. 		typedef list_node<T> Node;
  5. 	public:
  6. 		//迭代器
  7. 		typedef __list_iterator<T, T&, T*> iterator;
  8. 		typedef __list_iterator<T, const T&, const T*> const_iterator;
  9. 		iterator begin()
  10. 		{
  11. 			return iterator(_head->_next);
  12. 		}
  13.  
  14. 		iterator end()
  15. 		{
  16. 			return iterator(_head);
  17. 		}
  18.  
  19. 		const_iterator begin()const
  20. 		{
  21. 			return const_iterator(_head->_next);
  22. 		}
  23.  
  24. 		const_iterator end()const 
  25. 		{
  26. 			return const_iterator(_head);
  27. 		}
  28. 		
  29. 	private:
  30. 		Node* _head;
  31. 	};

 list在源码中的实现其实就是带头节点的双向循环链表

构造与析构

 构造函数

对于只有一个哨兵位来说的话只要让next和prev都指向自己就好了。

  1. 		//对哨兵位的头结点进行初始化
  2. 		void empty_Init()
  3. 		{
  4. 			_head = new Node;
  5. 			_head->_next = _head;
  6. 			_head->_prev = _head;
  7. 		}
  8. 		
  9. 		list()
  10. 		{
  11. 			empty_Init();
  12. 		}
  13.  
  14. 		//迭代器区间构造
  15. 		template<class Inputiterator>
  16. 		list(Inputiterator first, Inputiterator last)
  17. 		{
  18. 			empty_Init();
  19. 			while (first != last)
  20. 			{
  21. 				push_back(*first);
  22. 				first++;
  23. 			}
  24. 		}

析构函数 

调用clear函数就行，最后不要忘记哨兵位也要释放掉。 

  1. 		~list()
  2. 		{
  3. 			clear();
  4. 			delete _head;
  5. 			_head = nullptr;
  6. 		}

拷贝构造与赋值

这里就提供现代的写法啦，毕竟现代写法更简单。

有些细心的同学可能在C++文档中看到拷贝构造的接口时会省略掉模板参数，这是被C++所允许的，在类里面可以这样，但在类外可不能省略。建议初学者还是不要去省略这里的模板参数了。

 

  1. 		list(const list<T>& lt)
  2. 		{
  3. 			empty_Init();
  4. 			list<T> tmp(lt.begin(), lt.end());
  5. 			swap(tmp);
  6. 		}
  7.  
  8. 		list<T>& operator=(list<T> lt)
  9. 		{
  10. 			swap(lt);
  11. 			return *this;
  12. 		}

list的元素操作 

如果你数据结构学的非常扎实的话，这部分内容对你来说应该是小菜一碟。 

insert()

  1.         iterator insert(iterator pos, const T& x)
  2. 		{
  3. 			Node* cur = pos._node;
  4. 			Node* prev = cur->_prev;
  5.  
  6. 			Node* newnode = new Node(x);
  7.  
  8. 			prev->_next = newnode;
  9. 			newnode->_prev = prev;
  10. 			newnode->_next = cur;
  11. 			cur->_prev = newnode;
  12.  
  13. 			return iterator(newnode);
  14. 		}

push_back() 

  1.         void push_back(const T& x)
  2. 		{
  3. 			insert(end(), x);
  4. 		}

 push_front()

  1.         void push_front(const T& x)
  2. 		{
  3. 			insert(begin(), x);
  4. 		}

erase() 

  1.         iterator erase(iterator pos)
  2. 		{
  3. 			assert(pos != end());
  4. 			Node* cur = pos._node;
  5. 			Node* next = cur->_next;
  6. 			Node* prev = cur->_prev;
  7.  
  8. 			prev->_next = next;
  9. 			next->_prev = prev;
  10.  
  11. 			delete cur;
  12.  
  13. 			return iterator(next);
  14. 		}

pop_back()

  1.         void pop_back()
  2. 		{
  3. 			erase(--end());
  4. 		}

pop_front()

  1.         void pop_front()
  2. 		{
  3. 			erase(begin());
  4. 		}

clear()

  1.         void clear()
  2. 		{
  3. 			//写法一
  4. 			//Node* cur = _head->_next;
  5. 			头删
  6. 			//while (cur != _head)
  7. 			//{
  8. 			//	_head->_next = cur->_next;
  9. 			//	delete cur;
  10. 			//	cur = _head->_next;
  11. 			//}
  12. 			//_head->_next = _head->_prev = nullptr;
  13.  
  14. 			//写法二
  15. 			iterator it = begin();
  16. 			while (it != end())
  17. 			{
  18. 				it = erase(it);//erase返回的是下一个位置的迭代器
  19. 			}
  20. 		}

swap()

  1. 		void swap(list& x)
  2. 		{
  3. 			std::swap(_head, x._head);
  4. 		}

size()

  1. 		size_t size()const
  2. 		{
  3. 			Node* cur = _head->_next;
  4. 			size_t count = 0;
  5. 			while (cur != _head)
  6. 			{
  7. 				count++;
  8. 				cur = cur->_next;
  9. 			}
  10.  
  11. 			return count;
  12. 		}

 关于其它函数有兴趣可以自己动手去实现一下，这里就不在展示了。

完整代码链接 

代码链接：list

源码链接：STL源码 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/427640
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号