STL源码分析（三）——列表

gcc 版本4.4.0

本次我们将关注STL中list的实现方式。该数据结构可分为两个主要组成部分，即list的整体结构以及构成其基础的节点结构。
首先对list的节点（_List_node）进行分析。

list 节点

鉴于 _List_node 继承自 _List_node_base，因此有必要首先对 _List_node_base 进行分析。

    struct _List_node : public _List_node_base
    
    
    AI写代码c
    
    运行

_List_node_base 类仅包含两个数据成员，分别为指向先前节点的指针和指向后续节点的指针。通过这一结构特征可以明确判定，list 实际上是一种双向链表的实现形式。

      struct _List_node_base
      {
    _List_node_base* _M_next;
    _List_node_base* _M_prev;
    ...
      };
    
    
    AI写代码c
    
    运行

_List_node 结构体中仅包含一个数据成员，即 data 字段。

     template<typename _Tp>
    str