【C++】STL — List的接口讲解 +详细模拟实现-易微帮

前言：
本章我们将学习STL中另一个重要的类模板list…

list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
list的底层是带头双向循环链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
list与forward_list非常相似：主要区别在于forward_list对象是单链接列表，因此它们只能向前迭代，以换取更小、更高效。
与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，需要线性的时间开销。

list是带哨兵位头节点的双向循环链表,
在list中进行插入节点不会导致list的迭代器失效,
只有删除节点时才会出现失效问题，并且失效的只是指向被删除节点的迭代器,会有野指针问题，其他迭代器不受影响

1. list的使用

我们学习的STL中的list是一种：带头双向循环链表。（带有哨兵位头结点的）

带头双向循环链表 – 链表中的最优设计
可以实现任意位置〇(1)的插入删除，只需要改前后的关系

1.1 list的初始化 + 迭代器的使用

在我们使用list之前我们需要先包一下头文件#include< list >
在这里插入图片描述

#include <iostream>
#include <list>

int main ()
{
  // constructors used in the same order as described above:
  std::list<int> first;                                // empty list of ints
  std::list<int> second (4,100);                       // four ints with value 100
  std::list<int> third (second.begin(),second.end());  // iterating through second
  std::list<int> fourth (third);                       // a copy of third

  // the iterator constructor can also be used to construct from arrays:
  int myints[] = {16,2,77,29};
  std::list<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );
  return 0;
}

1.2 对list的排序

对于一般的容器而言，我们包一个算法库 #incldue < alogrithm > 可以对普通的容器进行排序。

void test_list2()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(4);
	v.push_back(2);
	v.push_back(4);
	v.push_back(3);
	sort(v.begin(), v.end());
	
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;

	list<int> lt;
	lt.push_back(1);
	lt.push_back(4);
	lt.push_back(2);
	lt.push_back(4);
	lt.push_back(3);
	lt.sort();
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
}

像vector和string而言，这种连续的容器可以直接用库中的sort
而对于list而言和之前的顺序容器有所区别，因为其链式结构，库中的算法不支持
list单独实现了一个自己的排序
但是list的排序效率很低

注意：
可见把list的数据拷贝到vector中再，用sort算法对vector中排序，再将vector中的数据拷贝到list中都比直接用list排序要快，所以list的排序效率很低。

2. list的模拟实现（list.h）

在这里插入图片描述

2.1 链表结点的申请：

namespace Joker
{
    //list的节点类
	template<class T>
	struct list_node
	{
		list_node<T>* _next;
		list_node<T>* _prev;
		T _data;

		list_node(const T& val = T())
			:_next(nullptr)
			, _prev(nullptr)
			, _data(val)
		{}
	};

注意：

- 默认生成的析构函数够用。

2.2 用类封装List 的迭代器

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

1. 原生态指针，比如：vector
1. 将原生态指针进行封装，因迭代器使用形式与指针完全相同，因此在自定义的类中必须实现以下方法：
  1. 指针可以解引用，迭代器的类中必须重载operator*()
  2. 指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()
  3. 指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)
    至于operator–()/operator–(int)释放需要重载，根据具体的结构来抉择，双向链表可以向前移动，所以需要重载，如果是forward_list就不需要重载–
  4. 迭代器需要进行是否相等的比较，因此还需要重载operator==()与operator!=()

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

     public:
         // 构造
		ListIterator(Node* node = nullptr)
			: _node(node)
		{}
      // 具有指针类似行为
		Ref operator*() 
		{ 
			return _node->_data;
		}

		Ptr operator->() 
		{ 
			//return &(operator*()); 
			return &_node->_data;
		}	//
		// 迭代器支持移动
		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		Self operator++(int)
		{
			Self temp(*this);
			_node = _node->_next;
			return temp;
		}
         //--it
		Self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
        //it--
		Self operator--(int)
		{
			Self temp(*this);
			_node = _node->_prev;
			return temp;
		}
//
		// 迭代器支持比较
		bool operator!=(const Self& l)const
		{ 
			return _node != l._node;
		}

		bool operator==(const Self& l)const
		{ 
			return _node != l._node;
		}
		Node* _node;
	};

注意：

析构函数（不需要写）-- 节点不属于迭代器，不需要迭代器释放
编译器生成的默认析构函数够用，对内置类型不敢处理，只对自定义类型处理
拷贝构造和赋值重载（不需要写）
默认生成的浅拷贝就可以

（2）运算符重载 - > ：

Ptr operator->() 
	{
		//return &(operator*());0
		return &_node->_data;
	}
	返回的是一个指针。

优化如下：

it.operator->() – 返回类型是AA*的迭代器
it.operator->() ->_data;
编译器为了可读性进行了优化处理
如果不优化应该是it->->_data;
优化以后，省略了一个->

