Article title

list,stl Basic container linked list in , Specifically, it is a circular two-way linked list .

Realization

node

As a linked list , Let's first look at the important basic elements - node . A node node The composition is as follows :

• prev： Front node
• next： Post node
• data : data

iterator

A pointer is required inside the iterator (list_type *node) Point to the corresponding node , And it can realize some basic operations of iterators .

• ++

self& operator++(){     // ++iter;
    node = node->next;
    return *this;
} 

self& operator++(){     // iter++;
    self tmp = *this;
    ++*this;
    return tmp;
}

• ->
• *

self & opearator *()const{
    return node->data;
}

The iterator basic operation passes through the node pointer node To achieve .

list

For linked lists , Only one node pointer is required pNode To achieve a two-way circular linked list . The node pointer points to the trailing blank node .
For related operations of linked lists , Analyze one by one

• begin : pNode->next

• end : pNode

• empty : pNode->next == pNode

• size : distance(begin(), end(), result

• front : *begin(), Using an iterator * operation

• back : *end(), ditto

Next, consider push,pop,insert,erase Wait for the operation

• insert
  notes :stl all insert All operations are inserted before the current position
  insert(iterator pos, const T &x); stay pos Before the position Insert elements x, Involving old and new nodes next and prev Pointer replacement, etc , No specific analysis , The interior is also very simple .
  Note here ： This function returns the iterator of the new node , also pos The position of the iterator does not change .

• push_back
  call insert operation insert(end(),x)

• push_front
  call insert operation insert(begin(),x)

• erase
  Delete a node , Note that the function returns the deleted node pos Iterator for the next node of

• pop_front

• pop_back

• clear

• remove
  remove(const T &x) Remove all elements with values of x

• unique
  Remove consecutive but identical elements , eg: unique Before and after
  1,2,2,2,1,3,3,4,1
  1,2,1,3,4,1

• transfer （ Internal operation ）
  It belongs to internal operation - transfer ,transfer(positon,first,last) take [first,last) All the elements in the postion Before , Make a series of nodes next and prev Replacement operation of (3 link 6 Line operation ). For subsequent merge,sort And so on .
  Be careful ：position The linked list can be linked to [first,last) The linked list belongs to the same , It can also belong to different .
  When they belong to the same ,position Can't be in [first,last) Within the interval .

• splice
  splice(iterator pos,list &x);
  splice(iterator pos, list &, iterator first, iterator last);
  External interface , Internal calls transfer operation .

• sort
  list You can only use your own functions sort Sort , From small to large , Out of commission stl Algorithm sort Function to sort .

When list When the element is a non basic data type such as a class or structure , Need to be right >,< Wait for heavy load . The details are analyzed in the sorting section .

• reverse
  Reverse the linked list , This operation can be used to change from ascending to descending .

• merge
  Linked list merging ,merge(x) Link list x Merge into this On .