【百度】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;
}

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