C++从入门到实战（二十）详细讲解C++List的使用及模拟实现

前言

• 上一篇博客中，我们深入学习了vector容器——作为动态数组，它以连续内存为核心，支持随机访问，但在头部/中间插入删除时效率较低。
• 本篇将聚焦STL中的另一个核心容器——list。它与vector在底层结构上完全不同：list是双向循环链表，通过节点间的指针连接数据，这使得它在头部/中间插入删除时效率极高，但不支持随机访问。
• 我们将从list的核心概念入手，讲解其常用接口（尤其是与vector差异显著的操作）、特殊接口（如splice、unique），并深入模拟实现list的底层结构，帮助大家理解链表容器的设计思想。

我的个人主页，欢迎来阅读我的其他文章
https://blog.csdn.net/2402_83322742?spm=1011.2415.3001.5343
我的C++知识文章专栏
欢迎来阅读指出不足
https://blog.csdn.net/2402_83322742/category_12880513.html?spm=1001.2014.3001.5482

C++官方list文档
https://cplusplus.com/reference/list/list/

一、什么是List

std::list 是C++ STL中的双向循环链表容器，==其底层由一个个独立的“节点”==组成，每个节点包含数据、前驱指针（指向前一个节点）和后继指针（指向后一个节点），最终形成循环结构（尾节点的后继指向头节点，头节点的前驱指向尾节点）。

1.1 List的核心特性

• 非连续内存：节点在内存中离散存储，无需整块连续内存。
• 双向访问：通过前驱/后继指针，可从任意节点向前或向后遍历。
• 高效插入删除：在任意位置（头部、中间、尾部）插入/删除节点时，仅需修改指针指向，时间复杂度为 O(1)（前提是已找到目标位置）。
• 不支持随机访问：无法通过下标（如list[i]）直接访问元素，必须从头部或尾部逐步遍历，访问效率低于vector。

1.2 List与vector的核心差异

list和vector是STL中最常用的两个序列容器，但适用场景完全不同，其核心差异如下表所示：

1.3 List的构造、拷贝构造与析构

list的构造方式与vector类似，但需注意其“链表特性”（无“容量”概念，仅关注节点数量）。

1.3.1 常用构造函数

1. 默认构造：创建空list（仅初始化“哨兵位头节点”，无数据节点）

   list<T>();  // T为元素类型（如int、自定义类）
   

   例子：

   #include <list>
   #include <iostream>
   using namespace std;
   
   int main() {
       list<int> l1;  // 空list（仅含哨兵位，无数据节点）
       list<string> l2;  // 存储string类型的空list
       cout << l1.empty() << endl;  // 输出：1（true，空）
       return 0;
   }
   

   

2. 指定数量+初始值构造：创建包含n个值为val的节点

   list<T>(size_t n, const T& val);
   

   例子：

   list<int> l(3, 10);  // 3个节点，每个节点值为10
   for (auto num : l) {
       cout << num << " ";  
   }
   

3. 迭代器范围构造：从其他容器（如vector、list）复制元素

   template <class InputIterator>
   list<T>(InputIterator first, InputIterator last);
   

   例子：

   vector<int> v = {1, 2, 3};
   list<int> l(v.begin(), v.end());  // 从vector复制元素到list
   for (auto num : l) {
       cout << num << " ";  // 输出：1 2 3
   }
   
   

   

4. 拷贝构造：复制已有list的所有节点

   list<T>(const list<T>& other);
   

   例子：

   list<int> l1 = {1, 2, 3};
   list<int> l2(l1);  // 拷贝构造，l2与l1完全相同
   for (auto num : l2) {
       cout << num << " ";  // 输出：1 2 3
   }
   

5. 列表初始化（C++11起）：直接指定元素

   list<T> l = {a, b, c, ...};  // 或 list<T> l{a, b, c, ...};
   

   例子：

   list<int> l = {10, 20, 30};  // 3个节点：10、20、30
   

1.3.2 析构函数

list的析构函数会逐个释放所有数据节点，最后释放哨兵位头节点，避免内存泄漏。

• 过程：从哨兵位开始，遍历所有数据节点，依次delete每个节点，最后delete哨兵位。
• 无需手动调用：容器生命周期结束时，析构函数自动执行。

1.4 List的迭代器

list的迭代器是理解其用法的核心——由于list内存不连续，其迭代器不是原生指针，而是封装了“节点指针”的自定义类，通过重载运算符（++、--、*、->）模拟指针行为。

1.4.1 迭代器类型与用法

