C++ STL list容器用法详解与实战示例

// list的典型内部结构示意
template<typename T>
class list_node {
    T data;              // 元素数据
    list_node* prev;     // 指向前一个节点的指针
    list_node* next;     // 指向后一个节点的指针
};

#include <list>
#include <iostream>
 
// 基本声明方式
std::list<int> numbers;                    // 空list
std::list<int> numbers(10);                 // 包含10个默认元素
std::list<int> numbers(10, 5);              // 包含10个值为5的元素
std::list<int> numbers{1, 2, 3, 4, 5};     // 初始化列表
 
// 拷贝构造
std::list<int> copy_list(numbers);
 
// 范围构造
std::vector<int> vec{1, 2, 3, 4, 5};
std::list<int> from_vec(vec.begin(), vec.end());

std::list<std::string> fruits{"apple", "banana", "orange"};
 
// 首尾元素直接访问
std::cout << "First fruit: " << fruits.front() << std::endl;
std::cout << "Last fruit: " << fruits.back() << std::endl;
 
// 迭代器遍历
for (auto it = fruits.begin(); it != fruits.end(); ++it) {
    std::cout << *it << " ";
}
 
// 范围for循环（C++11）
for (const auto& fruit : fruits) {
    std::cout << fruit << " ";
}
 
// 反向遍历
for (auto rit = fruits.rbegin(); rit != fruits.rend(); ++rit) {
    std::cout << *rit << " ";
}

std::list<int> numbers{1, 2, 3, 4, 5};
 
// 在容器开头添加元素
numbers.push_front(0);          // {0, 1, 2, 3, 4, 5}
 
// 在容器末尾添加元素
numbers.push_back(6);           // {0, 1, 2, 3, 4, 5, 6}
 
// 删除第一个元素
numbers.pop_front();            // {1, 2, 3, 4, 5, 6}
 
// 删除最后一个元素
numbers.pop_back();             // {1, 2, 3, 4, 5}
 
// 在指定位置插入元素
auto it = numbers.begin();
std::advance(it, 2);            // 移动到第3个位置
numbers.insert(it, 999);        // {1, 2, 999, 3, 4, 5}
 
// 删除指定位置的元素
it = numbers.begin();
std::advance(it, 2);
numbers.erase(it);              // {1, 2, 3, 4, 5}
 
// 修改首尾元素
numbers.front() = 10;
numbers.back() = 50;            // {10, 2, 3, 4, 50}

std::list<int> list1{1, 2, 3, 4, 5};
std::list<int> list2{10, 20, 30};
 
// 将整个list2拼接到list1的指定位置
auto it = list1.begin();
std::advance(it, 2);            // 指向list1的第3个元素
list1.splice(it, list2);        // list1: {1, 2, 10, 20, 30, 3, 4, 5}
                                // list2现在为空
 
// 只拼接list2的一个元素
std::list<int> list3{100, 200, 300};
auto pos = list1.begin();
std::advance(pos, 1);
auto elem = list3.begin();
std::advance(elem, 1);          // 指向200
list1.splice(pos, list3, elem); // list1: {1, 10, 200, 2, 10, 20, 30, 3, 4, 5}
 
// 拼接一段范围
std::list<int> list4{1000, 2000, 3000, 4000};
auto start = list4.begin();
auto end = list4.begin();
std::advance(start, 1);         // 2000
std::advance(end, 3);           // 4000 (不包含)
pos = list1.begin();
std::advance(pos, 2);
list1.splice(pos, list4, start, end); // list1: {1, 10, 200, 2000, 3000, 2, 10, 20, 30, 3, 4, 5}

