[STL container] Simulate the implementation of list class templates {deep analysis of list iterators, to achieve list deep copy}

1. Core structure

template <class T>
struct list_node{<!-- --> //[1]
  T_data; //[2]
  list_node *_next; //point to the next node
  list_node *_prev; // point to the previous node
  
  list_node(const T & val = T())
    :_data(val),
    _next(nullptr),
    _prev(nullptr)
  {<!-- -->}
};

template <class T>
class Mylist{<!-- -->
  typedef list_node<T> Node; //[3]
  Node *_phead; //[4]
  //...
};

explain

  • [1] Use struct to expose member variables to facilitate direct access to node data in the Mylist class.
  • [2] The data stored in the node is a template type, so that the linked list can store various types of data including custom types.
  • [3] typedef is an alias for the type, which simplifies the code and facilitates later maintenance.
  • [4] The Mylist class has only one member variable, which is the pointer to the sentinel node (Mylist is a doubly linked circular list with the head).

Structure diagram:

2. Iterator

2.1 Structure and structure

//list_iterator
template <class T, class Ref, class Ptr>
struct list_iterator{<!-- --> //[1]
  typedef list_node<T> Node;
  typedef list_iterator<T, Ref, Ptr> iterator;
  Node *_pnode; //[2]

  list_iterator(Node *pnode) //[3]
    :_pnode(pnode)
  {<!-- -->}

explain:

  • [1] Use struct to expose member variables to facilitate direct access to the iterator pointer data in the Mylist class.
  • [2] The member variable of list_iterator has only one pointer to the node. But encapsulates the method of list iterator:
    1. dereference returns a reference to data_data
    2. Arrow returns the address of data_data
    3. The + + operation realizes the movement of the linked list pointer on the linked list, etc.
  • [3] Constructs a list iterator with a pointer to a node.
  • [4] The copy construction of list_iterator, assignment overload, and destructor can be generated by default (there is only one pointer inside, and no resource application is involved).
//begin() & end()
template <class T>
class Mylist{<!-- -->
  //...
  public:
  //iterator
  typedef list_iterator<T, T &, T*> iterator;
  typedef list_iterator<T, const T &, const T*> const_iterator; //[2]

  iterator begin(){<!-- -->
    return iterator(_phead->_next); //[1]
  }

  iterator end(){<!-- -->
    return iterator(_phead);
  }

  const_iterator begin() const{<!-- --> //[3]
    return const_iterator(_phead->_next);
  }

  const_iterator end() const{<!-- -->
    return const_iterator(_phead);
  //...
  }

explain:

  • [1] Here, the pointer to the node is used to construct an anonymous object as the return value.
  • [2] The latter two template parameters of iterator and const_iterator are different are two different instantiation types:
    • The * and -> operations of the iterator class return ordinary references and ordinary pointers.
    • The * and -> operations of the const_iterator class return const references and const pointers.
  • [3] The const here is used to modify the this pointer, that is, the object calling the function is const Mylist
    1. A const object returns a const iterator, and the return values of the const iterator’s * and -> operations are read-only const references and const pointers.
    2. In other words, the node pointed to by the constiterator cannot be modified. (similar to constant pointer const int *ptr)

Structure diagram:

2.2 operator* & operator->

 Ref operator*() const{<!-- --> //[3]
    return _pnode->_data; //[1]
  }

  Ptr operator->() const{<!-- --> //[3]
    return & amp;(_pnode->_data); //[2]
  }

//The following code uses -> to access the members of the object:
  struct Pos{<!-- -->
    int_row;
    int_col;
    Pos(int row = 0, int col = 0)
      :_row(row),
      _col(col)
    {<!-- -->}
  };

  void Test7(){<!-- -->
    cout << "Test7: " << endl;
    Mylist<Pos> mlt; //The data type stored in the linked list is a custom type
    mlt.push_back(Pos(10,10));
    mlt.push_back(Pos(20,20));

    for(auto it = mlt.begin(); it != mlt.end(); + + it)
    {<!-- -->
      cout << it->_row << ":" << it->_col << endl; //[4]
    }
  }

explain:

  • [1] The iterator dereference returns a reference to node data_data. After the iterator is dereferenced, you can directly access and modify the node data.
  • [2] operator->returns the address of the node data _data of the iterator. It is specially used for custom type _data, you can directly use the iterator plus -> to access the members of _data.
  • [3] * and -> operations involve permission issues of ordinary objects and const objects, and need to pass in two template parameters, Ref and Ptr, and generic return value.
  • [3] Ordinary objects pass in ordinary references and ordinary pointers, * and -> return references and pointers readable and writable; const objects pass in const references and const pointers, * and -> The references and pointers returned after the operation are readable but not writable.
  • [4] There should actually be two arrows here it->->_row:
    1. The first arrow calls the operator-> function which returns the address of the _data object.
    2. The second arrow is used to access the member _row of the _data object.
    3. To improve readability, an arrow was omitted when designing the C++ syntax. The operation compiler here will do special processing.

2.3 operator== & operator!=

