模板泛型

template<typename Key, typename Value>；定义一个模板，里面有两个可变类型

原来我只能读写int变量，而工程里需要根据用户自己决定存储什么。

这里的key value 不是变量，而是类型占位符；

当你写的数据结构不想绑定固定类型时，就用模板。

链表
栈
队列
哈希表
缓存系统
树
图

比如标准库里的以下几种都是模板：

std::vector<int>
std::vector<std::string>
std::unordered_map<int, int>
std::unordered_map<std::string, int>

节点封装

template<typename Key, typename Value>
class LruNode 
{
private:
    Key key_;
    Value value_;
    size_t accessCount_;
    std::weak_ptr<LruNode<Key, Value>> prev_;
    std::shared_ptr<LruNode<Key, Value>> next_;

public:
    LruNode(Key key, Value value)
        : key_(key)
        , value_(value)
        , accessCount_(1) 
    {}

    Key getKey() const { return key_; }
    Value getValue() const { return value_; }
    void setValue(const Value& value) { value_ = value; }
    size_t getAccessCount() const { return accessCount_; }
    void incrementAccessCount() { ++accessCount_; }

    friend class KLruCache<Key, Value>;
};

节点

基础节点：

Key key_;  //节点
Value value_; //
size_t accessCount_; //无符号整数类型,记录访问次数

Key getKey() const { return key_; }

Value getValue() const { return value_; }

void setValue(const Value& value) { value_ = value; }

size_t getAccessCount() const { return accessCount_; }

void incrementAccessCount() { ++accessCount_; }

讲这个节点之前，先介绍几种函数：getter和setter，分别是读取成员变量和修改成员变量的函数，因为成员变量属于私有变量，不能直接用来读取修改，所以必须用一个接口函数来公开给外部操作，incrementAccessCount()就是访问次数加1函数。

举例说明：Key getKey() const { return key_; }//数据类型   函数名   const{返回值}

你发现，此处有一个const，没毛病，他也是一个成员函数，表示：这个函数不会修改当前对象内部的数据。像getKey(),这种不会修改数据，可以使用const.   但是！！set不行，所以你会看到：

void setValue(const Value& value) { value_ = value; }

Value&：引用传参，不复制外部数据；     

const：函数内部不能修改这个传入参数

引用传参：不复制外部数据，只用引用方式借用它

按值传参：把外部传进来的数据复制一份

简单的说就是：外部----拷贝一份作为传入函数----成员变量----拷贝一份。引用传参就省略第一步的外部拷贝，直接传进来。（很多时候大数据拷贝会很浪费资源）

封装

关于封装：把数据藏在类内部，不让外部直接乱改；然后通过 public 函数提供受控访问入口，细心的你发现了吗？封装就是上面说的public里写的函数，我们的getter,setter都是封装的函数，为了给外部提供一个受控的访问入口。

对象

在 C++ 里，类是设计图，对象是根据设计图创建出来的具体东西

比如我们写一个类：

class Student

{private:

     int age_;

};//类：Student 这种东西里面有一个 age_

但是如果我写Student stu;就变成了具体的对象。

总结：对象就是类真正创建出来的实体，里面有自己的成员变量

friend友元类

与private public一样是访问权限。

friend class表示允许某个类访问当前类的 private 成员

friend class KLruCache<Key, Value>;就是让缓存管理类可以访问自己的private。

LruNode 负责保存节点数据；
KLruCache 负责管理节点连接关系。

所以这里必须得给一个friend,好兄弟！

所学回顾：

1. 使用模板 template，让 key 和 value 不再固定为 int

2. 使用 private 封装成员变量，防止外部随意修改

3. 使用 getter / setter 提供受控访问接口

4. 使用 shared_ptr / weak_ptr 管理节点指针

5. 使用 accessCount_ 记录访问次数，方便后续扩展

6. 使用 friend class 允许 KLruCache 管理节点内部指针

智能指针

上一个基础版里我写的是Node*这个指针，但是我自己建完节点，需要自己手动删除节点：

delete tailNode;

这一节我们学习智能指针 std::shared_ptr<LruNodeType>，

比较以下两种：

Node* p = new Node(1, 100);

std::shared_ptr<Node> p = std::make_shared<Node>(1, 100);

区别是shared_ptr没人使用时会自动释放内存，所以工程版不需要再去写析构函数手动删除节点。

什么时候用到呢？当对象生命周期比较复杂、多个地方都可能引用同一个对象时，就比如我们的LRU_cache里的一个节点会被哈希表和双向链表同时使用。

