C++ STL list 容器使用、底层原理及自定义实现

(3) list 的 sort

list 不支持算法库里的 sort（核心是快速排序），因为 sort 对迭代器的功能有要求，必须是随机迭代器，而 list 是双向迭代器。

虽然 list 自己实现了一个 sort，核心是归并排序，但是不建议使用，因为效率太差。

在 STL 中，vector 的 sort 是随机访问迭代器下的快速排序（平均时间复杂度 O(nlogn)），而list 的 sort 是双向迭代器下的归并排序（稳定时间复杂度为 O(nlogn)）；数据量大时不建议用 list 的 sort。

二、list 与 vector 的核心区别

list 的核心缺陷是没有办法做下标随机访问。

但其实，vector 和 list 是互补的关系，如果需要大量的存储数据，尽量选择用 vector 去存储数据，因为 vector 是连续的存储数据，在读取数据的的时候可以快速的读取。如果需要头插，头删，建议使用 list。

三、list 底层逻辑与部分源代码

如果 List 的成员变量是 vector 之类的，那么在销毁时，不仅要调用 list 的析构函数，还要调用 vector 的析构函数。

四、自定义 List 实现

1. push_back

习惯上来说，如果类不想让访问限定符限制，就使用 struct，例如下面的 list_node 就不想限制，因为 list_node 是作为链表的一个子结构，是存储每个数据的最小单元，而链表是需要大量访问数据的，就不需要访问限定符的限制，使用 struct 更好。

这个时候就有人问了，那这样设定不就可以随便访问了吗？但是我们有迭代器，只能从内部看出节点，外部无法看出。而且不同的平台 list_node 的名称也不同。

我们先来写定义和初始化部分：

#pragma once 
namespace bit { 
template<class T> struct list_node { 
    list_node<T>* _next; 
    list_node<T>* _prev; 
    T _data; 
    list_node(const T& x = T()) :_next(nullptr), _prev(nullptr), _data(x) {} 
}; 
}

然后来写 push_back：

void push_back(const T& x) { 
    Node* newnode = new Node(x); 
    Node* tail = _head->_prev; 
    tail->_next = newnode; 
    newnode->_prev = tail; 
    newnode->_next = _head; 
    _head->_prev = newnode; 
}

tail 是尾节点。

2. iterator

迭代器的核心使用就是解引用，找到指向的数据，在不暴露底层的情况下去访问你的数据，不管是链表，还是之后的树型结构，都是一样的访问方式，它是一种封装。

迭代器的设计是一种封装，封装隐藏底层的结构差异，提供类似统一的方式访问容器

我们在写这部分的完整代码时，用了三个：类一个类封装链表，一个类封装节点。一个类封装迭代器。完整代码将会在结尾展出。

类里封装了一个节点的指针，然后重载运算符，这个时候迭代器就是这个类。*it 就会调用 *operator，*operator 中含有节点指针指向的数据，所以迭代器解引用就会访问这个指针。

++it 就会调用 operator++，指向当前节点的下一个地址。

为什么要封装呢？

通过类的成员函数（如重载的 operator*、operator++ 等），可以为迭代器提供统一、简洁的接口。不管底层容器（如 list）的实现多么复杂，用户都可以用相同的方式（如 *it 访问元素、++it 移动迭代器）来操作不同容器的迭代器。通过统一的方式访问容器，不用管底层是怎么样的

那我们来自己实现一下：

// 实现双向迭代器，支持前向和后向遍历 
template<class T, class Ref> struct list_iterator { 
    using Self = list_iterator<T, Ref>; 
    using Node = list_node<T>; 
    Node* _node; 
    list_iterator(Node* node) :_node(node) {} 
    // *it = 1 
    Ref operator*() { return _node->_data; } 
    // ++it 
    Self& operator++() { _node = _node->_next; return *this; } 
    Self operator++(int) { Self tmp(*this); _node = _node->_next; return tmp; } 
    // --it 
    Self& operator--() { _node = _node->_prev; return *this; } 
    Self operator--(int) { Self tmp(*this); _node = _node->_prev; return tmp; } 
    bool operator!=(const Self& s) const { return _node != s._node; } 
    bool operator==(const Self& s) const { return _node == s._node; } 
}; 

using Self = list_iterator<T, Ref>：简化自身类型的使用（避免重复写）

void Print(const bit::list<int>& lt) { 
    bit::list<int>::const_iterator it = lt.begin(); 
    while (it != lt.end()) { 
        //*it = 1; 
        cout << *it << " "; 
        ++it; 
    } 
    cout << endl; 
}

