C++ STL list 容器底层实现详解

概述

本文将聚焦于 list 容器的底层实现，分析其常用接口与应用逻辑。

核心数据结构

list 的底层基于双向链表构建。主要通过三个部分协同工作：存储数据的节点、封装节点的迭代器以及实现增删查改的容器类本身。

节点结构

template<class T> struct list_node {
    typedef list_node<T> Node;
    T _data;
    Node* _prev;
    Node* _next;
};

这里定义了前驱指针 _prev、后继指针 _next 以及数据域 _data。由于结构体较长，实践中常通过 typedef 将其重命名为 Node。

迭代器封装

迭代器负责屏蔽底层指针的细节，提供统一的访问接口。

template<class T, class Ref, class Ptr> struct list_iterator {
    typedef list_node<T> Node;
    typedef list_iterator< T, Ref, Ptr> Self;
    Node* _pnode;
};

模板参数 Ref 和 Ptr 是关键设计。它们允许同一个类模板同时生成普通迭代器和常量迭代器。例如，普通迭代器传入 T& 和 T* 以支持修改，而常量迭代器传入 const T& 和 const T* 以保护数据。

容器类定义

template<class T> class list {
public:
    typedef list_node<T> Node;
    typedef list_iterator<T, T&, T*> iterator;
    typedef list_iterator<T, const T&, const T*> const_iterator;
private:
    Node* _head; // 哨兵位结点指针
};

注意 _head 指向的是哨兵节点（Sentinel），而非第一个有效元素。这种设计能简化边界条件的处理。