8、【C++】STL容器：list的用法及模拟实现

目录

一、list概述

1. list的定义与特性

list是C++标准库提供的双向链表容器，定义在<list>头文件中。它由节点组成，每个节点包含数据域和两个指针域（前驱指针prev和后继指针next），通过指针将节点连接成链表。

核心特性：

  • 双向遍历：支持向前和向后遍历（通过++和--操作符）。
  • 动态节点：元素存储在独立节点中，节点间通过指针连接，非连续存储。
  • 高效插入删除：在任意位置插入/删除元素只需修改指针，时间复杂度O(1)（已知位置时）。
  • 无随机访问：访问第n个元素需从头遍历，时间复杂度O(n)。
  • 不浪费空间：除节点指针外无额外空间开销（对比vector的预分配容量）。

节点结构示意图：

[prev] <---> [data|prev|next] <---> [data|prev|next] <---> [next]
             头节点                  中间节点                  尾节点

2. list与vector的对比

特性list（双向链表）vector（动态数组）
内存布局非连续存储，节点通过指针连接连续存储，元素在一块内存中
随机访问不支持（O(n)）支持（O(1) via operator[]）
插入删除（中间）O(1)（已知位置）O(n)（需移动元素）
插入删除（尾部）O(1)O(1)（未扩容时）/O(n)（扩容时）
空间利用率无浪费（按需分配节点）可能浪费预分配容量
迭代器类型双向迭代器（Bidirectional）随机访问迭代器（Random Access）
迭代器失效删除节点时仅当前迭代器失效扩容/插入时可能导致所有迭代器失效

3. list的应用场景

list适用于频繁插入删除且无需随机访问的场景：

  • 实现队列/栈：list的push/pop操作在头尾均为O(1)。
  • 频繁修改中间元素：如链表式数据结构（邻接表、多项式表示）。
  • 大数据量动态调整：避免vector扩容时的内存拷贝开销。

反例场景：

  • 需要随机访问（如v[1000]）。
  • 数据量小且访问频繁（vector的缓存局部性更优）。

二、list的基本用法

1. 构造函数与初始化

list提供多种构造方式，适应不同初始化需求：

构造函数原型功能描述
list()默认构造，创建空list
list(size_t n, const T& val = T())创建包含n个val的list
list(const list& lst)拷贝构造，复制lst的内容
list(InputIt first, InputIt last)范围构造，复制[first, last)区间的元素
list(std::initializer_list<T> il)列表初始化（C++11），如list<int> l{1,2,3}

示例：

#include <list>
#include <vector>

int main() {
    // 默认构造
    std::list<int> l1;
    
    // 包含5个3的list
    std::list<int> l2(5, 3); // {3,3,3,3,3}
    
    // 拷贝构造
    std::list<int> l3(l2);
    
    // 范围构造（从vector拷贝）
    std::vector<int> v = {1,2,3};
    std::list<int> l4(v.begin(), v.end()); // {1,2,3}
    
    // 列表初始化（C++11）
    std::list<int> l5{1,2,3,4}; // {1,2,3,4}
    
    return 0;
}

2. 元素访问与遍历

list不支持随机访问，元素访问需通过迭代器或front()/back()：

（1）元素访问接口
  • front()：返回第一个元素的引用（O(1)）。
  • back()：返回最后一个元素的引用（O(1)）。
  • 无operator[]和at()：不支持随机访问。
（2）遍历方式
  • 迭代器遍历：支持正向和反向遍历。
  • 范围for：基于迭代器实现，语法简洁。

示例：

std::list<int> l = {1,2,3,4};

// 正向迭代器遍历
std::list<int>::iterator it = l.begin();
for (; it != l.end(); ++it) {
    std::cout << *it << " "; // 1 2 3 4
}

// const迭代器遍历（只读）
std::list<int>::const_iterator cit = l.cbegin();
for (; cit != l.cend(); ++cit) {
    std::cout << *cit << " "; // 1 2 3 4
}

// 反向迭代器遍历
std::list<int>::reverse_iterator rit = l.rbegin();
for (; rit != l.rend(); ++rit) {
    std::cout << *rit << " "; // 4 3 2 1
}

// 范围for遍历
for (int x : l) {
    std::cout << x << " "; // 1 2 3 4
}

3. 容量与大小管理