void test_list1() { 
    bit::list<int> lt; 
    lt.push_back(1); 
    lt.push_back(2); 
    lt.push_back(3); 
    lt.push_back(4); 
    bit::list<int>::iterator it = lt.begin(); 
    while (it != lt.end()) { 
        cout << *it << " "; 
        ++it; 
    } 
    cout << endl; 
    for (auto e : lt) { 
        cout << e << " "; 
    } 
    cout << endl; 
}

支持迭代器就支持范围 for（范围 for 的底层就是迭代器）。

我们来看右上角：

Node* it1 和 bit::list::iterator it2 都保存了 1 这个节点，但是因为类型不一样，所以解引用后的使用也不一样。

迭代器是借助链表的指针，去访问链表的数据，但是迭代器销毁以后不会销毁节点，因为节点是归链表管，迭代器销毁了节点还在，所以迭代器不会实现析构函数。

3. insert

void insert(iterator pos, const T& x) { 
    Node* cur = pos._node; 
    Node* prev = cur->_prev; 
    Node* newnode = new Node(x); 
    // prev newnode cur 
    prev->_next = newnode; 
    newnode->_prev = prev; 
    newnode->_next = cur; 
    cur->_prev = newnode; 
    ++_size; 
}

4. erase

iterator erase(iterator pos) { 
    Node* cur = pos._node; 
    Node* prev = cur->_prev; 
    Node* next = cur->_next; 
    prev->_next = next; 
    next->_prev = prev; 
    delete[] cur; 
    --_size; 
    return next; 
}

在 erase 函数中返回 next（被删除节点的下一个节点对应的迭代器），是为了保证迭代器的有效性，避免用户使用已失效的迭代器。

5. size

size_t size() const { /*size_t n = 0; for (auto& e : *this) { ++n; } return n;*/ return _size; } 
private: 
    Node* _head; 
    size_t _size = 0; 
};

这段代码实现了链表的 size 成员函数，用于获取链表中元素的个数，同时定义了链表类的私有成员变量。核心设计思路是通过维护一个 _size 变量，避免每次获取大小都遍历链表，从而提升效率。

这段代码实现了两种方法：

因为遍历计数比较麻烦，所以我们可以直接在私有成员变量中添加一个 size 变量。

6. 头插头删 尾插尾删

因为我们已经完成了 insert 的函数，所以我们可以利用函数的复用降低函数的代码长度。

void push_back(const T& x) { insert(end(), x); } 
void push_front(const T& x) { insert(begin(), x); } 
void pop_back() { erase(--end()); } 
void pop_front() { erase(begin()); } 

7. 链表核心框架实现

a 链表类及核心类型定义

