STL源码剖析(侯捷版本) —— 第四章 序列式容器（三）

传送门

STL源码剖析(侯捷版本) —— 第一章 STL 概论与版本简介
STL源码剖析(侯捷版本) —— 第二章 空間配置器 allocator
STL源码剖析(侯捷版本) —— 第三章 迭代器(Iterators)与Traits编程技巧在C++ STL中的应用

STL源码剖析(侯捷版本) —— 第四章 序列式容器（一）
STL源码剖析(侯捷版本) —— 第四章 序列式容器（二）
STL源码剖析(侯捷版本) —— 第四章 序列式容器（三）
STL源码剖析(侯捷版本) —— 第四章 序列式容器（四）
STL源码剖析(侯捷版本) —— 第四章 序列式容器（五）

SGI STL 的 list

在 SGI STL 中，list 是一个环状双向链表，支持在任意位置进行高效的插入和删除操作。这些操作的时间复杂度为常数时间。

1. list 的节点 (node)

双向链表的基本结构

list 的底层是由一个节点结构组成的双向链表：

struct _List_node_base {
  _List_node_base* _M_next;
  _List_node_base* _M_prev;
};

每个节点通过 _M_next 和 _M_prev 指针连接，构成链表。

节点的实现

每个 list 节点存储链表的值：

template <class _Tp>
struct _List_node : public _List_node_base {
  _Tp _M_data; // 节点存储的值
};

2. list 的迭代器

由于 list 的节点在内存中不连续存储，迭代器需要具备前移和后移的能力。因此，list 提供了双向迭代器（Bidirectional iterator）。

迭代器基类

struct _List_iterator_base {
  typedef size_t                     size_type;
  typedef ptrdiff_t                  difference_type;
  typedef bidirectional_iterator_tag iterator_category; // 双向迭代器标签
  _List_node_base* _M_node; // 指向节点的指针
};

前移与后移

void _M_incr() { _M_node = _M_node->_M_next; } // 前移
void _M_decr() { _M_node = _M_node->_M_prev; } // 后移

比较操作

bool operator==(const _List_iterator_base& __x) const {
  return _M_node == __x._M_node;
}
bool operator!=(const _List_iterator_base& __x) const {
  return _M_node != __x._M_node;
}

3. list 的数据结构

list 的数据结构是一个环状的双向链表，遵循 STL 的前闭后开原则。

list 的基类

template <class _Tp, class _Alloc>
class _List_base {
public:
  typedef _Alloc allocator_type;
  allocator_type get_allocator() const { return allocator_type(); }

构造与析构

构造函数会初始化一个空白节点用于标记链表的尾部：

  _List_base(const allocator_type&) {
    _M_node = _M_get_node();
    _M_node->_M_next = _M_node;
    _M_node->_M_prev = _M_node;
  }

析构函数会清空链表并释放节点：

 _List_base(const allocator_type&) {
    _M_node = _M_get_node();
    _M_node->_M_next = _M_node;
    _M_node->_M_prev = _M_node;
  }

空间管理

list 使用专属的空间配置器管理节点内存：

protected:
  typedef simple_alloc<_List_node<_Tp>, _Alloc> _Alloc_type;
  _List_node<_Tp>* _M_get_node() {
    return _Alloc_type::allocate(1); // 分配一个节点
  }
  void _M_put_node(_List_node<_Tp>* __p) {
    _Alloc_type::deallocate(__p, 1); // 释放一个节点
  }
};

4. 特点总结

• list 的底层是一个环状双向链表。
• 节点使用 _M_next 和 _M_prev 连接，形成环状结构。
• 默认有一个尾端的空白节点，用于支持 STL 的前闭后开原则。
• 插入与删除操作时间复杂度为常数时间。
• 提供双向迭代器支持前移和后移操作。