还有一个智能指针weak_ptr，它的区别如下：

shared_ptr：拥有对象，会增加引用计数
weak_ptr：只观察对象，不拥有对象，不增加引用计数

也就是说shared_ptr真正拿着一个节点，也能自动释放节点，而weak_ptr只记住节点位置。这样能避免循环引用，也就是A拥有B，B也拥有A。

但是weak_ptr是弱引用，访问前需要先变成shared_ptr。

类型别名

1.using:   起别名，本次我们会用using给长对象起短名：using LruNodeType = LruNode<Key, Value>;以后 LruNodeType 就代表 LruNode<Key, Value> 这个类型.

看下面这行：

LruNodeType node(key, value);等价于LruNode<Key, Value> node(key, value);

LruNodeType同样是类型名，node是变量名，  LruNode是前面创建的模板  ，加上LruNode<Key, Value>才是一个节点类型。

接口继承

在C++中，通常用抽象基类 + 纯虚函数来表示接口；

template<typename Key, typename Value>
class KLruCache : public KICachePolicy<Key, Value>

假设我们写了一个类：KICachePolicy;假设类里有这么一个函数：

virtual void put(Key key, Value value) = 0;这个叫做纯虚函数，只说名字和参数，具体实现都没有，这玩意纯虚；那么含有这玩意的类叫做抽象类，含有抽象类的叫接口。明白了吗？核子

将KICachePolicy名字拆开：

K       项目前缀
I       Interface，接口
Cache   缓存
Policy  策略

很显然这玩意就是缓存策略接口，他不管你具体是 LRU、LFU、FIFO，还是别的缓存算法之类的，只管指定规则，你用了我，就按我的规矩，比如一个缓存策略应该具备哪些基本操作之类。

举个栗子：

class KLruCache : public KICachePolicy<Key, Value>

前面的是一个类，这个类用来写我具体的缓存策略，但是一些基本的缓存规定继承自KI，你也可以写不同的策略，但是都继承这一个KI就行了，因为里面有基本的读写删都有。

但是注意里面规定了一些纯虚的玩意，你得自己给定义好了，我chovy。

这么说吧：

KICachePolicy 是考试大纲；
KLruCache 是按照大纲写出来的具体答案。

那有人就说了，我直接写，就不继承你，那我说白了，白说了。

所以具体使用场景就是：

当你有多种实现，但希望它们对外表现一致时，就用接口继承；

再举个栗子

class PaymentInterface
{
public:
    virtual void pay() = 0;
};

class AliPay : public PaymentInterface   //阿里支付
class WeChatPay : public PaymentInterface   //微信支付
class BankPay : public PaymentInterface   //银行支付

用户：payment->pay(); //明白了吗

那么我就管KI这一类叫做父类接口，在父类接口里写了抽象类，在子类中我们就要给他落实，比如：

void put(Key key, Value value) override

bool get(Key key, Value& value) override

这个override就跟编译器说：你看你看，这里是在重写父类里的纯虚函数，快检查一下写错没。

还有：~KLruCache() override = default;这不是前几期讲的析构函数嘛，介玩意怎么也成纯虚的了，是的，这表示允许通过父类指针正确释放子类对象，(通常父类里有virtual ~KICachePolicy() = default;);只要一个类被当作接口基类使用，析构函数通常要写成 virtual。

线程安全

试想一下，你和我同时访问一个缓存系统，如果不写一个安全保障，可能会乱，我们的目标就是多个线程同时访问同一份数据时，程序结果仍然正确，不会把数据结构改乱。

互斥锁：std::mutex mutex_;

给共享数据加一把锁，同一时间只允许一个线程进入关键区域

我的系统里共享资源有：

int capacity_;
NodeMap nodeMap_;
NodePtr dummyHead_;
NodePtr dummyTail_;我得保护他们

std::lock_guard<std::mutex> lock(mutex_);

当前函数开始操作共享数据前，先锁住 mutex_。
等函数结束时，自动解锁。

这里用guard自动析构，而不是手动，就是 C++ 里的 RAII 思想：

资源交给对象管理；
对象创建时获取资源；
对象销毁时释放资源。

锁就对应资源

那我这么一说，聪明的你就知道了，这样做简单安全，但是并发操作性能几乎没有，你得排队

完整工程版

完整代码放在这里，下一讲我们来聊一聊整个编程的思路，如果有帮助记得三连一下，阿里嘎多思密达。

// 前向声明
template<typename Key, typename Value> class KLruCache;

