力扣 LRU缓存-146

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; }
};