 bool operator!=(const iterator & amp;it) const{<!-- --> //[1]
    return _pnode!=it._pnode;
  }

  bool operator==(const iterator & amp;it) const{<!-- --> //[1]
    return _pnode==it._pnode;
  }

explain:

  • [1] Here we need to distinguish between const iterator objects and const Mylist objects:
  • [1] The last const here is used to modify the this pointer, that is, the object of the called function is const iterator.
    1. const iterator means that its member variable _pnode cannot be changed, that is to say, The pointer of the iterator cannot be changed. (similar to pointer constant int *const ptr)
    2. const iterator can be dereferenced, -> access member variables, conditional judgment of ==/!=, etc. But operations such as ++ cannot be performed.

2.4 pre + + & amp; post + + 

 iterator & amp; operator + + (){<!-- -->
    _pnode = _pnode->_next; //[1]
    return *this;
  }

  iterator operator + + (int){<!-- -->
    iterator tmp(*this); //[2]
    _pnode = _pnode->_next;
    return tmp;
  }

explain:

  • [1] The + + operation of the list iterator is different from the vector iterator (the native pointer directly + +), which needs to access the _next of the node to point the pointer to the next node.
  • [2] Post-post ++ needs to copy a temporary iterator to return the previous result of ++. So you need to return by value.

Tip: There are also pre– and post–, you only need to visit the _prev of the node to point the pointer to the previous node.

3. Default member function

3.1 Structure

 void empty_initialize(){<!-- --> //[1]
    _phead = new Node;
    _phead->_next = _phead;
    _phead->_prev = _phead;
  }

  Mylist(){<!-- -->
    empty_initialize();
  }

  template <typename InputIterator>
  Mylist(InputIterator first, InputIterator last){<!-- -->
    empty_initialize(); //[2]
    while(first!=last)
    {<!-- -->
      push_back(*first);
       + + first;
    }
  }

explain:

  • [1] Here, the empty initialization is taken out separately, in order to facilitate multiplexing in the following places
  • [2] Empty initialization must be performed before the exchange, otherwise it will crash when accessing wild pointers

3.2 Copy construction & amp; assignment overload

 //void swap(Mylist<T> &mlt)
  void swap(Mylist & amp;mlt){<!-- --> //[1]
    std::swap(_phead, mlt._phead);
  }
  //Mylist<T>(const Mylist<T> &mlt)
  Mylist(const Mylist & amp;mlt){<!-- --> //[1]
    empty_initialize(); //Empty initialization must be performed before the exchange, otherwise it will crash when accessing wild pointers
    Mylist tmp(mlt.begin(), mlt.end());
    swap(tmp);
  }

  Mylist & operator=(Mylist mlt){<!-- -->
    swap(mlt);
    return *this;
  }

explain:

  • [1] When defining a class member function, the type name of the same type can omit the template parameter, but pay attention to:
    1. Type names of different classes cannot omit template parameters.
    2. Functions defined outside the class must specify template parameters.

3.3 Destruction

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

  ~Mylist(){<!-- -->
    clear(); //clear all data nodes
    delete _phead; //Release the sentinel bit node
  }

Note: Be sure to release the sentinel node!

4. Insert and delete

4.1 insert

 iterator insert(iterator pos, const T & amp;val){<!-- -->
    Node *cur = pos._pnode; //[1]
    Node *prev = cur->_prev;
    Node *newnode = new Node(val);
    prev->_next = newnode;
    newnode->_prev = prev;
    newnode->_next = cur;
    cur->_prev = newnode;
    return iterator(newnode); //[2]
  }

explain:

  • [1] list_iterator uses struct, Mylist class can directly access its members.
  • [2] Returns an iterator over the newly inserted node.

4.2 push_back & push_front

 void push_back(const T & amp;val){<!-- -->
    insert(end(), val);
  }

  void push_front(const T & amp;val){<!-- -->
    insert(begin(), val);
  }

4.3 erase

 iterator erase(iterator pos){<!-- -->
    assert(pos != end()); //[1]
    Node *cur = pos._pnode;
    Node *prev = cur->_prev;
    Node *next = cur->_next;
    next->_prev = prev;
    prev->_next = next;
    delete cur;
    return iterator(next); //[2]
  }

explain:

  • [1] Sentinel nodes cannot be deleted.
  • [2] Returns an iterator to the next node of the deleted node.

4.4 pop_back & pop_front

 void pop_back(){<!-- -->
    assert(_phead->_next != _phead); //[1]
    erase(--end());
  }

  void pop_front(){<!-- -->
    assert(_phead->_next != _phead);
    erase(begin());
  }

Note: Before pop, it must be judged as empty!