1, Overview

  list and vector in the previous chapter are the most commonly used containers in our daily development. However, unlike vector, list is not an absolutely fixed container of continuous space. The reason why it is designed in this way is to consider the time consumption of deleting and inserting continuous space. STL list is actually a two-way linked list. Those who understand the concept of linked list should understand that this front and back movable linked list structure provides very flexible operability.

2, Definition

2.1 node form

   its node form can be visualized as shown in the following figure:

  the specific code is also very simple:

template <class T> struct __list_node {
    typedef void* void_pointer;
    void_pointerprev; //The type is void *. In fact, it can be set as__ list_ node<T>* void_ pointer next;
    T data;
};

2.2 iterators

   the introduction of iterators is too much here, but one thing I have to mention is that there is a big difference between iterators of list and vector s, that is, list cannot use native pointers as iterators, but needs to be designed with different structures.

   its structure is easy to understand, that is, we need to make the splicing and separation work simple enough.

template<class T, class Ref, class Ptr> 
struct __list_iterator {
	typedef __list_iterator<T, T&, T*> iterator; 
    typedef __list_iterator<T, Ref, Ptr> self;
   	typedef bidirectional_iterator_tag iterator_category;
   	typedef T value_type;
   	typedef Ptr pointer;
   	typedef Ref reference;
	typedef __list_node<T>* link_type; 
    typedef size_t size_type;
	typedef ptrdiff_t difference_type;
	link_type node; // Of course, there should be a native indicator inside the iterator, pointing to the node of the list
   // constructor
   __list_iterator(link_type x) : node(x) {}
   __list_iterator() {}
   __list_iterator(const iterator& x) : node(x.node) {}
	bool operator==(const self& x) const { return node == x.node; } 
    bool operator!=(const self& x) const { return node != x.node; } 
    
    // The following is the dereference of the iterator, which takes the data value of the node.
	reference operator*() const { return (*node).data; }
	
    // The following is the standard practice for member access operators of iterators.
    pointer operator->() const { return &(operator*()); }
	
    // To accumulate 1 for the iterator is to advance one node 
    self& operator++()
        node = (link_type)((*node).next);
        return *this;
   	}
	self operator++(int) 
        self tmp = *this; 
		++*this;
		return tmp;
	}
	// Decrementing the iterator by 1 is to step back by one node 
	self& operator--()
    	node = (link_type)((*node).prev);
     	return *this;
   	}
	self operator--(int) self tmp = *this; 
	--*this;
	return tmp;
	} 
};

2.3 node structure

  as mentioned above, STL list is a two-way linked list structure. Therefore, the whole complete chain can be shown as the following code:

template <class T, class Alloc = alloc> // By default, alloc is used as the configurator class list{
    protected:
    	typedef __list_node<T> list_node; 
	public:
       typedef list_node* link_type;
    protected:
    	link_type node; // Only one indicator can represent the whole circular bidirectional series
	... 
};

   imagine that we need a marker that constantly adds nodes backward, so our whole operation must actually rely on the pointer of a node. link_type is to change the name of the entire node pointer. Then mark all the heads and tails so that we can find the head and tail directly when we use them.

iterator begin() { return (link_type)((*node).next); }
iterator end() { return node; }
bool empty() const { return node->next == node; }
size_type size() const {
	size_type result = 0; 
    distance(begin(),end(),result); //Global functions, Chapter 3. 
    return result;
}
// Take the content (element value) of the header node.
reference front() { return *begin(); } 

// Take the content (element value) of the tail node.
reference back() { return *(--end()); }

   the operations before and after value taking can be vividly shown in the following figure:

3, Understanding list in operation