list的容量管理接口较简单，无需预分配内存：

  • size()：返回元素个数（O(1)，C++11后）。
  • empty()：判断是否为空（O(1)）。
  • resize(size_t n, T val = T())：调整大小，新增元素用val填充。

示例：

std::list<int> l = {1,2,3};
l.resize(5, 0); // {1,2,3,0,0}
l.resize(2);    // {1,2}
std::cout << l.size() << std::endl; // 2
std::cout << l.empty() << std::endl; // false

4. 修改操作

list提供丰富的修改接口，核心操作如下：

（1）头尾操作
  • push_front(const T& val)：头插元素（O(1)）。
  • pop_front()：头删元素（O(1)）。
  • push_back(const T& val)：尾插元素（O(1)）。
  • pop_back()：尾删元素（O(1)）。
（2）任意位置操作
  • insert(iterator pos, const T& val)：在pos位置插入val（O(1)，已知pos时）。
  • erase(iterator pos)：删除pos位置元素（O(1)，已知pos时）。
  • splice(iterator pos, list& l)：将l的所有元素移到pos位置（O(1)，无拷贝）。
（3）其他操作
  • swap(list& l)：交换两个list的内容（O(1)，仅交换头指针）。
  • clear()：清空所有元素（O(n)，删除每个节点）。
  • remove(const T& val)：删除所有值为val的元素（O(n)）。
  • unique()：删除连续重复元素（需先排序，O(n)）。
  • sort()：排序（归并排序，O(n log n)）。

示例：

std::list<int> l = {2,1,3};
l.push_front(0); // {0,2,1,3}
l.push_back(4);  // {0,2,1,3,4}
auto it = std::find(l.begin(), l.end(), 1);
l.insert(it, 5); // {0,2,5,1,3,4}
l.erase(it);     // {0,2,5,3,4}（it指向1，删除后失效）
l.sort();        // {0,2,3,4,5}
l.unique();      // 无连续重复元素，保持不变
l.remove(3);     // {0,2,4,5}

三、list的排序

1. list::sort与std::sort的区别

list不能直接使用std::sort，需使用自身的sort成员函数，核心区别如下：

特性list::sortstd::sort
迭代器要求双向迭代器（Bidirectional）随机访问迭代器（Random Access）
算法实现稳定归并排序（Stable Merge Sort）快速排序（不稳定，C++11后为IntroSort）
时间复杂度O(n log n)O(n log n)
空间复杂度O(log n)（递归栈）O(log n)（递归栈）
原位排序是（仅修改指针）是（修改元素位置）
适用容器list（双向链表）vector、array等（随机访问容器）

为什么list不能用std::sort？
std::sort需要通过迭代器进行随机访问（如it + n），而list的双向迭代器仅支持++和--操作，不支持算术运算，因此无法满足std::sort的迭代器要求。

2. list::sort的实现原理（归并排序）

list::sort采用双向链表的归并排序，核心步骤：

  1. 分割：将链表递归分割为两半，直到每个子链表长度≤1。
  2. 合并：将两个有序子链表合并为一个有序链表（通过调整指针实现，无内存分配）。
  3. 递归合并：重复合并步骤，直至得到完整有序链表。

归并排序优势：

  • 稳定排序：相等元素保持原有顺序。
  • 链表友好：无需随机访问，通过指针操作合并，效率高。

3. 排序示例与性能对比

示例：

#include <list>
#include <vector>
#include <algorithm>
#include <chrono>
#include <iostream>

int main() {
    // 生成100万个随机数
    std::vector<int> v(1000000);
    std::generate(v.begin(), v.end(), rand);
    std::list<int> l(v.begin(), v.end());
    
    // 测试list::sort
    auto start = std::chrono::high_resolution_clock::now();
    l.sort();
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << "list::sort: " 
              << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() 
              << "ms" << std::endl;
    
    // 测试vector + std::sort
    std::list<int> l2(v.begin(), v.end());
    start = std::chrono::high_resolution_clock::now();
    std::vector<int> v2(l2.begin(), l2.end()); // list->vector
    std::sort(v2.begin(), v2.end());
    l2.assign(v2.begin(), v2.end()); // vector->list
    end = std::chrono::high_resolution_clock::now();
    std::cout << "vector + std::sort: " 
              << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() 
              << "ms" << std::endl;
    
    return 0;
}

