目录

list的节点类

 list的迭代器类

list的模拟实现


要模拟实现list,必须要熟悉list的底层结构以及其接口的含义,通过之前学习,这些内容已基本掌握,现在我们来模拟实现list。

C++入门 list的模拟实现-LMLPHP参照带头双向循环链表的结构,我们可以建立以下三个类来模拟实现list 

C++入门 list的模拟实现-LMLPHP


list的节点类

	template<class T>
	struct ListNode
	{
		ListNode<T>* _next;
		ListNode<T>* _prev;
		T _data;

		// 构造函数 
		ListNode(const T& data = T())
			:_next(nullptr),
			_prev(nullptr),
			_data(data)
		{}
	};

C++入门 list的模拟实现-LMLPHP


 list的迭代器类

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

  1. 指针可以解引用,迭代器的类中必须重载operator*()
  2. 指针可以通过->访问其所指空间成员,迭代器类中必须重载oprator->()
  3. 指针可以++向后移动,迭代器类中必须重载operator++()与operator++(int),至于operator--()/operator--(int)释放需要重载,根据具体的结构来抉择,双向链表可以向前移动,所以需要重载,如果是forward_list就不需要重载--
  4. 迭代器需要进行是否相等的比较,因此还需要重载operator==()与operator!=()
	template<class T, class Ref, class Ptr>
	struct ListIterator
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T, Ref, Ptr> Self;
		Node* _node;
		//
		// 构造
		ListIterator(Node* node)
			:_node(node)
		{}        
        //
		// 迭代器支持移动
		// ++it;
		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

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

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

			return tmp;
		}

		Self& operator--(int)
		{
			Self tmp(*this);
			_node = _node->_prev;

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

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

		bool operator==(const Self& it)
		{
			return _node == it._node;
		}
	};

迭代器类不需要析构函数,我们只要能够访问list中的元素即可,访问完不需要析构节点。

C++入门 list的模拟实现-LMLPHP

可以这样理解:这里的Self是当前这个节点,通过类模板又被细化为普通类型,引用类型,指针类型,以int代替T来实例化,这时候ListIterator中的T告诉迭代器是什么类型(int),Ref代替引用(int&),Ptr代替指针(int*)。而这里的Self可以当作节点本身。

C++入门 list的模拟实现-LMLPHP


list的模拟实现

namespace bite
{
	template<class T>
	struct ListNode
	{
		ListNode<T>* _next;
		ListNode<T>* _prev;
		T _data;

		// 构造函数 
		ListNode(const T& data = T())
			:_next(nullptr),
			_prev(nullptr),
			_data(data)
		{}
	};

	template<class T, class Ref, class Ptr>
	struct ListIterator
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T, Ref, Ptr> Self;
		Node* _node;

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

		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

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

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

			return tmp;
		}

		Self& operator--(int)
		{
			Self tmp(*this);
			_node = _node->_prev;

			return tmp;
		}

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

		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
	{
		typedef ListNode<T> Node;
	public:
		typedef ListIterator<T, T&, T*> iterator;
		typedef ListIterator<T, const T&, const T*> const_iterator;

		iterator begin()
		{
			//iterator it(_head->_next);
			//return it;
			return iterator(_head->_next);
		}

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

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

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

		list()
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
		}

		void push_back(const T& x)
		{
			insert(end(), x);
		}

		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& x)
		{
			Node* cur = pos._node;
			Node* newnode = new Node(x);
			Node* prev = cur->_prev;

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

			return iterator(newnode);
		}

		// erase 后 pos失效了,pos指向节点被释放了
		iterator erase(iterator pos)
		{
			assert(pos != end());

			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

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

			delete cur;

			return iterator(next);
		}

	private:
		Node* _head;
	};
}

前面说过,此处大家可将迭代器暂时理解成类似于指针,迭代器失效即迭代器所指向的节点的无效即该节点被删除了。因为list的底层结构为带头结点的双向循环链表,因此在list中进行插入时是不会导致list的迭代器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭代器,其他迭代器不会受到影响。因此使用erase之后需要对迭代器进行赋值刷新

07-01 13:17