After talking about vector, let's take a look at list today.

list introduction

The list in c + + is actually a circular bi-directional linked list structure of the leading node.

1. list 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.
2. The bottom layer of list is a two-way linked list structure. Each element in the two-way linked list is stored in independent nodes that are not related to each other. In the node, a pointer points to its previous element and the latter element.
3. List and forward_list is very similar: the main difference is forward_list is a single linked list, which can only iterate forward, making it simpler and higher
   Effective.
4. Compared with other sequential containers (array, vector, deque), list usually inserts and removes elements at any position, which is more efficient.
5. Compared with other sequential containers, list and forward_ The biggest drawback of the list is that it does not support random access to any location. For example, to access the sixth element of the list, you must iterate from a known location (such as the head or tail) to that location, which requires linear time overhead; The list also needs some extra space to hold the associated information of each node (this may be an important factor for a large list that stores elements of a smaller type)

Simulation Implementation of list

Next, while explaining the use of list library functions, we simulate the implementation of list(c++98 version).

ps: it is suggested that students who have not read the first two articles on string and vector simulation implementation can take a look first in order to form a more overall understanding.
[C + +] teach you to write your own String class
[C + +] teach you to write your own vector class

Construction of list

Use of constructors

There are four constructors for list

Constructor	Interface description
list()	$1600
list(size_type n, const value_type& val = value_type())	The constructed list contains n elements with value val
list(const list& x)	copy constructor
list(InputIterator first,InputIterator last)	Construct a list with elements from other iterator intervals

Usage example:

#include<iostream>
using namespace std;

int main()
{
	list<int>l1; //Construct an empty l1
	list<int>l2 (4,100); //Structure l2, containing 4 100
	list<int>l3 (l2.begin(),l2.end()); //Interval construction of iterators using l2
	list<int>l4 (l3);  //Constructing l4 with l3 copy
	// Construct l5 with array as iterator interval
	int array[] = {16,2,77,29};
	std::list<int> l5 (array, array + sizeof(array) / sizeof(int) );
}

Simulation Implementation of constructor

Before implementing the constructor, we must first make it clear that the linked list structure in the list is a two-way linked list of the leading node.

Here we first implement the parameterless constructor.

Here we need to understand, what did we initialize? For a two-way linked list of leading nodes, parameterless initialization is to establish a head node (without storing data) and point the pointer to itself.

Therefore, implementing constructors is not difficult.

1. Encapsulate the structure of a node into a structure

   template<class T>
   struct __list_node
   {
     //Constructor
     __list_node(const T& val = T())
       :_next(nullptr)
       :_prev(nullptr)
       :_val(val)
     {}
       
     __list_node<T>* _next;
     __list_node<T>* _prev;
     T _val;
   };
   

1. Implement parameterless constructor

template<class T>
class list
{
  typedef __list_node<T> Node;
  
public:

  list()
  {
     _head=new Node();
     _head->next=_head;
     _head->prev=_prev;
  }
private:
  Node* _head;  
   
} 
}

iterator

Use of iterators

The use of list iterators is not much different from string and vertor. But there are great differences in structure.

Function declaration	Interface description
begin+end	Returns the iterator of the first element + returns the iterator of the next position of the last element
rebegin+rend	Returns the reverse of the first element_ Iterator, that is, the end position, returns the reverse of the next position of the last element_+ Iterator, i.e. begin position

void print_list(const list<int>& l)
{
   list<int>::const_iterator it =l.begin();
   for(it;it!=l.end();++it)
   {
     cout<<*it<<endl;
   }
   cout<<endl;
}

Simulation Implementation of iterator

Before we explain the iterators of list, let's classify the iterators as follows:
Iterators can be implemented in two ways, which should be implemented according to the underlying data structure of the container:

1. Primitive pointer, such as vector

