编辑“︁C++list”︁

{{Note|本教程适用于C++初学者及需要复习STL容器的开发者。建议先掌握[[C++基础语法]]和[[迭代器]]相关知识。}}

= C++ STL list容器详解 =

'''std::list'''是C++标准模板库(STL)中提供的'''双向链表'''容器，在<list>头文件中定义。与vector和array不同，list不支持随机访问，但可以在任意位置高效插入和删除元素。

== 基本特性 ==
* '''双向链表结构'''：每个元素包含指向前驱和后继的指针
* '''时间复杂度'''：
** 插入/删除：O(1)（已知位置时）
** 查找：O(n)
* '''内存布局'''：非连续内存存储
* '''迭代器类型'''：双向迭代器

<mermaid>
graph LR
    A[list] --> B[元素1]
    B --> C[元素2]
    C --> D[元素3]
    D --> E[...]
    E --> F[元素N]
    F --> E
    E --> D
    D --> C
    C --> B
    B --> A
</mermaid>

== 声明与初始化 ==
list提供多种初始化方式：

<syntaxhighlight lang="cpp">
#include <list>
#include <iostream>

int main() {
    // 1. 空list
    std::list<int> list1;
    
    // 2. 包含5个元素，每个值为10
    std::list<int> list2(5, 10);
    
    // 3. 通过初始化列表
    std::list<int> list3 = {1, 2, 3, 4, 5};
    
    // 4. 通过迭代器范围
    int arr[] = {6, 7, 8};
    std::list<int> list4(arr, arr + sizeof(arr)/sizeof(arr[0]));
    
    // 输出验证
    for(int n : list4)
        std::cout << n << " ";
    // 输出: 6 7 8
    
    return 0;
}
</syntaxhighlight>

== 常用成员函数 ==
=== 容量相关 ===
* '''empty()'''：检查是否为空
* '''size()'''：返回元素数量
* '''max_size()'''：返回可容纳的最大元素数

=== 元素访问 ===
* '''front()'''：访问第一个元素
* '''back()'''：访问最后一个元素

=== 修改操作 ===
* '''push_front()'''/'''pop_front()'''：在头部插入/删除
* '''push_back()'''/'''pop_back()'''：在尾部插入/删除
* '''insert()'''：在指定位置插入
* '''erase()'''：删除指定位置元素
* '''clear()'''：清空容器

=== 特殊操作 ===
* '''splice()'''：转移元素到另一个list
* '''remove()'''/'''remove_if()'''：删除特定元素
* '''unique()'''：删除连续重复元素
* '''merge()'''：合并两个已排序list
* '''sort()'''：排序
* '''reverse()'''：反转元素顺序

== 详细示例 ==
=== 基本操作 ===
<syntaxhighlight lang="cpp">
#include <list>
#include <iostream>

int main() {
    std::list<std::string> names;
    
    // 添加元素
    names.push_back("Alice");
    names.push_front("Bob");
    names.insert(++names.begin(), "Charlie"); // 在第二个位置插入
    
    // 遍历输出
    for(const auto& name : names)
        std::cout << name << " ";
    // 输出: Bob Charlie Alice
    
    // 删除元素
    names.remove("Bob"); // 删除值为"Bob"的元素
    names.pop_back();    // 删除最后一个元素
    
    std::cout << "\nSize after deletion: " << names.size();
    // 输出: Size after deletion: 1
    
    return 0;
}
</syntaxhighlight>

=== 高级操作示例 ===
<syntaxhighlight lang="cpp">
#include <list>
#include <algorithm>
#include <iostream>

int main() {
    std::list<int> nums = {5, 3, 7, 1, 9, 2};
    
    // 排序
    nums.sort(); // list特有的排序方法
    
    // 删除所有奇数
    nums.remove_if([](int n) { return n % 2 != 0; });
    
    // 合并两个list
    std::list<int> other = {4, 8};
    nums.merge(other);
    
    // 输出结果
    for(int n : nums)
        std::cout << n << " ";
    // 输出: 2 4 8
    
    return 0;
}
</syntaxhighlight>

== 性能分析 ==
list与其它序列容器的比较：

{| class="wikitable"
|+ 容器操作时间复杂度比较
! 操作 !! list !! vector !! deque
|-
| 头部插入/删除 || O(1) || O(n) || O(1)
|-
| 尾部插入/删除 || O(1) || O(1) || O(1)
|-
| 中间插入/删除 || O(1) || O(n) || O(n)
|-
| 随机访问 || O(n) || O(1) || O(1)
|}

== 实际应用案例 ==
=== 场景1：高频插入删除 ===
在游戏开发中，管理动态变化的实体列表：

<syntaxhighlight lang="cpp">
class GameEntity {
    // 实体类定义...
};

std::list<GameEntity> entities;

// 每帧更新
void updateGame() {
    for(auto it = entities.begin(); it != entities.end(); ) {
        if(it->shouldBeRemoved()) {
            it = entities.erase(it); // 高效删除
        } else {
            it->update();
            ++it;
        }
    }
    
    // 添加新实体
    if(shouldSpawnNewEntity()) {
        entities.emplace_back(createEntity());
    }
}
</syntaxhighlight>

=== 场景2：LRU缓存实现 ===
利用list的快速插入删除和顺序保持特性：

<syntaxhighlight lang="cpp">
template<typename K, typename V>
class LRUCache {
    std::list<std::pair<K, V>> items;
    std::unordered_map<K, typename std::list<std::pair<K, V>>::iterator> keyToItem;
    size_t capacity;
    
public:
    LRUCache(size_t cap) : capacity(cap) {}
    
    void put(const K& key, const V& value) {
        auto it = keyToItem.find(key);
        if(it != keyToItem.end()) {
            items.erase(it->second);
            keyToItem.erase(it);
        }
        
        items.push_front({key, value});
        keyToItem[key] = items.begin();
        
        if(items.size() > capacity) {
            keyToItem.erase(items.back().first);
            items.pop_back();
        }
    }
    
    bool get(const K& key, V& value) {
        auto it = keyToItem.find(key);
        if(it == keyToItem.end()) return false;
        
        items.splice(items.begin(), items, it->second); // 关键操作
        value = it->second->second;
        return true;
    }
};
</syntaxhighlight>

== 最佳实践与注意事项 ==
1. '''迭代器失效'''：只有被删除元素的迭代器会失效，其它迭代器保持有效
2. '''内存使用'''：每个元素需要额外存储两个指针，内存开销较大
3. '''缓存不友好'''：非连续存储可能导致缓存命中率低
4. '''何时使用'''：
   * 需要频繁在中间位置插入删除
   * 不需要随机访问
   * 需要稳定的迭代器和引用（元素地址不变）

== 数学特性 ==
对于包含N个元素的list：
* 空间复杂度：O(N)
* 指针操作次数：插入/删除操作需要常数时间指针重定向（<math>O(1)</math>）
* 排序时间复杂度：<math>O(N \log N)</math>（使用归并排序实现）

== 扩展阅读 ==
* [[C++ STL概览]]
* [[迭代器设计模式]]
* [[链表数据结构详解]]

{{Tip|在C++11及以后版本中，考虑使用emplace_front()和emplace_back()代替push操作，可以避免不必要的拷贝/移动操作。}}

[[Category:编程语言]]
[[Category:C++]]
[[Category:C++stl 容器]]