• C++学习之list的实现

    在了解学习list实现之前我们首先了解一下关于迭代器的分类：

    按功能分类：

    正向迭代器    反向迭代器

    const正向迭代器  const反向迭代器

    按性质分类：

    单向迭代器      只能++    例如单链表

     双向迭代器     可++，也可--     例如双链表 ，map和set

     随机迭代器     可加加，可减减，可+，可减  如顺序表（vector string）,deque(双端队列)

    这些都是由容器的底层实现。

    可以看到库中提供的list模板是带头双向链表，故此我们实现它就大部分操作都是在数据结构中实现双链表时是一样。

    目录

    1.成员变量

    节点类型的定义：

    迭代器

    重载前置++/--

    重载后置++/--

    重载*与->

    重载!=与==

    const迭代器

    迭代器的优化：

    反向迭代器 

    const反向迭代器 

    成员函数

    构造函数

    析构函数

    拷贝构造函数

    容量

    size

    修饰符 

    insert()

    erase ()

    push_front()

    pop_front()

    push_back()

    pop_back()

    clear()

    1.成员变量

    1. template<class T>class mylist
    2. 	{
    3.         typedef list_node<T>  Node;
    4. 		typedef _list_iterator<T, T&, T*> iterator;
    5. 		typedef _list_iterator<T,const T&,const T*> const_iterator;
    6. private:
    7. 		Node* _head;
    8. 		size_t _size;
    9. ......
    10. }

    因为实现的是链表，故此我们的成员变量是链表头节点与链表的大小，这里我们还需要给出

    节点类型的定义：

    1. typedef list_node<T>  Node;
    2. template<class T>struct list_node
    3. 	{
    4. 		//我们给一个缺省值为T的匿名对象
    5. 		list_node(const T& x = T())
    6. 			:data(x)
    7. 			, _next(nullptr)
    8. 			, _prev(nullptr)
    9. 		{}
    10. 		T data;
    11. 		list_node<T>* _next;
    12. 		list_node<T>* _prev;
    13. 	};

    迭代器

    因为我们实现的是链表，那么迭代器的操作也就是链表节点的操作，节点并非一般的数据类型，

    故此我们这里需要封装迭代器，迭代器本质是节点的地址：

    1. //迭代器
    2. 	//认真思考的话，迭代器模拟的是一个双链表节点的运动，故我们封装迭代器里面一定是节点，这里放入节点的地址
    3. 	//并且重载对应的运算符，封装之后，我们在定义为iterator
    4. 	template<class T>struct _list_iterator
    5. 	{
    6. 		//利用节点的指针实现迭代器
    7. 		typedef list_node<T>  Node;
    8. 		typedef _list_iterator<T> self;
    9. 		Node* _node;
    10.         _list_iterator(Node* node)
    11. 			:_node(node)
    12. 		{}
    13.  
    14. 	};

    封装之后，我们还需要重载对于迭代器的运算符，这些重载都是在迭代器中的，我只是为了吧方法一个个体现出来，分开了。

    重载前置++/--

    1.        //重载加加
    2. 		self& operator++()
    3. 		{
    4. 			_node = _node->_next;
    5. 			return *this;
    6. 		}
    7. 		self& operator--()
    8. 		{
    9. 			_node = _node->_prev;
    10. 			return *this;
    11. 		}

    重载后置++/--

    1.        self& operator++(int)
    2. 		{
    3. 			self tmp(*this);
    4. 			_node = _node->_next;
    5. 			return tmp;
    6. 		}
    7. 		self& operator--(int)
    8. 		{
    9. 			self tmp(*this);
    10. 			_node = _node->prev;
    11. 			return tmp;
    12. 		}

    重载*与->

    1.         T* operator->()
    2. 		{
    3. 			return _node->data;
    4. 		}
    5. 		T& operator*()
    6. 		{
    7. 			return &_node->data;
    8. 		}

    重载!=与==

    1. bool operator!=(const self& s)
    2. 		{
    3. 			return _node != s._node;
    4. 		}
    5. 		bool operator==(const self& s)
    6. 		{
    7. 			return _node == s._node;
    8. 		}

    const迭代器

    const迭代器对应const对象,指的是内容不能被修改，而非指针（迭代器）本身，因此我们不能直接const iterator去认为是const迭代器,这样反而不能对迭代器进行++等操作，而需要我们去重新定义
     定义const迭代器，即内容是无法被修改，由于我们访问内容是通过解引用的方法故我们需要修改访问的的这两个操作符其引用返回为const，即内容无法被修改了。

    1. template<class T>struct _list_const_iterator
    2. 	{
    3. 		typedef list_node<T>  Node;
    4. 		typedef _list_const_iterator<T> self;
    5. 		Node* _node;
    6. 		_list_const_iterator(Node* node)
    7. 			:_node(node)
    8. 		{}
    9. 		//迭代器的运算符重载
    10. 		self& operator++()
    11. 		{
    12. 			_node = _node->_next;
    13. 			return *this;
    14. 		}
    15. 		self& operator--()
    16. 		{
    17. 			_node = _node->prev;
    18. 			return *this;
    19. 		}
    20. 		self& operator++(int)
    21. 		{
    22. 			self tmp(*this);
    23. 			_node = _node->_next;
    24. 			return tmp;
    25. 		}
    26. 		self& operator--(int)
    27. 		{
    28. 			self tmp(*this);
    29. 			_node = _node->prev;
    30. 			return tmp;
    31. 		}
    32. 		const T* operator->()
    33. 		{
    34. 			return &_node->data;
    35. 		}
    36. 		const T& operator*()
    37. 		{
    38. 			return &_node->data;
    39. 		}
    40. 		bool operator!=(const self& s)
    41. 		{
    42. 			return _node != s._node;
    43. 		}
    44. 		bool operator==(const self& s)
    45. 		{
    46. 			return _node == s._node;
    47. 		}
    48.  
    49. 	};

    由于const迭代器与普通的迭代器区别也就在于访问的内容无法被修改，也就是修改*与->这两个访问内容的操作符，重新实现较为麻烦，库中实现是增加了两个模板参数Ref,Ptr，利用我们传的参数不一样，从而决定用的是哪一个迭代器。

    迭代器的优化：

    多出两个模板参数之后，我们的*与->返回类型就是到时候传入时候的类型，故这里我们直接用Ref与Ptr代替即可。

    1. template<class T,class Ref,class Ptr>struct _list_iterator
    2. 	{
    3. 		//利用节点的指针实现迭代器
    4. 		typedef list_node<T>  Node;
    5. 		typedef _list_iterator<T,Ref,Ptr> self;
    6. 		Node* _node;
    7.         _list_iterator(Node* node)
    8. 			:_node(node)
    9. 		{}
    10. }
    1.         Ptr operator->()
    2. 		{
    3. 			return _node->data;
    4. 		}
    5. 		Ref operator*()
    6. 		{
    7. 			return &_node->data;
    8. 		}

     在list中，对于模板迭代器我们传参不一样，决定了是const还是普通

    1. typedef _list_iterator<T, T&, T*> iterator;
    2. typedef _list_iterator<T,const T&,const T*> const_iterator;
    3.         iterator begin()
    4. 		{
    5. 			//return iterator(_head->data);
    6. 			return _head->_next;
    7. 		}
    8. 		iterator end()
    9. 		{
    10. 			return _head;//哨兵位就是链表的结束标志
    11. 		}
    12. 		const_iterator begin()const
    13. 		{
    14. 			return _head->_next;
    15. 		}
    16. 		const_iterator end()const
    17. 		{
    18. 			return _head;
    19. 		}

    反向迭代器 

    反向迭代器与正向迭代器的区别就在于遍历的反向不一样了，两者的本质是非常相似的，那么我们就可以利用正向得带起适配出一个反向迭代器。我们直接将正向的封装成一个反向迭代器：

    1. //利用正向迭代器去适配一个反向迭代器
    2. template <class iterator,class Ref ,class Ptr>class Reverse_iotearator
    3. {
    4. public:
    5.  
    6. 	Reverse_iotearator(iterator it)
    7. 		:_it(it)
    8. 	{}
    9. 	Reverse_iotearator<iterator, Ref, Ptr>operator++()
    10. 	{
    11. 		--_it;
    12. 		return *this;
    13. 	}
    14. 	Ref operator*()
    15. 	{
    16. 		return *_it;
    17. 	}
    18. 	Ptr operator->()
    19. 	{
    20. 		return _it.operator->();//这里需要显式调用不能直接->
    21. 	}
    22. 	Reverse_iotearator<iterator,Ref ,Ptr>operator()
    23. 	{
    24. 		++_it;
    25. 		return *this;
    26. 	}
    27. 	bool operator!=(const Reverse_iotearator<iterator, Ref, Ptr>& it)
    28. 	{
    29. 		return _it != it;
    30. 	}
    31. private:
    32. 	iterator _it;
    33. };

     实现一个rever_iterator的类，其模板参数分别用正向迭代器，数据的类型，数据地址类型做参数也实现了对于反向迭代器数据的访问。

    之后就可以包含该类，封装出反向迭代器：

    1. //反向迭代器
    2. 		typedef Reverse_iterator<iterator, T&,  T*> reverse_iterator;
    3. 		
    4. 		reverse_iterator rbegin()
    5. 		{
    6. 			//return _head->_next;
    7. 			return reverse_iterator(--end());//直接调用构造函数 
    8. 		const_reverse_iterator rend()const
    9. 		{
    10. 			//return _head;
    11. 			return reverse_iterator(end());
    12. 		}

     同理实现了反向迭代器我们直接可以实现const的反向迭代器

    const反向迭代器 

    1. typedef Reverse_iterator<const_iterator, const T&, const T*>const_reverse_iterator;
    2.  
    3. const_reverse_iterator rend()const
    4. 		{
    5. 			//return _head;
    6. 			return reverse_iterator(end());
    7. 		}
    8. 		const_reverse_iterator rbegin()const
    9. 		{
    10. 			//return _head->_next;
    11. 			return reverse_iterator(--end());
    12. 		}

    成员函数

    构造函数

    1.        //通过调用一个初始化链表的函数来实现构造函数
    2.        mylist()
    3. 		{
    4. 			empty_init();
    5. 		}

    析构函数

    1.       //通过调用clear函数释放链表的节点，在释放哨兵位，即为析构
    2.  ~mylist()
    3. 		{
    4. 			clear();
    5. 			delete _head;
    6. 			_head = nullptr;
    7. 		}

    拷贝构造函数

    1. //拷贝构造,将节点尾插入新的对象
    2. 		mylist(mylist& p)
    3. 		{
    4. 			empty_init(p);
    5. 			for (auto it : p)
    6. 			{
    7. 				push_back(it);
    8. 			}
    9. 		}

    容量

    size

    1. size_t size()
    2. 		{
    3. 			return _size;
    4. 		}

    修饰符 

    insert()

    在基于实现insert，我们的其他对list的操作都可以调用insert，不需要都去对链表节点一个个操作，

    其次我们设计insert的返回值及参数位置都是迭代器，直接用。

    1. iterator insert(iterator pos, const T x)//插入也会使迭代器失效，原位置节点找不到了
    2. 		{
    3. 			Node* cur = pos._node;
    4. 			Node* newnode = new Node(x);
    5. 			Node* prev = cur->_prev;
    6. 			//链接节点
    7. 			prev->_next = newnode;
    8. 			newnode->_prev = prev;
    9. 			newnode->_next = cur;
    10. 			cur->_prev = newnode;
    11. 			_size++;
    12. 			return iterator(newnode);
    13. 		}

    erase ()

    1. //删除   这里删除cur节点释放掉，会导致迭代器失效,因此要返回下一节点的迭代器
    2. 		iterator erase(iterator pos)
    3. 		{
    4. 			Node* cur = pos._node;
    5. 			Node* prev = cur->_prev;
    6. 			Node* next = cur->_next;
    7. 			delete cur;
    8. 			prev->_next = next;
    9. 			next->_prev = prev;
    10. 			_size--;
    11. 			return iterator(next);
    12. 		}

    push_front()

    1. void push_front()
    2. 		{
    3. 			insert(begin());
    4. 		}

    pop_front()

    1. //头删
    2. 		void pop_front()
    3. 		{
    4. 			erase(begin());
    5. 		}

    push_back()

    1. //尾插
    2. 		void push_back(const T& x)
    3. 		{
    4. 			//Node* tail = _head->preav;
    5. 			//Node* newnode = new Node(x);
    6. 			连接节点
    7. 			//tail->_next = newnode;
    8. 			//newnode->_next = _head;
    9. 			//newnode->prev = tail;
    10. 			//tail->_prev = newnode;
    11. 			//tail = newnode;
    12. 			//return (tail);
    13. 			insert(end(), x);
    14. 		}

    pop_back()

    1. //尾删
    2. 		void pop_back()
    3. 		{
    4. 			erase(end());
    5. 		}

    clear()

    1. //清数据
    2. 		void clear()
    3. 		{
    4. 			iterator it = begin();
    5. 			while (it != end())
    6. 			{
    7. 				it = erase(it);
    8. 			}
    9.          }

    至此我们对list的简单实现就完成了。

  • 相关阅读:
    阿里云六代、七代云服务器、轻量应用服务器、GPU云服务器最新活动报价表参考
    在以「基础设施」为定位的发展阶段里，产业变成了一个可以有诸多创新的存在
    优先级队列实现原理
    Zabbix监控
    https SSL证书使用 git bash 解密
    【Linux】线程池 | 自旋锁 | 读写锁
    springcloud之自我介绍
    php服务端 和 python 爬虫 结合 user-agent
    vue项目实现table表格竖向
    阿里二面：列出 Api 接口优化的几个技巧
  • 原文地址：https://blog.csdn.net/qq_61422622/article/details/132794351