2. Encapsulate the original pointer. Because the use form of the iterator should be exactly the same as that of the pointer, the following methods must be implemented in the custom class:

     1. Pointers can be dereferenced, that is, they must be overloaded in the iterator's class operator*()
     2. The pointer can pass through->To access a member of its reference space, it must be overloaded in the iterator class operator->()
     3. The pointer can pass through++Move backward, that is, reload in the iterator opoerator++() And operator++(int)
         (ps: For whether it is necessary -- ,You need to choose according to the specific structure. The two-way linked list can move back and forth,
          So it needs to be overloaded--,however forward_list(Single linked list structure) does not need to be overloaded)
    4.  Iterators need to compare whether they are equal or not, and they need to be overloaded operator==() And operator!=()
   

In short, the purpose of any iterator is to disguise itself as a pointer

So, what kind of iterator does list belong to?
Obviously, it belongs to the second kind. Why?
Because this is determined by the structure of the list:

• For vector, because it is continuous storage, we do not need to overload + +. We can access elements directly through the addition and subtraction of pointers, but list is not continuous storage. We need to access the next element through the next pointer stored by the node in advance, not directly + +.
• For vector, the dereference of the pointer corresponds to the corresponding value, while for list, each position stores a structure, which cannot be directly used to obtain the corresponding value through dereference, but (* _head)_ val

How much space does the iterator of vector and list occupy under a 32-bit system?
In fact, it's the same. It's all 4 bytes, because all the addresses are stored

Therefore, we need to encapsulate the original pointer and overload some operators:

template<class T,class Ref,class Ptr>
struct __list_iterator
{
  typedef __list_iterator <T,Ref,Ptr> self;
  typedef __list_node<T> Node;
  
  Node* _node;
  
  //Constructor
  __list_iterator(Node*node)
      :_node(node)
  {}

  Ref operator*()
  {
     return _node->_data;
  }    
  Ptr operator->()
  {
    return &_node->_data;
  }
  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& it) const
 {
	return _node != it._node;
 }

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

So far, we have completed the iterator. The library method of our iterator is implemented in the list class as follows:

Note here why the position taken by end() is_ head. This is because the list is a circularly linked list, and the end() location is the next to the last location, that is, the head node_ Head position

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()
		{
			// Lead two-way cycle
			//_head = new Node(T());
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}

 
private:
  Node*_head; 
}

Seeing this, I believe many students have questions:
Why do iterators have three template parameters?

template<class T, class Ref, class Ptr>

This is a clever design in the original code:

1. The first parameter controls the type of data passed in
2. The second parameter distinguishes between iterator and const_iterator
3. The third parameter is used for overloading of '>'

Here we will focus on the template parameters Ref and Ptr:

• Ref
  For most containers, there are two types of iterators: one supports reading and writing, and the other only supports reading, namely iterator and const_iterator.
  For iterators implemented with native pointers (such as string and list), it is easy to distinguish them. You only need to add const when calling:

 typedef T*  iterator;
 typedef const T* const_iterator;

However, for iterators that encapsulate pointer implementation (such as list), we need to add const to all member functions, that is, we need to write two iterators, which will make the code redundant and reduce the readability.

Therefore, we can add a parameter to the template parameter (the third parameter can be ignored temporarily), so that we can distinguish the two on the premise of writing only one iterator.

typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T,const T&,const T*> const_iterator;

According to the original code, the parameter we pass to the iterator here is T &, that is, the reference type.

• Ptr

The third parameter Ptr is created for overloading - > to.

When we pass parameters, Ptr is of type T *, that is, the address of T.

  Ptr operator->()
  {
    return &_node->_data;
  }

Usage example:

For the following example, when we use iterators to access nodes, the three template parameters are * * < treenode, & treenode, treenode * >**

struct TreeNode
	{
		struct TreeNode* _left;
		struct TreeNode* _right;
		int _val;

		TreeNode(int val=-1)
			:_left(nullptr)
			,_right(nullptr)
			,_val(val)
		{}
	};

void test_list2()
{
		list<TreeNode>lt;
		lt.push_back(TreeNode(1));
		lt.push_back(TreeNode(2));
		lt.push_back(TreeNode(3));
		lt.push_back(TreeNode(4));

		list<TreeNode>::iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << (*it)._val << endl;
			cout << it->_val << endl;
			
			++it;
		}
		cout << endl;

	}

