概述

"道生一，一生二，二生三，三生万物。" ——《道德经》

        在道家智慧中，"道"是万物运行的底层规律，无形无相却贯穿始终；"术"是表象的具体技法，有形有相而易学易用。

        学习std::list亦如此：通晓道法，则明其双向链表之本质，知其在内存中如何环环相扣，晓其增删之妙与访问之限；掌握术法，则熟其接口用法，能随心调用而无碍。

        今AI昌盛，求"术"者瞬息可得。然欲成高手，当先悟"道"——内力深厚者，招式自然通透。本篇仍从道、术两途，为你揭开std::list的奥秘。

list 道法篇

        std::list 核心原理基于双向链表的设计，它通过节点连接的方式存储元素，每个节点包含指向前后节点的指针，支持高效的插入删除操作，但不支持随机访问。

双向链表原理

随机访问 vs 顺序访问：相信很多初学者对"随机访问"这个词不是很理解，在上一篇《C++ STL 容器 -- 道与术 篇（一） vector》中已经对随机访问做了说明，这里继续用之前的例子：

（1）如果5个人并排站在一起（内存上连续的），你就可以很容易地找到第五个人（随机访问）。
（2）假如这五个人站的位置并不是并排，而是通过绳子连在一起，首尾相连，每个人只知道前一个人和后一个人在哪，那么你要找到第5个人，你就只能从第一个人开始逐个往后找（顺序访问）。

list就是第二种情况，每个节点只知道它的前驱和后继节点。

list 两个重点：

（1）在内存布局上是非连续的 --> 不支持随机访问，但支持快速插入删除。

（2）每个节点包含两个指针（前驱和后继） --> 支持双向遍历。

系列特性说明：

基于这两个"道法"原理，就决定了他的一系列特性。

（1） 插入删除效率高（O(1)）

由于是链表结构，在已知位置插入或删除元素只需要修改相邻节点的指针，不需要移动其他元素。

（2） 不支持随机访问

访问某个位置的元素需要从头部或尾部遍历过去，时间复杂度为O(n)。

（3） 内存开销较大

每个节点除了存储元素外，还需要两个指针（前驱和后继），在64位系统上，每个指针占8字节，所以每个节点需要额外的16字节开销。

（4） 内存布局

list的节点结构简化如下：

GCC风格：

// 在GCC的bits/stl_list.h中可以看到：
template<typename _Tp>
class list {
protected:
    _List_node_base _M_node;  // 哨兵节点：16字节
    size_t _M_size;           // 大小计数器：8字节
    // 总计：24字节
};

struct _List_node_base {
    _List_node_base* _M_next;
    _List_node_base* _M_prev;
    // 16字节
};

template<typename _Tp>
struct _List_node : public _List_node_base {
    _Tp _M_data;
    // 继承16字节 + sizeof(_Tp) + 填充
    // 对于int：16 + 4 + 4 = 24字节
};

list对象本身通常包含一个指向首尾节点的指针和记录元素个数的变量。

std::list<int> empty_list;
哨兵节点:
  _M_next → 指向哨兵节点自身
  _M_prev → 指向哨兵节点自身

std::list<int> list = {10, 20, 30};
哨兵节点:
  _M_next → 指向第一个数据节点(10)
  _M_prev → 指向最后一个数据节点(30)

数据节点布局:
哨兵 ←→ [10] ←→ [20] ←→ [30] ←→ 哨兵

我们通过重定义new操作符，来捕获内存分配情况：

#include <new>
#include <iostream>
#include <list>
#include <cstdint>

// 重载全局new操作符
void* operator new(size_t size) {
    void* ptr = std::malloc(size);
    std::cout << "-->new size: " << size << " byte" << " src: " << ptr << std::endl;
    return ptr;
}

// 重载全局delete操作符
void operator delete(void* ptr) noexcept {
    if (ptr) {
        std::cout << "-->free src: " << ptr << std::endl;
        std::free(ptr);
    }
}
typedef struct test{
    test(uint64_t t){
        t1 = t;
    }
    uint64_t t1;//8字节
    uint64_t t2;//8字节
    uint64_t t3;//8字节
}test;