性能对比结果（仅供参考）：

  • list::sort：约200ms（无内存拷贝，仅指针操作）。
  • vector + std::sort：约50ms（vector随机访问更优，std::sort算法效率更高）。

结论：尽管list::sort无需移动元素，但std::sort的算法优化（如缓存局部性）通常更高效。实际应用中，若需排序，可将list转为vector排序后再转回list（数据量大时更优）。

四、迭代器

1. list迭代器的类型与特性

list迭代器属于双向迭代器（Bidirectional Iterator），支持以下操作：

  • ++it/it++：后移迭代器（指向下一个节点）。
  • --it/it--：前移迭代器（指向前一个节点）。
  • *it：解引用，获取元素引用。
  • it1 == it2/it1 != it2：比较迭代器是否指向同一节点。

不支持的操作：

  • 算术运算（it + n、it - n）。
  • 关系运算（<、>、<=、>=）。

2. list的迭代器失效问题

list迭代器失效场景远少于vector，仅在删除节点时发生：

  • 删除节点：指向被删除节点的迭代器失效，其他迭代器不受影响。
  • 插入节点：所有迭代器均有效（仅修改指针，节点地址不变）。

示例：

std::list<int> l = {1,2,3,4};
auto it = l.begin();
++it; // 指向2
l.erase(it); // 删除2，it失效
// *it = 5; // 未定义行为（it指向已删除节点）

// 正确做法：使用erase返回的新迭代器
it = l.begin();
it = l.erase(it); // 删除1，it指向2（原3）
*it = 5; // 有效，l变为{5,3,4}

3. 迭代器的功能分类

C++标准将迭代器分为五类，功能递增：

迭代器类型支持操作典型容器
输入迭代器++、*（只读）、==、!=istream_iterator
输出迭代器++、*（只写）ostream_iterator
前向迭代器输入+输出迭代器功能，支持多遍遍历forward_list
双向迭代器前向迭代器功能 + --list、set、map
随机访问迭代器双向迭代器功能 + 算术运算（+n、-n）、关系运算（<、>等）vector、deque、array

4. list迭代器的模拟实现

4.1 普通迭代器

迭代器本质是节点指针的封装，需重载++、--、*、->等操作符：

// 节点结构
template <typename T>
struct __list_node {
    T _data;
    __list_node* _prev;
    __list_node* _next;
    __list_node(const T& val = T()) 
        : _data(val), _prev(nullptr), _next(nullptr) {}
};

// 普通迭代器
template <typename T>
struct __list_iterator {
    typedef __list_node<T> node;
    typedef __list_iterator<T> self;

    node* _pnode; // 指向链表节点的指针

    __list_iterator(node* p) : _pnode(p) {}

    // 解引用：返回节点数据的引用
    T& operator*() const { return _pnode->_data; }

    // 箭头运算符：返回节点数据的指针（用于指针类型元素）
    T* operator->() const { return &(_pnode->_data); }

    // 前置++
    self& operator++() {
        _pnode = _pnode->_next;
        return *this;
    }

    // 后置++
    self operator++(int) {
        self tmp(*this);
        _pnode = _pnode->_next;
        return tmp;
    }

    // 前置--
    self& operator--() {
        _pnode = _pnode->_prev;
        return *this;
    }

    // 后置--
    self operator--(int) {
        self tmp(*this);
        _pnode = _pnode->_prev;
        return tmp;
    }

    bool operator==(const self& it) const {
        return _pnode == it._pnode;
    }

    bool operator!=(const self& it) const {
        return _pnode != it._pnode;
    }
};
4.2 const迭代器

const迭代器与普通迭代器类似，但解引用返回const T&，确保只读：

template <typename T>
struct __list_const_iterator {
    typedef __list_node<T> node;
    typedef __list_const_iterator<T> self;

    node* _pnode;

    __list_const_iterator(node* p) : _pnode(p) {}

    // 解引用：返回const引用（只读）
    const T& operator*() const { return _pnode->_data; }

    // 箭头运算符：返回const指针（只读）
    const T* operator->() const { return &(_pnode->_data); }

    // ++、--等操作与普通迭代器相同（略）
};
4.3 反向迭代器（适配器模式）

反向迭代器通过适配正向迭代器实现，将++转为--，--转为++：

