C++学习第九天（list及其模拟实现）

1、list介绍

• list是可以在常熟范围内任意位置进行 插入和删除的序列式容器，并且该容器可以前后双向迭代
• list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素
• list和forward_list非常相似，最主要不同的是forward_list是单链表，只能朝前迭代，以让其更简单高效。
• list可以在任何位置进行插入，移除元素的效率更高
• 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问。

 2、list的使用

list中的接口比较多，一下是常见的重要接口

list的构造

list iterator的使用

【ATT】

• begin和end为正向迭代器，对迭代器执行++操作，迭代器向后移动
• rbegin和rend为反向迭代器，对迭代器执行++操作，迭代器向前移动

list capacity的使用

list element access的使用

list modifiers的使用

list的迭代器失效（重点）

概念：迭代器失效即迭代器所指向的节点无效，即该节点被删除了，因为list的底层结构是带头节点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除的时候才会失效，而且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响

void test3()
{
	int array[] = { 1,2,3,4,5,6,7,8,9,0 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	list<int>::iterator it = l.begin();
	while (it != l.end())
	{
		//erase()函数被执行后，it所指向的节点已经被删除，因此it无效，在下一次使用it时，必须先给其赋值
		l.erase(it);
		++it;
	}
}
 
//修正
void test2()
{
	int array[] = { 1,2,3,4,5,6,7,8,9,0 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	list<int>::iterator it = l.begin();
	while (it != l.end())
	{
		
		it = l.erase(it);
	}
	for (auto e : l)
	{
		cout << e << " ";
	}
}
 
int main()
{
	test2();
	return 0;
}

3、list的模拟实现

#pragma once
#include
#include
 
using namespace std;
 
namespace bit
{
	//List节点类
	template<class T>
	struct ListNode
	{
		ListNode(const T& val = T())
			:_prev(nullptr)
			,_next(nullptr)
			,_val(val)
		{}
 
		ListNode* _prev;
		ListNode* _next;
		T _val;
	};
		
	template<class T, class Ref, class Ptr>
	class ListIterator
	{
		typedef ListNode Node;
		typedef ListIterator Self;
 
	public:
		typedef Ref Ref;
		typedef Ptr Ptr;
	public:
 
		ListIterator(Node* node = nullptr)
			:_node(node)
		{}
 
		//具有指针行为
		Ref operator*()
		{
			return _node->_val;
		}
 
		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->_prev;
			return *this;
		}
 
		Self& operator--(int)
		{
			Self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
 
 
		//迭代器支持比较
		bool operator!=(const Self& l)const
		{
			return _node != l._node;
		}
 
		bool operator==(const Self& l)const
		{
			return _node != l._node;
		}
 
		Node* _node;
	};
 
	template<class Iterator>
	class ReverseListIterator
	{
		//typename的作用是明确告诉编译器,Ref是Iterator中的一个类型，而不是静态成员变量
		//否则编译器就不知道Ref是Iterator中的类型还是静态成员变量
		//因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
	public:
		typedef typename Iterator::Ref Ref;
		typedef typename Iterator::Ptr Ptr;
		typedef ReverseListIterator Self;
	public:
		ReverseListIterator(Iterator it)
			:_it(it)
		{}
 
		Ref operator*()
		{
			Iterator tmp(_it);
			--tmp;
			return *tmp;
		}
 
		Ptr operator->()
		{
			return &(operator*());
		}
 
		Self& operator++()
		{
			--_it;
			return *this;
		}
 
		Self operator++(int)
		{
			Self temp(*this);
			--_it;
			return temp;
		}
 
		Self& operator--()
		{
			++_it;
			return *this;
		}
 
		Self operator--(int)
		{
			Self temp(*this);
			++_it;
			return temp;
		}
 
		//
		// 迭代器支持比较
		bool operator!=(const Self& l)const
		{
			return _it != l._it;
		}
 
		bool operator==(const Self& l)const
		{
			return _it != l._it;
		}
 
		Iterator _it;
	};
 
	template<class T>
	class list
	{
		typedef ListNode Node;
 
	public:
		// 正向迭代器
		typedef ListIterator iterator;
		typedef ListIteratorconst T&, const T&> const_iterator;
 
		// 反向迭代器
		typedef ReverseListIterator reverse_iterator;
		typedef ReverseListIterator const_reverse_iterator;
	public:
		///
		// List的构造
		list()
		{
			CreateHead();
		}
 
		list(int n, const T& value = T())
		{
			CreateHead();
			for (int i = 0; i < n; ++i)
				push_back(value);
		}
 
		template <class Iterator>
		list(Iterator first, Iterator last)
		{
			CreateHead();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
 
		list(const list& l)
		{
			CreateHead();
 
			// 用l中的元素构造临时的temp,然后与当前对象交换
			list temp(l.begin(), l.end());
			this->swap(temp);
		}
 
		list& operator=(list 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)
		{
			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& l)
		{
			std::swap(_head, l._head);
		}
 
	private:
		void CreateHead()
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
		}
	private:
		Node* _head;
	};
}
 
 
///
// 对模拟实现的list进行测试
// 正向打印链表
template<class T>
void PrintList(const bite::list& l)
{
	auto it = l.begin();
	while (it != l.end())
	{
		cout << *it << " ";
		++it;
	}
 
	cout << endl;
}
 
// 测试List的构造
void TestBiteList1()
{
	bite::list<int> l1;
	bite::list<int> l2(10, 5);
	PrintList(l2);
 
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	bite::list<int> l3(array, array + sizeof(array) / sizeof(array[0]));
	PrintList(l3);
 
	bite::list<int> l4(l3);
	PrintList(l4);
 
	l1 = l4;
	PrintList(l1);
}
 
// PushBack()/PopBack()/PushFront()/PopFront()
void TestBiteList2()
{
	// 测试PushBack与PopBack
	bite::list<int> l;
	l.push_back(1);
	l.push_back(2);
	l.push_back(3);
	PrintList(l);
 
	l.pop_back();
	l.pop_back();
	PrintList(l);
 
	l.pop_back();
	cout << l.size() << endl;
 
	// 测试PushFront与PopFront
	l.push_front(1);
	l.push_front(2);
	l.push_front(3);
	PrintList(l);
 
	l.pop_front();
	l.pop_front();
	PrintList(l);
 
	l.pop_front();
	cout << l.size() << endl;
}
 
// 测试insert和erase
void TestBiteList3()
{
	int array[] = { 1, 2, 3, 4, 5 };
	bite::list<int> l(array, array + sizeof(array) / sizeof(array[0]));
 
	auto pos = l.begin();
	l.insert(l.begin(), 0);
	PrintList(l);
 
	++pos;
	l.insert(pos, 2);
	PrintList(l);
 
	l.erase(l.begin());
	l.erase(pos);
	PrintList(l);
 
	// pos指向的节点已经被删除，pos迭代器失效
	cout << *pos << endl;
 
	auto it = l.begin();
	while (it != l.end())
	{
		it = l.erase(it);
	}
	cout << l.size() << endl;
}
 
// 测试反向迭代器
void TestBiteList4()
{
	int array[] = { 1, 2, 3, 4, 5 };
	bite::list<int> l(array, array + sizeof(array) / sizeof(array[0]));
 
	auto rit = l.rbegin();
	while (rit != l.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;
 
	const bite::list<int> cl(l);
	auto crit = l.rbegin();
	while (crit != l.rend())
	{
		cout << *crit << " ";
		++crit;
	}
	cout << endl;
}
	};
}