Simulation Implementation of List in C++ and construction of List inversion iterator

I List introduction

The bottom layer of the list is a two-way circular linked list. It is a sequential container that can be inserted and deleted at any position within the constant range, and the container can iterate back and forth. Compared with other containers (vector, array, deque) whose bottom layer is a sequential table, the list inserts at any position and removes elements more efficiently; However, compared with these containers whose bottom layer is a sequential table, the biggest defect of list is that it does not support random access at any location.

II Member variable

	public:
		Node* node;

The member variable of list has only one pointer of node type, which points to the virtual head node of the bidirectional circular linked list.

II list constructor

		//non-parameter constructor 
        list()
		{
			head = new Node();
			head->next = head;
			head->prev = head;
		}
		//Using template functions and iterators to construct objects
		template<class Inputiterator>
		list(Inputiterator first, Inputiterator last)
		{
			head = new Node();
			head->next = head;
			head->prev = head;
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
		//Copy constructor for deep copy, modern writing
		list(const list<T>& x)
		{
			head = new Node();
			head->next = head;
			head->prev = head;
			list<T> tmp(x.begin(), x.end());
			std::swap(head, tmp.head);
		}

Note: each constructor of List needs to create a virtual header node

III Use of list iterator: begin, end, rbegin, and rend functions

3.1 function function

3.2 code implementation

//Iterator for header node
		iterator begin()
		{
			return iterator(head->next);
		}

		const_iterator begin() const
		{
			return const_iterator(head->next);
		}

		//Constructed with an iterator at the next position of the last element_ revese_ As the return value, iterator simulates the implementation of the reverse iterator with the forward iterator. This is a manifestation of reuse and can reduce the amount of code
		_revese_iterator rbegin()
		{
			return _revese_iterator(end());
		}

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

		//Iterator for tail node (virtual head node)
		iterator end()
		{
			return iterator(head);
		}

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

		//Constructed with the iterator of the first element_ revese_ As the return value, iterator simulates the implementation of the reverse iterator with the forward iterator. This is a manifestation of reuse and can reduce the amount of code
		_revese_iterator rend()
		{
			return _revese_iterator(begin());
		}

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

Above_ reverse_ The iterator reverse iterator is constructed and implemented by the forward iterator. It is a design pattern and a reusable representation, which can reduce the amount of code.

IV List class forward iterator

4.1. The function of list class iterator

Use the nodes in the list object to construct an iterator, and then you can use the iterator to traverse each node in the list object to dereference the iterator object to complete the operation of getting the value in the node. You can also use ++, - - to traverse the nodes in the list object. The list class iterator is essentially a class, a class that can complete the node traversal in the list object.

4.2. Member variable

The member variable of list has only one pointer of node type, which points to the virtual head node of the bidirectional circular linked list.

	public:
		Node* node;

4.3. code implementation

	template<class T, class Ref, class Ptr>
	class __list_iterator
	{
	public:
		typedef ListNode<T> Node;
		typedef __list_iterator<T, Ref, Ptr> self;
		__list_iterator(Node* x)
			:node(x)
		{
		}
		//Dereference operator overload
		Ref operator*()
		{
			return node->data;
		}
		//->The iterator accesses and modifies the linked list with the help of the pointer of the node. Here, it means that the pointer - > - > is used to obtain data, and then the compiler will optimize the pointer - > to obtain data
		Ptr operator->()
		{
			return &node->data;
		}
		//Iterator adds before and returns the iterator after addition
		self operator++()
		{
			node = node->next;
			return *this;
		}
		//Add after iterator, return the iterator before adding
		self operator++(int)
		{
			self tmp(node);
			node = node->next;
			return tmp;
		}
		//Iterator pre subtract and return the subtracted iterator
		self operator--()
		{
			node = node->prev;
			return *this;
		}
		//Iterator post subtraction returns the iterator before subtraction
		self operator--(int)
		{
			self tmp(node);
			node = node->prev;
			return tmp;
		}

		//Determine whether the contents pointed to by two iterators are equal
		bool operator!=(const self& it)  const
		{
			if (it.node != node)
			{
				return true;
			}
			return false;
		}

		bool operator==(const self& it)  const
		{
			return !(*this != it);
		}

	public:
		Node* node;
	};

V List class reverse iterator

5.1 introduction to reverse iterators

Its function is to traverse each node in the List in reverse. It is constructed by the forward iterator, so all its functions are realized by the forward iterator. Different from the forward iterator, when dereferencing the reverse iterator, it obtains the value of the previous node instead of the node pointed to by the previous iterator. This is because the iterator rend points to the header node, The iterator rbegin points to the virtual header node. The --, and ++ operations of the reverse iterator correspond to the ++, - operations of the forward iterator.

5.2 member variables

public:
	_iterator it;

Is a forward iterator

5.3 code implementation:

template<class iterator, class Ref, class Ptr>
class resverse_iterator
{
public:
	typedef iterator _iterator;
	typedef resverse_iterator<iterator, Ref, Ptr> self;
	resverse_iterator(const _iterator& x)
		:it(x)
	{
	}
	//Dereference operator overload
	Ref operator*()
	{
		_iterator prev = it;
		return *(--prev);
	}
	//->The iterator accesses and modifies the linked list with the help of the pointer of the node. Here, it means that the pointer - > - > is used to obtain data, and then the compiler will optimize the pointer - > to obtain data
	Ptr operator->()
	{
		_iterator prev = it;
		--prev;
		return &*(prev);
	}
	//Iterator adds before and returns the iterator after addition
	self operator++()
	{
		--it;
		return *this;
	}
	//Add after iterator, return the iterator before adding
	self operator++(int)
	{
		self tmp(it);
		--it;
		return tmp;
	}
	//Iterator pre subtract and return the subtracted iterator
	self operator--()
	{
		++it;
		return *this;
	}
	//Iterator post subtraction returns the iterator before subtraction
	self operator--(int)
	{
		self tmp(it);
		++it;
		return tmp;
	}

	//Determine whether the contents pointed to by two iterators are equal
	bool operator!=(const self& It)  const
	{
		return it != It.it;
	}

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

public:
	_iterator it;
};

Vi push_back function

6.1 functions

Insert a node at the end of the List

6.2 return value

No return value

6.3 implementation logic

(1) First, apply for a space on the heap where the value of a new node is stored

(2) Let the prev pointer of the virtual head node point to the new node, and the next pointer of the tail node point to the new node

(3) The prev of the new node points to the tail node, and the next of the new node points to the virtual head node

		//Insert an element after
		void push_back(const T& val)
		{
			Node* newnode = new Node(val);
			Node* _prev = head->prev;
			_prev->next = newnode;
			newnode->prev = _prev;
			newnode->next = head;
			head->prev = newnode;
		}

6.4 achieving results

VII erase function

7.1 functions

Delete the node pointed to by an iterator in the List object. It can be reused to implement tail deletion, header deletion, and clear all valid nodes of the List object

7.2 return value

Returns the iterator for the next node

7.3 implementation logic

(1) The previous node of the node to be deleted points to the next node of the node to be deleted

(2) Free up space for nodes to delete

		// Is pos invalid after erase? Certain failure
		iterator erase(iterator pos)
		{
			assert(pos != end());
			Node* cur = pos.node;
			Node* pre = pos.node->prev;
			Node* _next = pos.node->next;
			pre->next = _next;
			_next->prev = pre;
			delete cur;
			iterator(_next);
		}
		//End delete an element
		void pop_back()
		{
			erase(--end());
		}

		//Header delete an element
		void pop_front()
		{
			erase(begin());
		}

		void clear()
		{
            //The first method:
			//list<int>::iterator it = begin();
			//while (it != end())
			//{
			//	iterator del = it++;
			//	delete del.node;
			//}
			//head->next = head;
			//head->prev = head;
			Another way
			while (it != end())
			{
				erase(it++);
			}
		}

7.4 achieving results

VIII insert function

8.1 functions

Insert a node after the node pointed to by the iterator pos

8.2 return value

Returns the iterator of the inserted new node

8.3 implementation logic