template<typename Key, typename Value>
class LruNode 
{
private:
    Key key_;
    Value value_;
    size_t accessCount_;  // 访问次数
    std::weak_ptr<LruNode<Key, Value>> prev_;  // 改为weak_ptr打破循环引用
    std::shared_ptr<LruNode<Key, Value>> next_;

public:
    LruNode(Key key, Value value)
        : key_(key)
        , value_(value)
        , accessCount_(1) 
    {}

    // 提供必要的访问器
    Key getKey() const { return key_; }
    Value getValue() const { return value_; }
    void setValue(const Value& value) { value_ = value; }
    size_t getAccessCount() const { return accessCount_; }
    void incrementAccessCount() { ++accessCount_; }

    friend class KLruCache<Key, Value>;
};


template<typename Key, typename Value>
class KLruCache : public KICachePolicy<Key, Value>
{
public:
    using LruNodeType = LruNode<Key, Value>;
    using NodePtr = std::shared_ptr<LruNodeType>;
    using NodeMap = std::unordered_map<Key, NodePtr>;

    KLruCache(int capacity)
        : capacity_(capacity)
    {
        initializeList();
    }

    ~KLruCache() override = default;

    // 添加缓存
    void put(Key key, Value value) override
    {
        if (capacity_ <= 0)
            return;
    
        std::lock_guard<std::mutex> lock(mutex_);
        auto it = nodeMap_.find(key);
        if (it != nodeMap_.end())
        {
            // 如果在当前容器中,则更新value,并调用get方法，代表该数据刚被访问
            updateExistingNode(it->second, value);
            return ;
        }

        addNewNode(key, value);
    }

    bool get(Key key, Value& value) override
    {
        std::lock_guard<std::mutex> lock(mutex_);
        auto it = nodeMap_.find(key);
        if (it != nodeMap_.end())
        {
            moveToMostRecent(it->second);
            value = it->second->getValue();
            return true;
        }
        return false;
    }

    Value get(Key key) override
    {
        Value value{};
        // memset(&value, 0, sizeof(value));   // memset 是按字节设置内存的，对于复杂类型（如 string）使用 memset 可能会破坏对象的内部结构
        get(key, value);
        return value;
    }

    // 删除指定元素
    void remove(Key key) 
    {   
        std::lock_guard<std::mutex> lock(mutex_);
        auto it = nodeMap_.find(key);
        if (it != nodeMap_.end())
        {
            removeNode(it->second);
            nodeMap_.erase(it);
        }
    }

private:
    void initializeList()
    {
        // 创建首尾虚拟节点
        dummyHead_ = std::make_shared<LruNodeType>(Key(), Value());
        dummyTail_ = std::make_shared<LruNodeType>(Key(), Value());
        dummyHead_->next_ = dummyTail_;
        dummyTail_->prev_ = dummyHead_;
    }

    void updateExistingNode(NodePtr node, const Value& value) 
    {
        node->setValue(value);
        moveToMostRecent(node);
    }

    void addNewNode(const Key& key, const Value& value) 
    {
       if (nodeMap_.size() >= capacity_) 
       {
           evictLeastRecent();
       }

       NodePtr newNode = std::make_shared<LruNodeType>(key, value);
       insertNode(newNode);
       nodeMap_[key] = newNode;
    }

    // 将该节点移动到最新的位置
    void moveToMostRecent(NodePtr node) 
    {
        removeNode(node);
        insertNode(node);
    }

    void removeNode(NodePtr node) 
    {
        if(!node->prev_.expired() && node->next_) 
        {
            auto prev = node->prev_.lock(); // 使用lock()获取shared_ptr
            prev->next_ = node->next_;
            node->next_->prev_ = prev;
            node->next_ = nullptr; // 清空next_指针，彻底断开节点与链表的连接
        }
    }

    // 从尾部插入结点
    void insertNode(NodePtr node) 
    {
        node->next_ = dummyTail_;
        node->prev_ = dummyTail_->prev_;
        dummyTail_->prev_.lock()->next_ = node; // 使用lock()获取shared_ptr
        dummyTail_->prev_ = node;
    }

    // 驱逐最近最少访问
    void evictLeastRecent() 
    {
        NodePtr leastRecent = dummyHead_->next_;
        removeNode(leastRecent);
        nodeMap_.erase(leastRecent->getKey());
    }

private:
    int           capacity_; // 缓存容量
    NodeMap       nodeMap_; // key -> Node 
    std::mutex    mutex_;
    NodePtr       dummyHead_; // 虚拟头结点
    NodePtr       dummyTail_;
};