list支持4种常用迭代器，用法与vector类似，但需注意仅支持双向移动（不能it+2，只能++it两次）：

示例1：正向迭代器遍历

list<int> l = {1, 2, 3};
// 正向遍历（从第一个元素到最后一个元素）
for (list<int>::iterator it = l.begin(); it != l.end(); ++it) {
    *it *= 2;  // 修改元素（2、4、6）
    cout << *it << " ";  // 输出：2 4 6
}

• begin()：指向第一个数据节点的迭代器。
• end()：指向哨兵位头节点的迭代器（不存储数据，作为遍历结束标志）。

示例2：反向迭代器遍历

list<int> l = {1, 2, 3};
// 反向遍历（从最后一个元素到第一个元素）
for (list<int>::reverse_iterator rit = l.rbegin(); rit != l.rend(); ++rit) {
    cout << *rit << " ";  // 输出：3 2 1
}

• rbegin()：指向最后一个数据节点的反向迭代器。
• rend()：指向哨兵位头节点的反向迭代器（遍历结束标志）。

示例3：const迭代器（只读遍历）

const list<int> l = {1, 2, 3};  // const list，元素不可修改
for (list<int>::const_iterator it = l.cbegin(); it != l.cend(); ++it) {
    // *it = 10;  // 错误！const迭代器不可修改元素
    cout << *it << " ";  // 输出：1 2 3
}

1.4.2 List迭代器的核心特性

• 双向移动：仅支持++it（向后移动）和--it（向前移动），不支持it + n或it - n（随机访问）。
• 迭代器不失效：插入/删除节点时，仅修改指针指向，其他节点的迭代器不会失效（vector插入时可能因扩容导致迭代器失效）。
  例外：被删除节点的迭代器会失效，需避免使用。

二、List的使用

list提供了丰富的接口，其中部分与vector同名，但实现逻辑不同；还有部分是list特有的接口（如splice、unique），需重点掌握。

2.1 List常用核心接口

以下是企业开发中list最常用的接口，按“增删查改”分类：

2.1.1 元素添加（增）

示例：

list<int> l;
l.push_back(1);    // 尾部添加：1
l.push_front(0);   // 头部添加：0 → 1
l.insert(++l.begin(), 5);  // 在0和1之间插入5 → 0 5 1

for (auto num : l) {
    cout << num << " ";  // 输出：0 5 1
}

2.1.2 元素删除（删）

示例：

list<int> l = {0, 5, 1};
l.pop_back();  // 删除尾部节点1 → 0 5

auto it = l.begin();
++it;  // it指向5
it = l.erase(it);  // 删除5，返回指向0后一个节点（哨兵位）的迭代器
cout << *it << endl;  // 错误！it指向哨兵位，无数据（需避免访问）

l.clear();  // 清空所有节点，list为空
cout << l.size() << endl;  // 输出：0

2.1.3 其他常用接口

示例：

list<int> l = {1, 2, 3};
cout << l.size() << endl;    // 输出：3
cout << l.front() << endl;   // 输出：1
cout << l.back() << endl;    // 输出：3

list<int> l2 = {4, 5};
l.swap(l2);  // 交换l和l2的节点
for (auto num : l) cout << num << " ";  // 输出：4 5

2.2 emplace_back：更高效的元素构造

emplace_back是C++11新增的接口，与push_back功能类似（尾部添加元素），但效率更高——原因是它直接在链表尾部的节点中构造对象，而push_back需要先构造临时对象，再将临时对象拷贝到节点中。

核心差异：构造次数

以自定义类Person为例，对比push_back和emplace_back的构造行为：

#include <list>
#include <string>
#include <iostream>
using namespace std;

class Person {
public:
    Person(string name, int age) : _name(name), _age(age) {
        cout << "Person构造函数调用" << endl;
    }
    Person(const Person& p) : _name(p._name), _age(p._age) {
        cout << "Person拷贝构造函数调用" << endl;
    }
private:
    string _name;
    int _age;
};

int main() {
    list<Person> l;
    cout << "--- push_back ---" << endl;
    l.push_back(Person("张三", 20));  // 1次构造（临时对象）+ 1次拷贝构造

    cout << "--- emplace_back ---" << endl;
    l.emplace_back("李四", 22);  // 仅1次构造（直接在节点中构造）
    return 0;
}

输出结果：

--- push_back ---
Person构造函数调用  // 临时对象构造
Person拷贝构造函数调用  // 拷贝到list节点
--- emplace_back ---
Person构造函数调用  // 直接在节点中构造（无拷贝）

