C++ STL【list】(二）

• • list 的模拟实现
  • • list 遍历实现：
    • insert的实现
    • push_front
    • push_back
    • erase的实现（迭代器失效）
    • pop_back
    • pop_back
    • 默认成员函数
    • • 析构函数
      • • clear
        • 析构
      • 构造函数
      • 编译器调用构造函数时匹配问题
    • list的反向迭代器
  • list 全部代码

结构：

//  链表节点
	template
	class ListNode
	{
	public:
		typedef ListNode Node;
		Node* _pre;
		Node* _next;
		T _data;
	};

// list迭代器 -> 类去分装节点指针，重载*、++ 等运算符，让它们像指针一样使用
	template
	class _list_iterator
	{
	public:
		typedef _list_iterator < T, Ref,Ptr> self;
		typedef ListNode Node;
		
		Node* _node;//  节点指针
	};

//  
template
	class list
	{
	public:
		typedef ListNode Node;
		typedef _list_iterator iterator;
		typedef _list_iterator const_iterator;
	private:
		Node* _head;// 头结点指针
	};

节点实现：

template
	class ListNode
	{
	public:
		typedef ListNode Node;
		ListNode(const T& x = T())
			:_pre(nullptr)
			,_next(nullptr)
			,_data(x)
		{}
		Node* _pre;
		Node* _next;
		T _data;
	};

链表节点无需写析构函数，节点没有涉及动态开辟的资源。

链表迭代器实现：

// iterator -> 类去分装节点指针，重载*、++ 等运算符，让它们像指针一样使用
	template
	class _list_iterator
	{
	public:
		typedef _list_iterator < T, Ref,Ptr> self;
		typedef ListNode Node;
		_list_iterator( Node* x)
			:_node(x)
		{}
		// ++it
		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

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

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

		// it--
		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& x)
		{
			return _node != x._node;
		}
		//==
		bool operator==(const self& x)
		{
			return _node == x._node;
		}

		Node* _node;
	};

	template
	class list
	{
	public:
		typedef ListNode Node;
		typedef _list_iterator iterator;
		typedef _list_iterator 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(const T&x)
		{
			Node* newnode = new Node(x);
			Node* tail = _head->_pre;
			newnode-> _pre = tail;
			tail->_next = newnode;
			newnode->_next = _head;
			_head->_pre = newnode;
		}

	private:
		Node* _head;// 头结点指针
	};
	// 打印链表
	void print_list(const list& List)
	{
		list::const_iterator it = List.begin();
		while (it != List.end())
		{
			std::cout << *it;
			it++;
		}
		std::cout << std::endl;
	}
	// 正向迭代器测试
	void test1()
	{
		BBQ::list L1;
		L1.push_back(1);
		L1.push_back(2);
		L1.push_back(3);
		list::iterator it = L1.begin();
		while (it != L1.end())
		{
			*it *= 2;
			std::cout << *it;
			it++;
		}
		std::cout << std::endl;
	}
	// const 迭代器测试
	void test2()
	{
		BBQ::list L1;
		L1.push_back(1);
		L1.push_back(2);
		L1.push_back(3);
		BBQ::print_list(L1);
	}

	struct Date
	{
		int _year;
		int _month;
		int _day;

		Date(int year = 1, int month = 1, int day = 1)
			:_year(year)
			, _month(month)
			, _day(day)
		{}
	};
	// 迭代器  运算符 "->" 测试
	void test3()
	{
		list lt;
		lt.push_back(Date(2022, 3, 12));
		lt.push_back(Date(2022, 3, 13));
		lt.push_back(Date(2022, 3, 14));

		list::iterator it = lt.begin();
		while (it != lt.end())
		{
			//cout << (*it)._year << "/" << (*it)._month << "/" << (*it)._day << endl;
			std::cout << it->_year << "/" << it->_month << "/" << it->_day << std::endl;
			++it;
			//  本来应该是这样 it->->_year，但编译器优化了一个->运算符。
		}
		std::cout << std::endl;
	}

迭代器的玩法和string类似，只是迭代器不仅可以是源生迭代器，还能是自定义的迭代器，通过iterator 类去分装节点指针，重载*、++ 等运算符，让它们像指针一样使用，所以链表的迭代器与源生的迭代器的操作结果就可以不相同了。

		
		iterator insert(iterator pos, const T& val)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;S
			Node* newnode = new Node(x);

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

			return iterator(newnode);

		}

新节点插入到pos的前面， 这里insert以后，pos迭代器不失效，虽然链接关系发生了改变，但是pos迭代器还是指向原先节点并且该节点还存在。

有了insert()实现push_front，就很容易了。

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

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

// 这里erase以后，pos是否失效？一定失效
iterator erase(iterator pos)
{
	assert(pos != end());
			
	Node* prev = pos._node->_prev;
	Node* next = pos._node->_next;
	delete pos._node;
	prev->_next = next;
	next->_prev = prev;
	
	return iterator(next);
}

