C++第十二节：详解list （从零掌握list的使用与模拟实现）

一、list介绍

list是C++ STL中的序列式容器，底层实现为双向循环链表（通常带有一个头节点）。与vector不同，list中的元素在内存中不是连续存储的，而是通过指针链接。这种结构使得list在任意位置插入和删除元素非常高效，时间复杂度为O(1)，但随机访问（如operator[]）不被支持，访问第i个元素需要遍历链表，时间复杂度为O(n)。

list的头文件是，定义在命名空间std中。一个典型的list节点包含数据域和指向前后节点的指针。

二、list的使用

1. 构造函数

list提供了多种构造函数：

• list lst; 构造空list
• list lst(n, val); 构造包含n个val的list
• list lst(begin, end); 用迭代器区间构造
• list lst(const list& other); 拷贝构造

示例：list l1(5, 10); // 5个10

2. 迭代器

list的迭代器是双向迭代器，支持++和--操作，但不支持随机访问。常用函数有begin(), end(), rbegin(), rend()等。

3. 容量与元素访问

• empty()：判断是否为空
• size()：返回元素个数（C++11前为O(n)，C++11后为O(1)）
• front()、back()：访问首尾元素

4. 修改器

• push_back(val)、push_front(val)：尾插/头插
• pop_back()、pop_front()：尾删/头删
• insert(pos, val)：在pos位置前插入val
• erase(pos)：删除pos位置元素
• clear()：清空list

5. 操作函数

list还提供了一些特有操作，如splice（转移元素）、remove（移除特定值）、unique（去重）、merge（合并有序链表）、sort（排序）、reverse（反转）等。

三、list模拟实现

理解list的最好方式是自己实现一个简化版。我们将从节点设计、迭代器封装到list类逐步构建。

1. 节点设计

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

2. 迭代器封装

迭代器需要支持基本操作：解引用、递增、递减、比较等。我们可以设计一个迭代器类模板。

    templatestruct ListIterator {    typedef ListNode* NodePtr;    typedef ListIterator Self;    NodePtr _node;        ListIterator(NodePtr node = nullptr) : _node(node) {}        Ref operator*() { return _node->data; }    Ptr operator->() { return &_node->data; }        Self& operator++() { _node = _node->next; return this; }    Self operator++(int) { Self tmp(this); _node = _node->next; return tmp; }    Self& operator--() { _node = _node->prev; return this; }    Self operator--(int) { Self tmp(this); _node = _node->prev; return tmp; }        bool operator==(const Self& it) const { return _node == it._node; }    bool operator!=(const Self& it) const { return _node != it._node; }};  

3. list类框架

    templateclass list {    typedef ListNode Node;    Node* _head;  // 头节点，不存储数据public:    typedef ListIterator iterator;    typedef ListIterator const_iterator;        // 构造函数、析构函数、拷贝控制等};  

4. 重要函数实现

以push_back为例：

    void push_back(const T& val) {    Node* newNode = new Node(val);    Node* tail = _head->prev;    tail->next = newNode;    newNode->prev = tail;    newNode->next = _head;    _head->prev = newNode;}  

其他函数如insert、erase、迭代器操作等类似，需注意边界情况。

总结

本文全面介绍了C++ list的list介绍、常用接口的list使用，并给出了list模拟实现的核心代码。希望通过本教程，你能深入理解list的原理，并在实际开发中灵活运用。下一节我们将探讨其他容器，敬请期待！