int main() {
    std::cout << "test t0" << std::endl;
    std::list<test>* list1 = new std::list<test>();
    std::cout << "size t1: " << list1->size() << std::endl;
    
    list1->push_back(1);
    std::cout << "size t2: " << list1->size() << std::endl;
    
    list1->push_back(2);
    std::cout << "size t3: " << list1->size() << std::endl;
    
    list1->push_back(3);
    std::cout << "size t4: " << list1->size() << std::endl;
    
    delete list1;
}

可以直接使用在线编译工具运行https://www.onlinegdb.com/，输出如下：

输出如下：

test t0
-->new size: 24 byte src: 0x600b7fc17d30
size t1: 0
-->new size: 40 byte src: 0x600b7fc17d50
size t2: 1
-->new size: 40 byte src: 0x600b7fc17d80
size t3: 2
-->new size: 40 byte src: 0x600b7fc17db0
size t4: 3
-->free src: 0x600b7fc17d50
-->free src: 0x600b7fc17d80
-->free src: 0x600b7fc17db0
-->free src: 0x600b7fc17d30

可以看到，每次插入一个元素，就分配了一个40字节的节点（在64位系统中，两个指针16字节，加上一个test 占据24字节）。

怎么在某个位置插入一条数据：

我们通过应该视频来看怎么在list中搜索一个数据：

std::list 术法篇

前面我通过"道法"篇，详细介绍了list的实现原理，以及在内存上的布局。至此，对于list你应该知道其真正长什么样了，不再被其表像所迷惑，也应该知道其性能瓶颈了。

📋 完整API目录

• 🏗️ 成员类型

• 🏗️ 构造函数

• 🗑️ 析构函数

• 🔄 赋值操作

• 🔍 元素访问

• 🔄 迭代器

• 📦 容量操作

• 🛠️ 修改器

• 🎯 链表特有操作

• 🔗 非成员函数

• 💻 代码示例

🏗️ 成员类型

类型	定义	说明
value_type	T	容器中存储的元素类型
allocator_type	Allocator	用于管理内存的分配器类型
size_type	std::size_t	无符号整数类型，用于表示大小
difference_type	std::ptrdiff_t	有符号整数类型，用于表示距离
reference	value_type&	元素的引用类型
const_reference	const value_type&	元素的常量引用类型
pointer	Allocator::pointer	指向元素的指针类型
const_pointer	Allocator::const_pointer	指向常量元素的指针类型
iterator	双向迭代器	指向元素的迭代器
const_iterator	常量双向迭代器	指向常量元素的迭代器
reverse_iterator	std::reverse_iterator<iterator>	反向迭代器
const_reverse_iterator	std::reverse_iterator<const_iterator>	常量反向迭代器

🏗️ 构造函数

构造函数	说明	示例
list() noexcept	默认构造函数	std::list<int> l1;
explicit list(const Allocator& alloc) noexcept	带分配器的默认构造	std::list<int> l2(alloc);
list(size_type count, const T& value, const Allocator& alloc = Allocator())	构造count个value	std::list<int> l3(5, 10);
explicit list(size_type count, const Allocator& alloc = Allocator())	构造count个默认值	std::list<int> l4(5);
template<class InputIt> list(InputIt first, InputIt last, const Allocator& alloc = Allocator())	范围构造	std::list<int> l5(arr, arr+3);
list(const list& other)	拷贝构造	std::list<int> l6(l5);
list(const list& other, const Allocator& alloc)	带分配器的拷贝构造	std::list<int> l7(l5, alloc);
list(list&& other) noexcept	移动构造	std::list<int> l8(std::move(l6));
list(list&& other, const Allocator& alloc)	带分配器的移动构造	std::list<int> l9(std::move(l7), alloc);
list(std::initializer_list<T> init, const Allocator& alloc = Allocator())	初始化列表构造	std::list<int> l10{1,2,3};

🗑️ 析构函数

函数	说明	示例
~list()	销毁所有元素并释放内存	自动调用

🔄 赋值操作

