C++ std::list概念与使用案例

发布于:2025-07-28 ⋅ 阅读:(12) ⋅ 点赞:(0)

C++ std::list 概念详解

std::list 是 C++ 标准模板库(STL)中的一个双向链表容器。与 vectorarray 不同,它不保证元素在内存中连续存储,而是通过指针将各个元素连接起来。

核心特性

  1. 双向链表结构
    • 每个元素包含指向前驱和后继的指针
    • 支持双向遍历(前向和后向)
  2. 时间复杂度
    • 任意位置插入/删除:O(1)
    • 随机访问:O(n)(效率低)
    • 排序:O(n log n)(使用成员函数 sort()
  3. 内存特性
    • 非连续内存分配
    • 每个元素有额外指针开销(前驱 + 后继)
    • 不会导致迭代器失效(除被删除元素)
  4. 迭代器类型
    • 双向迭代器(支持 ++--
    • 不支持随机访问(不能 + n

常用成员函数

操作 函数 示例
插入元素 push_back() list.push_back(10);
push_front() list.push_front(5);
insert() list.insert(it, 7);
删除元素 pop_back() list.pop_back();
pop_front() list.pop_front();
erase() list.erase(it);
访问元素 front() int first = list.front()
back() int last = list.back()
容量操作 size() int len = list.size()
empty() if (list.empty()) ...
特殊操作 splice() list1.splice(pos, list2)
sort() list.sort();
merge() list1.merge(list2);
reverse() list.reverse();

使用案例:订单管理系统

#include <iostream>
#include <list>
#include <string>
#include <algorithm>

// 订单结构
struct Order {
    int id;
    std::string customer;
    double amount;
    
    Order(int i, std::string c, double a) 
        : id(i), customer(c), amount(a) {}
};

int main() {
    // 创建订单链表
    std::list<Order> orders;
    
    // 添加订单(三种方式)
    orders.push_back(Order(101, "Alice", 150.0));     // 尾部添加
    orders.emplace_back(102, "Bob", 99.99);           // 直接构造(C++11)
    orders.push_front(Order(100, "VIP", 500.0));      // 头部添加
    
    // 在特定位置插入
    auto it = orders.begin();
    std::advance(it, 2);  // 移动到第三个位置
    orders.insert(it, Order(103, "Charlie", 75.5));
    
    // 遍历并打印订单(C++11范围循环)
    std::cout << "All Orders:\n";
    for (const auto& order : orders) {
        std::cout << "ID: " << order.id 
                  << ", Customer: " << order.customer 
                  << ", Amount: $" << order.amount << "\n";
    }
    
    // 删除特定订单(金额<100)
    orders.remove_if([](const Order& o) {
        return o.amount < 100.0;
    });
    
    // 按金额升序排序
    orders.sort([](const Order& a, const Order& b) {
        return a.amount < b.amount;
    });
    
    // 新订单批次
    std::list<Order> newOrders = {
        {201, "David", 200.0},
        {202, "Eva", 350.0}
    };
    
    // 合并订单(到链表尾部)
    orders.splice(orders.end(), newOrders);
    
    // 遍历打印最终订单
    std::cout << "\nFinal Orders (Sorted & Merged):\n";
    for (const auto& order : orders) {
        std::cout << "ID: " << order.id 
                  << ", Customer: " << order.customer 
                  << ", Amount: $" << order.amount << "\n";
    }
    
    // 查找特定订单
    auto findIt = std::find_if(orders.begin(), orders.end(), 
        [](const Order& o) { return o.customer == "Eva"; });
    
    if (findIt != orders.end()) {
        std::cout << "\nFound Eva's order: $" << findIt->amount << "\n";
    }
    
    return 0;
}
输出示例:
All Orders:
ID: 100, Customer: VIP, Amount: $500
ID: 101, Customer: Alice, Amount: $150
ID: 103, Customer: Charlie, Amount: $75.5
ID: 102, Customer: Bob, Amount: $99.99

Final Orders (Sorted & Merged):
ID: 103, Customer: Charlie, Amount: $75.5
ID: 102, Customer: Bob, Amount: $99.99
ID: 101, Customer: Alice, Amount: $150
ID: 201, Customer: David, Amount: $200
ID: 202, Customer: Eva, Amount: $350
ID: 100, Customer: VIP, Amount: $500

Found Eva's order: $350

关键操作详解

  1. 高效插入/删除

    // 在任意位置插入(O(1))
    auto it = orders.begin();
    std::advance(it, 3);
    orders.insert(it, Order(105, "Frank", 120.0));
    
    // 删除指定位置元素(O(1))
    orders.erase(it);
    
  2. 链表拼接

    // 将list2的所有元素移动到list1的指定位置
    list1.splice(position, list2);
    
    // 移动list2中的单个元素
    list1.splice(pos, list2, elementIt);
    
    // 移动list2中的元素范围
    list1.splice(pos, list2, startIt, endIt);
    
  3. 专用排序算法

    // 成员函数sort(比std::sort更高效)
    orders.sort(); // 默认使用operator<
    
    // 自定义排序
    orders.sort([](const Order& a, const Order& b) {
        return a.amount > b.amount; // 按金额降序
    });
    
  4. 链表合并

    // 合并两个有序链表
    list1.merge(list2); 
    // 注意:合并后list2为空
    

性能对比(vs vector)

操作 std::list std::vector
随机访问 O(n) O(1)
头部插入/删除 O(1) O(n)
尾部插入/删除 O(1) O(1) 摊销
中间插入 O(1) O(n)
内存连续性
内存开销 高(指针)

最佳实践

  1. 适用场景

    • 需要频繁在任意位置插入/删除
    • 不需要随机访问
    • 需要稳定迭代器(不失效)
    • 需要高效合并/拆分操作
  2. 不适用场景

    • 需要随机访问元素
    • 内存受限环境
    • 需要缓存友好的操作
  3. 现代C++技巧

    // 结构化绑定(C++17)
    for (const auto& [id, customer, amount] : orders) {
        std::cout << customer << ": $" << amount << "\n";
    }
    
    // 自定义内存分配器
    std::list<int, MyAllocator> customList;
    

经典应用场景

  1. LRU缓存实现:使用链表+哈希表
  2. 撤销/重做功能:维护操作历史
  3. 消息队列系统:高效插入/删除
  4. 图算法:邻接表表示
  5. 多线程任务池:任务调度

网站公告

今日签到

点亮在社区的每一天
去签到