【百度】C++开发（25届提前批 一面）面经

1. 代码实现：说说LRU，并代码实现LRU

为什么使用哈希表？（有两个原因）

1. 仅用双向链表的缺陷

如果只使用双向链表来实现 LRU，每次你需要查找某个缓存键值时，必须从链表头部开始遍历，直到找到目标节点。这种操作的时间复杂度是 O(n)，其中 n 是链表的长度，即缓存的大小。如果缓存很大，这种查找操作会变得非常慢。

例如：
假设你缓存了 1000 个键值对，要查找某个键时，你需要遍历 1000 个节点才能找到目标。这种线性查找效率非常低。

2. 引入哈希表的作用

哈希表（unordered_map）用于将键映射到双向链表中的节点，允许我们在 O(1) 的时间内直接找到双向链表中的目标节点。通过哈希表，避免了链表的线性查找。下面是哈希表在 LRU 实现中的几个作用：

1. 快速查找：

通过哈希表，你可以在 O(1) 的时间内直接定位到缓存中某个键对应的双向链表节点。例如，当你调用 get(key) 时，不需要遍历链表来查找，而是直接通过哈希表找到节点。

• 没有哈希表时查找是 O(n)。
• 有了哈希表后，查找是 O(1)。

2. 快速插入与删除：

当缓存中不存在某个键时，使用 put(key, value)，可以通过哈希表快速将新节点插入双向链表，并将其键值存入哈希表；如果缓存满了，也可以通过哈希表在 O(1) 时间内定位到需要删除的节点，并将其从链表和哈希表中移除。

双向链表 + 哈希表的协作过程

举例说明

假设我们有一个容量为 2 的 LRU 缓存，操作过程如下：

1. put(1, 1)：插入键值对 (1, 1)。链表中插入新节点，同时将键 1 映射到该节点。
   - 链表：[1]（1是最新的）
   - 哈希表：{1 -> 节点1}
2. put(2, 2)：插入键值对 (2, 2)。
   - 链表：[2, 1]（2是最新的，1是次新的）
   - 哈希表：{1 -> 节点1, 2 -> 节点2}
3. get(1)：访问键 1。
   - 通过哈希表查找键 1 对应的节点，并将其移到链表头部，表示最近使用。
   - 链表：[1, 2]（1是最新的，2是次新的）
   - 哈希表：{1 -> 节点1, 2 -> 节点2}
4. put(3, 3)：插入键值对 (3, 3)。因为缓存满了，删除最久未使用的键 2。
   - 链表：[3, 1]（3是最新的，1是次新的）
   - 哈希表：{1 -> 节点1, 3 -> 节点3}

如果没有哈希表，在 get(1) 操作时，你需要遍历整个链表来找到键 1。而引入哈希表后，可以在 O(1) 时间内直接定位到键 1 对应的节点，大幅提升查找效率。

代码实现

14、一个线程池应该包含什么？

一个线程池在实现时，通常需要包含以下几个关键组成部分：

线程池的一个简单示例代码：

#include <iostream>
#include <vector>
#include <thread>
#include <queue>
#include <mutex>
#include <condition_variable>
#include <functional>
#include <future>

class ThreadPool {
public:
    ThreadPool(size_t threads);
    ~ThreadPool();
    
    template<class F, class... Args>
    auto enqueue(F&& f, Args&&... args) -> std::future<typename std::result_of<F(Args...)>::type>;
    
private:
    // 工作线程
    std::vector<std::thread> workers;
    // 任务队列
    std::queue<std::function<void()>> tasks;
    
    // 同步
    std::mutex queue_mutex;
    std::condition_variable condition;
    bool stop;
};

// 构造函数，创建线程池
ThreadPool::ThreadPool(size_t threads) : stop(false) {
    for (size_t i = 0; i < threads; ++i) {
        workers.emplace_back([this] {
            for (;;) {
                std::function<void()> task;
                
                {
                    std::unique_lock<std::mutex> lock(this->queue_mutex);
                    this->condition.wait(lock, [this]{ return this->stop || !this->tasks.empty(); });
                    if (this->stop && this->tasks.empty()) return;
                    task = std::move(this->tasks.front());
                    this->tasks.pop();
                }
                
                task();
            }
        });
    }
}

// 添加任务到线程池中
template<class F, class... Args>
auto ThreadPool::enqueue(F&& f, Args&&... args) -> std::future<typename std::result_of<F(Args...)>::type> {
    using return_type = typename std::result_of<F(Args...)>::type;
    
    auto task = std::make_shared<std::packaged_task<return_type()>>(std::bind(std::forward<F>(f), std::forward<Args>(args)...));
    
    std::future<return_type> res = task->get_future();
    {
        std::unique_lock<std::mutex> lock(queue_mutex);
        
        if (stop) {
            throw std::runtime_error("enqueue on stopped ThreadPool");
        }
        
        tasks.emplace([task](){ (*task)(); });
    }
    condition.notify_one();
    return res;
}

// 析构函数，销毁线程池
ThreadPool::~ThreadPool() {
    {
        std::unique_lock<std::mutex> lock(queue_mutex);
        stop = true;
    }
    condition.notify_all();
    for (std::thread &worker : workers) {
        worker.join();
    }
}

int main() {
    ThreadPool pool(4);
    
    auto result1 = pool.enqueue([](int answer) { return answer; }, 42);
    auto result2 = pool.enqueue([](int a, int b) { return a + b; }, 10, 20);
    
    std::cout << "Result 1: " << result1.get() << std::endl;
    std::cout << "Result 2: " << result2.get() << std::endl;
    
    return 0;
}

之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！