结论：对于自定义类型，emplace_back比push_back少一次拷贝构造，效率更高；对于内置类型（如int），两者效率差异可忽略。

2.3 仿函数：自定义操作规则

“仿函数”（Functor）本质是重载了()运算符的类或结构体，可以像函数一样被调用。在list的部分接口（如sort、unique）中，仿函数用于自定义操作规则（如排序的比较逻辑、去重的判断逻辑）。

示例1：仿函数实现自定义排序

list的sort接口默认按“升序”排序，若需降序，可传入自定义仿函数：

#include <list>
#include <iostream>
using namespace std;

// 自定义仿函数：降序比较
struct Greater {
    bool operator()(int a, int b) const {
        return a > b;  // a > b时返回true，即a排在b前面
    }
};

int main() {
    list<int> l = {3, 1, 4, 2};
    l.sort(Greater());  // 传入仿函数对象，按降序排序
    for (auto num : l) {
        cout << num << " ";  // 输出：4 3 2 1
    }
    return 0;
}

示例2：仿函数实现自定义去重

unique接口默认删除“值相等”的相邻重复元素，若需按自定义规则去重（如“绝对值相等”），可传入仿函数：

// 自定义仿函数：判断绝对值是否相等
struct AbsEqual {
    bool operator()(int a, int b) const {
        return abs(a) == abs(b);
    }
};

int main() {
    list<int> l = {1, -1, 2, -2, 3};
    l.sort();  // 去重前需先排序（确保重复元素相邻）
    l.unique(AbsEqual());  // 按绝对值去重
    for (auto num : l) {
        cout << num << " ";  // 输出：-2 -1 3（或其他排序后去重结果）
    }
    return 0;
}

2.4 unique：删除相邻重复元素

unique是list的特有接口，功能是删除相邻的重复元素，但需注意两个关键点：

1. 仅删除“相邻”重复元素：若重复元素不相邻，需先调用sort()排序，确保重复元素相邻。
2. 不改变list的大小：删除的是“重复的多余元素”，最终保留一个不重复的元素。

语法

void unique();  // 默认：删除值相等的相邻元素
template <class BinaryPredicate>
void unique(BinaryPredicate pred);  // 自定义：按pred仿函数判断重复

示例（默认去重）

list<int> l = {1, 2, 2, 3, 3, 3};
l.unique();  // 删除相邻重复元素
for (auto num : l) {
    cout << num << " ";  // 输出：1 2 3
}

示例（排序后去重）

list<int> l = {2, 1, 2, 3, 1, 3};
l.sort();  // 先排序：1 1 2 2 3 3
l.unique();  // 去重后：1 2 3

2.5 splice：高效转移元素

splice是list最具特色的接口之一，功能是将一个list的元素“转移”到另一个list的指定位置，其核心优势是效率极高（O(1)时间）——仅需修改节点的前驱/后继指针，无需复制元素。

语法（三种常用形式）

示例1：转移整个list

list<int> l1 = {1, 2, 3};
list<int> l2 = {4, 5};

// 将l2的所有元素转移到l1的开头（pos = l1.begin()）
l1.splice(l1.begin(), l2);

cout << "l1: ";  // 输出：l1: 4 5 1 2 3
for (auto num : l1) cout << num << " ";
cout << "\nl2: ";  // 输出：l2: （l2为空）
for (auto num : l2) cout << num << " ";

示例2：转移单个元素

list<int> l1 = {1, 2, 3};
list<int> l2 = {4, 5};

auto it = l2.begin();  // it指向4
// 将l2中的4转移到l1的2和3之间（pos = ++l1.begin()）
l1.splice(++l1.begin(), l2, it);

cout << "l1: ";  // 输出：l1: 1 4 2 3
for (auto num : l1) cout << num << " ";
cout << "\nl2: ";  // 输出：l2: 5
for (auto num : l2) cout << num << " ";

2.6 慎用list::sort

list自带sort接口，但在实际开发中尽量避免使用，推荐将list的元素拷贝到vector中，用STL全局sort排序后再拷贝回list。原因如下：

核心原因：排序效率差异

• list::sort：基于“归并排序”实现，时间复杂度O(n log n)，但由于list不支持随机访问，每次比较都需通过迭代器移动，实际效率较低。
• 全局sort（std::sort）：基于“快速排序”（或混合排序）实现，仅支持随机访问迭代器（vector的迭代器符合要求），可直接通过指针访问元素，效率远高于list::sort。

代码对比：list::sort vs std::sort

