C++ STL list完全指南：实战派的入门到进阶技巧

#include <list>
#include <iostream>
using namespace std;

int main() {
    list<int> l;
    // 1. 尾部插入
    l.push_back(1);  // l: [1]
    // 2. 头部插入
    l.push_front(0); // l: [0,1]
    // 3. 中间插入（用迭代器定位）
    auto it = l.begin(); ++it; // 指向1的位置
    l.insert(it, 2);           // l: [0,2,1]（在it前插入2）
    // 4. 删除尾部
    l.pop_back();  // l: [0,2]
    // 5. 删除指定位置
    it = l.begin();
    l.erase(it);   // l: [2]（删除头部元素）
    return 0;
}

list<int> l{1,2,3,4};
// 方式1：迭代器遍历（最通用）
for (list<int>::iterator it = l.begin(); it != l.end(); ++it) {
    cout << *it << " "; // 输出：1 2 3 4
}
// 方式2：范围for（更简洁）
for (auto num : l) {
    cout << num << " ";
}
// 方式3：反向迭代器（从后往前）
for (auto rit = l.rbegin(); rit != l.rend(); ++rit) {
    cout << *rit << " "; // 输出：4 3 2 1
}

list<int> l{1,2,3};
auto it = l.begin(); // 指向1
l.insert(it, 0);     // 插入0，it仍然指向1（有效！）
cout << *it << endl; // 输出1（正确）

// 错误示例：删除所有偶数（会崩溃！）
for (auto it = l.begin(); it != l.end(); ++it) {
    if (*it % 2 == 0) {
        l.erase(it); // erase后it失效，++it会出错
    }
}
// 正确示例：用erase的返回值
for (auto it = l.begin(); it != l.end(); ) { // 注意：这里没有++it
    if (*it % 2 == 0) {
        it = l.erase(it); // erase返回下一个有效迭代器
    } else {
        ++it; // 只有不删除时才移动迭代器
    }
}

list<int> l{3,1,4,1,5};
// 默认升序排序
l.sort(); // l: [1,1,3,4,5]
// 自定义降序排序（用lambda）
l.sort([](int a, int b) { return a > b; }); // l: [5,4,3,1,1]

list<int> l1{1,3,5};
list<int> l2{2,4,6};
l1.merge(l2); // l1: [1,2,3,4,5,6]，l2变为空

#include <list>
#include <unordered_map>
#include <iostream>
using namespace std;

class LRUCache {
private:
    int capacity; // 缓存容量
    // list存储键值对：front是最近使用，back是最久未使用
    list<pair<int, int>> cache;
    // 哈希表：键 -> list中的迭代器（快速找到元素位置）
    unordered_map<int, list<pair<int, int>>::iterator> map;

public:
    LRUCache(int cap) : capacity(cap) {}

    // 获取缓存值
    int get(int key) {
        auto it = map.find(key);
        if (it == map.end()) {
            return -1; // 不存在该键
        }
        // 把访问的元素移到list头部（splice是list的成员函数，O(1)时间）
        cache.splice(cache.begin(), cache, it->second);
        return it->second->second; // 返回值
    }

    // 插入/更新缓存
    void put(int key, int value) {
        auto it = map.find(key);
        if (it != map.end()) {
            // 存在，更新值并移到头部
            it->second->second = value;
            cache.splice(cache.begin(), cache, it->second);
            return;
        }
        // 不存在，检查容量
        if (cache.size() == capacity) {
            // 删除最久未使用的元素（list尾部）
            auto last = cache.back();
            map.erase(last.first); // 从哈希表删除键
            cache.pop_back();      // 从list删除尾部
        }
        // 插入新元素到头部
        cache.push_front({key, value});
        map[key] = cache.begin(); // 哈希表记录迭代器
    }
};

// 测试代码
int main() {
    LRUCache cache(2);
    cache.put(1, 1); // 缓存：[(1,1)]
    cache.put(2, 2); // 缓存：[(2,2), (1,1)]
    cout << cache.get(1) << endl; // 1，缓存变为[(1,1), (2,2)]
    cache.put(3, 3); // 容量满，删除(2,2)，缓存变为[(3,3), (1,1)]
    cout << cache.get(2) << endl; // -1（已删除）
    return 0;
}