引言
本文使用示例程序和范围来改进C ++中的树遍历的惰性实现，该示例改进了Qt框架中用于处理QObject类的子级的接口的示例。 将详细考虑创建用于处理子元素的自定义视图，并给出惰性和经典实现。 在文章的结尾，有一个到库的链接以及完整的源代码。
关于作者
我在The Qt Company挪威办事处担任高级开发人员。 我一直在开发小部件和QtQuick元素，最近是Qt Core。 我使用C ++，并且对函数式编程有些兴趣。 有时我做报告并写文章。
什么是Qt
Qt是用于创建图形用户界面（GUI）的跨平台框架。 除了用于创建GUI的模块之外，Qt还包含许多用于开发应用程序软件的模块。 该框架主要是用C ++编程语言设计的，某些组件使用QML和JavaScript 。
QObject类别
QObject是围绕其构建Qt对象模型的类。 从QObject继承的类可以在时隙信号模型和事件循环中使用。 此外， QObject允许您访问元对象类信息并将对象组织成树形结构。
QObject树结构
使用树结构意味着每个QObject对象可以具有一个父对象和零个或多QObject对象。 父对象控制子对象的生存期。 在以下示例中，两个孩子将被自动删除：
auto parent = std::make_unique<QObject>(); auto onDestroyed = [](auto obj){ qDebug("Object %p destroyed.", obj); }; QObject::connect(new QObject(parent.get()), &QObject::destroyed, onDestroyed); QObject::connect(new QObject(parent.get()), &QObject::destroyed, onDestroyed);
不幸的是，到目前为止，大多数Qt API仅适用于原始指针。 我们正在为此努力，也许很快情况至少会部分改善。
QObject类接口允许您获取所有子对象的列表并按某些条件进行搜索。 考虑获取所有子对象列表的示例：
auto parent = std::make_unique<QObject>();
QObject::children方法返回给定对象的所有子项的列表。 但是，通常需要根据某些条件在对象的整个子树中进行搜索：
auto children = parent->findChildren<QObject>(QRegularExpression("0$")); qDebug() << children.count();
上面的示例演示了如何获取名称以0结尾的QObject类型的所有子元素的列表。与children方法不同， findChildren方法以递归方式遍历树，即在对象的整个层次结构中进行搜索。 可以通过传递Qt::FindDirectChildrenOnly来更改此行为。
使用子元素的界面的缺点
乍一看，似乎与孩子一起工作的界面是经过深思熟虑且灵活的。 但是，他并非没有缺陷。 让我们考虑其中的一些：
- 冗余接口
有两种不同的findChildren方法（不久前有三种）：用于查找一项的findChild方法和children方法。 它们全部部分重叠。 - 界面很难改变
Qt在单个主要版本中保证二进制兼容性和源代码级别的兼容性。 因此，您不能仅更改方法的签名或添加新方法。 - 界面难以扩展
除了违反兼容性之外，例如，不可能根据指定的标准获得子元素列表。 要添加此功能，必须等待下一个版本或创建其他方法。 - 过度复制所有项目
通常，您只需要浏览按给定条件过滤的所有子元素的列表。 为此，不必返回指向所有这些元素的指针的容器。 - 可能违反SRP
这是一个颇具争议的问题，但是，需要更改类接口以进行更改，例如，遍历子级的方法看起来很奇怪。
使用range-v3修复一些缺陷
range-v3是一个库，提供用于处理元素范围的组件。 实际上，这是经典迭代器之上的另一层抽象，它使您可以编写操作并利用惰性计算。
之所以使用第三方库，是因为在编写本文时，作者尚不知道具有对此功能的内置支持的编译器。 情况可能很快就会改变。
对于QObject使用这种方法将使我们能够从类中分离遍历子元素树的操作，并根据给定的条件创建一个灵活的接口来搜索对象，可以轻松地对其进行修改。
Ranges-v3示例
首先，考虑一个使用库的简单示例。 在继续该示例之前，我们为命名空间引入了简化的表示法：
namespace r = ranges; namespace v = r::views; namespace a = r::actions;
现在考虑一个程序示例，该程序以相反的顺序打印间隔[1，10）中所有奇数的多维数据集：
auto is_odd = [](int n) { return n % 2 != 0; }; auto pow3 = [](int n) { return std::pow(n, 3); };
应该注意的是，所有计算都是延迟进行的，即 临时数据集不会创建或复制。 上面的程序与此等效，除了格式化输出：
从上面的示例可以看到，该库使您可以优雅地编写各种操作。 在range-v3存储库的tests和examples目录中可以找到更多用法示例。
代表一系列孩子的类
range-v3库提供了用于创建各种自定义包装器类的帮助器类。 其中包括view类别中的类。 这些类旨在以某种方式表示元素序列，而无需转换和复制序列本身。 在前面的示例中， filter类用于仅考虑序列中与指定条件匹配的那些元素。
要创建用于QObject子元素的此类，必须从辅助类ranges::view_facade继承它：
namespace qt::detail { template <class T = QObject> class children_view : public r::view_facade<children_view<T>> {
值得注意的是，该类会自动定义end_cursor方法，该方法返回序列结尾的符号。 如有必要，可以重写此方法。
接下来，我们定义游标类本身。 这既可以在children_view类内部也可以在其他范围内完成：
struct cursor {
上面定义的光标是单次通过。 这意味着序列只能在一个方向上移动一次。 对于此实现，这不是必需的，因为 我们存储了所有子对象的序列，并且可以按任意方向多次遍历它们。 为了表明您可以多次执行一个序列，必须在游标类中实现以下方法：
auto equal(const cursor &that) const { return current_index == that.current_index; }
现在，您需要添加以确保所创建的视图可以包含在合成中。 为此，请使用辅助功能ranges::make_pipeable ：
namespace qt { constexpr auto children = r::make_pipeable([](auto &&o) { return detail::children_view(o); }); constexpr auto find_children(Qt::FindChildOptions opts = Qt::FindChildrenRecursively) { return r::make_pipeable([opts](auto &&o) { return detail::children_view(o, opts); }); } }
现在您可以编写以下代码：
for (auto &&c : root | qt::children) {
实现现有的QObject类功能
在实现演示文稿类之后，您可以轻松实现与孩子一起工作的所有功能。 为此，您需要实现三个功能：
namespace qt { template <class T> const auto with_type = v::filter([](auto &&o) { using ObjType = std::remove_cv_t<std::remove_pointer_t<T>>; return ObjType::staticMetaObject.cast(o); }) | v::transform([](auto &&o){ return static_cast<T>(o); }); auto by_name(const QString &name) { return v::filter([name](auto &&obj) { return obj->objectName() == name; }); } auto by_re(const QRegularExpression &re) { return v::filter([re](auto &&obj) { return re.match(obj->objectName()).hasMatch(); }); } }
作为使用示例，请考虑以下代码：
for (auto &&c : root | qt::children | qt::with_type<Foo*>) {
中间结论
可以通过代码判断，在不更改类接口的情况下扩展功能非常简单。 此外，所有操作均由单独的功能表示，并可以按所需顺序排列。 这尤其可以提高代码的可读性，并避免在类接口中使用带有多个参数的函数。 还值得注意的是，类接口的卸载和更改它的原因有所减少。
实际上，此实现已经消除了几乎所有列出的接口缺点，除了我们仍然必须将所有子项都复制到容器之外。 解决此问题的一种方法是使用协程。
使用协程的对象树遍历的延迟实现
协程（协程）使您可以暂停功能并在以后恢复它。 您可以将此技术视为某种有限状态机。
在撰写本文时，标准库缺少舒适使用协程的许多重要元素。 因此，建议使用第三方cppcoro库，该库很可能以一种或另一种形式输入标准。
首先，我们将编写函数以按需返回下一个子级：
namespace qt::detail { cppcoro::recursive_generator<QObject*> takeChildRecursivelyImpl( const QObjectList &children, Qt::FindChildOptions opts) { for (QObject *c : children) { if (opts == Qt::FindChildrenRecursively) { co_yield takeChildRecursivelyImpl(c->children(), opts); } co_yield c; } } cppcoro::recursive_generator<QObject*> takeChildRecursively( QObject *root, Qt::FindChildOptions opts = Qt::FindChildrenRecursively) { if (root) { co_yield takeChildRecursivelyImpl(root->children(), opts); } } }
co_yield指令将值返回到调用代码并暂停协程。
现在，将此代码集成到children_view类中。 以下代码仅显示已更改的元素：
游标也必须被修改：
template <class T> struct children_view<T>::cursor { cppcoro::recursive_generator<QObject*>::iterator it; decltype(auto) read() const { return *it; } void next() { ++it; } auto equal(ranges::default_sentinel_t) const { return it == cppcoro::recursive_generator<QObject*>::iterator(nullptr); } explicit cursor(cppcoro::recursive_generator<QObject*>::iterator it): it(it) {} cursor() = default; };
这里的游标只是充当常规迭代器的包装。 其余代码可以按原样使用，而无需进行其他更改。
懒树走的危险
值得注意的是，懒惰地遍历儿童树并不总是安全的。 这主要涉及绕过图形元素（例如，小部件）的复杂层次结构。 事实是，遍历过程中可以重建层次结构，并且某些元素可以完全删除。 如果在这种情况下使用懒惰的解决方法，则可能会导致程序非常有趣且不可预测的结果。
这意味着在某些情况下将所有元素复制到容器中很有用。 为此，您可以使用以下帮助器功能：
auto children = ranges::to<std::vector>(root | qt::children);
严格来说，在这种情况下，无需使用协程，并且可以使用第一次迭代中的视图。
它会在Qt中吗
也许可以，但是在下一个版本中不会。 这有几个原因：
- 下一个主要版本Qt 6将正式要求并支持C ++ 17，但不会更高。
- 没有第三方库，无法实现它。
- 适应现有的代码库将相对困难。
作为Qt 7版本的一部分，他们很可能会回到此问题。
结论
提议的遍历子元素树的实现方式可以轻松添加新功能。 由于操作的分离，因此可以编写更干净的代码并从类接口中删除不必要的元素。
值得注意的是，两个使用的库（range-v3和cpp-coro）均作为头文件提供，从而简化了构建过程。 将来，完全有可能没有第三方库。
但是，所描述的方法具有一些缺点。 其中，可以注意到许多开发人员的语法不寻常，实现的相对复杂性和惰性，这在某些情况下可能很危险。
选配
源代码
特别感谢Misha Svetkin（ Trilla ）对项目实施和讨论的贡献。