template <typename Iterator>
struct __reverse_iterator {
    typedef typename Iterator::reference reference;
    typedef typename Iterator::pointer pointer;
    typedef __reverse_iterator<Iterator> self;

    Iterator _it; // 适配的正向迭代器

    __reverse_iterator(Iterator it) : _it(it) {}

    // 反向迭代器的++等价于正向迭代器的--
    self& operator++() {
        --_it;
        return *this;
    }

    // 反向迭代器的--等价于正向迭代器的++
    self& operator--() {
        ++_it;
        return *this;
    }

    reference operator*() const {
        Iterator tmp = _it;
        --tmp;
        return *tmp; // 返回前一个元素
    }

    pointer operator->() const {
        return &(operator*());
    }

    bool operator==(const self& rit) const {
        return _it == rit._it;
    }

    bool operator!=(const self& rit) const {
        return _it != rit._it;
    }
};

// list中定义反向迭代器
typedef __reverse_iterator<iterator> reverse_iterator;
typedef __reverse_iterator<const_iterator> const_reverse_iterator;

反向迭代器与正向迭代器的关系：

正向迭代器：begin() --> [1] --> [2] --> [3] --> end()
反向迭代器：rbegin() --> [3] --> [2] --> [1] --> rend()
// rbegin()对应end()，rend()对应begin()

5. 迭代器的价值与设计思想

迭代器是容器与算法之间的桥梁，其设计思想：

  • 封装容器细节：算法无需关心容器内部实现（链表/数组），只需通过迭代器访问元素。
  • 统一接口：不同容器的迭代器提供相同操作（++、*等），使算法可复用。
  • 数据抽象：迭代器隐藏了数据的存储结构，仅暴露访问接口，符合面向对象设计原则。

示例：std::find算法通过迭代器可同时用于list和vector：

template <typename InputIt, typename T>
InputIt find(InputIt first, InputIt last, const T& val) {
    while (first != last && *first != val) {
        ++first;
    }
    return first;
}

// 用于vector
std::vector<int> v = {1,2,3};
auto it1 = std::find(v.begin(), v.end(), 2);

// 用于list
std::list<int> l = {1,2,3};
auto it2 = std::find(l.begin(), l.end(), 2);

6. 迭代器operator->的重载

当list存储指针类型元素（如list<T*>）时，operator->用于直接访问指针指向对象的成员：

示例：

struct A {
    int _a;
    A(int a) : _a(a) {}
};

int main() {
    std::list<A*> l;
    l.push_back(new A(1));
    l.push_back(new A(2));
    
    auto it = l.begin();
    // 不重载->：(*it)->_a
    std::cout << (*it)->_a << std::endl; // 1
    
    // 重载->后：it->_a（编译器优化为(it.operator->())->_a）
    std::cout << it->_a << std::endl; // 1（更简洁）
    return 0;
}

重载实现（见4.1节普通迭代器）：

T* operator->() const { return &(_pnode->_data); }
// 当_data为A*时，返回A**，编译器自动优化为A*（it->_a等价于(*it)->_a）

五、模拟实现时遇到的困惑及注意点

1. 调用拷贝构造时，链表内节点数据为什么已经是深拷贝了？

现象：list的拷贝构造会复制每个节点的数据，而非共享节点指针，因此是深拷贝。

原因：list拷贝构造的实现逻辑为：

  1. 遍历源链表的每个节点。
  2. 为每个节点创建新节点（调用T的拷贝构造函数）。
  3. 将新节点链接到目标链表。

代码验证：

template <typename T>
list<T>::list(const list<T>& l) {
    // 创建头节点（哨兵节点）
    _head = new node;
    _head->_prev = _head;
    _head->_next = _head;

    // 遍历源链表，深拷贝每个节点
    const_iterator it = l.begin();
    while (it != l.end()) {
        push_back(*it); // 为每个元素创建新节点
        ++it;
    }
}

结论：list的深拷贝是节点级别的深拷贝，每个节点的_data通过T的拷贝构造函数复制，因此即使T是指针类型，list仍会复制指针本身（但不会复制指针指向的对象，即浅拷贝指针指向的内容）。

2. 类名和类型的区别（以list为例）

  • 类名：list是类模板的名称，不是具体类型，需实例化后才能使用。
  • 类型：list<int>、list<string>是实例化后的具体类型，包含模板参数。

示例：