erase返回值的意义和vector类似，需要返回删除该节点之后的迭代器。erase以后，pos一定会失效，因为pos指向的节点被释放了，POS指向的意义变了。

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

尾删，end()指向头结点的，所以需要-- 才能指向末尾节点。

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

删除所有的节点，不包含头节点。

	void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				iterator del = it++;
				delete del._node;
			}
			_head->_next = _head;
			_head->_pre = _head;
		}

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

注意：头结点也是动态开辟的，也需要手动释放。

注意 ：写list的构造函数前需要先有头节点。

default (1)	
explicit list (const allocator_type& alloc = allocator_type());

fill (2)	
explicit list (size_type n, const value_type& val = value_type(),
                const allocator_type& alloc = allocator_type());
                
range (3)	
template 
  list (InputIterator first, InputIterator last,
         const allocator_type& alloc = allocator_type());
         
copy (4)	
list (const list& x);

构造函数有4个我们只需要实现迭代器，拷贝构造就能复用了。

list(const list& x)
{
	_head = new Node();
	_head->_next = _head;
	_head->_pre = _head;
	list tmp(x.begin(), x.end());
	std::swap(_head, tmp._head);
}
list& operator=(list tmp)
{
	_head = new Node();
	_head->_next = _head;
	_head->_pre = _head;
	std::swap(_head, tmp._head);
	return *this;
}
list(int n, const T& val = T())
{
	_head = new Node();
	_head->_next = _head;
	_head->_prev = _head;
	for (int i = 0; i < n; ++i)
	{
		push_back(val);
	}
}
list(size_t n, const T& val = T())
{
	_head = new Node();
	_head->_next = _head;
	_head->_prev = _head;
	for (size_t i = 0; i < n; ++i)
	{
		push_back(val);
	}
}

	// 没有写list(int n, const T& val = T()) 时，
	// 编译器认为构造函数迭代器模版更加的匹配。
	//如果 插入的是Data类型时，编译器能正确调用 list(size_t n, const T& val = T());
	// 解决方案：重载一份 list(int n, const T& val = T())
	void test9()
	{
		BBQ::list L1(10,2);// 调用迭代器构造函数模版，在函数体里非法访问报错。	
		BBQ::listL2(10,Data(2022,12,23));//调用list(size_t n, const T& val = T());
	}

10和2本质都是int类型，(int,Data)在选则 无参的()，(intputIterator,intputIterator),(size_t,T), 通过对比并且size_t是整型家族，必然选择了(size_t,T)。而(int,int) 在选择时，肯定选择了(intputIterator,intputIterator)，两个类型都一样的原因。
注意：vector容器也有这样的问题。

文章

namespace BBQ
{
==============================================================
	// Iterator是哪个容器的迭代器，reverse_iterator就可以
	// 适配出哪个容器的反向迭代器。复用的体现
	template 
	class reverse_iterator
	{
		typedef reverse_iterator self;
	public:
		reverse_iterator(Iterator it)
			:_it(it)
		{}

		Ref operator*()
		{
			//正常思路
			//return *_it;
			Iterator prev = _it;
			return *--prev;
		}

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

		self& operator++()
		{
			--_it;
			return *this;
		}

		self& operator--()
		{
			++_it;
			return *this;
		}

		bool operator!= (const self& rit)
		{
			return _it != rit._it;
		}

	private:
		Iterator _it;
	};
	template
	class ListNode
	{
	public:
		typedef ListNode Node;
		ListNode(const T& x = T())
			:_pre(nullptr)
			,_next(nullptr)
			,_data(x)
		{}
		Node* _pre;
		Node* _next;
		T _data;
	};
==============================================================
	// iterator -> 类去分装节点指针，重载*、++ 等运算符，让它们像指针一样使用
	template
	class _list_iterator
	{
	public:
		typedef _list_iterator < T, Ref,Ptr> self;
		typedef ListNode Node;
		_list_iterator( Node* x)
			:_node(x)
		{}
		// ++it
		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

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

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

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

		//*
		Ref operator*()
		{
			return _node->_data;
		}
		//->
		Ptr operator->()
		{
			return &(_node->_data);
		}
		//!=
		bool operator!=(const self& x)
		{
			return _node != x._node;
		}
		//==
		bool operator==(const self& x)
		{
			return _node == x._node;
		}