std::list<int> numbers{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
 
// 排序（默认升序）
numbers.sort();                 // {1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9}
 
// 降序排序
numbers.sort(std::greater<int>()); // {9, 6, 5, 5, 5, 4, 3, 3, 2, 1, 1}
 
// 去重（需要先排序）
numbers.unique();               // {9, 6, 5, 4, 3, 2, 1}
 
// 自定义去重条件
std::list<int> numbers2{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
numbers2.unique([](int a, int b) { 
    return (a % 2) == (b % 2);    // 相邻且奇偶性相同的视为重复
});                              // {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

struct Student {
    std::string name;
    int score;
    int age;
};
 
std::list<Student> students{
    {"Alice", 85, 20},
    {"Bob", 92, 19},
    {"Charlie", 78, 21},
    {"David", 95, 18}
};
 
// 按分数降序排序
students.sort([](const Student& a, const Student& b) {
    return a.score > b.score;
});
 
// 多条件排序：先按分数，再按年龄
students.sort([](const Student& a, const Student& b) {
    if (a.score != b.score) {
        return a.score > b.score;
    }
    return a.age < b.age;
});
 
// 输出排序结果
for (const auto& student : students) {
    std::cout << student.name << ": " << student.score 
              << " (" << student.age << "岁)" << std::endl;
}

#include <list>
#include <iostream>
#include <string>
#include <chrono>
#include <algorithm>
 
enum class TaskPriority {
    LOW = 1,
    NORMAL = 2,
    HIGH = 3,
    CRITICAL = 4
};
 
struct Task {
    std::string id;
    std::string description;
    TaskPriority priority;
    std::chrono::system_clock::time_point created_time;
    bool completed;
    
    Task(const std::string& desc, TaskPriority prio = TaskPriority::NORMAL)
        : id(generate_id()), description(desc), priority(prio),
          created_time(std::chrono::system_clock::now()), completed(false) {}
    
private:
    static std::string generate_id() {
        static int counter = 0;
        return "TASK_" + std::to_string(++counter);
    }
};
 
class TaskScheduler {
private:
    std::list<Task> tasks;
    
public:
    // 添加任务（按优先级排序插入）
    void add_task(const Task& task) {
        auto it = std::find_if(tasks.begin(), tasks.end(),
            [&task](const Task& t) { return t.priority < task.priority; });
        tasks.insert(it, task);
        std::cout << "添加任务: " << task.id << " - " << task.description << std::endl;
    }
    
    // 获取下一个高优先级任务
    Task get_next_task() {
        if (tasks.empty()) {
            throw std::runtime_error("没有待处理的任务");
        }
        
        auto it = std::find_if(tasks.begin(), tasks.end(),
            [](const Task& t) { return !t.completed; });
        
        if (it == tasks.end()) {
            throw std::runtime_error("所有任务都已完成");
        }
        
        Task task = *it;
        it->completed = true;
        return task;
    }
    
    // 完成任务并移除
    void complete_task(const std::string& task_id) {
        auto it = std::find_if(tasks.begin(), tasks.end(),
            [&task_id](const Task& t) { return t.id == task_id; });
        
        if (it != tasks.end()) {
            it->completed = true;
            std::cout << "完成任务: " << task_id << std::endl;
        }
    }
    
    // 紧急插入任务到队列前端
    void insert_urgent_task(const Task& task) {
        tasks.push_front(task);
        std::cout << "紧急插入任务: " << task.id << std::endl;
    }
    
    // 合并另一个调度器的任务
    void merge_tasks(TaskScheduler& other) {
        tasks.splice(tasks.end(), other.tasks);
        // 重新按优先级排序
        tasks.sort([](const Task& a, const Task& b) {
            if (a.priority != b.priority) {
                return static_cast<int>(a.priority) > static_cast<int>(b.priority);
            }
            return a.created_time < b.created_time;
        });
        std::cout << "合并任务完成，当前任务数: " << tasks.size() << std::endl;
    }
    
    // 显示所有任务状态
    void display_tasks() const {
        std::cout << "\n=== 任务列表 ===" << std::endl;
        for (const auto& task : tasks) {
            std::cout << "ID: " << task.id 
                      << " | 描述: " << task.description
                      << " | 优先级: " << static_cast<int>(task.priority)
                      << " | 状态: " << (task.completed ? "已完成" : "待处理")
                      << std::endl;
        }
        std::cout << "总任务数: " << tasks.size() << std::endl;
    }
    
    // 清理已完成的任务
    void cleanup_completed() {
        auto it = std::remove_if(tasks.begin(), tasks.end(),
            [](const Task& t) { return t.completed; });
        tasks.erase(it, tasks.end());
        std::cout << "清理已完成任务，剩余任务数: " << tasks.size() << std::endl;
    }
    
    size_t size() const { return tasks.size(); }
    bool empty() const { return tasks.empty(); }
};
 
// 使用示例
int main() {
    TaskScheduler scheduler;
    
    // 添加不同优先级的任务
    scheduler.add_task(Task("修复登录页面的bug", TaskPriority::HIGH));
    scheduler.add_task(Task("更新文档", TaskPriority::LOW));
    scheduler.add_task(Task("数据库备份", TaskPriority::CRITICAL));
    scheduler.add_task(Task("代码审查", TaskPriority::NORMAL));
    scheduler.add_task(Task("性能优化", TaskPriority::HIGH));
    
    // 紧急任务插入
    scheduler.insert_urgent_task(Task("服务器宕机紧急修复", TaskPriority::CRITICAL));
    
    std::cout << "\n初始任务队列:" << std::endl;
    scheduler.display_tasks();
    
    // 处理几个任务
    std::cout << "\n处理任务:" << std::endl;
    for (int i = 0; i < 3; ++i) {
        try {
            Task task = scheduler.get_next_task();
            std::cout << "执行任务: " << task.id << " - " << task.description << std::endl;
        } catch (const std::exception& e) {
            std::cout << "错误: " << e.what() << std::endl;
        }
    }
    
    // 创建另一个调度器并合并任务
    TaskScheduler scheduler2;
    scheduler2.add_task(Task("新功能开发", TaskPriority::NORMAL));
    scheduler2.add_task(Task("安全漏洞修复", TaskPriority::CRITICAL));
    
    std::cout << "\n合并任务前:" << std::endl;
    scheduler.display_tasks();
    
    scheduler.merge_tasks(scheduler2);
    
    std::cout << "\n合并任务后:" << std::endl;
    scheduler.display_tasks();
    
    // 清理已完成的任务
    scheduler.cleanup_completed();
    
    std::cout << "\n清理后:" << std::endl;
    scheduler.display_tasks();
    
    return 0;
}

// 预分配节点池以减少内存分配开销
template<typename T>
class ListWithPool {
private:
    std::list<T> data;
    std::list<T> pool;  // 预分配的节点池
    
public:
    void reserve(size_t n) {
        // 预分配n个节点到池中
        for (size_t i = 0; i < n; ++i) {
            pool.emplace_back();
        }
    }
    
    void push_back(const T& value) {
        if (!pool.empty()) {
            // 从池中获取节点，避免新的内存分配
            data.splice(data.end(), pool, pool.begin());
            data.back() = value;
        } else {
            data.push_back(value);
        }
    }
    
    void pop_back() {
        if (!data.empty()) {
            // 将节点返回到池中，而不是立即释放
            pool.splice(pool.end(), data, std::prev(data.end()));
        }
    }
};

std::list<int> numbers{1, 2, 3, 4, 5};
auto it = std::find(numbers.begin(), numbers.end(), 3);  // 指向元素3
 
// 在list开头插入元素，it仍然有效
numbers.push_front(0);
std::cout << *it << std::endl;  // 输出: 3
 
// 删除其他元素，it仍然有效
numbers.pop_front();
std::cout << *it << std::endl;  // 输出: 3
 
// 只有当it指向的元素被删除时，迭代器才会失效
numbers.erase(it);  // 现在it失效了

void safe_operations() {
    std::list<std::string> list1{"a", "b", "c"};
    std::list<std::string> list2{"x", "y", "z"};
    
    try {
        // splice操作提供强异常安全保证
        list1.splice(list1.begin(), list2);
        
        // 如果元素的拷贝构造函数抛出异常，
        // list会保持操作前的状态
        std::string value = "test";
        list1.push_back(value);
        
    } catch (const std::exception& e) {
        // 异常发生时，list1和list2都处于有效状态
        std::cout << "异常: " << e.what() << std::endl;
    }
}

// 性能测试对比示例
#include <chrono>
#include <vector>
#include <random>
 
template<typename Container>
double benchmark_insert_delete(size_t operations) {
    Container container;
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(0, 1000);
    
    // 预填充数据
    for (size_t i = 0; i < 1000; ++i) {
        container.push_back(dis(gen));
    }
    
    auto start = std::chrono::high_resolution_clock::now();
    
    for (size_t i = 0; i < operations; ++i) {
        auto it = container.begin();
        std::advance(it, dis(gen) % container.size());
        container.insert(it, dis(gen));
        
        it = container.begin();
        std::advance(it, dis(gen) % container.size());
        container.erase(it);
    }
    
    auto end = std::chrono::high_resolution_clock::now();
    return std::chrono::duration<double, std::milli>(end - start).count();
}
 
int main() {
    const size_t operations = 10000;
    
    double list_time = benchmark_insert_delete<std::list<int>>(operations);
    double vector_time = benchmark_insert_delete<std::vector<int>>(operations);
    
    std::cout << "List插入删除时间: " << list_time << " ms" << std::endl;
    std::cout << "Vector插入删除时间: " << vector_time << " ms" << std::endl;
    std::cout << "性能提升: " << (vector_time / list_time) << "x" << std::endl;
    
    return 0;
}