Demystifying the underlying mysteries of lists

This article realizes through simulationlistconstructors, iterators, and some of the member functions to help you get a deeper understanding.listI hope that after reading this article, you will be able to understand the principle of thelistA deeper understanding.

I. List underlying framework

listThe bottom layer of thebounded bi-directional recurring table.

(1) Node class

on account oflistThe nodes may store various types of values, so a template parameter is used here.T.

list <int> list<doubel> …

// Node classes for Lists
    template<class T>
    struct list_node
    {
        list_node(const T& val = T())
            :_val(val)
        {}
        // T() here means that an object is created using the default constructor of type T.
        // It will call the default constructor for type T to initialize val. If type T does not provide a default constructor, the code will not compile.
        list_node<T>* _prev=nullptr; // point to the predecessor node
        list_node<T>* _next=nullptr; // point to the successor node
        T _val; //store data
    };

(2) Iterator class

Many of you will be wondering why an iterator class uses theThree template parametersI don’t know, isn’t it a bit redundant? Actually, it’s not, as Bull explains in turn.

1. class T: is a template parameter to be used by the node class to store different data. This template parameter indicates the type of the element to be processed. It can be of any type such as integer, float, custom class, etc. A specific type needs to be provided at the time of template instantiation.
2. Ref: This template parameter indicates the type of element to point toT (used form a nominal expression)quote. It defines the type of reference to an element, and the specified reference type will be used to manipulate the element when the template is instantiated.
3. Ptr: This template parameter indicates the type of element to point toT (used form a nominal expression)pointer on a gauge. It defines the type of pointer to an element, and the specified pointer type will be used to manipulate the element when the template is instantiated.

template<class T, class Ref, class Ptr> represent list_iterator<T, const T&, const T*>; listis used to iterate through the elements of the chain table, and the external iterator is passed through the iterator’s++and--Performs access to the elements of a chained table, which is a type ofseal inside, Hide the insidelistimplementation details, which can only be accessed externally by means of iterators.

// Iterator class
	template<class T, class Ref, class Ptr>
  	struct list_iterator
  	{
      typedef list_node<T> Node;
      typedef list_iterator<T, Ref, Ptr> self; //self Indicates oneself
     
      list_iterator(Node* node);	 // Construction
      list_iterator(const self& list);     // Copy construction
      Ref operator*();
      Ptr operator->();
      //Frontloading++
      self& operator++();  
      // post ++
      self operator++(int);
      //Front--
      self& operator--();
      //Post--
      self& operator--(int);
      bool operator!=(const self& list) const; 
      bool operator==(const self& list);
      
      //Member variables
      Node* _node;
 	 };

(3) The list class

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;
        
        list()//(no-parameter construction)
        //n-value construction
        list(int n, const T& value = T());
        //Iterator interval construction
        template <class Iterator>
        list(Iterator first, Iterator last);    
        //copy construction
        list(const list<T>& list);
        //various member functions
        /...
        //Destructor
        ~list();
        iterator begin();       
        iterator end();
        //Constant Attribute Iterator
        const_iterator begin()const;
        const_iterator end()const; 
    private:
        Node* _head;
        size_t _size;
    };

II. Constructors

with regards tobounded bi-directional recurring table, its initialization is necessary because a header pointer must be created. with regards tolistconstructor, which is used in a variety of ways, e.g., unparameterized constructor,navalconstructs, iterator interval constructs, and so on. For each construct, the initial initialization operation must be performed before, in order to avoid code redundancy, we will write this part into a separate function for the initialization operation. As follows.

void  Init_List()
  {
	_head = new Node; //create head pointer
    _head->_prev = _head;
    _head->_next = _head;
    _size = 0;
  }

(1) Parameterless construction

call (programming)Init_List();Initialize the function.

list()//initialization is important (no-parameter construction)
  {
      Init_List();
  }

(2) n-value construction

1. Perform initialization operations.
2. tail plugnavalue.

//n-value construction
   list(int n, const T& value = T())
   {
       Init_List();
       while (n--)
       {
           push_back(value);
       }
   }

(3) Iterator interval construction

1. Perform initialization operations.
2. Using the properties of iterators, the data in the interval are transferred at once.tail plugInto a linked list.

//Iterator interval construction
  template <class Iterator>
  list(Iterator first, Iterator last)
  {
      Init_List();
      while (first != last)
      {
          push_back(*first);
          ++first;
      }
  }

(4) Copy construction

Chained lists are not contiguous in physical space, so the only way to insert data sequentially is to traverse a chained list whose argument is a copy of another chained list.

//copy construction
	list(const list<T>& list)
	{
	    Init_List();
	    auto it = list.begin();
	    while (_size!=list._size)
	    {
	        push_back(*it);
	        it++;
	    }
	}

III. Iterators

Iterator implementation

① Tectonic

An iterator is essentially anNode* _node;A pointer to a node class. For the constructor of an iterator, just pass the address of the node.

list_iterator(Node* node) //default construction
 :_node(node) {}
list_iterator(const self& list) // copy construction
 :_node(list._node){}

② *and->

(1) * *Operator overloading for dereferencing iterators. Usage Scenario.

list<int>::iterator it = L1.begin();
int start=*it;