#include <list>
#include <vector>
#include <algorithm>  // 包含std::sort
using namespace std;

int main() {
    list<int> l = {3, 1, 4, 2};

    // 1. 使用list::sort（不推荐）
    l.sort();
    for (auto num : l) cout << num << " ";  // 输出：1 2 3 4

    // 2. 推荐：拷贝到vector，用std::sort排序后拷贝回list
    vector<int> v(l.begin(), l.end());  // list → vector
    sort(v.begin(), v.end());           // 全局sort（高效）
    l.assign(v.begin(), v.end());       // vector → list

    for (auto num : l) cout << num << " ";  // 输出：1 2 3 4
    return 0;
}

结论：除非必须直接在list上排序（如元素不可拷贝），否则优先使用vector+std::sort的组合。

2.7 迭代器分类：双向、随机、单向

STL根据迭代器支持的操作，将其分为5类，其中与list、vector相关的主要是3类：单向迭代器、双向迭代器、随机访问迭代器。理解迭代器分类，能帮助我们正确选择容器和算法。

关键差异示例

vector<int> v = {1, 2, 3};
list<int> l = {1, 2, 3};

auto it_v = v.begin();
auto it_l = l.begin();

// 随机访问迭代器（vector）支持的操作（list不支持）
it_v += 2;  // 合法：直接移动2步，指向3
// it_l += 2;  // 错误：list的双向迭代器不支持随机移动

cout << *(it_v) << endl;  // 输出：3
cout << *(it_l++) << endl;  // 合法：list迭代器仅支持++

三、List的模拟实现

要深入理解list，最好的方式是模拟实现其核心结构。list的模拟实现需包含三部分：节点结构、迭代器类、list类。

3.1 底层框架：节点、迭代器、list类

3.1.1 节点结构（Node）

list的节点需存储数据、前驱指针、后继指针，定义为模板结构体：

template <class T>
struct ListNode {
    ListNode<T>* _prev;  // 前驱指针
    ListNode<T>* _next;  // 后继指针
    T _data;             // 数据

    // 节点构造函数（初始化数据和指针）
    ListNode(const T& data = T()) 
        : _prev(nullptr)
        , _next(nullptr)
        , _data(data)
    {}
};

3.1.2 迭代器类（Iterator）

list的迭代器需封装节点指针，并重载++、--、*、->等运算符，模拟指针行为：

template <class T, class Ref, class Ptr>  // Ref：引用类型，Ptr：指针类型
struct ListIterator {
    typedef ListNode<T> Node;
    typedef ListIterator<T, Ref, Ptr> Self;

    Node* _node;  // 封装节点指针

    // 迭代器构造函数
    ListIterator(Node* node) : _node(node) {}

    // 重载*：返回节点数据的引用
    Ref operator*() {
        return _node->_data;
    }

    // 重载->：返回节点数据的指针（用于自定义类型）
    Ptr operator->() {
        return &(_node->_data);
    }

    // 重载++：向后移动（指向后继节点）
    Self& operator++() {
        _node = _node->_next;
        return *this;
    }

    // 重载--：向前移动（指向前驱节点）
    Self& operator--() {
        _node = _node->_prev;
        return *this;
    }

    // 重载!=：判断两个迭代器是否指向不同节点
    bool operator!=(const Self& other) const {
        return _node != other._node;
    }

    // 重载==：判断两个迭代器是否指向相同节点
    bool operator==(const Self& other) const {
        return _node == other._node;
    }
};

• 模板参数说明：Ref和Ptr用于区分“普通迭代器”和“const迭代器”：
  • 普通迭代器：ListIterator<T, T&, T*>
  • const迭代器：ListIterator<T, const T&, const T*>

3.1.3 List类（核心框架）

list类需包含哨兵位头节点指针（简化边界操作），并提供构造、析构、拷贝构造、赋值重载等接口：

template <class T>
class List {
    typedef ListNode<T> Node;
public:
    // 迭代器类型定义
    typedef ListIterator<T, T&, T*> iterator;
    typedef ListIterator<T, const T&, const T*> const_iterator;

    // 1. 构造函数：初始化哨兵位头节点
    List() {
        _head = new Node();  // 哨兵位节点（无数据）
        _head->_prev = _head;  // 双向循环：前驱指向自己
        _head->_next = _head;
    }

    // 2. 析构函数：释放所有节点
    ~List() {
        clear();  // 先释放所有数据节点
        delete _head;  // 再释放哨兵位
        _head = nullptr;
    }