函数	说明	示例
list& operator=(const list& other)	拷贝赋值	l1 = l2;
list& operator=(list&& other) noexcept	移动赋值	l1 = std::move(l2);
list& operator=(std::initializer_list<T> ilist)	初始化列表赋值	l1 = {4,5,6};
void assign(size_type count, const T& value)	赋值count个value	l1.assign(3, 100);
template<class InputIt> void assign(InputIt first, InputIt last)	赋值范围元素	l1.assign(arr, arr+3);
void assign(std::initializer_list<T> ilist)	赋值初始化列表	l1.assign({7,8,9});

🔍 元素访问

函数	说明	示例	异常安全
reference front()	访问首元素	int x = l1.front();	空list未定义行为
const_reference front() const	const版本front	const int x = l1.front();	同上
reference back()	访问尾元素	int x = l1.back();	空list未定义行为
const_reference back() const	const版本back	const int x = l1.back();	同上

注意：list不支持随机访问，因此没有at和operator[]。

🔄 迭代器

函数	说明	示例
iterator begin() noexcept	指向首元素的迭代器	auto it = l1.begin();
const_iterator begin() const noexcept	const版本begin	auto it = l1.begin();
const_iterator cbegin() const noexcept	指向首元素的const迭代器	auto it = l1.cbegin();
iterator end() noexcept	指向尾后位置的迭代器	auto it = l1.end();
const_iterator end() const noexcept	const版本end	auto it = l1.end();
const_iterator cend() const noexcept	指向尾后位置的const迭代器	auto it = l1.cend();
reverse_iterator rbegin() noexcept	指向反向首元素的迭代器	auto it = l1.rbegin();
const_reverse_iterator rbegin() const noexcept	const版本rbegin	auto it = l1.rbegin();
const_reverse_iterator crbegin() const noexcept	指向反向首元素的const迭代器	auto it = l1.crbegin();
reverse_iterator rend() noexcept	指向反向尾后位置的迭代器	auto it = l1.rend();
const_reverse_iterator rend() const noexcept	const版本rend	auto it = l1.rend();
const_reverse_iterator crend() const noexcept	指向反向尾后位置的const迭代器	auto it = l1.crend();

📦 容量操作

函数	说明	示例	时间复杂度
bool empty() const noexcept	检查是否为空	if(l1.empty())	O(1)
size_type size() const noexcept	返回元素数量	size_t s = l1.size();	O(1)
size_type max_size() const noexcept	返回最大可能大小	size_t m = l1.max_size();	O(1)

注意：list没有capacity和reserve，因为链表不需要预先分配内存。

🛠️ 修改器

基本修改操作

函数	说明	示例	时间复杂度
void clear() noexcept	清空所有元素	l1.clear();	O(n)
iterator insert(const_iterator pos, const T& value)	插入元素	l1.insert(l1.begin(),10);	O(1)
iterator insert(const_iterator pos, T&& value)	移动插入元素	l1.insert(l1.begin(),std::move(x));	O(1)
iterator insert(const_iterator pos, size_type count, const T& value)	插入count个元素	l1.insert(l1.begin(),3,10);	O(count)
template<class InputIt> iterator insert(const_iterator pos, InputIt first, InputIt last)	插入范围	l1.insert(l1.begin(),arr,arr+3);	O(距离)
iterator insert(const_iterator pos, std::initializer_list<T> ilist)	插入初始化列表	l1.insert(l1.begin(),{1,2,3});	O(初始化列表大小)
template<class... Args> iterator emplace(const_iterator pos, Args&&... args)	原位构造元素	l1.emplace(l1.begin(),10);	O(1)
iterator erase(const_iterator pos)	擦除单个元素	l1.erase(l1.begin());	O(1)
iterator erase(const_iterator first, const_iterator last)	擦除范围	l1.erase(l1.begin(),std::next(l1.begin(),2));	O(距离)
void resize(size_type count)	改变大小（默认构造）	l1.resize(10);	O(|count-size|)
void resize(size_type count, const T& value)	改变大小（指定值）	l1.resize(10,5);	O(|count-size|)
void swap(list& other) noexcept	交换内容	l1.swap(l2);	O(1)

首尾操作

