C++
手写 ARC 缓存
实现 T1/T2/B1/B2 四队列与自适应参数 p，让缓存在线平衡近期性和频率。
发布于 2026年7月23日
手写 ARC 缓存
实现 T1/T2/B1/B2 四队列与自适应参数 p，让缓存在线平衡近期性和频率。
本系列代码使用 C++20 和
oc::handmade命名空间，目标是解释实现机制、复杂度和工程边界，不是替代标准库。普通容器与缓存核心不内置互斥锁；这不代表 lock-free。
一、学习目标
- 理解四队列职责
- 实现幽灵命中驱动的自适应
- 保持总容量边界
二、前置条件
完成 2Q 缓存，熟悉 LRU 链表和幽灵记录。
Linux/macOS：
cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build -j
ctest --test-dir build --output-on-failure
Windows PowerShell：
cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build --config Debug
ctest --test-dir build -C Debug --output-on-failure
三、问题与设计选择
T1 保存一次近期访问，T2 保存重复访问；B1/B2 分别记住两者淘汰的键。B1 命中增大 p 偏向近期，B2 命中减小 p 偏向频率。
这里刻意保留一条边界：教学实现覆盖构造、复制移动、核心修改、查找和迭代契约，但不复刻标准库全部重载、ABI、constexpr、异构查找或节点句柄。
四、内存布局与核心不变量
|T1|+|T2| <= c，四队列键互斥，0<=p<=c，幽灵总量受 2c 限制。
每个修改操作都按“准备资源 → 构造新状态 → 提交连接或指针 → 清理旧状态”的顺序设计。提交点之前发生异常，应保持原对象可继续使用；无法提供强保证时，会在接口说明中明确基本保证。
五、核心实现
void adapt_on_ghost_hit(bool in_b1) {
if (in_b1) {
const auto delta = std::max<std::size_t>(
1, b2_.size() / std::max<std::size_t>(1, b1_.size()));
p_ = std::min(capacity_, p_ + delta);
} else {
const auto delta = std::max<std::size_t>(
1, b1_.size() / std::max<std::size_t>(1, b2_.size()));
p_ = delta > p_ ? 0 : p_ - delta;
}
}
上面先聚焦最容易写错的核心步骤；若本篇对应一个独立组件，下一节给出统一工程中的完整教学实现。代码没有放入 std 命名空间，避免未定义行为和名称冲突。
六、完整教学实现
下面是统一工程中经过 GCC、Clang、GoogleTest 和 Sanitizer 验证的完整组件。它依赖前序文章已经实现的公共类型以及头文件中的标准库 #include。
namespace oc::handmade {
template<class Key, class Value, class Hash = std::hash<Key>>
class arc_cache {
using item = std::pair<Key, Value>;
using item_list = std::list<item>;
std::size_t capacity_;
std::size_t target_recent_{};
item_list t1_;
item_list t2_;
std::list<Key> b1_;
std::list<Key> b2_;
std::unordered_map<Key, typename item_list::iterator, Hash> t1_index_;
std::unordered_map<Key, typename item_list::iterator, Hash> t2_index_;
std::unordered_map<Key, typename std::list<Key>::iterator, Hash> b1_index_;
std::unordered_map<Key, typename std::list<Key>::iterator, Hash> b2_index_;
void trim_ghosts() {
while (b1_.size() + b2_.size() > capacity_) {
if (b1_.size() > target_recent_) {
b1_index_.erase(b1_.back());
b1_.pop_back();
} else {
b2_index_.erase(b2_.back());
b2_.pop_back();
}
}
}
void replace(bool incoming_from_b2) {
if (!t1_.empty() &&
(t1_.size() > target_recent_ ||
(incoming_from_b2 && t1_.size() == target_recent_))) {
Key key = t1_.back().first;
t1_index_.erase(key);
t1_.pop_back();
b1_.push_front(key);
b1_index_[key] = b1_.begin();
} else if (!t2_.empty()) {
Key key = t2_.back().first;
t2_index_.erase(key);
t2_.pop_back();
b2_.push_front(key);
b2_index_[key] = b2_.begin();
}
trim_ghosts();
}
public:
explicit arc_cache(std::size_t capacity) : capacity_(capacity) {}
std::size_t size() const noexcept { return t1_.size() + t2_.size(); }
std::size_t capacity() const noexcept { return capacity_; }
std::size_t target_recent() const noexcept { return target_recent_; }
bool contains(const Key& key) const {
return t1_index_.contains(key) || t2_index_.contains(key);
}
std::optional<Value> get(const Key& key) {
if (auto hot = t2_index_.find(key); hot != t2_index_.end()) {
t2_.splice(t2_.begin(), t2_, hot->second);
return hot->second->second;
}
if (auto recent = t1_index_.find(key); recent != t1_index_.end()) {
Value value = std::move(recent->second->second);
Key stored_key = recent->second->first;
t1_.erase(recent->second);
t1_index_.erase(recent);
t2_.push_front({stored_key, std::move(value)});
t2_index_[stored_key] = t2_.begin();
return t2_.front().second;
}
return std::nullopt;
}
bool erase(const Key& key) {
if (auto recent = t1_index_.find(key); recent != t1_index_.end()) {
t1_.erase(recent->second);
t1_index_.erase(recent);
return true;
}
if (auto hot = t2_index_.find(key); hot != t2_index_.end()) {
t2_.erase(hot->second);
t2_index_.erase(hot);
return true;
}
return false;
}
void put(Key key, Value value) {
if (capacity_ == 0) return;
if (contains(key)) {
erase(key);
t2_.push_front({std::move(key), std::move(value)});
t2_index_[t2_.front().first] = t2_.begin();
return;
}
if (auto ghost = b1_index_.find(key); ghost != b1_index_.end()) {
const auto delta = std::max<std::size_t>(
1, b2_.size() / std::max<std::size_t>(1, b1_.size()));
target_recent_ = std::min(capacity_, target_recent_ + delta);
replace(false);
b1_.erase(ghost->second);
b1_index_.erase(ghost);
t2_.push_front({std::move(key), std::move(value)});
t2_index_[t2_.front().first] = t2_.begin();
return;
}
if (auto ghost = b2_index_.find(key); ghost != b2_index_.end()) {
const auto delta = std::max<std::size_t>(
1, b1_.size() / std::max<std::size_t>(1, b2_.size()));
target_recent_ = delta > target_recent_ ? 0 : target_recent_ - delta;
replace(true);
b2_.erase(ghost->second);
b2_index_.erase(ghost);
t2_.push_front({std::move(key), std::move(value)});
t2_index_[t2_.front().first] = t2_.begin();
return;
}
if (size() >= capacity_) replace(false);
t1_.push_front({std::move(key), std::move(value)});
t1_index_[t1_.front().first] = t1_.begin();
}
};
} // namespace oc::handmade
生产级标准库还要处理完整 allocator 传播、全部重载、ABI、调试迭代器和平台特化；这里保留的是能够独立推导核心数据结构的教学边界。
七、使用示例与输出
预期输出或状态：
连续 B1 幽灵命中使 p 增大；连续 B2 命中使 p 减小，实际缓存容量始终不超过 c。
示例必须在文章对应的测试目标中实际编译。涉及顺序的输出只依赖接口明确承诺的顺序；无序容器不会把某次桶顺序写成稳定结果。
八、复杂度与失效规则
| 操作 | 复杂度 | 说明 |
|---|---|---|
| 命中 T1/T2 | 平均 O(1) | 移动至 T2 头 |
| 命中 B1/B2 | 平均 O(1) | 调整 p 并替换 |
| 首次访问 | 平均 O(1) | 进入 T1 |
| replace | O(1) | T1 或 T2 尾转幽灵 |
复杂度中的 O(1) 若标记为“平均”或“摊还”，不能在面试中省略限定词。任何重新分配、节点删除、rehash 或缓存淘汰都必须单独说明迭代器、引用与指针是否失效。
九、异常安全与资源管理
- 获取资源后立即交给 RAII 对象或明确记录已构造数量。
- 用户类型构造、复制、移动、比较器和哈希器都可能抛异常。
- 只有在所有后续步骤不会失败时才修改不可回滚的链接。
- 析构、释放和关闭路径不得抛异常。
- 并发包装通过回调在锁内访问，避免返回保护对象的裸引用。
十、常见错误
1. 四个索引更新不原子导致重复键
四个索引更新不原子导致重复键会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。
2. p 使用无符号数减法下溢
p 使用无符号数减法下溢会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。
3. 把幽灵队列计入实际值容量
把幽灵队列计入实际值容量会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。
十一、面试追问
- ARC 如何同时学习近期性和频率？
- p 的变化方向为什么这样定义？
- ARC 的专利历史对工程选型有什么提醒？
回答时先说数据结构不变量，再给复杂度，最后说明异常、迭代器或并发边界，通常比背诵结论更有说服力。
十二、练习与自测
- 实现 replace 规则
- 添加 invariant checker
- 构造让 p 来回变化的访问轨迹
自测标准：能够不看代码画出内存或节点关系，解释一次成功操作和一次失败回滚，并写出至少一个会击穿错误实现的测试。
十三、官方资料与延伸阅读
上一篇：手写 2Q 缓存 ｜ 下一篇：手写 Window TinyLFU 缓存