STL upper series - detailed explanation of list container

Traditional art can

Xiaobian is a non undergraduate freshman. I won't repeat it , Welcome the boss to point out （QQ：1319365055）
Previous blogs Am I ！ Am I ！ Please search for bloggers 【 Know the blue of the sky 】

Non Keban transcoding community sincerely invites you to settle in
friends , All the way north , Back fireworks , Before the other shore is suffering
A person's fighting alone is not as good as a group of people's forging ahead
This is the community I formed with my dream partner , We sincerely invite people with lofty ideals to join us ！！
Community users' good articles are refined （“ pacesetter ” The number of words in the article 2000+ Refinement ,“ Talent show" ” The number of words in the article 1500+ Refinement ）
Through ： Community link point i

Strive to create WeChat official account for transcoding communities

---

list

We all know C++ The container mechanism is essentially an encapsulation idea ,string Is the encapsulation of string array , and vector It is the encapsulation of the sequence table that supports dynamic development , Today's list It is no exception that it encapsulates the two-way leading circular linked list .

The advantage of this structure is that it supports two-way iteration , Allow insertion and deletion at any position within the constant range , High efficiency in insert and delete operations , But the defect is also the same as the two-way lead cycle linked list , Random access of subscripts is not supported .

list The constructor of is declared as follows ：

list<int>a{
    1,2,3,4,5}
list<int>a(n)    // Statement n Elements , Each element defaults to 0
list<int>a(n, a)  // Statement n Elements , Every element is a
list<int>a(iterator.begin, iterator.end)  // The elements in the sequence specified by the declaration interval come from the interval ,begin  and  end  Is the iterator of the interval 

list Traverse

list The iterator calls the member functions of the container begin() Get a point to the beginning of the container iterator,end() Function to get list Next position of the end , We can use iterators for list Traversal .

list<int>::iterator it = list.begin();
	while (it != list.end())
	{
    
		*it += 1;
		cout << *it <<" ";
		it++;
	}

Of course, it can also be directly simple and rough for Get it done ：

for (auto& e : list)
	{
    
		cout << e << " ";
	}

list iterator

because list It's a list structure , Naturally, he can't talk to vector Equally superior use of subscripts for access , We still use iterators to access , He and vector Iterators of are different , vector,string Belong to Random iterator , and list yes Bidirectional iterator , The current types of iterators are 5 Kind of ： Input iterator 、 Output iterator 、 Forward iterator 、 Bidirectional iterator 、 Random access iterator ; It also supports rbegin() And rend() The reverse iterator of （ It also supports self definition ）.

We are defining list When iterator , Due to different data types , We need to define two iterators ： Common iterators and const iterator , because const The data type can only be const Iterator to access .

Ordinary iterators are very simple ：

The same rule we just need take iterator begin（） and iterator end（） Add after statement const Define it again .

however ！ The problem is coming. , Considering whether the data type is const type , What if it is a pointer type or a reference type ？

Don't panic at this time , The idea is very simple, that is, in the template + function overloading , Include the reference type and pointer type ：

template<class T,class Ref,class Ptr>
struct __list_itrator
{
    
   typedef list_node<T> Node;
   typedef __list_itrator <T,T*,T&> iterator;
   Node* node;
   Ref operator*()
   {
    
      return node->data;
   }// heavy load  &  Back to  Ref  Reference type 
   Ptr operator*()
   {
    
      return &node->data;
   }// heavy load  *  Back to  Ptr  Pointer types 
}

const The same goes for iterators const Can be modified .

Iterator failure

list and vector There is also an iterator failure mechanism , But and vector comparison list The situation should be simpler , After deleting a node , Only the iterator pointing to the current node fails , The iterators before and after it are still valid , Because the bottom layer is discontinuous space , Only deleted nodes become invalid . General situation and solution reference vector One article ：STL Upper series ——vector Container details

Performance comparison

list Having a discrete memory space , If you need a lot of inserts and deletions , Use list It can operate efficiently , contrast vector and list,vector There is no need to move data when inserting data in the tail ,list It is also easy to find the tail for the two-way circular linked list , Therefore, the efficiency of inserting data in the tail is the same ,vector The head insertion efficiency is extremely low , Need to move a lot of data , It is precisely because the efficiency of inserting data in the header is very low , So no push_front Methods , however list Relatively independent individuals do not have this problem , therefore list It's easy to achieve push_back and push_front .

To sum up ：

vector advantage ：

1. Suitable for tail insertion and tail deletion , Random access ,CPU High cache hit rate

shortcoming ：

1. Not suitable for the insertion and deletion of the head and middle , It is inefficient to move data
2. Capacity expansion has a certain performance consumption , There is a certain degree of waste of space

list advantage ：

1. The efficiency of inserting and deleting at any position is high （ O(1) ）
2. Support dynamic development , Apply for free space on demand

shortcoming ：