    // 3. 清空数据节点（保留哨兵位）
    void clear() {
        iterator it = begin();
        while (it != end()) {
            it = erase(it);  // erase返回下一个迭代器
        }
    }

    // 4. 获取迭代器
    iterator begin() {
        return iterator(_head->_next);  // 第一个数据节点
    }
    iterator end() {
        return iterator(_head);  // 哨兵位（结束标志）
    }
    const_iterator cbegin() const {
        return const_iterator(_head->_next);
    }
    const_iterator cend() const {
        return const_iterator(_head);
    }

private:
    Node* _head;  // 哨兵位头节点指针
};

3.2 核心接口模拟实现

基于上述框架，实现push_back、push_front、insert、erase等核心接口：

3.2.1 push_back：尾部添加节点

void push_back(const T& data) {
    Node* newNode = new Node(data);  // 创建新节点
    Node* tail = _head->_prev;       // 找到尾节点（哨兵位的前驱）

    // 调整指针：tail → newNode → _head
    tail->_next = newNode;
    newNode->_prev = tail;
    newNode->_next = _head;
    _head->_prev = newNode;
}

3.2.2 push_front：头部添加节点

void push_front(const T& data) {
    Node* newNode = new Node(data);  // 创建新节点
    Node* first = _head->_next;      // 找到第一个数据节点

    // 调整指针：_head → newNode → first
    _head->_next = newNode;
    newNode->_prev = _head;
    newNode->_next = first;
    first->_prev = newNode;
}

3.2.3 insert：指定位置插入节点

iterator insert(iterator pos, const T& data) {
    Node* newNode = new Node(data);  // 创建新节点
    Node* cur = pos._node;           // 迭代器指向的当前节点
    Node* prev = cur->_prev;         // 当前节点的前驱

    // 调整指针：prev → newNode → cur
    prev->_next = newNode;
    newNode->_prev = prev;
    newNode->_next = cur;
    cur->_prev = newNode;

    return iterator(newNode);  // 返回指向新节点的迭代器
}

3.2.4 erase：删除指定位置节点

iterator erase(iterator pos) {
    Node* cur = pos._node;           // 要删除的节点
    Node* prev = cur->_prev;         // 前驱节点
    Node* next = cur->_next;         // 后继节点

    // 调整指针：prev → next（跳过cur）
    prev->_next = next;
    next->_prev = prev;
    delete cur;  // 释放当前节点

    return iterator(next);  // 返回指向后继节点的迭代器（避免迭代器失效）
}

3.3 开源代码解析（SGI STL为例）

SGI STL是最经典的STL实现之一，其list的设计与我们的模拟实现核心一致，但增加了更多细节优化：

3.3.1 节点结构（SGI STL）

template <class T>
struct __list_node {
    typedef void* void_pointer;
    void_pointer prev;  // 用void*，需强转（兼容不同类型）
    void_pointer next;
    T data;
};

• 与我们的模拟实现差异：前驱/后继用void*，需在迭代器中强转为__list_node*，兼容性更强。

3.3.2 迭代器（SGI STL）

template <class T, class Ref, class Ptr>
struct __list_iterator {
    typedef __list_node<T>* link_type;
    link_type node;  // 封装节点指针

    // 重载++、--、*、->等运算符（逻辑与我们的模拟实现一致）
    Ref operator*() const { return (*node).data; }
    Ptr operator->() const { return &(operator*()); }
    __list_iterator& operator++() { node = (link_type)((*node).next); return *this; }
    __list_iterator& operator--() { node = (link_type)((*node).prev); return *this; }
    
};

• 核心逻辑与我们的模拟实现完全一致：通过封装节点指针，重载运算符模拟双向移动。

3.3.3 list类（SGI STL）

SGI STL的list类同样使用哨兵位头节点，并提供了sort、splice、unique等接口，实现逻辑与我们的模拟实现相似，但增加了：

1. 内存分配器：使用allocator管理节点内存（我们的模拟实现直接用new，SGI用自定义内存分配器，效率更高）。
2. 空节点优化：当list为空时，哨兵位节点可复用（减少内存开销）。
3. 更多接口：如merge（合并两个有序list）、reverse（反转list）等。

以上就是这篇博客的全部内容，下一篇我们将继续探索STL中List的更多内容。

我的个人主页，欢迎来阅读我的其他文章
https://blog.csdn.net/2402_83322742?spm=1011.2415.3001.5343
我的C++知识文章专栏
欢迎来阅读指出不足
https://blog.csdn.net/2402_83322742/category_12880513.html?spm=1001.2014.3001.5482