template<class T> class list { 
    // 节点类型定义（链表的基本存储单元） 
    using Node = list_node<T>; 
    // 假设 list_node 是已定义的节点结构体（含_data, _prev, _next） 
public: 
    // 迭代器类型定义（通过模板参数控制读写权限） 
    using iterator = list_iterator<T, T&>; // 可读写迭代器（解引用返回 T&） 
    using const_iterator = list_iterator<T, const T&>; // 只读迭代器（解引用返回 const T&） 
    // 注释：另一种迭代器实现思路（通过两个独立类） 
    // using iterator = list_iterator<T>; 
    // using const_iterator = list_const_iterator<T>; 

b 迭代器接口

// 获取非 const 迭代器（指向第一个元素） 
iterator begin() { 
    // 头节点的_next 是第一个数据节点 
    return iterator(_head->_next); 
} 
// 获取非 const 迭代器（指向末尾标记，即头节点） 
iterator end() { 
    // 尾后迭代器指向头节点（符合 [begin, end) 左闭右开区间） 
    return iterator(_head); 
} 
// 获取 const 迭代器（指向第一个元素，只读） 
const_iterator begin() const { 
    return const_iterator(_head->_next); 
} 
// 获取 const 迭代器（指向末尾标记，只读） 
const_iterator end() const { 
    return const_iterator(_head); 
}

const 迭代器不是迭代器不能修改，而是指向的内容不能修改，注意 const 的位置，不要写错。

const 迭代器和普通迭代器的区别是：const 迭代器不能修改---->核心在于修改是通过解引用，*it 调用 operator*，而 operator* 返回 const T&，就不能修改了

c 初始化函数

private: 
    // 初始化空链表（创建哨兵头节点，形成双向循环） 
    void empty_init() { 
        _head = new Node; // 创建头节点（不存储实际数据，仅作哨兵） 
        _head->_next = _head; // 头节点的_next 指向自身 
        _head->_prev = _head; // 头节点的_prev 指向自身（循环结构） 
    } 
public:

d 构造函数（多种初始化方式）

// 默认构造函数（初始化空链表） 
list() { empty_init(); } 
// 初始化列表构造（支持 list<int> l = {1,2,3}） 
list(initializer_list<T> il) { 
    empty_init(); // 先初始化空链表 
    // 遍历初始化列表，逐个插入元素 
    for (auto& e : il) { 
        push_back(e); // 假设 push_back 已实现（尾插） 
    } 
} 
// 迭代器区间构造（从其他容器迭代器区间初始化） 
template <class InputIterator> list(InputIterator first, InputIterator last) { 
    empty_init(); // 先初始化空链表 
    // 遍历 [first, last) 区间，逐个插入元素 
    while (first != last) { 
        push_back(*first); // 插入当前元素 
        ++first; // 移动到下一个元素 
    } 
} 
// 构造 n 个值为 val 的元素（size_t 版本，避免类型歧义） 
list(size_t n, T val = T()) { 
    empty_init(); 
    for (size_t i = 0; i < n; ++i) { 
        push_back(val); 
    } 
} 
// 构造 n 个值为 val 的元素（int 版本，与 size_t 重载区分） 
list(int n, T val = T()) { 
    empty_init(); 
    for (int i = 0; i < n; ++i) { 
        push_back(val); 
    } 
}

e 析构函数

~list() { 
    clear(); // 清空所有数据节点（假设 clear 已实现） 
    delete _head; // 释放头节点 
    _head = nullptr; // 避免野指针 
    _size = 0; // 重置大小 
}

f 拷贝控制（深拷贝）

第一个是现代写法，第二个是传统写法。

// 拷贝构造函数（深拷贝，从另一个 list 复制） 
list(const list<T>& lt) { 
    empty_init(); // 先初始化空链表 
    // 遍历被拷贝链表，逐个复制元素 
    for (auto& e : lt) { 
        push_back(e); 
    } 
} 
// 赋值运算符重载（深拷贝，支持 lt1 = lt2） 
list<T>& operator=(const list<T>& lt) { 
    if (this != &lt) // 避免自我赋值（如 lt1 = lt1） 
    { 
        clear(); // 先清空当前链表的旧元素 
        // 复制 lt 中的元素到当前链表 
        for (auto& e : lt) { 
            push_back(e); 
        } 
    } 
    return *this; // 支持链式赋值（如 lt1 = lt2 = lt3） 
}

g 私有成员变量

private: 
    Node* _head; // 头节点指针（哨兵节点，不存储数据） 
    size_t _size = 0; // 链表元素个数（需在增删操作中维护） 
};

8. operator* 和 operator->

// 迭代器解引用操作 
// *it = 1 
// Ref 返回节点数据的引用（可读或可写） 
Ref operator*() // 解引用，Ref 就是 reference，引用的意思 
{ return _node->_data; } 
// operator*() 返回对应数据类型的引用 
Ptr operator->() // 返回对应数据类型的指针 
{ return &_node->_data; }

这个时候我们会在模板参数里加入一个新的模板，class Ptr，这也就和源代码里的三个模板一样。

template<class T, class Ref, class Ptr> // T 数据类型 <T> 提供 IntelliSense 的示例模板参数 
// Ref 引用类型 (T& 或 const T&) 
struct list_iterator { 
    // using 还具有 typedef 没有的功能 
    // 使用类型别名 (C++11 新特性) 
    using Self = list_iterator<T, Ref, Ptr>; // 自身类型 
    using Node = list_node<T>; // 节点类型 
    Node* _node; // 当前指向的节点 
}; 
// 迭代器类型定义 
using iterator = list_iterator<T, T&, T*>; // 普通迭代器 
using const_iterator = list_iterator<T, const T&, const T*>; // 常量迭代器 
// const T* 只能读取数据，不能修改数据

operator->：返回当前节点数据的指针（Ptr 类型，若为 T* 则可通过指针操作元素，若为 const T* 则只能读），支持像指针一样用 it->member 访问元素的成员（比如当元素是自定义结构体或类时，访问其成员变量或成员函数）。

operator-> 返回的是指针。