函数式数据结构：不可变数据与持久化数据结构
好，咱们今天聊点硬核的——函数式数据结构。
你可能听过「不可变数据」这个词。说白了，就是数据一旦创建，就再也不能改了。听起来有点反直觉对吧？我刚开始接触这个概念时也觉得很别扭。一个变量不能改，那还叫变量吗？
但后来我在一个多线程项目里被坑惨了——两个线程同时修改同一个 vector，导致内存越界，查了整整两天。从那以后，我对不可变数据的态度就彻底变了。
什么是不可变数据？
不可变数据，就是只读数据。你不能修改它，只能基于它创建新的副本。
在 C++ 里，最简单的例子就是 const 变量：
const int x = 42;
// x = 43; // 编译错误但真正的不可变数据结构，比这复杂得多。它要求整个对象图都是只读的，包括所有嵌套的子对象。
核心原则： 任何「修改」操作，实际上都是创建一个新的数据结构，同时尽可能复用旧结构中的部分。
持久化数据结构
持久化数据结构，是函数式编程的基石。这里的「持久化」不是指存到硬盘，而是指：
- 数据结构的旧版本始终可用
- 修改操作不会破坏旧版本
- 新旧版本共享大部分内部结构
嗯，你想想看，这跟 Git 的版本管理是不是很像？每次提交都是一个新的快照，但只保存差异部分。
为什么需要持久化？
我举个例子。假设你有一个数组 [1, 2, 3, 4, 5]，你想把第三个元素改成 99。在传统做法里：
std::vector<int> vec = {1, 2, 3, 4, 5};
vec[2] = 99; // 直接修改原数组这样做的问题是：如果你有其他代码正在使用这个数组，它们会看到修改后的值。这在并发环境下就是灾难。
持久化版本的做法是：
// 伪代码，表示概念
auto new_vec = vec.with(2, 99);
// vec 仍然是 [1, 2, 3, 4, 5]
// new_vec 是 [1, 2, 99, 4, 5]两个版本共存，互不干扰。
结构共享：性能的关键
你可能会问：「每次修改都复制整个数组，那性能不是炸了？」
没错，如果真复制整个数组，那确实不行。所以持久化数据结构用了结构共享——新旧版本共享不变的部分。
最常见的实现方式是持久化链表和持久化平衡树。
持久化链表
看这个例子：
// 链表节点
struct Node {
int value;
std::shared_ptr<Node> next;
};
// 创建一个链表: 1 -> 2 -> 3
auto list1 = std::make_shared<Node>(1,
std::make_shared<Node>(2,
std::make_shared<Node>(3, nullptr)));
// 在头部插入 0，得到新链表
auto list2 = std::make_shared<Node>(0, list1);
// list2: 0 -> 1 -> 2 -> 3
// list1: 1 -> 2 -> 3 (完全不变)看到了吗？list2 复用了 list1 的整个尾部。没有复制任何节点，只是新建了一个头节点。
小技巧： 用 std::shared_ptr 管理共享节点，自动处理引用计数和内存释放。我在项目里就是这么干的，省心不少。
持久化数组：更复杂的挑战
链表做头部插入很容易，但随机访问和中间修改就麻烦了。对于数组场景，我们需要更高级的结构。
常用的方案是持久化平衡树（比如持久化红黑树）或持久化 B 树。它们把数组分成多个块，每个块是一棵平衡树。修改时只复制受影响的块和路径上的节点。
复杂度分析：
| 操作 | 传统数组 | 持久化数组 |
|---|---|---|
| 读取 | O(1) | O(log n) |
| 写入 | O(1) | O(log n) |
| 空间开销 | O(n) | O(log n) 每次修改 |
嗯，持久化版本在读写上慢了一些，但换来了不可变性和线程安全。在大多数场景下，log n 的代价完全可以接受。
C++ 中的实践
C++ 标准库没有直接提供持久化数据结构。但我们可以自己实现，或者用第三方库。
我个人习惯用 immer 这个库，它提供了持久化的 vector、map、set 等容器。用法很直观：
#include <immer/vector.hpp>
immer::vector<int> v1 = {1, 2, 3, 4, 5};
auto v2 = v1.set(2, 99); // v2[2] = 99
// v1 仍然是 [1, 2, 3, 4, 5]
// v2 是 [1, 2, 99, 4, 5]
// 遍历
for (auto x : v2) {
std::cout << x << " ";
}如果你不想引入外部库，也可以用 std::shared_ptr 配合不可变接口自己封装。我在一个嵌入式项目里就这么做过——因为不能随便加依赖。
注意： 不要滥用不可变数据。对于频繁修改的热点路径，不可变数据可能带来性能问题。我曾经在一个实时音频处理模块里用了持久化 vector，结果延迟飙升。后来改回可变数组，配合互斥锁，才解决问题。
不可变数据的优势
说了这么多，总结一下不可变数据的好处：
- 线程安全： 没有数据竞争，不需要加锁
- 可回溯： 旧版本数据随时可用，方便调试和撤销
- 引用透明： 函数调用不会产生副作用，更容易推理
- 缓存友好： 相同输入永远返回相同输出，可以安全缓存
我记得有一次，一个同事在调试一个复杂的算法时，被可变状态搞得焦头烂额。我建议他把核心数据结构改成不可变的，结果 bug 瞬间消失。他后来跟我说：「早知道不可变这么好用，我就不用熬那三个通宵了。」
SVG：持久化数据结构核心逻辑
下面这张图展示了持久化链表的结构共享原理：
什么时候用不可变数据？
根据我的经验，以下场景特别适合：
- 多线程环境： 多个线程同时读取数据，不需要加锁
- 撤销/重做功能： 保存每次操作的历史快照
- 函数式编程风格： 配合 lambda 和算法，写出声明式代码
- 配置数据： 加载后不再修改，全局共享
但如果你在做高频交易系统、游戏引擎的渲染循环、或者实时信号处理——这些场景对延迟极度敏感，不可变数据可能不是最佳选择。
我的建议： 从非热点路径开始尝试不可变数据。比如配置管理、日志记录、状态快照。等熟悉了它的思维模式，再逐步推广到核心逻辑。
好了，关于不可变数据和持久化数据结构，今天就聊到这里。记住一句话：不可变不是限制，而是自由——它让你从状态管理的泥潭里解脱出来，专注于数据变换本身。
公众号:蓝海资料掘金营，微信deep3321