组合模式大概是C里最容易被低估的一个经典设计模式。教科书上三张图讲完Component、Leaf、Composite看起来谁都能写可真把一棵树塞进业务代码之后需求一多马上就知道“一个抽象基类加虚函数”这条路有多窄。给控件树加个渲染接口还容易后面再接“命中测试”“无障碍信息导出”“序列化存档”时整套类层次就得从上到下翻一遍叶子节点的空实现越来越滑稽。这篇要聊的正是组合模式在C里的几种实用变体访问者注入、std::variant强类型组合树、编译期静态树以及面向缓存与序列化的扁平化树。它们不互相取代而是分别解决不同层面的问题。适合已经写过基础树结构、正在为“加功能要动整片类”头疼的开发者参考。1. 组合模式的经典结构与为什么需要变体1.1 教科书组合模式的C形态先复习一下经典写法因为后面所有变体都要跟它对照。#include iostream #include memory #include vector class Component { public: virtual ~Component() default; virtual void render() const 0; virtual void add(std::unique_ptrComponent child) { (void)child; // 叶子节点用不上 } virtual const std::vectorstd::unique_ptrComponent children() const { static const std::vectorstd::unique_ptrComponent empty; return empty; } }; class Leaf : public Component { public: void render() const override { std::cout leaf\n; } }; class Composite : public Component { public: void render() const override { std::cout composite\n; for (const auto child : children_) { child-render(); } } void add(std::unique_ptrComponent child) override { children_.push_back(std::move(child)); } const std::vectorstd::unique_ptrComponent children() const override { return children_; } private: std::vectorstd::unique_ptrComponent children_; };这段代码本身没什么问题。组合模式的核心诉求是“让客户端统一对待叶子节点和组合节点”所以Component把所有可能用到的接口都摆在外面叶子节点用空实现占位组合节点用真实的容器实现。一处调用处处递归最终整棵树被遍历完。1.2 压在经典实现头上的几座山这套写法应付一个操作时很舒服操作一多就开始变形。第一个问题是操作爆炸。渲染、序列化、命中测试、字节数统计、事件分发每加一个操作都意味着在Component上加一个虚函数然后每一个继承者都补一份实现。哪怕某个叶子节点根本不可能参与“命中测试”你也得给它一个空函数。一个树形结构维护着五六个“与本节点无关”的空实现接口被撑得越来越脏。第二个问题是类型分支。组合模式宣称外部可以把Leaf和Composite混为一谈但实际业务里这两者天然不同叶子需要计算纹理尺寸组合节点需要录入子节点数量。客户端拿到一个Component时经常被逼着做dynamic_cast去区分实际类型。一旦代码里铺满了dynamic_cast这个模式的核心价值就开始打折。第三个问题是遍历逻辑和业务逻辑耦合。遍历顺序先父后子、先子后父、带剪枝的深度优先被固化在render()这类函数内部。换一种遍历策略你得再写一个函数里面又是一遍递归循环。树结构的表示和树上的操作被焊死在一起改动任何一方都要连累另一方。这三个痛点就是组合模式需要“变体”的根本原因。下面的几种变体本质上都是在调整“树结构本身”和“树上的操作”之间的解耦方式。2. 变体一访问者注入把操作从树结构里拆出去2.1 用双分派把“操作”反转到独立类里访问者模式的思路很简单不是让每个节点自己实现render()而是把“操作”本身抽成一个独立的类让节点把自身“交给”操作类去处理。C里常见的实现是这样的class NodeVisitor { public: virtual ~NodeVisitor() default; virtual void visit(Leaf node) 0; virtual void visit(Composite node) 0; }; class Node { public: virtual ~Node() default; virtual void accept(NodeVisitor visitor) 0; }; class Leaf : public Node { public: void accept(NodeVisitor visitor) override { visitor.visit(*this); } }; class Composite : public Node { public: void add(std::unique_ptrNode child) { children_.push_back(std::move(child)); } void accept(NodeVisitor visitor) override { visitor.visit(*this); for (auto child : children_) { child-accept(visitor); } } private: std::vectorstd::unique_ptrNode children_; };这样要加“序列化”操作时不用再动Component和所有子类只要新写一个SerializeVisitorclass SerializeVisitor : public NodeVisitor { public: void visit(Leaf node) override { // 输出叶子内容 } void visit(Composite node) override { // 输出组合节点内容 } };调用侧也很简单root-accept(serializeVisitor)。以后再加PDF导出、加统计、加无障碍文本全都是新增文件原有的树结构一行不改。这个变体把“操作”从“结构”里彻底拆了出去是经典组合模式最直接的进化方向。2.2 遍历顺序的控制权该给谁上面那版Composite::accept里遍历顺序被写死了先visit(*this)再递归子节点。如果访客想先遍历子节点、后处理自己它做不到。想在某个分支上剪枝它也没法插手。我的做法是把accept只保留“把自己分派出去”的功能真正的遍历逻辑收到Visitor内部。可以先提供一个统一的辅助接口void walk(Node node, NodeVisitor visitor) { node.accept(visitor); if (auto* composite dynamic_castComposite*(node)) { for (auto child : composite-children()) { walk(*child, visitor); } } }或者更干脆一点让每个Visitor自己决定是否需要遍历。RenderVisitor里可以这样写void visit(Composite node) override { // 渲染自己 // 然后自己控制是否递归 for (auto child : node.children()) { child-accept(*this); } }前一种方案胜在“约定统一”但灵活性受限后一种方案灵活却要求每个Visitor自己维护递归写多了会发现都是一样的循环。实际项目里我更喜欢折中在Visitor基类里提供一个受保护的walk(Node)帮助函数子类想用就自己调不想用就自写遍历逻辑。这样大部分操作类都能保持精简个别行为特殊的操作也有发挥空间。2.3 Visitor变体的隐藏成本Visitor几乎解决了“操作增加”的问题但它不是免费的。最大的代价是双分派。accept是一次分派visit里的重载又是一次分派深度递归时多一层函数调用甚至比普通虚函数还重一点。对性能极其敏感、树深度又高的场景要慎重。其次是新增节点类型的成本反转了。经典继承树新增一个节点类型只需写一个新子类Visitor树新增一个节点类型所有Visitor都要加一个visit重载。如果产品迭代方向是“不断有新型节点进来”Visitor会让你越改越烦。还有一个容易忽略的细节NodeVisitor::visit接收的是非const引用。想遍历一棵const树时你需要再做一套const重载或者干脆在每个Visitor里写两个版本。代码量会翻倍这是这套方案在设计之初就要预估到的。所以我自己的判断是Visitor变体适合“节点类型相对稳定、操作频繁新增”的业务比如引擎层的场景导出、工具链里的代码生成都不错。但如果你手头是一个“节点类型三天两头加新类”的编辑器Visitor会变成新的负担。3. 变体二std::variant强类型组合树3.1 递归variant类型怎么构造Visitor变体解决了一部分问题但经典继承的一些老毛病还在动态类型转换、堆上散落的节点、指针的裸野不确定性。C17以后std::variant给了另一种视野组合树的节点根本不需要继承体系直接用类型集合表达就行。难点在于递归。std::variantLeaf, Composite里Composite内部又要持有子节点子节点又是Leaf或Composite这就构成递归类型。标准库的std::variant要求所有类型完整不能直接自引用。常规解法是用一层unique_ptr做递归跳板struct Node; using NodePtr std::unique_ptrNode; struct Leaf { double size 0.0; }; struct Composite { std::vectorNodePtr children; }; struct Node : std::variantLeaf, Composite { using variant::variant; };Node继承std::variantLeaf, Composite之后可以直接写Node node{Leaf{3.14}}也可以写Node node{Composite{}}。因为Composite里只有std::vectorNodePtr而NodePtr是不完整类型Node的unique_ptr这种前向声明加智能指针的组合是合法的。unique_ptr允许指向不完整类型是标准库特意留下的口子这里的顺序必须先声明struct Node再用别名定义NodePtr最后再定义Leaf和Composite编译才能通过。3.2 std::visit overloaded遍历整棵树有了variant树最优雅的遍历方式是std::visit。配合C17的overloaded技巧代码可以写得非常集中templateclass... Ts struct overloaded : Ts... { using Ts::operator()...; }; templateclass... Ts overloaded(Ts...) - overloadedTs...; double totalSize(const Node node) { return std::visit(overloaded{ [](const Leaf leaf) { return leaf.size; }, [](const Composite composite) { double total 0.0; for (const auto child : composite.children) { total totalSize(*child); } return total; } }, node); }overloaded的本质是多个lambda的聚合体它继承所有lambda的operator()再用推导指引把多个lambda打包成一个访问器。std::visit拿到Node的实际类型后会选中匹配的lambda执行。每个访问分支在编译期就写死了不需要dynamic_cast也不需要任何运行时类型标记。这种写法的好处是类型安全到骨头里。如果我写漏了Leaf或Composite分支编译器直接报错绝不留给运行时一个神秘崩溃。另外因为我用的是匿名lambda编译器有很大概率把它内联进std::visit的分派逻辑里相比虚函数间接调用局部性更好。要说麻烦也有。节点创建时的类型操作不够直观Node root{Composite{}}; std::getComposite(root).children.push_back( std::make_uniqueNode(Leaf{3.14}));std::getComposite这串写法略长不过封装几个辅助函数就能解决。还有如果日后新增一种节点类型std::visit里所有操作类的lambda都要跟着加一个分支这和Visitor是一样的问题——节点类型稳定时才舒服。3.3 variant树的性能和“伪值语义”要分清很多人听说variant树第一反应是“值语义”。这里得泼一盆冷水variant确实按值内嵌存储Leaf或Composite本身不再有基类指针那一层间接但这棵树的子树是用unique_ptr链接的所以整棵树默认不可拷贝unique_ptr不允许复制。也就是说这台“值语义”只体现在单节点的内存布局上不代表你可以随意按值拷贝一棵树。如果你想深拷贝一棵variant树还是要手动写递归cloneNode cloneNode(const Node src) { return std::visit(overloaded{ [](const Leaf leaf) - Node { return Leaf{leaf}; }, [](const Composite composite) - Node { Composite copy; copy.children.reserve(composite.children.size()); for (const auto child : composite.children) { copy.children.push_back( std::make_uniqueNode(cloneNode(*child))); } return copy; } }, src); }反过来移动这棵树倒是很轻量因为vector和unique_ptr的移动都是常数时间。性能方面std::visit在编译器实现里通常是一张类型索引到函数指针的表和虚函数表的机制类似但它少了对象本身的vptr解引用分支跳转也更规整。我手头一个十万节点的模拟树做过粗略基准variant版本比虚函数版本快了大概一成但这类数据容易受编译器、访问模式影响只能当参考。真正适合variant树的场景是节点类型集合明确且不会频繁扩展、操作逻辑希望集中维护、希望避免继承体系的凌乱。配合第5章的索引化存储它可以成为一套非常现代的组合树实现。4. 变体三编译期组合树把“部分-整体”写进类型4.1 什么场景值得上编译期组合前两个变体都是运行期方案树的结构直到程序运行时才能完全确定节点之间靠指针或索引关联。但有些场景里整棵树的形状在编译期就完全清楚了比如一个固定公式的表达式树、一个静态的混合树配置、一个永不变动的菜单结构。这时候再把树塞进运行期虚函数或variant里等于白白付出一堆动态分派的钱。编译期组合树的思路是让树的结构直接映射成C类型。组合节点是一个模板子节点类型被写进模板参数里叶子节点是一个普通类型。遍历时不再依赖运行期类型判断所有“该走哪个分支”在编译期就定死了。4.2 用tuple和模板搭一棵静态树先看叶子templatetypename T class Constant { public: explicit Constant(T value) : value_(value) {} T evaluate() const { return value_; } private: T value_; };再看内部节点。一个内部节点持有若干子节点子节点类型各不相同所以放在std::tuple里templatetypename Op, typename... Children class StaticNode { public: explicit StaticNode(Children... children) : children_(std::forwardChildren(children)...) {} double evaluate() const { return std::apply([](const auto... child) { return Op{}(child.evaluate()...); }, children_); } private: std::tupleChildren... children_; };std::apply把tuple里的每个元素解开按顺序传给lambdalambda里再逐个调用evaluate()。因为所有子节点的类型在模板参数里已经确定这里没有任何运行期分支理论上可以被完全内联展开。工厂函数让类型推导简单一点templatetypename Op, typename... Children auto makeStaticNode(Children... children) { return StaticNodeOp, std::decay_tChildren...{ std::forwardChildren(children)... }; }用法struct SumOp { double operator()(double a, double b) const { return a b; } }; Constantdouble a(2.0), b(3.0), c(4.0); auto inner makeStaticNodeSumOp(b, c); auto tree makeStaticNodeSumOp(a, inner); double result tree.evaluate(); // 2 (3 4) 9注意inner本身就是一棵小树再作为子节点塞进tree之后组成了两层的静态树。类型层面这棵树是明确的StaticNodeSumOp, Constantdouble, StaticNodeSumOp, Constantdouble, Constantdouble。想再继续嵌套类型会继续膨胀但编译器完全hold住。4.3 编译期组合的边界与代价编译期组合树最大的优势是零运行期开销。它把组合模式从“对象结构”提升到了“类型结构”在编译期完成所有的子节点分发。如果你在做一个对性能敏感、且树结构静态固定的模块这一招很值。但代价也要说清楚。第一编译期组合树无法处理“运行时才确定形状”的数据结构。用户从配置里拖一棵树出来或者从XML读一批节点这条路直接废掉。第二模板类型本身极长报错信息会把人绕晕工程上一个通用节点的类型常常膨胀到难以读写的长度。第三相同形状的两棵静态树是同一个类型但形状略不同的两棵树就是完全不同的类型想把它们装进同一个容器、做统一遍历反而需要额外的类型擦除层。我的结论是编译期组合树适合做“核心计算路径”比如表达式模板、数学公式树、静态模板化场景树的一部分。它不适合作为通用的“用户数据容器”更不要指望在业务层整天构建这种树。工程上更常见的形态是静态模板树作为内部的性能热点外层再包一层variant或普通节点兼顾灵活性和速度这一点在第6章混合架构里会再提到。5. 变体四扁平化组合树用连续内存表达层级5.1 用数组装下整棵树的思路组合模式天然让人想到指针和堆分配每个节点new出来父子之间用指针关联。问题是几十万节点的树一旦构建起来节点在堆上东一块西一块遍历时的缓存命中率惨不忍睹。而且指针方案还要考虑所有权谁释放、会不会悬垂、会不会循环。工程里很多“树崩了”的问题本质上不是业务错了而是指针生命周期错了。扁平化组合树换了一个视角所有节点放进同一个std::vector节点之间不存指针存索引。指针变成了数组下标所有权问题从源头消失整个树还天然具备极好的序列化和缓存特性。5.2 first-child / next-sibling 表示法的实现要点扁平树常见的表示法是“首子节点 下一个兄弟节点”也就是常说的左孩子右兄弟表示法。每个节点只保存三个关联下标static constexpr uint32_t kNoIndex ~0u; struct Node { double value 0.0; uint32_t parent kNoIndex; uint32_t firstChild kNoIndex; uint32_t nextSibling kNoIndex; }; class FlatTree { public: uint32_t addChild(uint32_t parentIndex) { uint32_t index static_castuint32_t(nodes_.size()); nodes_.push_back(Node{}); nodes_[index].parent parentIndex; if (nodes_[parentIndex].firstChild kNoIndex) { nodes_[parentIndex].firstChild index; } else { uint32_t last nodes_[parentIndex].firstChild; while (nodes_[last].nextSibling ! kNoIndex) { last nodes_[last].nextSibling; } nodes_[last].nextSibling index; } return index; } const std::vectorNode nodes() const { return nodes_; } private: std::vectorNode nodes_; };往父节点挂子节点时如果父节点还没有孩子就挂在firstChild上已经有孩子就沿着nextSibling链找到最后一个再挂上去。遍历时也是顺着这条链走templatetypename F void traverse(const FlatTree tree, uint32_t index, F func) { func(tree.nodes()[index]); uint32_t child tree.nodes()[index].firstChild; while (child ! kNoIndex) { traverse(tree, child, func); child tree.nodes()[child].nextSibling; } }这个方案的优秀之处在于整个树就是一段连续内存。遍历时CPU缓存能把相邻节点一起带上速度快很多。序列化也简单到极致把std::vectorNode原样写文件加载时再原样读回来只要Node保持POD连字段对齐都不用担心索引天然有效。这就是索引相比指针最大的红利。5.3 扁平树的取舍与优化一定要提的取舍是“删除节点”变得麻烦。数组中间删掉一个元素后面所有索引都会移动原来记录的下标全部失效。工程上有两种应对一是用空闲索引回收机制删除时只标记为空不实际搬移数组后续复用二是干脆不提供单节点删除只提供整棵子树清理。很多游戏引擎的场景管理就是这么干的。另一个可以优化的是“插入子节点”的复杂度。上面的addChild每次都要沿着兄弟链走到尾部最坏O(子节点数量)。如果想高频挂载子节点可以在节点里加一个lastChild字段把尾部索引存起来挂接变成O(1)。我自己的经验是扁平树特别适合节点数量巨大、以构建和遍历为主、删除不频繁的场景。比如UI控件树、资源依赖图、静态配置层级。如果一棵树需要高频随机增删节点、树结构本身成为业务的操作核心那这种表示法会带来额外的心智负担不如回归unique_ptr树。6. 四个变体的横向对比与选型清单6.1 一张表看清四种写法的性格不同变体之间往往不是“谁更好”而是“在什么条件下谁更合适”。把它们放在一起看会更直观变体加操作加节点类型性能特征最适合的场景经典继承树改基类加所有子类新增一个子类即可vtable间接调用节点类型常变、操作稳定Visitor注入新增一个Visitor类所有Visitor都要加重载双分派多一次跳转操作常变、节点类型稳定std::variant树每个visit里加一个分支所有visit都要加分支编译期分派局部性好节点类型稳定、强调类型安全编译期静态树新增模板或运算操作新增模板类型零运行期分派树结构编译期已知、性能敏感扁平化树遍历方向由函数实现决定结构体加字段缓存友好、序列化友好节点数量巨大、构建与遍历为主后面四行其实是前四行的补充Visitor和variant都把“操作”从“结构”里挤了出去编译期静态树把“结构”也升到编译期扁平化树则从内存布局角度补上了前几个方案都不太在乎的缓存与序列化问题。6.2 真正实用的混合架构variant 访客 索引实际工程里最打动我的不是单一种变体而是它们之间的组合。一个树模块可以同时拥有variant的类型安全和扁平数组的数据布局再暴露一层类似Visitor的对外接口业务层完全无感知。举个例子某个编辑器场景树节点类型只有变换、网格、灯光三种相对稳定。树规模很大经常做全量遍历还需要频繁保存。这种情况下完全可以用std::variantTransformNode, MeshNode, LightNode定义节点但节点间不存智能指针整体放进一个std::vector父子关系用索引表达。遍历逻辑全部写成std::visit里的一组lambda保存时直接把节点数组连续落盘。改一个“导出GLTF”的操作只需在外面增加一个std::visit分支函数树结构本身一行不动。这种组合拳的好处是层层递进的variant负责类型安全和操作集中的问题扁平数组负责性能和序列化的问题索引解决了所有权和循环引用的问题三者分工明确。如果你现在正准备设计一个组合树我的建议是别急着选边站先想清楚你最痛的点是“操作太多”“节点类型不稳定”还是“树规模大到性能可见”再决定用哪一层方案解决哪个痛点。7. 常见问题与排查技巧实录7.1 深树递归导致栈溢出组合树最经典的翻车现场。节点一多、层数一深递归遍历时函数调用栈一路往上压几万层的树就能把默认栈空间撑爆。两个解法。一个是编译期优化开关给递归函数挂上尾递归或者手动内联展开但这通常救不了深树。最可靠的还是显式栈的迭代遍历templatetypename F void iterativePreorder(Node root, F func) { std::vectorNode* stack{root}; while (!stack.empty()) { Node* current stack.back(); stack.pop_back(); func(*current); if (auto* composite std::get_ifComposite(current)) { for (auto it composite-children.rbegin(); it ! composite-children.rend(); it) { stack.push_back(it-get()); } } } }栈式遍历把隐藏的调用栈换成了堆上的std::vector深度基本只受内存限制。代码里的rbegin到rend循环是为了保证处理顺序先压后序子节点再压先序子节点弹出时自然先处理先序。另外迭代遍历里最好不要在func回调中直接删除节点栈里还存着指向被删节点的裸指针稍不注意就悬垂。7.2 shared_ptr循环引用与析构炸栈很多人图省事把std::shared_ptr用成“万能节点指针”。父节点持子节点子节点再持回父节点一个回环引用计数永远不为零树就住在内存里不走了。解决方式很简单层级结构默认用unique_ptr表达独占所有权唯一的父子关系用独占指针如果确实存在交叉引用反向引用一律用weak_ptr打断回环。另一个很少人注意的坑是析构。unique_ptr的析构是递归的删除一个组合节点会连带删除所有子节点子节点又删自己的子节点。树过深时析构函数本身就能把栈炸了而且比遍历炸得更隐蔽因为没人会想到“程序退出时崩了”。排查了几次之后我的对应方案是手动做一次“剥洋葱”式清理先把所有子节点移到栈上临时容器里清空指针再逐层向下。代码逻辑不算复杂但处理极深树时很有效。7.3 深拷贝、切片与移动继承式组合树最常见的拷贝陷阱是切片。把一个Composite赋给Component值时子类的部分全丢了。所以继承式树做深拷贝一定要设计虚clone()函数virtual std::unique_ptrNode clone() const 0;每个子类都要写一个return std::make_uniqueLeaf(*this);之类的实现。这又是一个“每加一个节点感受一次”的样板代码避不开。variant树的情况前面提到过单节点天然支持值操作但整棵树因为unique_ptr的存在默认不可拷贝想深拷贝要手写clone循环。扁平化树反而是深拷贝最简单的一种std::vectorNode的拷贝语义就是深拷贝拷贝一个vector等于复制整棵树而且索引结构不需要任何重建。移动方面variant树和继承式树都得益于unique_ptr和vector的移动语义整棵树搬走只是几次指针交换非常快。如果树结构经常整体转移、直接移动运行时开销可以小到忽略。7.4 遍历时改树迭代器翻车实录树形结构的遍历和修改常常不在同一个节奏上。最典型的翻车场景是在遍历循环里发现某个节点满足条件顺手把它从children_里移除紧接着继续遍历这个children_——然后迭代器失效崩溃或出现未定义行为。我踩过这个坑之后定下两条规矩。第一遍历过程中绝不直接修改结构只做标记等遍历结束后统一删改。第二如果一定要在遍历时删除就把“待删除节点”收集到一个独立的std::vectorNode*里退出循环后再按索引逐个处理。扁平化树在这种场景下也没完全免疫删除中间节点会导致后续下标整体移动遍历用的索引列表同样会错位。不管用哪种树遍历和修改分离永远是最稳的姿势。还有一些具体场景下的排查技巧树节点数量巨大但崩溃位置飘忽不定时优先怀疑析构和栈溢出序列化后加载回来的树总是少了某个分支检查一下索引是否在写文件时被指针替代了类型转换频繁报错时回头数一下variant的分支有没有和节点类型对齐。组合模式的变体千千万核心还是递归数据结构的类型设计。把树的结构、树上的操作、树的内存布局这三件事分开想大部分问题都能归位到某一层去解决。最后分享一点个人体会。我实际维护的模块里最顺手的一套方案是“variant定义节点 索引数组存储 对外暴露visit风格接口”。它把组合模式的几个经典痛点一次性按住了操作扩展不动节点节点类型又足够稳定性能和序列化都过得去。如果你要在一个新项目里重新选型我建议先把“节点类型会不会频繁增加”“操作会不会频繁增加”“树的规模大概多大”这三个问题问清楚答案基本就能把变体方向定下来了。 
长河君 · 2026/10/22 11:26:23 · 阅读 1.2k C++组合模式四大变体：访问者、variant、编译期与扁平化树
组合模式大概是C里最容易被低估的一个经典设计模式。教科书上三张图讲完Component、Leaf、Composite看起来谁都能写可真把一棵树塞进业务代码之后需求一多马上就知道“一个抽象基类加虚函数”这条路有多窄。给控件树加个渲染接口还容易后面再接“命中测试”“无障碍信息导出”“序列化存档”时整套类层次就得从上到下翻一遍叶子节点的空实现越来越滑稽。这篇要聊的正是组合模式在C里的几种实用变体访问者注入、std::variant强类型组合树、编译期静态树以及面向缓存与序列化的扁平化树。它们不互相取代而是分别解决不同层面的问题。适合已经写过基础树结构、正在为“加功能要动整片类”头疼的开发者参考。1. 组合模式的经典结构与为什么需要变体1.1 教科书组合模式的C形态先复习一下经典写法因为后面所有变体都要跟它对照。#include iostream #include memory #include vector class Component { public: virtual ~Component() default; virtual void render() const 0; virtual void add(std::unique_ptrComponent child) { (void)child; // 叶子节点用不上 } virtual const std::vectorstd::unique_ptrComponent children() const { static const std::vectorstd::unique_ptrComponent empty; return empty; } }; class Leaf : public Component { public: void render() const override { std::cout leaf\n; } }; class Composite : public Component { public: void render() const override { std::cout composite\n; for (const auto child : children_) { child-render(); } } void add(std::unique_ptrComponent child) override { children_.push_back(std::move(child)); } const std::vectorstd::unique_ptrComponent children() const override { return children_; } private: std::vectorstd::unique_ptrComponent children_; };这段代码本身没什么问题。组合模式的核心诉求是“让客户端统一对待叶子节点和组合节点”所以Component把所有可能用到的接口都摆在外面叶子节点用空实现占位组合节点用真实的容器实现。一处调用处处递归最终整棵树被遍历完。1.2 压在经典实现头上的几座山这套写法应付一个操作时很舒服操作一多就开始变形。第一个问题是操作爆炸。渲染、序列化、命中测试、字节数统计、事件分发每加一个操作都意味着在Component上加一个虚函数然后每一个继承者都补一份实现。哪怕某个叶子节点根本不可能参与“命中测试”你也得给它一个空函数。一个树形结构维护着五六个“与本节点无关”的空实现接口被撑得越来越脏。第二个问题是类型分支。组合模式宣称外部可以把Leaf和Composite混为一谈但实际业务里这两者天然不同叶子需要计算纹理尺寸组合节点需要录入子节点数量。客户端拿到一个Component时经常被逼着做dynamic_cast去区分实际类型。一旦代码里铺满了dynamic_cast这个模式的核心价值就开始打折。第三个问题是遍历逻辑和业务逻辑耦合。遍历顺序先父后子、先子后父、带剪枝的深度优先被固化在render()这类函数内部。换一种遍历策略你得再写一个函数里面又是一遍递归循环。树结构的表示和树上的操作被焊死在一起改动任何一方都要连累另一方。这三个痛点就是组合模式需要“变体”的根本原因。下面的几种变体本质上都是在调整“树结构本身”和“树上的操作”之间的解耦方式。2. 变体一访问者注入把操作从树结构里拆出去2.1 用双分派把“操作”反转到独立类里访问者模式的思路很简单不是让每个节点自己实现render()而是把“操作”本身抽成一个独立的类让节点把自身“交给”操作类去处理。C里常见的实现是这样的class NodeVisitor { public: virtual ~NodeVisitor() default; virtual void visit(Leaf node) 0; virtual void visit(Composite node) 0; }; class Node { public: virtual ~Node() default; virtual void accept(NodeVisitor visitor) 0; }; class Leaf : public Node { public: void accept(NodeVisitor visitor) override { visitor.visit(*this); } }; class Composite : public Node { public: void add(std::unique_ptrNode child) { children_.push_back(std::move(child)); } void accept(NodeVisitor visitor) override { visitor.visit(*this); for (auto child : children_) { child-accept(visitor); } } private: std::vectorstd::unique_ptrNode children_; };这样要加“序列化”操作时不用再动Component和所有子类只要新写一个SerializeVisitorclass SerializeVisitor : public NodeVisitor { public: void visit(Leaf node) override { // 输出叶子内容 } void visit(Composite node) override { // 输出组合节点内容 } };调用侧也很简单root-accept(serializeVisitor)。以后再加PDF导出、加统计、加无障碍文本全都是新增文件原有的树结构一行不改。这个变体把“操作”从“结构”里彻底拆了出去是经典组合模式最直接的进化方向。2.2 遍历顺序的控制权该给谁上面那版Composite::accept里遍历顺序被写死了先visit(*this)再递归子节点。如果访客想先遍历子节点、后处理自己它做不到。想在某个分支上剪枝它也没法插手。我的做法是把accept只保留“把自己分派出去”的功能真正的遍历逻辑收到Visitor内部。可以先提供一个统一的辅助接口void walk(Node node, NodeVisitor visitor) { node.accept(visitor); if (auto* composite dynamic_castComposite*(node)) { for (auto child : composite-children()) { walk(*child, visitor); } } }或者更干脆一点让每个Visitor自己决定是否需要遍历。RenderVisitor里可以这样写void visit(Composite node) override { // 渲染自己 // 然后自己控制是否递归 for (auto child : node.children()) { child-accept(*this); } }前一种方案胜在“约定统一”但灵活性受限后一种方案灵活却要求每个Visitor自己维护递归写多了会发现都是一样的循环。实际项目里我更喜欢折中在Visitor基类里提供一个受保护的walk(Node)帮助函数子类想用就自己调不想用就自写遍历逻辑。这样大部分操作类都能保持精简个别行为特殊的操作也有发挥空间。2.3 Visitor变体的隐藏成本Visitor几乎解决了“操作增加”的问题但它不是免费的。最大的代价是双分派。accept是一次分派visit里的重载又是一次分派深度递归时多一层函数调用甚至比普通虚函数还重一点。对性能极其敏感、树深度又高的场景要慎重。其次是新增节点类型的成本反转了。经典继承树新增一个节点类型只需写一个新子类Visitor树新增一个节点类型所有Visitor都要加一个visit重载。如果产品迭代方向是“不断有新型节点进来”Visitor会让你越改越烦。还有一个容易忽略的细节NodeVisitor::visit接收的是非const引用。想遍历一棵const树时你需要再做一套const重载或者干脆在每个Visitor里写两个版本。代码量会翻倍这是这套方案在设计之初就要预估到的。所以我自己的判断是Visitor变体适合“节点类型相对稳定、操作频繁新增”的业务比如引擎层的场景导出、工具链里的代码生成都不错。但如果你手头是一个“节点类型三天两头加新类”的编辑器Visitor会变成新的负担。3. 变体二std::variant强类型组合树3.1 递归variant类型怎么构造Visitor变体解决了一部分问题但经典继承的一些老毛病还在动态类型转换、堆上散落的节点、指针的裸野不确定性。C17以后std::variant给了另一种视野组合树的节点根本不需要继承体系直接用类型集合表达就行。难点在于递归。std::variantLeaf, Composite里Composite内部又要持有子节点子节点又是Leaf或Composite这就构成递归类型。标准库的std::variant要求所有类型完整不能直接自引用。常规解法是用一层unique_ptr做递归跳板struct Node; using NodePtr std::unique_ptrNode; struct Leaf { double size 0.0; }; struct Composite { std::vectorNodePtr children; }; struct Node : std::variantLeaf, Composite { using variant::variant; };Node继承std::variantLeaf, Composite之后可以直接写Node node{Leaf{3.14}}也可以写Node node{Composite{}}。因为Composite里只有std::vectorNodePtr而NodePtr是不完整类型Node的unique_ptr这种前向声明加智能指针的组合是合法的。unique_ptr允许指向不完整类型是标准库特意留下的口子这里的顺序必须先声明struct Node再用别名定义NodePtr最后再定义Leaf和Composite编译才能通过。3.2 std::visit overloaded遍历整棵树有了variant树最优雅的遍历方式是std::visit。配合C17的overloaded技巧代码可以写得非常集中templateclass... Ts struct overloaded : Ts... { using Ts::operator()...; }; templateclass... Ts overloaded(Ts...) - overloadedTs...; double totalSize(const Node node) { return std::visit(overloaded{ [](const Leaf leaf) { return leaf.size; }, [](const Composite composite) { double total 0.0; for (const auto child : composite.children) { total totalSize(*child); } return total; } }, node); }overloaded的本质是多个lambda的聚合体它继承所有lambda的operator()再用推导指引把多个lambda打包成一个访问器。std::visit拿到Node的实际类型后会选中匹配的lambda执行。每个访问分支在编译期就写死了不需要dynamic_cast也不需要任何运行时类型标记。这种写法的好处是类型安全到骨头里。如果我写漏了Leaf或Composite分支编译器直接报错绝不留给运行时一个神秘崩溃。另外因为我用的是匿名lambda编译器有很大概率把它内联进std::visit的分派逻辑里相比虚函数间接调用局部性更好。要说麻烦也有。节点创建时的类型操作不够直观Node root{Composite{}}; std::getComposite(root).children.push_back( std::make_uniqueNode(Leaf{3.14}));std::getComposite这串写法略长不过封装几个辅助函数就能解决。还有如果日后新增一种节点类型std::visit里所有操作类的lambda都要跟着加一个分支这和Visitor是一样的问题——节点类型稳定时才舒服。3.3 variant树的性能和“伪值语义”要分清很多人听说variant树第一反应是“值语义”。这里得泼一盆冷水variant确实按值内嵌存储Leaf或Composite本身不再有基类指针那一层间接但这棵树的子树是用unique_ptr链接的所以整棵树默认不可拷贝unique_ptr不允许复制。也就是说这台“值语义”只体现在单节点的内存布局上不代表你可以随意按值拷贝一棵树。如果你想深拷贝一棵variant树还是要手动写递归cloneNode cloneNode(const Node src) { return std::visit(overloaded{ [](const Leaf leaf) - Node { return Leaf{leaf}; }, [](const Composite composite) - Node { Composite copy; copy.children.reserve(composite.children.size()); for (const auto child : composite.children) { copy.children.push_back( std::make_uniqueNode(cloneNode(*child))); } return copy; } }, src); }反过来移动这棵树倒是很轻量因为vector和unique_ptr的移动都是常数时间。性能方面std::visit在编译器实现里通常是一张类型索引到函数指针的表和虚函数表的机制类似但它少了对象本身的vptr解引用分支跳转也更规整。我手头一个十万节点的模拟树做过粗略基准variant版本比虚函数版本快了大概一成但这类数据容易受编译器、访问模式影响只能当参考。真正适合variant树的场景是节点类型集合明确且不会频繁扩展、操作逻辑希望集中维护、希望避免继承体系的凌乱。配合第5章的索引化存储它可以成为一套非常现代的组合树实现。4. 变体三编译期组合树把“部分-整体”写进类型4.1 什么场景值得上编译期组合前两个变体都是运行期方案树的结构直到程序运行时才能完全确定节点之间靠指针或索引关联。但有些场景里整棵树的形状在编译期就完全清楚了比如一个固定公式的表达式树、一个静态的混合树配置、一个永不变动的菜单结构。这时候再把树塞进运行期虚函数或variant里等于白白付出一堆动态分派的钱。编译期组合树的思路是让树的结构直接映射成C类型。组合节点是一个模板子节点类型被写进模板参数里叶子节点是一个普通类型。遍历时不再依赖运行期类型判断所有“该走哪个分支”在编译期就定死了。4.2 用tuple和模板搭一棵静态树先看叶子templatetypename T class Constant { public: explicit Constant(T value) : value_(value) {} T evaluate() const { return value_; } private: T value_; };再看内部节点。一个内部节点持有若干子节点子节点类型各不相同所以放在std::tuple里templatetypename Op, typename... Children class StaticNode { public: explicit StaticNode(Children... children) : children_(std::forwardChildren(children)...) {} double evaluate() const { return std::apply([](const auto... child) { return Op{}(child.evaluate()...); }, children_); } private: std::tupleChildren... children_; };std::apply把tuple里的每个元素解开按顺序传给lambdalambda里再逐个调用evaluate()。因为所有子节点的类型在模板参数里已经确定这里没有任何运行期分支理论上可以被完全内联展开。工厂函数让类型推导简单一点templatetypename Op, typename... Children auto makeStaticNode(Children... children) { return StaticNodeOp, std::decay_tChildren...{ std::forwardChildren(children)... }; }用法struct SumOp { double operator()(double a, double b) const { return a b; } }; Constantdouble a(2.0), b(3.0), c(4.0); auto inner makeStaticNodeSumOp(b, c); auto tree makeStaticNodeSumOp(a, inner); double result tree.evaluate(); // 2 (3 4) 9注意inner本身就是一棵小树再作为子节点塞进tree之后组成了两层的静态树。类型层面这棵树是明确的StaticNodeSumOp, Constantdouble, StaticNodeSumOp, Constantdouble, Constantdouble。想再继续嵌套类型会继续膨胀但编译器完全hold住。4.3 编译期组合的边界与代价编译期组合树最大的优势是零运行期开销。它把组合模式从“对象结构”提升到了“类型结构”在编译期完成所有的子节点分发。如果你在做一个对性能敏感、且树结构静态固定的模块这一招很值。但代价也要说清楚。第一编译期组合树无法处理“运行时才确定形状”的数据结构。用户从配置里拖一棵树出来或者从XML读一批节点这条路直接废掉。第二模板类型本身极长报错信息会把人绕晕工程上一个通用节点的类型常常膨胀到难以读写的长度。第三相同形状的两棵静态树是同一个类型但形状略不同的两棵树就是完全不同的类型想把它们装进同一个容器、做统一遍历反而需要额外的类型擦除层。我的结论是编译期组合树适合做“核心计算路径”比如表达式模板、数学公式树、静态模板化场景树的一部分。它不适合作为通用的“用户数据容器”更不要指望在业务层整天构建这种树。工程上更常见的形态是静态模板树作为内部的性能热点外层再包一层variant或普通节点兼顾灵活性和速度这一点在第6章混合架构里会再提到。5. 变体四扁平化组合树用连续内存表达层级5.1 用数组装下整棵树的思路组合模式天然让人想到指针和堆分配每个节点new出来父子之间用指针关联。问题是几十万节点的树一旦构建起来节点在堆上东一块西一块遍历时的缓存命中率惨不忍睹。而且指针方案还要考虑所有权谁释放、会不会悬垂、会不会循环。工程里很多“树崩了”的问题本质上不是业务错了而是指针生命周期错了。扁平化组合树换了一个视角所有节点放进同一个std::vector节点之间不存指针存索引。指针变成了数组下标所有权问题从源头消失整个树还天然具备极好的序列化和缓存特性。5.2 first-child / next-sibling 表示法的实现要点扁平树常见的表示法是“首子节点 下一个兄弟节点”也就是常说的左孩子右兄弟表示法。每个节点只保存三个关联下标static constexpr uint32_t kNoIndex ~0u; struct Node { double value 0.0; uint32_t parent kNoIndex; uint32_t firstChild kNoIndex; uint32_t nextSibling kNoIndex; }; class FlatTree { public: uint32_t addChild(uint32_t parentIndex) { uint32_t index static_castuint32_t(nodes_.size()); nodes_.push_back(Node{}); nodes_[index].parent parentIndex; if (nodes_[parentIndex].firstChild kNoIndex) { nodes_[parentIndex].firstChild index; } else { uint32_t last nodes_[parentIndex].firstChild; while (nodes_[last].nextSibling ! kNoIndex) { last nodes_[last].nextSibling; } nodes_[last].nextSibling index; } return index; } const std::vectorNode nodes() const { return nodes_; } private: std::vectorNode nodes_; };往父节点挂子节点时如果父节点还没有孩子就挂在firstChild上已经有孩子就沿着nextSibling链找到最后一个再挂上去。遍历时也是顺着这条链走templatetypename F void traverse(const FlatTree tree, uint32_t index, F func) { func(tree.nodes()[index]); uint32_t child tree.nodes()[index].firstChild; while (child ! kNoIndex) { traverse(tree, child, func); child tree.nodes()[child].nextSibling; } }这个方案的优秀之处在于整个树就是一段连续内存。遍历时CPU缓存能把相邻节点一起带上速度快很多。序列化也简单到极致把std::vectorNode原样写文件加载时再原样读回来只要Node保持POD连字段对齐都不用担心索引天然有效。这就是索引相比指针最大的红利。5.3 扁平树的取舍与优化一定要提的取舍是“删除节点”变得麻烦。数组中间删掉一个元素后面所有索引都会移动原来记录的下标全部失效。工程上有两种应对一是用空闲索引回收机制删除时只标记为空不实际搬移数组后续复用二是干脆不提供单节点删除只提供整棵子树清理。很多游戏引擎的场景管理就是这么干的。另一个可以优化的是“插入子节点”的复杂度。上面的addChild每次都要沿着兄弟链走到尾部最坏O(子节点数量)。如果想高频挂载子节点可以在节点里加一个lastChild字段把尾部索引存起来挂接变成O(1)。我自己的经验是扁平树特别适合节点数量巨大、以构建和遍历为主、删除不频繁的场景。比如UI控件树、资源依赖图、静态配置层级。如果一棵树需要高频随机增删节点、树结构本身成为业务的操作核心那这种表示法会带来额外的心智负担不如回归unique_ptr树。6. 四个变体的横向对比与选型清单6.1 一张表看清四种写法的性格不同变体之间往往不是“谁更好”而是“在什么条件下谁更合适”。把它们放在一起看会更直观变体加操作加节点类型性能特征最适合的场景经典继承树改基类加所有子类新增一个子类即可vtable间接调用节点类型常变、操作稳定Visitor注入新增一个Visitor类所有Visitor都要加重载双分派多一次跳转操作常变、节点类型稳定std::variant树每个visit里加一个分支所有visit都要加分支编译期分派局部性好节点类型稳定、强调类型安全编译期静态树新增模板或运算操作新增模板类型零运行期分派树结构编译期已知、性能敏感扁平化树遍历方向由函数实现决定结构体加字段缓存友好、序列化友好节点数量巨大、构建与遍历为主后面四行其实是前四行的补充Visitor和variant都把“操作”从“结构”里挤了出去编译期静态树把“结构”也升到编译期扁平化树则从内存布局角度补上了前几个方案都不太在乎的缓存与序列化问题。6.2 真正实用的混合架构variant 访客 索引实际工程里最打动我的不是单一种变体而是它们之间的组合。一个树模块可以同时拥有variant的类型安全和扁平数组的数据布局再暴露一层类似Visitor的对外接口业务层完全无感知。举个例子某个编辑器场景树节点类型只有变换、网格、灯光三种相对稳定。树规模很大经常做全量遍历还需要频繁保存。这种情况下完全可以用std::variantTransformNode, MeshNode, LightNode定义节点但节点间不存智能指针整体放进一个std::vector父子关系用索引表达。遍历逻辑全部写成std::visit里的一组lambda保存时直接把节点数组连续落盘。改一个“导出GLTF”的操作只需在外面增加一个std::visit分支函数树结构本身一行不动。这种组合拳的好处是层层递进的variant负责类型安全和操作集中的问题扁平数组负责性能和序列化的问题索引解决了所有权和循环引用的问题三者分工明确。如果你现在正准备设计一个组合树我的建议是别急着选边站先想清楚你最痛的点是“操作太多”“节点类型不稳定”还是“树规模大到性能可见”再决定用哪一层方案解决哪个痛点。7. 常见问题与排查技巧实录7.1 深树递归导致栈溢出组合树最经典的翻车现场。节点一多、层数一深递归遍历时函数调用栈一路往上压几万层的树就能把默认栈空间撑爆。两个解法。一个是编译期优化开关给递归函数挂上尾递归或者手动内联展开但这通常救不了深树。最可靠的还是显式栈的迭代遍历templatetypename F void iterativePreorder(Node root, F func) { std::vectorNode* stack{root}; while (!stack.empty()) { Node* current stack.back(); stack.pop_back(); func(*current); if (auto* composite std::get_ifComposite(current)) { for (auto it composite-children.rbegin(); it ! composite-children.rend(); it) { stack.push_back(it-get()); } } } }栈式遍历把隐藏的调用栈换成了堆上的std::vector深度基本只受内存限制。代码里的rbegin到rend循环是为了保证处理顺序先压后序子节点再压先序子节点弹出时自然先处理先序。另外迭代遍历里最好不要在func回调中直接删除节点栈里还存着指向被删节点的裸指针稍不注意就悬垂。7.2 shared_ptr循环引用与析构炸栈很多人图省事把std::shared_ptr用成“万能节点指针”。父节点持子节点子节点再持回父节点一个回环引用计数永远不为零树就住在内存里不走了。解决方式很简单层级结构默认用unique_ptr表达独占所有权唯一的父子关系用独占指针如果确实存在交叉引用反向引用一律用weak_ptr打断回环。另一个很少人注意的坑是析构。unique_ptr的析构是递归的删除一个组合节点会连带删除所有子节点子节点又删自己的子节点。树过深时析构函数本身就能把栈炸了而且比遍历炸得更隐蔽因为没人会想到“程序退出时崩了”。排查了几次之后我的对应方案是手动做一次“剥洋葱”式清理先把所有子节点移到栈上临时容器里清空指针再逐层向下。代码逻辑不算复杂但处理极深树时很有效。7.3 深拷贝、切片与移动继承式组合树最常见的拷贝陷阱是切片。把一个Composite赋给Component值时子类的部分全丢了。所以继承式树做深拷贝一定要设计虚clone()函数virtual std::unique_ptrNode clone() const 0;每个子类都要写一个return std::make_uniqueLeaf(*this);之类的实现。这又是一个“每加一个节点感受一次”的样板代码避不开。variant树的情况前面提到过单节点天然支持值操作但整棵树因为unique_ptr的存在默认不可拷贝想深拷贝要手写clone循环。扁平化树反而是深拷贝最简单的一种std::vectorNode的拷贝语义就是深拷贝拷贝一个vector等于复制整棵树而且索引结构不需要任何重建。移动方面variant树和继承式树都得益于unique_ptr和vector的移动语义整棵树搬走只是几次指针交换非常快。如果树结构经常整体转移、直接移动运行时开销可以小到忽略。7.4 遍历时改树迭代器翻车实录树形结构的遍历和修改常常不在同一个节奏上。最典型的翻车场景是在遍历循环里发现某个节点满足条件顺手把它从children_里移除紧接着继续遍历这个children_——然后迭代器失效崩溃或出现未定义行为。我踩过这个坑之后定下两条规矩。第一遍历过程中绝不直接修改结构只做标记等遍历结束后统一删改。第二如果一定要在遍历时删除就把“待删除节点”收集到一个独立的std::vectorNode*里退出循环后再按索引逐个处理。扁平化树在这种场景下也没完全免疫删除中间节点会导致后续下标整体移动遍历用的索引列表同样会错位。不管用哪种树遍历和修改分离永远是最稳的姿势。还有一些具体场景下的排查技巧树节点数量巨大但崩溃位置飘忽不定时优先怀疑析构和栈溢出序列化后加载回来的树总是少了某个分支检查一下索引是否在写文件时被指针替代了类型转换频繁报错时回头数一下variant的分支有没有和节点类型对齐。组合模式的变体千千万核心还是递归数据结构的类型设计。把树的结构、树上的操作、树的内存布局这三件事分开想大部分问题都能归位到某一层去解决。最后分享一点个人体会。我实际维护的模块里最顺手的一套方案是“variant定义节点 索引数组存储 对外暴露visit风格接口”。它把组合模式的几个经典痛点一次性按住了操作扩展不动节点节点类型又足够稳定性能和序列化都过得去。如果你要在一个新项目里重新选型我建议先把“节点类型会不会频繁增加”“操作会不会频繁增加”“树的规模大概多大”这三个问题问清楚答案基本就能把变体方向定下来了。