函数	说明	示例	时间复杂度
template<class... Args> void emplace_back(Args&&... args)	在末尾原位构造	l1.emplace_back(10);	O(1)
void push_back(const T& value)	在末尾添加元素	l1.push_back(10);	O(1)
void push_back(T&& value)	在末尾移动添加	l1.push_back(std::move(x));	O(1)
void pop_back()	移除末尾元素	l1.pop_back();	O(1)
template<class... Args> void emplace_front(Args&&... args)	在开头原位构造	l1.emplace_front(10);	O(1)
void push_front(const T& value)	在开头添加元素	l1.push_front(10);	O(1)
void push_front(T&& value)	在开头移动添加	l1.push_front(std::move(x));	O(1)
void pop_front()	移除开头元素	l1.pop_front();	O(1)

🎯 链表特有操作

拼接操作 (Splice)

函数	说明	示例	时间复杂度
void splice(const_iterator pos, list& other)	将other所有元素拼接到pos前	l1.splice(l1.end(), l2);	O(1)
void splice(const_iterator pos, list&& other)	移动版本的拼接	l1.splice(l1.end(), std::move(l2));	O(1)
void splice(const_iterator pos, list& other, const_iterator it)	将other中it指向的元素拼接到pos前	l1.splice(l1.end(), l2, l2.begin());	O(1)
void splice(const_iterator pos, list&& other, const_iterator it)	移动版本的单个元素拼接	l1.splice(l1.end(), std::move(l2), l2.begin());	O(1)
void splice(const_iterator pos, list& other, const_iterator first, const_iterator last)	将other中[first,last)范围的元素拼接到pos前	l1.splice(l1.end(), l2, l2.begin(), l2.end());	O(1)
void splice(const_iterator pos, list&& other, const_iterator first, const_iterator last)	移动版本的范围拼接	l1.splice(l1.end(), std::move(l2), l2.begin(), l2.end());	O(1)

删除操作

函数	说明	示例	时间复杂度
void remove(const T& value)	删除所有等于value的元素	l1.remove(10);	O(n)
template<class UnaryPredicate> void remove_if(UnaryPredicate p)	删除所有满足谓词p的元素	l1.remove_if([](int x){return x%2==0;});	O(n)
void unique()	删除连续的重复元素	l1.unique();	O(n)
template<class BinaryPredicate> void unique(BinaryPredicate p)	使用二元谓词删除连续重复元素	l1.unique(std::equal_to<int>());	O(n)

排序与合并

函数	说明	示例	时间复杂度
void merge(list& other)	合并两个有序链表	l1.merge(l2);	O(size() + other.size())
void merge(list&& other)	移动版本的合并	l1.merge(std::move(l2));	O(size() + other.size())
template<class Compare> void merge(list& other, Compare comp)	使用比较器合并	l1.merge(l2, std::greater<int>());	O(size() + other.size())
template<class Compare> void merge(list&& other, Compare comp)	移动版本+比较器合并	l1.merge(std::move(l2), std::greater<int>());	O(size() + other.size())
void sort()	对链表排序	l1.sort();	O(n log n)
template<class Compare> void sort(Compare comp)	使用比较器排序	l1.sort(std::greater<int>());	O(n log n)
void reverse() noexcept	反转链表	l1.reverse();	O(n)

🔗 非成员函数

比较操作

函数	说明	示例
bool operator==(const list& lhs, const list& rhs)	相等比较	if(l1 == l2)
bool operator!=(const list& lhs, const list& rhs)	不等比较	if(l1 != l2)
bool operator<(const list& lhs, const list& rhs)	小于比较	if(l1 < l2)
bool operator<=(const list& lhs, const list& rhs)	小于等于比较	if(l1 <= l2)
bool operator>(const list& lhs, const list& rhs)	大于比较	if(l1 > l2)
bool operator>=(const list& lhs, const list& rhs)	大于等于比较	if(l1 >= l2)

C++20 三路比较

函数	说明	示例
template<class T, class Alloc> auto operator<=>(const list<T,Alloc>& lhs, const list<T,Alloc>& rhs)	三路比较	auto cmp = l1 <=> l2;

交换操作

函数	说明	示例
void swap(list& lhs, list& rhs) noexcept	特化swap算法	std::swap(l1, l2);

擦除操作 (C++20)