Here is a small detail. When we use - > to access the node, the correct writing is it - > - > in fact_ val:
The first - > get the address of the node it points to, and the second - > get the address of the node_ val, but in order to increase readability, the compiler does special processing during compilation, omitting a - >.

copy construction

Use of copy constructs

Copy construction is a very common construction method, which refers to using an existing list to construct a new list

    list<int>l2 (4,100); //Structure l2, containing 4 100
	list<int>l4 (l2);  //Constructing l4 with l2 copy

Simulation Implementation of copy construction

We have talked about the writing method of copy structure many times before. The most noteworthy thing is that we should avoid the use of shallow copy. The reason will not be explained.

There are generally three ways to write a copy structure:

1. Traditional writing 1

This is the easiest way to think of. First establish and initialize the header node, and then link the elements to the header node.

list(const list<T>& lt)
{
  //Create a header node and initialize it
  _head=new Node;
  _head->_next=_head;
  _head->_prev=_head;
  //assignment
  for(const auto& e: lt)
  {
    push_back(e);
  }
}

1. Modern writing

The modern writing method is still familiar with "sit and enjoy". We use the iterator constructor to construct a tmp, and then exchange the tmp with the head node of this. This exchange enables the object to be copied to obtain the content of tmp, which achieves the purpose of copy construction.

Although this idea does not reflect the advantage in efficiency in the list for the time being, in other structures, this idea of "sitting back and enjoying success" plays a great role

template<class InputIterator>
  list(InputIterator first,InputIterator last)
  {
	  _head=new Node;
	  _head->_next=_head;
	  _head->_prev=_head;
	  
	  while(first!=last)
	  {
	    push_back(*first)
	    ++first;
	  }
 }
 	  
list(const list<T>& lt)
{
	 _head=new Node();
	 _head->_next=_head;
	 _head->_prev=_head;
	 
	 list<T>tmp(lt.begin(),lt.end());
	 std::tmp(_head,tmp._head);
}

assignment

Assignment between list s is also common. We just need to overload "=".

1. Traditional writing
   Some details about assignment have been discussed in the simulation implementation of string. I won't repeat them here. I'll just talk about the idea:

First empty all the assigned object contents (keep the header node), and then insert a new node.

list<T>& operator = (const list<T>& lt)
{
  if(this !=&lt)
  {
    clear();
    for(const auto& e: lt)
    {
      push_back(e);
    }
  }
  return *this;
}

1. Modern writing

The modern writing method is still a "sit and enjoy" way. The content of the formal parameter lt (lt is a temporary object obtained through deep copy) is obtained by exchanging header nodes

list<T>& operator = (const list<T> lt)
{
  swap(_head,lt.head);
  return *this;
}

insert

iterator insert(iterator pos,const T& x)
{
  assert(pos!=end());
  Node*cur=pos._node;
  Node*prev=cur->_prev;
  
  Node*newnode = new Node();
  newnode->_prev=prev;
  newnode->_next=cur;
  cur->_prev=newnode;
  
  //Returns the iterator for the newnode location
  return iterator(newnode);
  
}

earse

In addition to deleting data, erase also has a return value, which returns the iterator at the next position of the deleted element.

iterator earse(iterator pos)
{
  assert(pos!= end());
  Node*cur=pos._node;
  Node*cur->prev=_prev;
  Node*cur->next=_next;
  
  delete cur;
  prev->_next=next;
  next->_prev=prev;
  
  return iterator(next);
}
```,
---


## push_back and push_front
 Tail interpolation function and head interpolation function can be borrowed directly insert To achieve.

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

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

pop_back and pop_front

Similarly, header deletion and tail deletion can also be implemented directly through ear

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

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

clear

The clear function will delete all nodes in the list container except the header node.

When implementing clear, we can use the feature of return to the next location of deleted elements, such as ear, to delete elements one by one

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

Destructor

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

So far, we have completed most of the basic functions in the list container, which can be further improved by interested students.