C++----剖析list

发布于:2025-06-09 ⋅ 阅读:(22) ⋅ 点赞:(0)

前面学习了vector和string,接下来剖析stl中的list,在数据库中学习过,list逻辑上是连续的,但是存储中是分散的,这是与vector这种数组类型不同的地方。所以list中的元素设置为一个结构体,将list设计成双向的:

	template <class T>
	struct list_node
	{
		list_node<T>* _next;
		list_node<T>* _pre;
		T _data;

		list_node(const T& val=T())
			:_next(nullptr),
			_pre(nullptr),
			_data(val)
		{

		}
	};

接下来是stl中的迭代器部分,list的迭代器还可以像vector这种原生指针是的使用方式使用吗?答案是否定的,因为vector的底层存储是连续的,并且迭代器就是vector内部元素指针的简单封装。所以底层自然实现起来比较简单,但是list的底层不可以,比如迭代器++,vector本来就是连续的,所以直接就能用,但是struct不是连续的,所以要自己实现,否则谁知道会++到哪里造成访问未知空间。所以既然它不支持我们直接使用,那我们就造一个迭代器出来,这个迭代器的核心就是node:

	template <class T, class PTR, class PEF>
	struct _list_iterator
	{
		typedef list_node<T> Node;
		typedef _list_iterator<T,PTR,PEF> self;
		Node* _node;//核心

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

		PEF operator*()
		{
			return _node->_data;
		}//要可以返回值、还能修改!

		PTR operator->()
		{
			return &(operator*());
		}

		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		//后置++
		self operator++(int)
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		self& operator--()
		{
			_node = _node->_pre;
			return *this;
		}
		//后置--
		self operator--(int)
		{
			self tmp(*this);
			_node = _node->_pre;
			return tmp;
		}

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

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


	};

这里其他的地方没有太大的疑问,就是operator->发现了,返回的是nodedata的地址,首先咱们来看,当T是内置类型int时,是没有必要用这个的吧?直接*就可以得到,但是如果T时自定义类型的呢?比如:

	struct A
	{
		int _a;
		int _b;
		A(int a = 1,int b=1)
			:_a(a)
			,_b(b)
		{}
	};

	void test2()
	{
		list<A> l;
		l.push_back(A(1,1));
		l.push_back(A(2, 2));
		l.push_back(A(3, 3));
		l.push_back(A(4, 4));
        std::cout << it->_a << " " << it->_b << " ";
		list<A>::iterator it = l.begin();
	}

此时我想访问A中的数据,我当然可以重载<<这个运算符了,但是在stl中我们不知道自定义类型中会有什么数据,所以stl中是不会预先,也不能写出来<<运算符。所以就有了->符,我们可以自己访问struct中的数据,但是还有一个问题,->返回struct的地址,还应该再来一个->吧,就是it->->_a,这里编译器做了优化,所以只需要一个->就可以。

看list:

	template <class T>
	class list
	{
		typedef list_node<T> Node;
		
	public:
		typedef _list_iterator<T,T*,T&> iterator;
		typedef _list_iterator<T,const T*,const T&> const_iterator;


		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);
		}

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

		//void push_back(Node newnode)
		//{
		//	Node* tail = _head->_pre;
		//	tail->_next = newnode;
		//	newnode->_pre = tail;
		//	newnode->_next = _head;
		//	_head->_pre = newnode;
		//}

		void push_back(const T& val)
		{
			Node* newnode = new Node(val);
			Node* tail = _head->_pre;
			tail->_next = newnode;
			newnode->_pre = tail;
			newnode->_next = _head;
			_head->_pre = newnode;
		}
	private:
		Node* _head;
	};

list的形式:带哨兵位的双向列表

解释模板在const迭代器和普通迭代器中的巧妙使用,通过模板避免多写代码:

 巧妙使用模板参数。

list迭代器失效的场景只存在于删除结点时,他不像vector这种连续的,插入了会导致其中大部分元素发生移动,所以只会在删除结点时,如何解决?返回删除结点的下一个节点的迭代器。

附全部代码:

	template <class T>
	struct list_node
	{
		list_node<T>* _next;
		list_node<T>* _pre;
		T _data;

		list_node(const T& val=T())
			:_next(nullptr),
			_pre(nullptr),
			_data(val)
		{

		}
	};

	template <class T, class PTR, class PEF>
	struct _list_iterator
	{
		typedef list_node<T> Node;
		typedef _list_iterator<T,PTR,PEF> self;
		Node* _node;//核心

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

		PEF operator*()
		{
			return _node->_data;
		}//要可以返回值、还能修改!

		PTR operator->()
		{
			return &(operator*());
		}

		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		//后置++
		self operator++(int)
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		self& operator--()
		{
			_node = _node->_pre;
			return *this;
		}
		//后置--
		self operator--(int)
		{
			self tmp(*this);
			_node = _node->_pre;
			return tmp;
		}

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

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


	};

	template <class T>
	class list
	{
		typedef list_node<T> Node;
		
	public:
		typedef _list_iterator<T,T*,T&> iterator;
		typedef _list_iterator<T,const T*,const T&> const_iterator;


		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);
		}

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

		void empty_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_pre = _head;
		}

		template<class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			empty_init();

			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

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

		void swap(list<T>& l)
		{
			std::swap(_head, l._head);
		}
		  
		list(const list<T>& l)
		{ 
			empty_init();
			list<T> tmp(l.begin(), l.end());
			swap(tmp);
		}

		//l2=l1 
		list<T>& operator=(list<T> l)
		{
			swap(l);
			return *this;
		}

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

		//void push_back(Node newnode)
		//{
		//	Node* tail = _head->_pre;
		//	tail->_next = newnode;
		//	newnode->_pre = tail;
		//	newnode->_next = _head;
		//	_head->_pre = newnode;
		//}

		void insert(iterator pos, const T& val)
		{
			Node* newnode = new Node(val);
			Node* cur = pos._node;
			Node* pre = cur->_pre;

			cur->_pre = newnode;
			newnode->_next = cur;
			pre->_next = newnode;
			newnode->_pre = pre;
		}

		void push_front(const T& val)
		{
			insert(begin(),val);
		}

		void push_back(const T& val)
		{
			Node* newnode = new Node(val);
			Node* tail = _head->_pre;
			tail->_next = newnode;
			newnode->_pre = tail;
			newnode->_next = _head;
			_head->_pre = newnode;
		}

		//返回值是删去节点的下一个节点的迭代器,避免迭代器失效,
		//因为释放了当前迭代器的结点,再次访问会出现错误
		iterator erase(iterator pos)
		{
			assert(pos != end());
			Node* cur = pos._node;
			Node* pre = cur->_pre;
			Node* next = cur->_next;

			next->_pre = pre;
			pre->_next = next;
			delete cur;

			return iterator(next);
		}

		void pop_front()
		{
			iterator it = erase(begin());

		}

		void pop_back()
		{
			iterator it = erase(--end());

		}
	private:
		Node* _head;
	};