写在前面

想在现有的技术栈上，提高 C++ 的技能点。

这是新时代的学习方法：AI托举，边做边学。

做题

做题思路

记忆点：双向链表 + 哈希表 = LRU的完美搭档

题解

struct DataNode {
    int key;
    int value;
    DataNode* pre;
    DataNode* next;
    DataNode(int k, int v) : key(k), value(v) {};
};

class LRUCache {
/**
 * Your LRUCache object will be instantiated and called as such:
 */
int size;
int capacity;
map<int, DataNode*> cache;
DataNode* head;
DataNode* tail;

public:
    LRUCache(int _capacity): capacity(_capacity), size(0), head(new DataNode(0, 0)), tail(new DataNode(0, 0)) {
        head->next = tail;
        tail->pre = head;
    }
    
    int get(int key) {
        auto it = cache.find(key);
        if (it == cache.end()) {
            return -1;
        }
        DataNode* node = it->second;
        removeNode(node);
        move2Head(node);
        return node->value;
        
        // 报错
        // if (!cache.count(key)) {
        //     return -1;
        // }
        // // 如果 key 存在，先通过哈希表定位，再移到头部
        // DLinkedNode* node = cache[key];
        // moveToHead(node);
        // return node->value;
    }
    
    void put(int key, int value) {
        auto it = cache.find(key);
        if (it == cache.end()) {
            DataNode* node = new DataNode(key, value);
            cache[key] = node;
            move2Head(node);
            size++;
            if (size > capacity) {
                // 移出
                DataNode* node = tail->pre;
                cache.erase(node->key);
                tail->pre->pre->next = tail;
                tail->pre = tail->pre->pre;
                delete node;
                size--;
            }
        }else{
            it->second->value = value;
            removeNode(it->second);
            move2Head(it->second);
        }
    }
    
    void removeNode(DataNode* node){
        node->pre->next = node->next;
        node->next->pre = node->pre;
    }

    void move2Head(DataNode* node){
        // 放到head
        node->next = head->next;
        node->pre = head;
        head->next->pre = node;
        head->next = node;
    }
};

知识点

1. namespace和分文件的比较

// ✅ namespace 的逻辑清晰性
namespace myapp::network::http {
    class Client {};    // HTTP 客户端
    class Server {};    // HTTP 服务器  
    class Request {};   // HTTP 请求
    class Response {};  // HTTP 响应
}
// 所有相关类逻辑上组织在一起

// ⚠️ 分文件可能导致的分散
// http_client.h  - HTTP 客户端
// http_server.h  - HTTP 服务器  
// http_request.h - HTTP 请求
// http_response.h - HTTP 响应
// 可能分散在不同目录中，需要良好目录结构

// ***************************************************

// 方式A：大命名空间头文件
// utils_monolithic.h
namespace utils {
    class A { /* 大量代码 */ };
    class B { /* 大量代码 */ };
    class C { /* 大量代码 */ };
    // ... 20个类
}

// 方式B：分文件
// utils/a.h, utils/b.h, utils/c.h 等独立文件

// 编译时间对比：
// 方式A: 修改任何类 → 所有用户重新编译
// 方式B: 修改类B → 只有使用B的文件重新编译

2. 第三方库导入

g++编译参数：

• -I参数（Include）：指定头文件搜索路径

# 添加头文件搜索目录
g++ -I/path/to/include main.cpp -o app

# 多个目录
g++ -Iinclude -Ithird_party/include -I/usr/local/include main.cpp -o app

• -L参数（Library path）：指定库文件搜索路径

# 添加库文件搜索目录
g++ -L/path/to/lib main.cpp -o app

# 多个目录
g++ -Llib -L/usr/local/lib -Lthird_party/lib main.cpp -o app

#******************************** 搜索优先级

# 搜索顺序示例
g++ -L/path1 -L/path2 -lmyapp main.cpp -o app

# 库搜索顺序：
# 1. /path1/libmyapp.so 或 /path1/libmyapp.a
# 2. /path2/libmyapp.so 或 /path2/libmyapp.a  
# 3. 系统目录中的 libmyapp.so 或 libmyapp.a

• -l参数（Library）：指定要链接的库

# 链接库（去掉 lib 前缀和 .a/.so 后缀）
g++ -l库名 main.cpp -o app
# 链接多个库
g++ -Llib -lmylib -lnetwork -lssl -lcrypto main.cpp -o app

#******************************** 搜索优先级

# 1. 静态库 vs 动态库优先级
g++ -lmylib  # 优先查找 libmyllib.so，然后是 libmylib.a

# 2. 指定静态库优先
g++ -static -lmylib  # 强制使用静态库 libmylib.a

# 3. 直接指定库文件（避免搜索）
g++ lib/libmylib.a main.cpp -o app  # 直接使用具体文件

最佳目录实践

// 项目结构
myproject/
├── third_party/
│   └── jsonlib/
│       ├── include/
│       │   └── json.h
│       └── src/
│           └── json.cpp
├── lib/
│   ├── linux/
│   │   ├── libjson.a    # 静态库
│   │   └── libjson.so   # 动态库
│   └── include/
│       └── json.h
├── src/
│   └── main.cpp
└── CMakeLists.txt

3. CMake FetchContent包管理

# CMakeLists.txt
cmake_minimum_required(VERSION 3.14)
project(MyProject)

# 启用 FetchContent
include(FetchContent)

# 声明依赖
FetchContent_Declare(
  fmt
  GIT_REPOSITORY https://github.com/fmtlib/fmt.git
  GIT_TAG 9.1.0  # 明确指定版本
)

FetchContent_Declare(
  spdlog
  GIT_REPOSITORY https://github.com/gabime/spdlog.git
  GIT_TAG v1.11.0
)

# 下载并构建依赖
FetchContent_MakeAvailable(fmt spdlog)

# 创建你的目标
add_executable(myapp src/main.cpp)

# 链接依赖
target_link_libraries(myapp PRIVATE fmt::fmt spdlog::spdlog)

4. map的使用

#include <map>
using namespace std;

// 定义
map<key_type, value_type> myMap;

// 插入和修改
myMap[key] = value;

// 遍历
for (auto &p : myMap) {
    std::cout << p.first << " : " << p.second << std::endl;
}

// 检查键是否存在
auto it = myMap.find(key)
if (it != myMap.end()) {
    // 键存在, 使用 it 快捷访问或修改
}
if (map.count(key) > 0) {
    // 知道存在就够了
}
// C++20 最佳选择：清晰且高效
if (map.contains(key)) {
    // 仅检查存在性
}

5. 其他

• class中，默认是 private（不声明时）。
• C++ 不会自动初始化基本类型成员变量，int size; 这里可能会是垃圾值！！！