函数	说明	示例
template<class T, class Alloc, class U> typename list<T,Alloc>::size_type erase(list<T,Alloc>& c, const U& value)	从list中擦除所有等于value的元素	std::erase(l1, 10);
template<class T, class Alloc, class Pred> typename list<T,Alloc>::size_type erase_if(list<T,Alloc>& c, Pred pred)	从list中擦除所有满足pred的元素	std::erase_if(l1, [](int x){return x%2==0;});

💻 完整代码示例

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

int main() {
    // 1. 创建和初始化
    std::list<int> lst = {1, 2, 3, 4, 5};
    std::list<int> lst2 = {6, 7, 8};
    
    // 2. 元素访问
    std::cout << "第一个元素: " << lst.front() << std::endl;
    std::cout << "最后一个元素: " << lst.back() << std::endl;
    
    // 3. 容量操作
    std::cout << "大小: " << lst.size() << std::endl;
    std::cout << "是否为空: " << (lst.empty() ? "是" : "否") << std::endl;
    
    // 4. 基本修改操作
    lst.push_back(6);                    // 在末尾添加元素
    lst.push_front(0);                   // 在开头添加元素
    lst.emplace_back(7);                 // 在末尾原位构造
    lst.emplace_front(-1);               // 在开头原位构造
    
    // 5. 插入操作
    auto it = lst.begin();
    std::advance(it, 3);
    lst.insert(it, 99);                  // 在位置3插入
    
    // 6. 删除操作
    lst.pop_back();                      // 移除末尾元素
    lst.pop_front();                     // 移除开头元素
    it = lst.begin();
    std::advance(it, 2);
    lst.erase(it);                       // 移除位置2的元素
    
    // 7. 链表特有操作 - 拼接
    lst.splice(lst.end(), lst2);         // 将lst2拼接到lst末尾
    
    // 8. 链表特有操作 - 删除
    lst.remove(99);                      // 删除所有99
    lst.remove_if([](int x) { return x % 2 == 0; }); // 删除所有偶数
    
    // 9. 链表特有操作 - 排序和反转
    lst.sort();                          // 排序
    lst.reverse();                       // 反转
    
    // 10. 链表特有操作 - 合并
    std::list<int> sorted1 = {1, 3, 5};
    std::list<int> sorted2 = {2, 4, 6};
    sorted1.merge(sorted2);              // 合并两个有序链表
    
    // 11. 链表特有操作 - 去重
    std::list<int> dup_list = {1, 1, 2, 2, 3, 3};
    dup_list.unique();                   // 去除连续重复元素
    
    // 12. 迭代器遍历
    std::cout << "正向遍历: ";
    for (auto it = lst.begin(); it != lst.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    std::cout << "反向遍历: ";
    for (auto it = lst.rbegin(); it != lst.rend(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 13. 范围for循环
    std::cout << "范围for循环: ";
    for (const auto& element : lst) {
        std::cout << element << " ";
    }
    std::cout << std::endl;
    
    // 14. 算法使用
    auto found = std::find(lst.begin(), lst.end(), 3);
    if (found != lst.end()) {
        std::cout << "找到元素3" << std::endl;
    }
    
    // 15. 大小调整
    lst.resize(10, 100);                 // 调整大小为10，新元素为100
    std::cout << "调整大小后: ";
    for (const auto& element : lst) {
        std::cout << element << " ";
    }
    std::cout << std::endl;
    
    // 16. 交换操作
    std::list<int> swap_list = {10, 20, 30};
    lst.swap(swap_list);
    std::cout << "交换后lst: ";
    for (const auto& element : lst) {
        std::cout << element << " ";
    }
    std::cout << std::endl;
    
    // 17. C++20 擦除操作
    std::list<int> erase_list = {1, 2, 3, 2, 4, 2, 5};
    std::erase(erase_list, 2);           // 删除所有2
    std::cout << "删除所有2后: ";
    for (const auto& element : erase_list) {
        std::cout << element << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

"大道至简，衍化至繁。" ——《道德经》

至此，std::list的所有API已完整呈现。从基础构造到链表特有操作，从元素访问到复杂算法，每一招每一式都已涵盖。掌握这些"术法"，配合对双向链表"道法"的理解，你已能随心运用std::list这一利器。