Obviously.*The operator is needed to access the data stored in the node. In order to minimize copying and modification of the data, we use thepass a reference(Ref ) return .

Ref operator*() {
     return _node->_val;//get the data for this node
 }

(2) -> The data in the above chained table is of the simple typeint

Ptr operator->() {
       return &_node->_val;
       // is equivalent to return &(_node->_val);
   }

③ Pre-++ and post-++

For chained lists, the iterator ++ indicates a backward access to the next (successor) node. For those of you who have studied chained lists, you should know that. i.e._node = _node->_next; Front ++,Iterator that returns the node after +++ Back ++, return an iterator over the nodes before ++

//Frontloading++
  self& operator++() {
      _node = _node->_next;
      return *this;
  }

  // post ++
  self operator++(int) {
      Node* tmp=_node; // save the value before +++
      _node = _node->_next;
      return tmp; //returns the value before ++.
  }

④ Front- and back-

Similarly, return the current node iterator’sfront driveNodes. Namely._node = _node->_prev; Front-, iterator that returns the node after – Rear-, return an iterator over the -preceding nodes

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

 //Post--
 self& operator--(int){
     Node* tmp = _node; // save -- previous value
     _node = _node->_prev;
     return tmp; //return -- the previous value
 }

⑤ Comparison operators

Comparing iterators for equality is actually comparing the nodes pointed to by the iterators for equality.

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

Iterators in the list class

iterator begin(): Iterator that returns the position of the first valid element iterator end(): Iterator that returns the position of the last valid element

typedef list_iterator<T, T&, T*> iterator;
	typedef list_iterator<T, const T&, const T*> const_iterator;
	iterator begin()
	 {
      return _head->_next;
      //And also a strong turn.
      //return iterator(_head->_next);
 	 }
 	 
	iterator end()
	{
      return _head;
      //And also a strong turn.
     // return iterator(_head);
     }
     
	//Constant Attribute Iterator
	const_iterator begin()const
	{
	    return _head->_next;
	}
	const_iterator end()const
	{
	    return _head;
	}

front and back

T& front()
 {
     return _head->_next->_val; // Return value
 }
 const T& front()const
 {
     return _head->_next->_val;
 }
 T& back()
 {
     return _head->_prev->_val;
 }
 const T& back()const
 {
     return _head->_prev->_val;
 }

4. Modifiers:

In fact, with the head of the two-way circular chain table additions, deletions and changes compared to a single linked table, more simple, we draw a diagram to analyze or very easy to achieve.

(1) insert()

(Images are blogger’s originals, not to be used as screenshots) special case (Images are blogger’s originals, not to be used as screenshots) code example

// Insert the node with value val before the pos position.
 iterator insert(iterator pos, const T& val)
 {
     //pos.node instead of pos->node
     Node* newnode = new Node(val);
     Node* _prev_node = pos._node->_prev; // original predecessor of pos position node
     Node* _cur_node = pos._node; //node at pos position

     _prev_node->_next = newnode;
     newnode->_prev = _prev_node;

     _cur_node->_prev = newnode;
     newnode->_next = _cur_node;

     ++_size;//number of valid data +1.
     
     return newnode;
 }

(2) erase()

// Delete the node at position pos and return the next position of the node.
  iterator erase(iterator pos)
  {
      
      Node* _prev_node = pos._node->_prev; // original predecessor (prev) node of pos position node
      Node* _next_node = pos._node->_next; // the original posterior (next) node of the pos position node

      _next_node->_prev = _prev_node;
      _prev_node->_next = _next_node;

      delete pos._node;
      --_size;
      return _next_node;
  }

(3) push_back() and push_front()

//Tail plug
 //void push_back(const T& val)
 //{
 //    Node* newnode = new Node(val);
 // Node* _tail_node = _head->_prev; // original tail node
 //    _tail_node->_next = newnode;
 //    newnode->_prev = _tail_node;

 //    _head->_prev = newnode;
 //    newnode->_next = _head;
 //    
 // ++_size;// number of valid data +1.
 //}
 
 // Reusing inserts is easier
 void push_back(const T& val){
     insert(end(),val);//insert in front of the head node, i.e., tail insertion
 }
 
 // Header plugs
 void push_front(const T& val) { 
     insert(begin(), val);
 }

(4) pop_back() and pop_front()

Just reuse it, but I won’t go into it.

//Tailfish
  void pop_back() { 
      erase(--end()); 
  }
  //Header deletion
  void pop_front() { 
      erase(begin()); 
  }

(5) clear()

clear:: ClearancelistValid data in the Iterate through the linked table to delete nodes sequentially, and set size to 0.

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

      _size = 0;
  }

(6) swap()

Just swap the member variables of the two linked lists.

void swap(list<T>& list)
 {
     swap(_head, list._head);
     swap(_size, list._size);
 }

concluding remarks

After reading this article, I believe you have a deeper understanding of the list, for the list of iterators, it is not like the front of thestringandvectorInstead of native pointers, they are encapsulated in a class, which makes iterators over chained lists executable.++and--etc., because the iterator class overrides these operators. That’s all for today, if you find it helpful, can you give the bull a one-click trifecta? Thanks for your support!