		Node* _node;
	};
==============================================================
	template
	class list
	{
	public:
		typedef ListNode Node;
		typedef _list_iterator iterator;
		typedef _list_iterator const_iterator;
		typedef reverse_iterator const_reverse_iterator;
		typedef reverse_iterator reverse_iterator;
		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}
		const_reverse_iterator rbegin()const
		{
			return const_reverse_iterator(end());
		}
		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}
		const_reverse_iterator rend()const
		{
			return const_reverse_iterator(begin());
		}
		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;
		}
		template 
		list(InputIterator first, InputIterator last)
		{
			_head = new Node();
			_head->_next = _head;
			_head->_pre = _head;
			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}
		list(const list& x)
		{
			_head = new Node();
			_head->_next = _head;
			_head->_pre = _head;
			list tmp(x.begin(), x.end());
			std::swap(_head, tmp._head);
		}
		list& operator=(list tmp)
		{
			_head = new Node();
			_head->_next = _head;
			_head->_pre = _head;
			std::swap(_head, tmp._head);
			return *this;
		}
		list(int n, const T& val = T())
		{
			_head = new Node();
			_head->_next = _head;
			_head->_pre = _head;
			for (int i = 0; i < n; ++i)
			{
				push_back(val);
			}
		}
		list(size_t n, const T& val = T())
		{
			_head = new Node();
			_head->_next = _head;
			_head->_pre = _head;
			for (size_t i = 0; i < n; ++i)
			{
				push_back(val);
			}
		}

		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}
		// 删除所有的节点，不包含头节点
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				iterator del = it++;
				delete del._node;
			}
			_head->_next = _head;
			_head->_pre = _head;
		}
		// 这里insert以后，pos是否失效？不失效
		iterator insert(iterator pos, const T& val)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* newnode = new Node(val);

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

			return iterator(newnode);

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

	private:
		Node* _head;// 头结点指针
	};
==============================================================
	// 打印链表
	void print_list(const list& List)
	{
		list::const_iterator it = List.begin();
		while (it != List.end())
		{
			std::cout << *it;
			it++;
		}
		std::cout << std::endl;
	}
	//反向打印
	void reverse_print_list(const list& List)
	{
		list::const_reverse_iterator it = List.rbegin();
		while (it != List.rend())
		{
			std::cout << *it;
			++it;
		}
		std::cout << std::endl;
	}
	// 正向迭代器测试
	void test1()
	{
		BBQ::list L1;
		L1.push_back(1);
		L1.push_back(2);
		L1.push_back(3);
		list::iterator it = L1.begin();
		while (it != L1.end())
		{
			*it *= 2;
			std::cout << *it;
			it++;
		}
		std::cout << std::endl;
	}
	// const 迭代器测试
	void test2()
	{
		BBQ::list L1;
		L1.push_back(1);
		L1.push_back(2);
		L1.push_back(3);
		BBQ::print_list(L1);
	}

	struct Date
	{
		int _year;
		int _month;
		int _day;

		Date(int year = 1, int month = 1, int day = 1)
			:_year(year)
			, _month(month)
			, _day(day)
		{}
	};
	// 迭代器  运算符 "->" 测试
	void test3()
	{
		list lt;
		lt.push_back(Date(2022, 3, 12));
		lt.push_back(Date(2022, 3, 13));
		lt.push_back(Date(2022, 3, 14));

		list::iterator it = lt.begin();
		while (it != lt.end())
		{
			//cout << (*it)._year << "/" << (*it)._month << "/" << (*it)._day << endl;
			std::cout << it->_year << "/" << it->_month << "/" << it->_day << std::endl;
			++it;
			//  本来应该是这样 it->->_year，但编译器优化了一个->运算符。
		}
		std::cout << std::endl;
	}

	// clear 析构函数 测试
	void test4()
	{
		BBQ::list L1;
		L1.push_back(1);
		L1.push_back(2);
		L1.push_back(3);
	}

	// 默认生成的拷贝构造，是浅拷贝，析构两次会报错
	void test5()
	{
		BBQ::list L1;
		L1.push_back(1);
		L1.push_back(2);
		L1.push_back(3);
		// 默认的拷贝构造就是将，L2._node=L1._node
		BBQ::list L2(L1);
	}

	//迭代器构造函数 测试
	void test6()
	{
		BBQ::list L1;
		L1.push_back(1);
		L1.push_back(2);
		L1.push_back(3);
		BBQ::list L2(L1.begin(),L1.end());
		print_list(L2);
	}

	//拷贝构造函数 测试
	void test7()
	{
		BBQ::list L1;
		L1.push_back(1);
		L1.push_back(2);
		L1.push_back(3);
		BBQ::list L2(L1);
		print_list(L2);
	}

	// 赋值运算符重载 测试
	void test8()
	{
		BBQ::list L1;
		L1.push_back(1);
		L1.push_back(2);
		L1.push_back(3);
		BBQ::list L2(L1);
		BBQ::list L3;
		L3 = L2;
		print_list(L3);
	}

	// 构造函数 list(size_t n, const T& val = T());测试
	// 没有写list(int n, const T& val = T()) 时，编译器认为构造函数迭代器模版更加的匹配。
	// 解决方案：重载一份 list(int n, const T& val = T())
	void test9()
	{
		BBQ::list L1(10,2);// 在迭代器构造函数里，非法访问报错。
	}
	void test10()
	{
		BBQ::list L1(10,Date(1,1,1));
		std::cout << (*(L1.begin()))._day <<'/' << (*(L1.begin()))._month << '/' << (*(L1.begin()))._year << std::endl;
	}
	//反向迭代器
	void test11()
	{
		BBQ::list L1;
		L1.push_back(1);
		L1.push_back(2);
		L1.push_back(3);
		reverse_print_list(L1);
	}
}