2.3 List链表的实现

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;

		// List的构造
		list()
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
		}

		list(int n, const T& value = T())
		{
			empty_init();
			for (int i = 0; i < n; ++i)
				push_back(value);
		}

      //创造一个哨兵位头结点出来，通用
		void empty_init()
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
		}
		
		template <class Iterator（大写I）>
		list(Iterator first, Iterator last)
		{
			empty_init();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
//拷贝构造现代写法：--需要使用深拷贝
		list(const list<T>& l)
		{
		 //创造一个哨兵位头节点出来，不初始化就是随机值
			empty_init();
		// 用l中的元素构造临时的temp,然后与当前对象交换
			list<T> temp(l.begin(), l.end());
			this->swap(temp);
		}
		list<T>& operator=(list<T> l)
		{
			this->swap(l);
			return *this;
		}

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

		///
		// List的迭代器
		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); 
		}

		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}

		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}

		const_reverse_iterator rbegin()const
		{
			return const_reverse_iterator(end());
		}

		const_reverse_iterator rend()const
		{
			return const_reverse_iterator(begin());
		}

		///
		// List的容量相关
		size_t size()const
		{
			Node* cur = _head->_next;
			size_t count = 0;
			while (cur != _head)
			{
				count++;
				cur = cur->_next;
			}

			return count;
		}

		bool empty()const
		{
			return _head->_next == _head;
		}

		void resize(size_t newsize, const T& data = T())
		{
			size_t oldsize = size();
			if (newsize <= oldsize)
			{
				// 有效元素个数减少到newsize
				while (newsize < oldsize)
				{
					pop_back();
					oldsize--;
				}
			}
			else
			{
				while (oldsize < newsize)
				{
					push_back(data);
					oldsize++;
				}
			}
		}
		
		// List的元素访问操作
		// 注意：List不支持operator[]
		T& front()
		{
			return _head->_next->_val;
		}

		const T& front()const
		{
			return _head->_next->_val;
		}

		T& back()
		{
			return _head->_prev->_val;
		}

		const T& back()const
		{
			return _head->_prev->_val;
		}

		
		// List的插入和删除
		void push_back(const T& val) 
		{ 
		//Node* tail=_head->_prev;
		 //Node* newnode=new node(x);
		 _head     tail  newnode
		 //tail->_next=newnode;
		 //newnode->_prev=tail;
		 //newnode->_next=_head;
		 //_head->prev=newnode;
			insert(end(), val); 
		}

		void pop_back() 
		{ 
			erase(--end()); 
		}

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

		void pop_front() 
		{ 
			erase(begin()); 
		}

		// 在pos位置前插入值为val的节点
		iterator insert(iterator pos, const T& val)
		{
			Node* pNewNode = new Node(val);
			Node* pCur = pos._node;
			// 先将新节点插入
			pNewNode->_prev = pCur->_prev;
			pNewNode->_next = pCur;
			pNewNode->_prev->_next = pNewNode;
			pCur->_prev = pNewNode;
			return iterator(pNewNode);
		}

		// 删除pos位置的节点，返回该节点的下一个位置
		iterator erase(iterator pos)
		{
			// 找到待删除的节点
			Node* pDel = pos._node;
			Node* pRet = pDel->_next;

			// 将该节点从链表中拆下来并删除
			pDel->_prev->_next = pDel->_next;
			pDel->_next->_prev = pDel->_prev;
			delete pDel;

			return iterator(pRet);
		}

		void clear()
		{
			Node* cur = _head->_next;
			// 采用头删除删除
			while (cur != _head)
			{
				_head->_next = cur->_next;
				delete cur;
				cur = _head->_next;
			}

			_head->_next = _head->_prev = _head;
		}

		void swap(bite::list<T>& l)
		{
			std::swap(_head, l._head);
		}
	private:
		Node* _head;
	};
}

2.4 迭代器失效的问题

list insert迭代器不失效，不存在野指针的问题，也不存在意义变了的问题
list erase(it)以后，迭代器是会失效的,是野指针问题

解决办法：

之前vector容器迭代器失效时解决办法一样，使用返回值接收。

尾声
看到这里，相信大家对这个C++有了解了。
如果你感觉这篇博客对你有帮助，不要忘了一键三连哦

【C++】STL — List的接口讲解 +详细模拟实现

目录

1. list的使用

1.1 list的初始化 + 迭代器的使用

1.2 对list的排序

2. list的模拟实现（list.h）

2.1 链表结点的申请：

2.2 用类封装List 的迭代器

2.3 List链表的实现

2.4 迭代器失效的问题

网站公告

今日签到

热门文章

最新发布