C++组合模式实战：文件系统目录树与递归遍历

1. 组合模式到底是什么为什么值得学组合模式在 C 设计模式里算是个熟面孔了但我见过很多开发者在实际工程里把它写复杂或者干脆用错地方。有人觉得它跟“递归遍历一棵树”划等号有人把它当成“万能容器管理器”到处套。这个理解不能说完全错但离真正的价值还差一截。这篇东西我会用最直接的 C 代码把组合模式从定义到实战完整过一遍。适合已经写过一段时间 C、想搞懂设计模式该怎么落地的朋友也适合准备面试时被问到“组合模式怎么实现、怎么用”的同学。内容会贴着一个具体的实战场景走构建一个文件系统目录树。代码用 C11/14 风格不刻意炫技每个细节都尽量能直接抄走。1.1 先看看没有组合模式的代码有多痛想象你要实现一个公司组织架构的工资统计。经理下面有员工有小组小组下面又有员工。最“本能”的实现是给每个类都写一个 GetSalary()struct Employee { double salary; }; struct Manager { std::vectorEmployee employees; double salary; }; struct Department { std::vectorManager managers; double salary; };然后算总工资的时候你就会写出这样的代码double totalSalary(const Department dept) { double total 0; for (const auto m : dept.managers) { total m.salary; for (const auto e : m.employees) { total e.salary; } } return total; }这个代码能跑但有一个很典型的问题层次一旦加深比如变成“集团 → 事业部 → 部门 → 小组 → 员工”你就得跟着改循环嵌套每层都要重新写一遍遍历逻辑。而且客户端代码必须知道每一层的具体类型才能钻进下一层。这直接破坏了开闭原则加一种新的节点类型所有遍历函数都要跟着动。这就是组合模式要解决的经典场景不同类型对象共享同一个层次结构客户端希望像操作单个对象一样操作整个复合结构。1.2 组合模式的本质统一接口组合模式的核心思想其实特别朴素把叶子对象和组合对象都看作同一种类型让它们实现同一个接口。这样对客户端来说单个文件和整个目录是一回事单个员工和整个部门也是一回事。从设计模式分类上讲组合模式属于结构型模式。它的本质是通过多态把“整体与部分的层次关系”从客户端代码里剥离开。客户端只面向基类接口编程不需要关心它正在操作的是一个叶子还是一个树枝。三个最典型的应用场景需要表示对象的部分-整体层次结构例如文件系统、XML/DOM、UI 组件树希望客户端可以一致地处理单个对象和组合对象树形结构在运行时是动态变化的需要不断增删节点。为了把概念说透我用一个生活化的例子你去餐厅点餐“给我来一份套餐”。套餐里面可能是两个菜加一杯饮料也可能是一个汉堡加一份薯条。套餐对外就是一个可点的整体内部却能嵌套其他套餐。这就是组合模式的通俗版本。下面这个表格可以更直观地对比“不用模式”和“用模式”的差别维度不用组合模式用组合模式客户端代码复杂度随层次加深爆炸式增长恒定面向基类接口新增节点类型成本所有遍历逻辑都要改只需实现新接口类是否依赖具体类型是客户端要层层判断类型否多态天然解决2. 基础实现在 C 里把组合模式骨架搭出来2.1 抽象基类定义统一契约我先直接给代码再解释关键点#include iostream #include memory #include string #include vector #include stdexcept // 抽象基类文件和目录的共同接口 class FileSystemNode { public: virtual ~FileSystemNode() default; // 节点名称 virtual const std::string name() const 0; // 节点大小字节 virtual double size() const 0; // 组合节点特有的操作叶子节点默认抛异常 virtual void add(std::shared_ptrFileSystemNode child) { throw std::runtime_error(Unsupported operation: add() on leaf node); } virtual void remove(std::shared_ptrFileSystemNode child) { throw std::runtime_error(Unsupported operation: remove() on leaf node); } virtual std::shared_ptrFileSystemNode getChild(size_t index) const { throw std::runtime_error(Unsupported operation: getChild() on leaf node); } };这段代码里有几个非常关键的 C 细节。第一基类析构函数必须是虚的。因为客户端会通过基类指针删除实际对象如果析构函数不是虚的派生类析构就不会被调用内存泄漏和未定义行为就全来了。这里用 default既保证虚析构又保持默认实现是最标准的写法。第二add/remove/getChild 这些“组合节点特有”的操作到底放不放基类是一个经典的设计分歧。传统 GoF 书里会把它们放在 Component 里叶子节点实现为抛异常这就是“透明模式”。好处是客户端完全不知道节点类型所有节点都能用同一个接口操作坏处是叶子对象也暴露出无意义的接口调用 add 时只能靠运行时异常兜底。第三注意我用了std::shared_ptr这在组合模式里是一个非常重要的选择。为什么不用裸指针或者 unique_ptr后面避坑指南部分会专门展开讲。2.2 树枝节点写一个有实际意义的容器树枝节点在文件系统场景里就是“目录”它的核心职责是管理子节点列表同时实现递归逻辑class Directory : public FileSystemNode { private: std::string name_; double selfSize_; std::vectorstd::shared_ptrFileSystemNode children_; public: explicit Directory(std::string name, double selfSize 0) : name_(std::move(name)), selfSize_(selfSize) {} const std::string name() const override { return name_; } double size() const override { double total selfSize_; for (const auto child : children_) { total child-size(); } return total; } void add(std::shared_ptrFileSystemNode child) override { children_.push_back(std::move(child)); } void remove(std::shared_ptrFileSystemNode child) override { auto it std::find(children_.begin(), children_.end(), child); if (it ! children_.end()) { children_.erase(it); } } std::shared_ptrFileSystemNode getChild(size_t index) const override { return children_.at(index); } const std::vectorstd::shared_ptrFileSystemNode children() const { return children_; } };这里最有代表性的就是 size() 方法里的递归调用。目录大小 自身大小 所有子节点大小。子树是自己的子树子节点是自己的孩子所以child-size()能正确工作是因为child的类型虽然是shared_ptrFileSystemNode但实际的 size() 是虚函数编译器会自动分派到 File 或 Directory 的实现上。这叫递归组合是整个组合模式能工作的发动机。再补充几个实现细节size() 是 const 成员函数但内部通过 children_ 里的 shared_ptr 调用虚函数 size()多态不受 const 影响。add() 的参数是shared_ptrFileSystemNode不是 unique_ptr。原因很简单组合模式里同一个子节点对象经常会被多处引用。比如你从根目录拿一个节点再把它传给一个搜索函数、一个渲染函数如果每个函数都要持有它unique_ptr 就挪不走了。remove() 直接用 std::find 比较 shared_ptr比较的是底层指针地址不是名字。后面会提一个相关的坑。2.3 叶子节点最纯粹的单元class File : public FileSystemNode { private: std::string name_; double size_; public: File(std::string name, double size) : name_(std::move(name)), size_(size) {} const std::string name() const override { return name_; } double size() const override { return size_; } // 不重写 add/remove/getChild继承基类的默认抛异常实现 };叶子节点就是最朴素的实现size() 返回自己的真实大小没有任何子节点。它的 add/remove/getChild 全部继承基类的抛异常行为。这样客户端即使不小心对一个文件调 add()也能立刻得到明确的运行时报错而不是静默失败。这里有个设计上的小思考文件节点的大小是不变的目录大小是动态计算的。在真实文件系统里目录本身也会因为元数据变化而改变大小但为了保持模式演示的简洁我们可以让目录节点用“初始大小递归求和”的模型这个模型已经跟真实场景非常接近了。2.4 透明版和安全版你选哪个前面提到了透明模式这里把两种风格做一个完整对比对比维度透明模式安全模式add/remove/getChild 位置基类定义叶子继承抛异常只定义在树枝节点客户端是否需要判断类型不需要统一接口需要 dynamic_cast 或类型判断接口干净度叶子暴露出无意义接口接口纯净C 工程落地难度简单直接绕容易破坏多态我个人的经验是大部分落地代码里透明模式更实用。原因很简单——C 没有 Java 那种自带 throws 声明的强约束如果你在基类里不放 add/remove客户端就得先判断“这个节点是目录还是文件”。判断完基本就用 if-else 把多态绕回去了组合模式的意义就丢掉一大半。透明模式配合“抛异常”的默认实现已经能提供足够清晰的运行时契约。提示在透明模式下如果要求更严格的编译期约束可以用 typeid 或 dynamic_cast 判断节点类型但这会破坏多态一般不建议。正确做法是让接口语义尽量自洽客户端默认所有节点都可以 add遇到叶子节点抛出的异常再做处理。3. 实战案例搭建一个文件系统目录树3.1 需求拆解与类设计现在做一个真实可运行的东西一个命令行工具打印目录树的层级结构同时统计所有文件大小总和。需求就三条能构建一棵“目录-文件”的树节点可以动态增删能完整遍历树格式化输出用缩进表示层级能计算任意子树包括单个文件的总大小。用组合模式设计的话类关系很简单抽象节点 FileSystemNode定义 name() 和 size()File 类是叶子节点Directory 类持有子节点列表size() 递归求和客户端维护根目录的 shared_ptr后续操作都通过基类接口进行。3.2 完整代码与运行结果我把完整代码贴出来直接放到单个 .cpp 文件里就能编译运行#include iostream #include memory #include string #include vector #include algorithm #include stdexcept using std::cout; using std::endl; using std::string; using std::shared_ptr; using std::vector; class FileSystemNode { public: virtual ~FileSystemNode() default; virtual const string name() const 0; virtual double size() const 0; virtual void add(shared_ptrFileSystemNode child) { throw std::runtime_error(Cannot add child to a leaf node: name()); } virtual void remove(shared_ptrFileSystemNode child) { throw std::runtime_error(Cannot remove child from a leaf node: name()); } virtual shared_ptrFileSystemNode getChild(size_t index) const { throw std::runtime_error(Cannot get child from a leaf node: name()); } }; class File : public FileSystemNode { string name_; double size_; public: File(string name, double size) : name_(std::move(name)), size_(size) {} const string name() const override { return name_; } double size() const override { return size_; } }; class Directory : public FileSystemNode { string name_; double selfSize_; vectorshared_ptrFileSystemNode children_; public: Directory(string name, double selfSize 0) : name_(std::move(name)), selfSize_(selfSize) {} const string name() const override { return name_; } double size() const override { double total selfSize_; for (const auto child : children_) { total child-size(); } return total; } void add(shared_ptrFileSystemNode child) override { children_.push_back(std::move(child)); } void remove(shared_ptrFileSystemNode child) override { auto it std::find(children_.begin(), children_.end(), child); if (it ! children_.end()) { children_.erase(it); } } shared_ptrFileSystemNode getChild(size_t index) const override { return children_.at(index); } const vectorshared_ptrFileSystemNode children() const { return children_; } }; void printTree(const shared_ptrFileSystemNode node, int depth 0) { if (!node) return; for (int i 0; i depth; i) cout ; cout node-name() ( node-size() ) endl; auto dir std::dynamic_pointer_castDirectory(node); if (dir) { for (const auto child : dir-children()) { printTree(child, depth 1); } } } int main() { auto root std::make_sharedDirectory(root, 100); auto etc std::make_sharedDirectory(etc, 50); etc-add(std::make_sharedFile(hosts, 1)); etc-add(std::make_sharedFile(nginx.conf, 12.5)); auto data std::make_sharedDirectory(data, 200); auto logs std::make_sharedDirectory(logs, 10); logs-add(std::make_sharedFile(app.log, 512.3)); logs-add(std::make_sharedFile(error.log, 32.8)); >g -stdc14 -Wall -o composite_demo composite_demo.cpp ./composite_demo输出结果root (2910.6) etc (63.5) hosts (1) nginx.conf (12.5) data (2755.1) logs (555.1) app.log (512.3) error.log (32.8) db.sql (2000) ---------------------- root 总大小: 2910.6 bytes data 总大小: 2755.1 bytes这个结果完美验证了组合模式的核心能力打印整个目录树和统计任意节点大小客户端只用了同一个 size() 接口没有任何“先判断文件还是目录、再分情况求和”的逻辑。3.3 几个代码实现里的关键思考先看 printTree 函数。我在遍历时用了dynamic_pointer_castDirectory这在形式上确实“泄露”了类型信息。但从实战角度这是合理的打印树形结构时需要知道哪些节点有子节点走基类的 getChild() 接口反而更绕因为叶子节点的 getChild() 会抛异常你要在每个递归分支都包一层 try-catch代码会非常难看。如果你想让遍历代码完全面向基类接口可以给基类增加一个virtual bool isComposite() const { return false; }然后 Directory 里重写为 true。这样打印函数就能写成统一的基类接口调用。我自己在工程里的习惯是基类并不总是暴露 children 容器而是用 isComposite() 加上 getChild(index) 组合。这种方式保留透明接口又避免每次抛出异常。第二个核心细节是 size() 的递归。Directory::size() 编译时调用 child-size()因为 child 是 shared_ptr 所以编译器必然生成虚函数调用。这保证无论 child 实际是 File 还是 Directory都能拿到正确的 size。这就是组合模式“透明递归”的基石。第三个细节是 remove() 用 std::find 按指针比较。如果传进来的 shared_ptr 跟存进去的不是同一个对象即使名字相同也删不掉而且不会报错后续排查会非常心累。更稳妥的做法是让节点有唯一的标识符按 id 或名字删除。注意组合模式的遍历写法没有唯一标准。是统一走基类接口还是允许 dynamic_cast 到具体类型取决于你的团队约定和场景需要。无论选哪种请把约定写进代码注释里否则后来维护的人一定会用出两种风格。4. 避坑指南C 实现组合模式的 5 个常见问题这部分是实战里最值得看的内容。下面这些问题都是真实项目里反复踩过的我一个个来讲。4.1 虚析构函数真的别漏如果一个类定义了虚函数基本就要把析构函数写成虚的否则通过基类指针删除派生类对象时会触发未定义行为。在组合模式里这个规则几乎是在拿生命开玩笑因为客户端一定会有这种代码std::shared_ptrFileSystemNode node std::make_sharedDirectory(root);当 node 被释放时shared_ptr 的删除器会把实际的删除逻辑执行出来。只要 FileSystemNode 的析构函数不是虚的Directory 的析构函数就不会被调用children_ 向量的析构同样不会发生整棵子树直接泄漏。虽然有些编译器在 shared_ptr 的实现细节上可能“侥幸”调用到正确的析构但这是不可依赖的行为。组合模式类里基类virtual ~FileSystemNode() default;是底线。4.2 智能指针shared_ptr 还是 unique_ptr组合模式的第一直觉是用 shared_ptr 管理子节点因为目录可能被多处引用。但如果你的树是“纯树形结构”每个节点只有一个父节点所有权非常清晰其实用 unique_ptr 也完全可以class Directory { std::vectorstd::unique_ptrFileSystemNode children_; public: void add(std::unique_ptrFileSystemNode child) { children_.push_back(std::move(child)); } };但这样你会遇到两个麻烦。第一编译期限制一个 unique_ptr 不能同时是“父节点持有的孩子”和“外部传递的观测者”。如果你想实现“从一个目录移除节点并插入到另一个目录”必须先把节点 unique_ptr 移出来一步都不能错代码会变得很难看。第二组合模式经常配合“非拥有观察”的需求。比如我要遍历一棵树先在主函数里保存根节点又要传给打印函数打印函数内部可能还要把某个子目录临时存下来。这时 shared_ptr 就是最自然的选择它同时充当了“所有权”和“安全引用”。我的建议是树是一次构建、只读遍历用 unique_ptr效率高、语义清晰树需要动态调整、多位置引用用 shared_ptr开发效率高观察者指针用 raw pointer 或者 weak_ptr绝不拥有节点。提示使用 shared_ptr 时如果 A 包含 BB 也包含 A比如目录里存父指针会产生循环引用内存泄漏逃不掉。树形结构里父指针建议用 raw pointer 或 weak_ptr。只要方向是单向的“父持有子”shared_ptr 非常安全。4.3 深拷贝最容易翻车的场景组合树的拷贝看起来简单实际上坑很深。默认情况下如果你写Directory copy(*original);编译器会逐成员拷贝如果成员是vectorshared_ptrFileSystemNode那么拷贝出来的新目录里的 children_ 和原目录的 children_ 会指向同一个子节点对象——两个父节点共享同一个子节点。你改了拷贝的子树原树也变了。所以你必须实现深拷贝。最经典的方式是给基类加一个虚函数 clone()class FileSystemNode { public: virtual ~FileSystemNode() default; virtual std::unique_ptrFileSystemNode clone() const 0; }; class Directory : public FileSystemNode { public: std::unique_ptrFileSystemNode clone() const override { auto copy std::make_uniqueDirectory(name_, selfSize_); for (const auto child : children_) { copy-add(child-clone()); } return copy; } }; class File : public FileSystemNode { public: std::unique_ptrFileSystemNode clone() const override { return std::make_uniqueFile(name_, size_); } };clone() 返回 unique_ptr 而不是 shared_ptr 更合理因为拷贝出来的对象由调用者单独拥有。它要不要被共享由调用者自己决定——想共享再转成 shared_ptr 很容易。这里有个反直觉的细节即使你的成员是 shared_ptrclone() 也应该返回 unique_ptr否则一个 shared_ptr 套一个 clone()拷贝出来的树节点仍然可能纠缠在一起。4.4 const 正确性组合模式里容易被忽略的是 const 正确性。size() 应该是 const 成员函数children() 也应该是 const。但这里有个陷阱如果 children() 返回const vectorshared_ptrFileSystemNode调用端可以直接取出auto child dir.children()[0]拿到的 shared_ptr 指向的节点对象本身可不是 const 的于是你可以对“只读”目录树做修改void readOnlyTraverse(const Directory root) { auto child root.children()[0]; child-add(std::make_sharedFile(evil.txt, 1)); // 合法但破坏了只读语义 }C 里想彻底解决这个问题需要让 FileSystemNode 提供 const 版本和非 const 版本的两套接口或者用传播 const 的智能指针模板。但这两样都会显著增加代码复杂度。工程上的务实建议是不要过度纠结只在需要 const 只读遍历的函数里注意不要通过拿到的 shared_ptr 调用 add/remove 即可。如果真做严格权限控制设计阶段就约定好“构建期可变、运行期只读”比在类型系统层面硬扛简单得多。4.5 线程安全与并发遍历组合模式的树结构在只读场景下天然友好构建完成后不修改多线程同时调用 const size() 是很安全的。但如果运行时要动态增删节点你就需要并发策略。组合模式本身没有规定并发策略必须自己在外部加锁。最无脑也最有效的是“全局一把锁”缺点是并发度低。按节点粒度加锁则要小心死锁因为 size() 递归遍历时如果每个子节点都要加锁锁的顺序没有统一规则很容易形成循环等待。我的经验是在设计阶段就明确“构建期可变、运行期只读”运行时所有修改都排队到一个写线程。这种架构最简单也几乎不会出错。真实项目里绝大多数组合模式的应用场景都是这种“构建完毕后只读”的用法。5. 什么时候别用组合模式以及现代 C 的替代方案先泼一盆冷水组合模式不是万能的。在某些 C 场景里它反而是最笨重的选择。5.1 用 std::variant 替代如果你的节点类型在编译期就固定且数量有限比如一个表达式计算器只有数值字面量和加减乘除那用std::variant会比虚函数多态更高效也更安全struct Node; using NodePtr std::shared_ptrNode; struct Number { double value; }; struct BinOp { char op; NodePtr lhs; NodePtr rhs; }; struct Node : std::variantNumber, BinOp { using variant::variant; }; double eval(const Node n) { return std::visit([](const auto arg) - double { using T std::decay_tdecltype(arg); if constexpr (std::is_same_vT, Number) { return arg.value; } else if constexpr (std::is_same_vT, BinOp) { const double lhs eval(*arg.lhs); const double rhs eval(*arg.rhs); switch (arg.op) { case : return lhs rhs; case -: return lhs - rhs; case *: return lhs * rhs; case /: return lhs / rhs; } } }, n); }虚函数多态相比variant 是值语义、无虚表开销、遍历不需要递归虚函数调用性能更好。但代价是“节点类型集合必须是编译期已知的”而且类型是封闭的新增节点类型要改所有 std::visit 分支。组合模式的好处是类型开放新增一种节点只需新写一个类不用改原有遍历代码——前提是你的遍历函数只用了基类接口。这个取舍要记在心里类型集合已知且不会扩增用 variant类型集合开放、需要不断扩展用组合模式。5.2 用模板和 Concepts 替代如果节点类型在编译期已知但你想保留组合结构还可以用模板编程把“遍历”变成编译期递归。但说实话模板版本的组合结构在工程里很难维护因为每一层都要把子节点的类型包进去写出来的类型签名非常长。C20 的 concept 能缓解一部分可读性问题但总体复杂度还是比虚函数版本高。组合模式最大的优势是“运行时动态扩张”这是模板给不了的。所以模板方案只适合编译期就能确定完整树形结构的极少数场景日常项目基本用不上。5.3 组合模式的性能账虚函数调用不是免费的。在组合模式里child-size()的每次调用都是一个虚函数调用对树形结构来说这个开销被放大了 N 倍。如果 size() 本身做了大量工作虚函数开销可忽略但如果你在做一个“每帧遍历整个 UI 组件树”的高频渲染逻辑虚函数调用和 shared_ptr 的引用计数可能就是实打实的性能瓶颈。几个优化方向能预先计算的统计值就缓存起来比如目录构建完成后size() 预先算好不再每次递归子节点容器优先用 vector不要用 list缓存友好性差很多如果确实需要极高的遍历性能可以考虑“扁平化”结构把树拍平成数组用索引代替指针。很多游戏引擎不会直接拿组合模式做场景节点树而是用实体组件系统ECS的扁平结构就是这个原因。组合模式不是银弹。理解它的边界比学会怎么写更重要。6. 扩展方向与个人心得最后分享两个我自己用过、觉得非常有价值的扩展玩法。第一个是“组合 迭代器”。组合模式本身没有规定遍历算法但你可以在抽象基类里增加 begin()/end()返回一个深度优先迭代器这样就能用 range-for 直接遍历树客户端代码会清爽很多for (const auto node : root) { cout node-name() endl; }C 里实现一个递归迭代器是有点麻烦的因为迭代器要保存完整的递归栈帧。我的建议是不要一开始就写惰性迭代器先用一个最简单的方式遍历一次把所有节点收集进 vector再返回迭代器。思路简单性能也够用。真正的惰性迭代器适合大规模树的剪枝遍历复杂度高按需再说。第二个是“组合 访问者”。当树的节点类型很多每个节点都有各自不同的操作比如渲染、序列化、权限校验访问者模式可以把这些操作从节点类里剥离开。组合模式提供结构访问者模式提供对结构的多态操作这两个模式一起用是教科书里的经典组合也非常适合实际项目。我拆分过一套渲染树的序列化逻辑效果立竿见影RenderNode 本身只管 add/remove 和渲染序列化逻辑全部收敛到单独访问者里新增导出格式只写一个新访问者类就行。我个人的体会是组合模式是设计模式里少有的“结构简单但思想深刻”的模式。它不难写难的是想清楚在哪里用、在哪里不用。我在项目里见过不少过度设计的目录树——有些明明用两行循环嵌套就够了的简单结构非要先造一个 Component 抽象结果节点增删逻辑被套进各种重抽象里最后维护的人叫苦不迭。反过来该用的时候也别犹豫。如果你发现自己正在为“整体/部分层次结构”反复写类型分支而且每加一种节点都要改一遍遍历逻辑那就停下来想想组合模式。它也许不会让你的程序跑得更快但它能让代码结构变清晰让后续扩展变得安全——这正是工程价值的落脚点。学完这一篇可以自己动手做一个“表达式树计算器”或者“UI 控件树”把组合模式的增删、遍历、深拷贝都练一遍。练到不看示例也能把实现写出来这个模式就是真正属于你的东西了。