SGI list代码分析与原理解析[2]

2013年5月1日 由 Creater 留言 »

SGI list代码分析与原理解析[1]分析了list节点定义,迭代器定义,list类的定义。再来总结一下:
客户需要使用list这个容器,那么就需要通过list配套的迭代器iterator,所以list中有

typedef __list_iterator<T, T&, T*>             iterator;

这个迭代器如何与list关联的呢?比如客户有如下代码

list<int> myList;
myList.begin();

客户想返回头迭代器,而list内部使用的是link_type。看下面的代码就知道了
list类定义中有

iterator begin() { return (link_type)((*node).next); }

__list_iterator类的定义中有

  
link_type node;
__list_iterator(link_type x) : node(x) {}

这样子,客户就可以返回想要的迭代器了。并且能够通过iterator来操作元素了。

list由于使用一个指针就可以来完整访问整个链表,那么list如何设计才能具有如此的性质,初始化的node( link_type node)应该是什么?
其实list设置在尾部有一个空白节点,初始化时让node指向该空白节点,而且符合了stl要求的“前闭后开”特性。

由于node指向尾部空白节点,即为end(),那么begin则为

iterator begin() { return (link_type)((*node).next); }
  const_iterator begin() const { return (link_type)((*node).next); }
  iterator end() { return node; }
  const_iterator end() const { return node; }

可以看出node的下一节点则是头部节点。这样判断list为空也好判断

bool empty() const { return node->next == node; }

因为node的前驱和后继都初始化为它自己。

  void empty_initialize() { 
    node = get_node();
    node->next = node;
    node->prev = node;
  
广告位

发表评论

你必须 登陆 方可发表评论.