template <typename T> // T是模板参数
class list { ... }; // list是类模板名

// 实例化类型
list<int> l1; // list<int>是类型，l1是该类型的对象
list<string> l2; // list<string>是另一种类型

// 错误：类模板名不能直接作为类型
list l3; // 编译错误：缺少模板参数

延伸：模板参数不同的实例化类型是完全独立的类型，如list<int>和list<double>无任何关系。

3. 链表节点的内存管理注意事项

  • 手动释放节点：析构函数需遍历链表，删除每个节点（避免内存泄漏）。
  • 避免野指针：删除节点后，确保所有指向该节点的指针（迭代器）不再使用。
  • 哨兵节点处理：模拟实现时通常使用哨兵节点（头节点）简化边界条件，析构时需单独释放哨兵节点。

示例（析构函数实现）：

template <typename T>
list<T>::~list() {
    clear(); // 删除所有数据节点
    delete _head; // 删除哨兵节点
    _head = nullptr;
}

void clear() {
    iterator it = begin();
    while (it != end()) {
        it = erase(it); // 逐个删除节点
    }
}

六、vector和list的优缺点对比

1. vector的优缺点

优点：
  • 随机访问高效：O(1)时间访问任意元素，适合频繁读操作。
  • 缓存友好：连续存储，元素在CPU缓存中命中率高，遍历速度快。
  • 尾部操作高效：push_back/pop_back在未扩容时为O(1)。
  • 空间紧凑：无额外指针开销，内存利用率高。
缺点：
  • 中间插入删除低效：需移动大量元素，O(n)时间。
  • 扩容开销大：扩容时需分配新内存并拷贝元素，可能导致迭代器失效。
  • 预分配浪费：reserve可能预留过多内存，造成空间浪费。

2. list的优缺点

优点：
  • 任意位置插入删除高效：已知位置时为O(1)，无需移动元素。
  • 无扩容问题：节点按需分配，不会导致迭代器大范围失效。
  • 内存利用率高：无预分配，每个节点仅额外两个指针开销。
缺点：
  • 无随机访问：访问第n个元素需O(n)时间。
  • 缓存不友好：节点分散存储，CPU缓存命中率低，遍历速度慢。
  • 额外空间开销：每个节点需存储prev和next指针（64位系统16字节/节点）。

3. 容器选择决策指南

场景优先选择原因分析
频繁随机访问（如v[i]）vectorO(1)随机访问，缓存友好
频繁插入删除（中间位置）listO(1)插入删除，无元素移动
数据量小且访问频繁vector缓存优势抵消随机访问劣势
大数据量且动态增长list避免vector扩容的内存拷贝开销
需要与C API交互（如char*）vector连续存储可直接转换为数组指针
实现栈/队列（尾部操作）vector尾部操作O(1)，缓存更优
实现双向队列（头尾操作）deque兼顾vector和list的头尾操作效率

七、模拟实现的list整体代码

1. 节点结构设计

template <typename T>
struct __list_node {
    T _data;
    __list_node* _prev;
    __list_node* _next;

    __list_node(const T& val = T())
        : _data(val)
        , _prev(nullptr)
        , _next(nullptr) {}
};

2. 迭代器实现

// 普通迭代器
template <typename T>
struct __list_iterator {
    typedef __list_node<T> node;
    typedef __list_iterator<T> self;
    typedef T& reference;
    typedef T* pointer;

    node* _pnode;

    __list_iterator(node* p = nullptr) : _pnode(p) {}

    reference operator*() const { return _pnode->_data; }
    pointer operator->() const { return &(operator*()); }

    self& operator++() {
        _pnode = _pnode->_next;
        return *this;
    }

    self operator++(int) {
        self tmp(*this);
        _pnode = _pnode->_next;
        return tmp;
    }

    self& operator--() {
        _pnode = _pnode->_prev;
        return *this;
    }

    self operator--(int) {
        self tmp(*this);
        _pnode = _pnode->_prev;
        return tmp;
    }

    bool operator==(const self& it) const { return _pnode == it._pnode; }
    bool operator!=(const self& it) const { return _pnode != it._pnode; }
};

// const迭代器
template <typename T>
struct __list_const_iterator {
    typedef __list_node<T> node;
    typedef __list_const_iterator<T> self;
    typedef const T& reference;
    typedef const T* pointer;