1. Random access is not supported
2. CPU Low cache hit rate

list Realization

namespace bite
{
    
  // List Node class of 
  template<class T>
  
  struct ListNode
  {
    

    ListNode(const T& val = T()): _pPre(nullptr), _pNext(nullptr), _val(val)
    {
    }
    ListNode<T>* _pPre;

    ListNode<T>* _pNext;

    T _val;

  };
  //List Iterator class for 

  template<class T, class Ref, class Ptr>

  class ListIterator

  {
    

    typedef ListNode<T>* PNode;

    typedef ListIterator<T, Ref, Ptr> Self;

  public:

    ListIterator(PNode pNode = nullptr):_pNode(pNode)
    {
    }
    ListIterator(const Self& l): _pNode(l._pNode)
    {
    }

    T& operator*()
    {
    
      return _pNode->_val;
    }
    
    T* operator->()
    {
    
      return &*this;
    }
    
    Self& operator++()
    {
    
      _pNode = _pNode->_pNext;
      return *this;
    }

    Self operator++(int)
    {
    
      Self temp(*this);
      _pNode = _pNode->_pNext;
      return temp;
    }

    Self& operator--()
    {
    
      _pNode = _pNode->_pPre;
      return *this;
    }

    Self& operator--(int)
    {
    
      Self temp(*this);
      _pNode = _pNode->_pPre;
      return temp;
    }

    bool operator!=(const Self& l)
    {
    
      return _pNode != l._pNode;
    }

    bool operator==(const Self& l)
    {
    
      return !(*this!=l);
    }

  private:
  
    PNode _pNode;
  };
  //list class 

  template<class T>

  class list
  {
    
    typedef ListNode<T> Node;
    typedef Node* PNode;

  public:

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

  public:
    // List Construction 
    list()
    {
    
      CreateHead();
    }

    list(int n, const T& value = T())
    {
    
      CreateHead();
      for (int i = 0; i < n; ++i)
       push_back(value);
    }

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

    list(const list<T>& l)
    {
    
      CreateHead();
      //  use l Elements in construct temporary temp, Then exchange with the current object 
      list<T> temp(l.cbegin(), l.cend());
      this->swap(temp);
    }

    list<T>& operator=(const list<T> l)
    {
    
      this->swap(l);
      return *this;
    }
    
    ~list()
    {
    
      clear();
      delete _pHead;
      _pHead = nullptr;
    }

    // List  iterator 

    iterator begin()
    {
    
      return iterator(_pHead->_pNext);
    }
    
    iterator end()
    {
    
      return iterator(_pHead);
    }

    const_iterator begin()const

    {
    
      return const_iterator(_pHead->_pNext);
    }

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

    // List  Capacity operation 

    size_t size()const
    {
    
      size_t size = 0;
      ListNode *p = _pHead->_pNext;
      while(p != _pHead)
      {
    
        size++;
        p = p->_pNext;
      }
      return size;       
    }

    bool empty()const
    {
    
      return size() == 0;
    }
    
    // List  visit 
    T& front()
    {
    
      assert(!empty());
      return _pHead->_pNext->_val;
    }
    const T& front()const
    {
    
      assert(!empty());
      return _pHead->_pNext->_val;
    }

    T& back()
    {
    
     assert(!empty());
      return _pHead->_pPre->_val;
    }

    const T& back()const
    {
    
      assert(!empty());
      return _pHead->_pPre->_val;
    }
    
    // List  modify 

    void push_back(const T& val)
    {
    
      insert(begin(), val);
    }

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

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

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

    //  stay pos The value inserted before the position is val The node of 

    iterator insert(iterator pos, const T& val)
    {
    
      PNode pNewNode = new Node(val);
      PNode pCur = pos._pNode;
      //  First insert the new node into 
      pNewNode->_pPre = pCur->_pPre;
      pNewNode->_pNext = pCur;
      pNewNode->_pPre->_pNext = pNewNode;
      pCur->_pPre = pNewNode;
      return iterator(pNewNode);
    }

    //  Delete pos The nodes of the location , Return to the next location of the node 

    iterator erase(iterator pos)
    {
    
      //  Find the node to delete 
      PNode pDel = pos._pNode;
      PNode pRet = pDel->_pNext;
      //  Remove the node from the linked list and delete 
      pDel->_pPre->_pNext = pDel->_pNext;
      pDel->_pNext->_pPre = pDel->_pPre;
      delete pDel;
      return iterator(pRet);
    }

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

    void swap(List<T>& l)
    {
    
      pNode tmp = _pHead;
      _pHead = l._pHead;
      l._pHead = tmp;
    }

  private:

    void CreateHead()
    {
    
      _pHead = new Node;
      _pHead->_pPre = _pHead;
      _pHead->_pNext = _pHead;
    }

    PNode _pHead;
  };

}
 

Come here today , Moisten the family .