C++ list详解：从使用到底层模拟实现（STL双向链表完全指南）

一、C++ list的基本介绍

list是C++ STL中的序列容器，它允许在序列的任何位置进行常数时间内的插入和删除操作。list的底层是一个双向链表，每个节点存储一个元素以及指向前后节点的指针。由于这种结构，list在插入和删除时不需要移动其他元素，非常高效。但缺点是只能双向顺序访问，无法像vector那样通过下标随机访问。

二、list的使用方法

要使用list，需要包含头文件。list定义在命名空间std中。

1. list的构造函数

list提供了多种构造函数，以下是一些常用形式：

std::list l1;                      // 空liststd::list l2(5, 100);                // 5个值为100的元素std::list l3(l2.begin(), l2.end());  // 迭代器范围初始化std::list l4(l3);                     // 拷贝构造

2. list迭代器

list的迭代器是双向迭代器，支持++和--操作，但不支持随机访问。常用迭代器操作：

std::list::iterator it = l1.begin();while (it != l1.end()) {    // 处理 *it    ++it;}

3. 容量相关

empty()、size()等：

if (!l.empty()) {    size_t s = l.size();}

4. 元素访问

list提供front()和back()访问首尾元素。

l.front() = 10;  // 修改第一个元素int last = l.back();

5. 修改器

push_back、push_front、insert、erase等：

l.push_back(1);l.push_front(2);auto it = l.begin();++it;l.insert(it, 100);   // 在it位置之前插入100l.erase(it);         // 删除it指向的元素

三、list的模拟实现

理解list底层实现有助于更好地使用它。下面我们将模拟实现一个简化版的list，主要包括节点、迭代器和list类。

1. 节点结构

每个节点包含数据和前后指针：

template struct ListNode {    T data;    ListNode* prev;    ListNode* next;    ListNode(const T& val = T()) : data(val), prev(nullptr), next(nullptr) {}};

2. 迭代器封装

迭代器需要封装节点指针，并重载相关操作：

template struct ListIterator {    typedef ListNode Node;    Node* ptr;    // ...    T& operator*() { return ptr->data; }    ListIterator& operator++() { ptr = ptr->next; return *this; }    // 其他操作};

3. list类框架

template class List {public:    typedef ListIterator iterator;    List() { create_head(); }    ~List() { clear(); delete head_; }    // 其他成员private:    ListNode* head_;  // 头节点（哨兵）    size_t size_;};

通过模拟实现，我们可以更清晰地看到list的内部运作机制。例如插入操作需要修改前后节点的指针，这正是list使用方法中高效插入的根源。

总结：C++ list是STL中重要的双向链表容器，掌握其list使用方法和list底层实现对写出高效C++代码至关重要。希望本文能帮助你深入理解C++ STL list。