    node* _pnode;

    __list_const_iterator(node* p = nullptr) : _pnode(p) {}
    __list_const_iterator(const __list_iterator<T>& it) : _pnode(it._pnode) {}

    reference operator*() const { return _pnode->_data; }
    pointer operator->() const { return &(operator*()); }

    // ++、--等操作与普通迭代器类似（略）
};

// 反向迭代器适配器
template <typename Iterator>
struct __reverse_iterator {
    typedef typename Iterator::reference reference;
    typedef typename Iterator::pointer pointer;
    typedef __reverse_iterator<Iterator> self;
    typedef Iterator iterator_type;

    iterator_type _it;

    __reverse_iterator(iterator_type it) : _it(it) {}

    self& operator++() {
        --_it;
        return *this;
    }

    self operator++(int) {
        self tmp(*this);
        --_it;
        return tmp;
    }

    self& operator--() {
        ++_it;
        return *this;
    }

    self operator--(int) {
        self tmp(*this);
        ++_it;
        return tmp;
    }

    reference operator*() const {
        iterator_type tmp = _it;
        --tmp;
        return *tmp;
    }

    pointer operator->() const { return &(operator*()); }

    bool operator==(const self& rit) const { return _it == rit._it; }
    bool operator!=(const self& rit) const { return _it != rit._it; }
};

3. list核心接口实现

template <typename T>
class list {
public:
    typedef __list_node<T> node;
    typedef __list_iterator<T> iterator;
    typedef __list_const_iterator<T> const_iterator;
    typedef __reverse_iterator<iterator> reverse_iterator;
    typedef __reverse_iterator<const_iterator> const_reverse_iterator;

    // 构造函数
    list() {
        _head = new node; // 创建哨兵节点
        _head->_prev = _head;
        _head->_next = _head;
    }

    list(size_t n, const T& val = T()) : list() {
        for (size_t i = 0; i < n; ++i) {
            push_back(val);
        }
    }

    template <typename InputIt>
    list(InputIt first, InputIt last) : list() {
        while (first != last) {
            push_back(*first);
            ++first;
        }
    }

    list(const list& l) : list() {
        const_iterator it = l.begin();
        while (it != l.end()) {
            push_back(*it);
            ++it;
        }
    }

    list(std::initializer_list<T> il) : list(il.begin(), il.end()) {}

    // 赋值运算符
    list& operator=(const list& l) {
        if (this != &l) {
            list tmp(l); // 拷贝构造临时对象
            swap(tmp); // 交换临时对象和当前对象
        }
        return *this;
    }

    // 析构函数
    ~list() {
        clear();
        delete _head;
        _head = nullptr;
    }

    // 迭代器接口
    iterator begin() { return iterator(_head->_next); }
    const_iterator begin() const { return const_iterator(_head->_next); }
    iterator end() { return iterator(_head); }
    const_iterator end() const { return const_iterator(_head); }

    reverse_iterator rbegin() { return reverse_iterator(end()); }
    const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
    reverse_iterator rend() { return reverse_iterator(begin()); }
    const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }

    // 容量接口
    size_t size() const {
        size_t count = 0;
        const_iterator it = begin();
        while (it != end()) {
            ++count;
            ++it;
        }
        return count;
    }

    bool empty() const { return begin() == end(); }

    void resize(size_t n, const T& val = T()) {
        size_t old_size = size();
        if (n > old_size) {
            for (size_t i = old_size; i < n; ++i) {
                push_back(val);
            }
        } else if (n < old_size) {
            for (size_t i = n; i < old_size; ++i) {
                pop_back();
            }
        }
    }

    // 元素访问
    T& front() { return *begin(); }
    const T& front() const { return *begin(); }
    T& back() { return *(--end()); }
    const T& back() const { return *(--end()); }

    // 修改操作
    void push_back(const T& val) { insert(end(), val); }
    void pop_back() { erase(--end()); }
    void push_front(const T& val) { insert(begin(), val); }
    void pop_front() { erase(begin()); }

    iterator insert(iterator pos, const T& val) {
        node* new_node = new node(val);
        node* cur = pos._pnode;
        node* prev = cur->_prev;

        // 链接新节点
        prev->_next = new_node;
        new_node->_prev = prev;
        new_node->_next = cur;
        cur->_prev = new_node;

        return iterator(new_node);
    }

    iterator erase(iterator pos) {
        node* cur = pos._pnode;
        node* prev = cur->_prev;
        node* next = cur->_next;

        // 断开链接
        prev->_next = next;
        next->_prev = prev;
        delete cur;

        return iterator(next);
    }

    void swap(list& l) {
        std::swap(_head, l._head);
    }

    void clear() {
        iterator it = begin();
        while (it != end()) {
            it = erase(it);
        }
    }

    // 排序（归并排序，简化版）
    void sort() {
        if (size() <= 1) return;

        list<T> left, right;
        iterator mid = begin();
        size_t half = size() / 2;
        for (size_t i = 0; i < half; ++i) {
            left.push_back(*mid);
            mid = erase(mid);
        }
        right.swap(*this); // 剩余元素移至right

        left.sort();
        right.sort();
        merge(left, right); // 合并两个有序链表
    }

