重读STL源码剖析:list

list

STL list实际上是一个双向链表

正因为如此,其迭代器是一个Bidirectional Iterators

迭代器的插入insert,接合splice以及删除erase都不会导致原有的迭代器(list中的其他迭代器)失效。

迭代器的数据结构:

内部一个成员node;node的类型为List的节点list_node*,也就是说迭代器的成员是一个指向list节点的指针.

迭代器的方法:

这里对++i的重载,实际上该迭代器的地址时不换的,只是更改迭代器内成员node的值

而对i++的重载,实际上是返回一个该迭代器的拷贝,然后对原迭代器++.

self& operator++()//相当于++i
{
  node=(link_type)((*node).next);
  return *this;    
}
self operator++(int)//相当于i++
{
  self tmp =*this;
  ++*this;//调用上面的operator++()
  return tmp;      
}

  

list的数据结构:

只有一个数据成员node,这个node也是一个指向节点的指针,也就是说list中的成员是一个指针。

list不仅是一个双向链表,还是一个环形链表,链表头与链表尾通过一个空白节点头尾相连,node就指向这个空节点。end()也就是这个节点。

重要函数:

begin():return (link_type)((*node).next);//空白节点的下一个节点就是链表头

end();return node;

empty():return node->next==node;//一个节点成环为空

 

原文地址:https://www.cnblogs.com/lxy-xf/p/11509502.html