C++持久化数据结构详解（从零开始掌握函数式编程中的不可变数据结构）

为什么使用持久化数据结构？

• 支持高效的“撤销”操作（如文本编辑器的历史记录）
• 天然线程安全（因为数据不可变）
• 便于调试和测试（状态不会意外改变）
• 节省内存（通过结构共享，新旧版本共用未修改的部分）

用 C++ 实现一个简单的持久化栈

我们以栈（Stack）为例，展示如何用 C++ 构建一个持久化的版本。我们将使用链表结构，并确保每次 push 或 pop 操作都返回一个新栈，而不修改原栈。

#include <iostream>#include <memory>template<typename T>class PersistentStack {private:    struct Node {        T data;        std::shared_ptr<Node> next;        Node(T val, std::shared_ptr<Node> n = nullptr)            : data(val), next(n) {}    };    std::shared_ptr<Node> head;    size_t _size;public:    // 默认构造：空栈    PersistentStack() : head(nullptr), _size(0) {}    // 拷贝构造（浅拷贝即可，因为是不可变的）    PersistentStack(const PersistentStack& other)        : head(other.head), _size(other._size) {}    // Push 操作：返回一个新栈    PersistentStack push(T value) const {        PersistentStack newStack;        newStack.head = std::make_shared<Node>(value, head);        newStack._size = _size + 1;        return newStack;    }    // Pop 操作：返回弹出后的新栈    PersistentStack pop() const {        if (empty()) {            throw std::runtime_error("Stack is empty!");        }        PersistentStack newStack;        newStack.head = head->next;        newStack._size = _size - 1;        return newStack;    }    // 获取栈顶元素    T top() const {        if (empty()) {            throw std::runtime_error("Stack is empty!");        }        return head->data;    }    bool empty() const {        return head == nullptr;    }    size_t size() const {        return _size;    }};// 使用示例int main() {    auto stack1 = PersistentStack<int>();    auto stack2 = stack1.push(10);    auto stack3 = stack2.push(20);    std::cout << "stack3.top(): " << stack3.top() << std::endl; // 输出 20    std::cout << "stack2.top(): " << stack2.top() << std::endl; // 输出 10    std::cout << "stack1.empty(): " << stack1.empty() << std::endl; // 输出 1 (true)    return 0;}

上面的代码展示了如何构建一个C++不可变数据结构。注意以下几点：

• 所有修改操作（如 push 和 pop）都返回一个新对象，原对象不变。
• 使用 std::shared_ptr 实现内存共享，避免不必要的复制。
• 由于数据不可变，多个版本可以安全地共享底层节点。

进阶：持久化数组与更复杂结构

栈只是最简单的例子。更复杂的持久化数据结构包括持久化数组、持久化二叉搜索树（如 可持久化线段树）等。它们通常依赖于路径复制（path copying）或胖节点（fat node）等技术来实现高效更新。

例如，一个高效的持久化数组实现可能使用分层结构（如 Trie 树）来将 O(n) 的复制开销降低到 O(log n)。这在算法竞赛和高性能系统中非常有用。

总结

通过本教程，你已经了解了 C++持久化数据结构 的基本概念、优势以及一个完整的栈实现。虽然 C++ 不是纯函数式语言，但借助智能指针和不可变设计，我们依然可以构建出高效、安全的持久化结构。

记住，关键在于：不修改原数据，只生成新版本，并尽可能复用已有内存。掌握这一思想，你就能在需要版本控制、并发或回溯功能的项目中大显身手！

希望这篇关于 函数式数据结构 的入门教程对你有帮助。动手试试吧，写一个自己的持久化队列或列表！