private:
    // 合并两个有序链表（假设this为空）
    void merge(list& left, list& right) {
        iterator it_left = left.begin();
        iterator it_right = right.begin();
        while (it_left != left.end() && it_right != right.end()) {
            if (*it_left <= *it_right) {
                push_back(*it_left);
                it_left = left.erase(it_left);
            } else {
                push_back(*it_right);
                it_right = right.erase(it_right);
            }
        }
        while (it_left != left.end()) {
            push_back(*it_left);
            it_left = left.erase(it_left);
        }
        while (it_right != right.end()) {
            push_back(*it_right);
            it_right = right.erase(it_right);
        }
    }

    node* _head; // 哨兵节点
};

4. 完整代码与测试示例

测试代码：

#include <iostream>
#include <algorithm>

int main() {
    my::list<int> l;
    l.push_back(3);
    l.push_back(1);
    l.push_back(2);
    l.push_front(0); // {0,3,1,2}

    std::cout << "排序前：";
    for (int x : l) std::cout << x << " "; // 0 3 1 2

    l.sort();
    std::cout << "\n排序后：";
    for (int x : l) std::cout << x << " "; // 0 1 2 3

    l.reverse();
    std::cout << "\n反转后：";
    for (int x : l) std::cout << x << " "; // 3 2 1 0

    return 0;
}

输出：

排序前：0 3 1 2 
排序后：0 1 2 3 
反转后：3 2 1 0

注意：上述sort实现为简化版，实际STL的list::sort更复杂，包含对连续重复元素的优化和非递归实现。

# c++ # list # 开发语言
Logo
亚马逊云科技技术品牌专区

更多推荐

open-code-review Codex 插件教程：对话式调用评审技能指南

本文是一份面向新手的 **open-code-review Codex 插件教程**，教你在 Codex 中通过对话式方式调用 open-code-review 的 AI 代码评审技能。open-code-review 是阿里巴巴开源的 AI 代码评审工具，采用"确定性流水线 + LLM Agent"混合架构，内置多语言评审规则（NPE、线程安全、XSS、SQL 注入等），可在 Codex 里用一

avatar 亚马逊云科技技术品牌专区

OBS Studio 完整指南：免费开源录屏与直播软件从零上手

想做一场像模像样的直播，或者把屏幕内容录成教程视频，但一想到商用软件的订阅费就有些犹豫？其实你不需要花一分钱。OBS Studio 是一款免费开源的直播与录屏软件，支持 Windows、macOS 和 Linux，采集、混音、编码、推流、录制，一条流水线全包了。## 先搞清楚 OBS Studio 是什么OBS Studio 是一个"场景化"的采集合成工具：你把摄像头、窗口、浏览器、图片、

avatar 亚马逊云科技技术品牌专区

如何用MediaCrawler爬取小红书抖音数据？7大平台爬虫从安装到实战完整指南

MediaCrawler 是一个支持小红书、抖音、快手、B站、微博、百度贴吧、知乎的开源自媒体数据采集工具。它能按关键词、按帖子、按创作者主页三种方式抓取笔记/视频内容、评论甚至二级评论，并把结果存成 JSON、CSV、Excel 或数据库。适合做市场调研、竞品监控、内容选题的运营人员，以及想要现成爬虫框架而不想从零写 JS 逆向的开发者。## 从一次"手动抄数据"说起想象这个场景：你负责

avatar 亚马逊云科技技术品牌专区