一, List的模拟实现

     List 是一个双向循环链表,由于List的节点不连续,不能用节点指针直接作为迭代器,因此我们要对结点指针封装,来实现迭代器的作用。

迭代器有两种实现方式,具体应根据容器底层数据结构实现:

        1. 原生态指针,比如:vector

        2. 将原生态指针进行封装,因迭代器使用形式与指针完全相同,因此在自定义的类中必须实现以下方法:

        1. 指针可以解引用,迭代器的类中必须重载operator*()

        2. 指针可以通过->访问其所指空间成员,迭代器类中必须重载oprator->()

        3. 指针可以++向后移动,迭代器类中必须重载operator++()与operator++(int)

至于operator--()/operator--(int)释放需要重载,根据具体的结构来抉择,双向链表可以向前 移动,所以需要重载,如果是forward_list就不需要重载--

        4. 迭代器需要进行是否相等的比较,因此还需要重载operator==()与operator!=()

二,代码实现

#pragma once
#include<assert.h>
#include<iostream>
#include <initializer_list>
#include<algorithm>
using namespace std;


namespace BMH
{
	template<class T>
	struct ListNode
	{
		typedef ListNode<T> Node;

		Node* _prev;
		Node* _next;
		T _data;

		ListNode(const T& data = T())
			:_prev(nullptr)
			, _next(nullptr)
			, _data(data)
		{}

	};

	
	template<class T, class Ref, class Ptr>
	struct ListIterator
	{
		//正向迭代器
		typedef ListNode<T> Node;
		typedef ListIterator<T, Ref, Ptr> Self;



		// Ref 和 Ptr 类型需要重定义下,实现反向迭代器时需要用到
	public:
		typedef Ref Ref;
		typedef Ptr Ptr;

		Node* _node;

		ListIterator(Node* node =nullptr)
			:_node(node)
		{}

		//++it
		Self& operator++()
		{
			_node = _node->_next;
			return *this;//++it 返回自己(迭代器)
		}

		//--it
		Self& operator--()
		{
			_node = _node->_prev;
			return  *this;
		}

		//it++
		Self operator++(int)
		{
			Self tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		//it--
		Self operator--(int)
		{
			Self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}


		//
		// 具有指针类似行为
		//*it  返回值
		Ref operator*()
		{
			return _node->_data;;
		}

		//it->  返回指针
		Ptr operator->()
		{
			return &(_node->_data);
		}
		//


		//
		// 迭代器支持比较
		bool operator == (const Self& it)
		{
			return _node == it._node;
		}
		bool operator != (const Self& it)
		{
			return _node != it._node;
		}

	};


	template<class T>
	class List
	{

	public:
		typedef ListNode<T> Node;

		typedef ListIterator<T, T&, T*> iterator;
		typedef ListIterator<T, const T&, const T*> const_iterator;


		///
		//初始化创建头结点
		void empty_init()
		{
			_head = new Node();
			_head->_prev = _head;
			_head->_next = _head;
		}


		//构造函数
		List()
		{
			empty_init();
		}

		List(int n, const T& value = T())
		{
			empty_init();
			for (int i = 0; i < n; ++i)
				push_back(value);
		}
		//用下面拷贝构造函数来实现构造函数,拷贝构造函数是构造函数的一种。
		//List<int> lt2(lt1)
		//List(const List<T>& lt)
		//{
		//	empty_init();
		//	for (const auto& e : lt)
		//	{
		//		Push_Back(e);
		//	}
		//}
		 

		//List<int> lt1 ={1,2,3,4}
		List(initializer_list<T> il)//不用引用的原因:il本身是两个指针,拷贝代价小
		{
			empty_init();

			for (const auto& e : il)
			{
				Push_Back(e);
			}
		}

		template<class Inputiterator >
		List(Inputiterator p1, Inputiterator p2)
		{
			empty_init();
			while (p1 != p2)
			{
				Push_Back(*p1);
				++p1;
			}
		}

		//拷贝构造
		//lt2(lt1)
		List(const List<T>& lt)
		{
			empty_init();
			for (const auto& e : lt)
			{
				Push_Back(e);
			}
		}


		//赋值重载
		//lt1=lt2
		List<T>& operator=(List<T> lt)
		{
			swap(_head, lt._head);
			return *this;
		}

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);//用erase时会发生迭代器失效
			}
		}

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

		///
		//迭代器
		iterator begin()
		{
			return iterator(_head->_next);
		}

		iterator end()
		{
			return iterator(_head);
		}


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

		const_iterator end() const
		{
			return  const_iterator(_head);
		}



		///
		// 容量相关
		//尾插
		void Push_Back(const T& x)
		{
			Node* tail = _head->_prev;
			Node* newnode = new Node(x);

			newnode->_prev = tail;
			tail->_next = newnode;
			newnode->_next = _head;
			_head->_prev = newnode;
		}
		void Pop_Back()
		{
			erase(--end());
		}
		void Push_Front(const T& x)
		{
			insert(begin(),x);
		}
		void Pop_Front()
		{
			erase(begin());
		}


		//之前插入,无迭代器失效
		iterator insert(iterator pos ,const T& data )
		{
			Node* cur = pos._node;//pos是迭代器,找到其中的节点地址即可
			Node* newnode = new Node(data);
			Node* prev = cur->_prev;

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

			return iterator(newnode);
		}
		//有迭代器失效,返回删除节点下一个的迭代器
		iterator erase(iterator pos)
		{
			assert(pos!= (*this).end());//防止将
			Node* cur = pos._node;
			Node* next = cur->_next;
			Node* prev = cur->_prev;

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

			delete cur;

			return iterator(next);
		}


	private:
		Node* _head;
	};

三、list和vector的区别

        1、任意位置插入删除时:list可以随意插入删除,但是vector任意位置的插入删除效率低,需要挪动元素,尤其是插入时有时候需要异地扩容,就需要开辟新空间,拷贝元素,释放旧空间,效率很低

        2、访问元素时:vector支持随机访问,但是list不支持随机访问
        3、迭代器的使用上:vector可以使用原生指针,但是list需要对原生指针进行封装
        4、空间利用上:vector使用的是一个连续的空间,空间利用率高,而list使用的是零碎的空间,空间利用率低

这个博客如果对你有帮助,给博主一个免费的点赞就是最大的帮助

欢迎各位点赞,收藏和关注哦

如果有疑问或有不同见解,欢迎在评论区留言哦

后续我会一直分享双一流211西北大学软工(C,数据结构,C++,Linux,MySQL)的学习干货以及重要代码的分享

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部