C++学习笔记（二十九）——list

一、std::list

（1）list与其适用场景

std::list 是 C++的STL（标准模板库）中的双向链表容器，支持高效的插入、删除操作，适用于频繁在容器中间插入或删除元素的场景。

特点：

• 双向链表（Doubly Linked List），支持双向迭代。
• 任意位置插入/删除效率高（O(1)）。
• 不支持随机访问（O(n) 查找）。
• 遍历比 vector 慢（由于链表节点分散存储）。

适用场景：

• 频繁插入/删除
• 不需要随机访问
• 链表结构（如 LRU 缓存）

（2）list vs vector

list 在需要高效插入/删除的情况下比 vector 更合适，但如果需要频繁访问元素，vector 更优。

二、std::list 的常用函数

三、std::list的基本使用

(1) 插入与删除

示例：

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

int main() {
    list<int> myList;

    myList.push_back(10);   // 尾部插入
    myList.push_front(5);   // 头部插入
    myList.insert(++myList.begin(), 7); // 在第二个位置插入 7

    cout << "链表内容: ";
    for (int val : myList)
    {
        cout << val << " "; // 5 7 10
    }
    cout << endl;

    myList.pop_back();   // 删除尾部元素
    myList.pop_front();  // 删除头部元素

    cout << "删除后: ";
    for (int val : myList)
    {
        cout << val << " "; // 7
    }
    cout << endl;
    
    system("pause");
    return 0;
}

注意：

• push_back(val) —— 尾部插入元素；pop_back() —— 删除尾部元素。
• push_front(val) —— 头部插入元素；pop_front() —— 删除头部元素。

(2) 删除特定值

示例：

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

int main() {
    list<int> myList = { 1, 2, 2, 3, 4, 2, 5 };

    myList.remove(2); // 删除所有 2

    for (int val : myList)
    {
        cout << val << " "; // 1 3 4 5
    }
    cout << endl;

    system("pause");
    return 0;
}

(3) 排序与反转

示例：

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

void printList(list<int> L)
{
    for (int val : L)
    {
        cout << val << " ";
    }
    cout << endl;
}

int main() {
    list<int> myList = { 3, 1, 4, 1, 5, 9 };

    myList.sort(); // 默认升序
    printList(myList);

    myList.reverse(); // 反转
    printList(myList);
    
    system("pause");
    return 0;
}

注意：

• sort() 默认为升序排列，再执行reverse()后为逆序排列；

(4) 去重

示例：

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

void printList(list<int> L)
{
    for (int val : L)
    {
        cout << val << " ";
    }
    cout << endl;
}

int main() {
    list<int> myList = {1, 1, 2, 3, 2, 4, 5, 5, 6};
    printList(myList);

    myList.unique(); // 仅删除相邻的重复元素
    printList(myList);
    
    system("pause");
    return 0;
}

注意：

• myList.unique() 删除链表myList中的连续重复元素（连续重复时，只保留一个副本）。

四、std::list 的应用

(1) LRU（最近最少使用）缓存

LRU（Least Recently Used） 是一种基于访问时间排序的缓存淘汰策略，
其核心思想是：‌最近被访问的数据在未来被访问的概率更高‌，因此当缓存容量满时，优先淘汰最久未被使用的数据‌。

示例：

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

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

    void access(int key)
    {
        if (cacheMap.find(key) != cacheMap.end())
        {
            cacheList.erase(cacheMap[key]); // 若重复访问，删除最早访问记录，保留最近访问记录
        }
        else if (cacheList.size() == capacity)
        {
            int last = cacheList.back();
            cacheList.pop_back(); // 若达到容量限制，删除最近最少使用的数据
            cacheMap.erase(last);
        }

        cacheList.push_front(key);
        cacheMap[key] = cacheList.begin();
    }

    void print()
    {
        for (int val : cacheList)
        {
            cout << val << " ";
        }
        cout << endl;
    }

private:
    int capacity; // 缓存空间的最大容量
    list<int> cacheList; // 缓存数据
    unordered_map<int, list<int>::iterator> cacheMap; // 访问记录
};

int main() {
    LRUCache cache(3);
    cache.access(1);
    cache.access(2);
    cache.access(3);

    cache.access(4); // 1 被淘汰
    cache.access(2);
    cache.print(); // 2 4 3

    system("pause");
    return 0;
}

注意：

• LRUCache cache(3); 中链表最大容量为3。
• 连续访问数据1，2，3后，达到最大容量，继续访问数据4时，删除最近最少使用的数据1。