LRU缓存-146
/*
定义双向链表节点，用于存储缓存中的每个键值对。
成员变量：key和value存储键值对。preb和next指向前一个和后一个节点，形成双向链表。
构造函数：默认构造函数：初始化空节点。参数化构造函数：初始化带有特定键值的节点。
*/
struct LinksNode{int key,value;LinksNode* prev;LinksNode* next;LinksNode():key(0),value(0),prev(nullptr),next(nullptr){}LinksNode(int _key,int _value):key(_key),value(_value),prev(nullptr),next(nullptr){}
};
class LRUCache {
private:
/*
定义LRUCache类的成员变量和构造函数
成员变量： cache:哈希表，键时缓存的key，值是链表节点的指针，用于快速定位节点。head和tail:伪头部和伪尾部节点，用于简化链表操作。size:当前缓存的大小。capacity:缓存的容量。
*/map<int,LinksNode*> cache;LinksNode* head;LinksNode* tail;int size = 0;int capacity = 0;
public:
/*
构造函数：初始化缓存的容量为 _capacity。创建两个特殊的伪节点head和tail，不存储数据，用于简化链表的插入和删除操作。head->next指向tail，tail->prev指向head，形成一个空的双向链表。
*/LRUCache(int _capacity):capacity(_capacity) {head = new LinksNode();tail = new LinksNode();head->next = tail;tail->prev = head;}
/*
获取指定键的值
如果键不存在，返回-1.
如果键存在：使用哈希表cache快速定位节点。调用moveToHead(node)将节点移动到链表头部，表示最近被访问。返回节点的值。
*/int get(int key) {if(!cache.count(key))return -1;else{LinksNode* node = cache[key];moveToHead(node); return node->value; }}
/*
插入新的键值对或更新已有键值对。
1.键不存在：创建一个新节点并插入到链表头部。添加到哈希表。如果超出容量：调用removeTail()删除最久未使用的节点。从哈希表中移除相应的键值对。
2.键已存在更新对应节点的值。调用moveToHead()将节点移动到链表头部
*/void put(int key, int value) {if(!cache.count(key)){LinksNode* node = new LinksNode(key,value);addToHead(node);cache[key] = node;++size;if(size>capacity){LinksNode* re = removeTail();//返回链表尾部被删除的键cache.erase(re->key);delete re;--size;}}else{LinksNode* node = cache[key];node->value = value;moveToHead(node);}}
/*
将一个节点插入到链表的头部设置新节点的 prev 为 head，next 为 head->next。更新原先头部节点的 prev 为新节点。更新 head->next 为新节点。
*/void addToHead(LinksNode* node){node->prev = head;node->next = head->next;head->next->prev = node;head->next = node;}
/*
从链表中删除指定节点：更新节点前后连接：node->prev->next = node->next和node->next->prev = node->prev。节点 node 与链表完全断开。
*/void removeNode(LinksNode* node){node->prev->next = node->next;node->next->prev = node->prev;}
/*
将指定节点移动到链表头部：调用 removeNode(node) 将节点从原位置移除。调用 addToHead(node) 将节点插入到链表头部。
*/void moveToHead(LinksNode* node){removeNode(node);addToHead(node);}
/*
删除链表的尾部节点（最久未使用的节点）并返回：找到伪尾部节点之前的节点：tail->prev。调用 removeNode(node) 将其从链表中移除。返回该节点，供 put 函数释放资源。
*/LinksNode* removeTail(){LinksNode* node = tail->prev;removeNode(node);return node;}
};每日问题
什么是 C++ 中的智能指针？有哪些类型的智能指针？
C++中的智能指针是一种用于管理动态内存的工具，它封装了裸指针（raw pointer），并通过 RAII（资源获取即初始化）的方式自动管理资源的生命周期，从而避免了内存泄漏和悬空指针问题。
智能指针在头文件 中定义，常见的智能指针有三种：std::unique_ptr、std::shared_ptr 和 std::weak_ptr。
智能指针的特点
1.自动管理资源：
2.避免内存泄漏：无需手动调用 delete，减少资源管理的复杂度和错误风险。
3.指针行为：智能指针提供类似裸指针的操作（如 * 和 ->），使用方便。
智能指针的类型
1. std::unique_ptr
特点：
独占所有权，不能共享。
一个资源只能被一个 std::unique_ptr 管理。
不可复制，但可以通过 std::move 转移所有权。
适用场景：
确保某个资源只需一个所有者。
管理动态分配的内存，避免手动释放。
代码示例
#include <memory>
#include <iostream>int main() {std::unique_ptr<int> ptr = std::make_unique<int>(42); // 创建并管理资源std::cout << *ptr << std::endl;// std::unique_ptr<int> ptr2 = ptr; // 错误：不可复制std::unique_ptr<int> ptr2 = std::move(ptr); // 转移所有权if (!ptr) std::cout << "ptr is now null." << std::endl;
}
2. std::shared_ptr
特点：
支持共享所有权。
多个 std::shared_ptr 可以共享一个资源，内部使用引用计数管理资源。
当引用计数变为 0 时，资源被释放。
适用场景：
需要多个对象共享同一个资源。
不明确资源的生命周期，但确保资源在最后一个使用者销毁时释放。
代码示例：
#include <memory>
#include <iostream>int main() {std::shared_ptr<int> ptr1 = std::make_shared<int>(42); // 创建并共享资源std::shared_ptr<int> ptr2 = ptr1; // 共享所有权std::cout << "Value: " << *ptr1 << ", Ref count: " << ptr1.use_count() << std::endl;
}
3. std::weak_ptr
特点：
弱引用，不影响资源的引用计数。
依赖于 std::shared_ptr，通常用于解决循环引用问题。
需要通过 lock() 方法将 std::weak_ptr 转换为 std::shared_ptr 访问资源。
适用场景：
配合 std::shared_ptr 使用，避免循环引用。
希望访问资源但不影响资源的生命周期。
代码示例：
#include <memory>
#include <iostream>int main() {std::shared_ptr<int> sp = std::make_shared<int>(42);std::weak_ptr<int> wp = sp; // 弱引用，不增加引用计数std::cout << "Shared count: " << sp.use_count() << std::endl;if (auto locked = wp.lock()) { // 转换为 std::shared_ptrstd::cout << "Value: " << *locked << std::endl;} else {std::cout << "Resource is expired." << std::endl;}
}
智能指针的注意事项
不要混用裸指针和智能指针：
避免循环引用：使用 std::weak_ptr 打破 std::shared_ptr 的循环引用。
性能问题：std::shared_ptr 和 std::weak_ptr 引入了额外的引用计数开销，使用时需注意性能影响。
移动语义和拷贝语义有什么区别？
拷贝语义
在 C++ 中，移动语义和拷贝语义是处理对象所有权和资源管理的两种机制。它们的核心区别在于资源的分配方式和所有权转移是否发生。以下是它们的详细对比：
拷贝语义：
1.定义
拷贝语义通过复制对象的数据来创建一个新的对象。拷贝后的两个对象互不影响，拥有各自的资源。
2.实现方式
调用拷贝构造函数T(const T&)。
调用拷贝赋值运算符T& operator=(const T&)。
3.资源处理
资源完全被复制（例如深拷贝）。
每个对象独立管理自己的资源。
拷贝语义不会修改原对象的状态。
4.适用场景
对象的数据需要完整保留。
对象的数据较小，或者深拷贝的成本较低。
5.示例
class MyClass {
private:int* data;public:MyClass(int value) : data(new int(value)) {}// 拷贝构造函数（深拷贝）MyClass(const MyClass& other) : data(new int(*other.data)) {}// 拷贝赋值运算符（深拷贝）MyClass& operator=(const MyClass& other) {if (this == &other) return *this;delete data; // 释放原有资源data = new int(*other.data); // 复制新资源return *this;}~MyClass() { delete data; }
};
移动语义
1.定义
移动语义通过转移对象的资源来创建一个新对象，而不是复制数据。转移后，原对象的状态变为不可用或空。
2.实现方式
调用移动构造函数T(T&&)。
调用移动赋值运算符T& operator=(T&&)。
3.资源处理
资源被转移到新对象（例如指针的所有权转移）。
避免了资源的深拷贝，提高了性能。
转移后，原对象被置为安全状态（如 nullptr）。
4.适用场景
对象的数据较大，深拷贝成本高。
对象的资源需要高效管理（如动态内存、文件句柄等）。
5.示例
class MyClass {
private:int* data;public:MyClass(int value) : data(new int(value)) {}// 移动构造函数MyClass(MyClass&& other) noexcept : data(other.data) {other.data = nullptr; // 转移后，清空原对象的数据指针}// 移动赋值运算符MyClass& operator=(MyClass&& other) noexcept {if (this == &other) return *this;delete data; // 释放原有资源data = other.data; // 转移资源other.data = nullptr; // 清空原对象的数据指针return *this;}~MyClass() { delete data; }
};
典型应用场景
1.拷贝语义：
必须要保留多个对象副本时。
数据较小，深拷贝开销可以忽略。
2.移动语义：
临时对象的资源管理（如 std::move）。
对象资源较大，深拷贝开销不可忽略（如容器 std::vector、std::string）。