c++ - 使用 ranges-v3 实现 DFS

Question

我对使用 range-v3 构建和查询线性四叉树数据结构很感兴趣。我已经能够成功地使用 range-v3 使用库中的现有 View 构建线性四叉树数据结构。我很高兴能够将查询逻辑表达为 View 适配器，因为您可以通过推进派生范围的 RandomAccessIterator 来遍历四叉树中的节点，这有助于方便地将查询行为与四叉树的结构分开。

我的 View 适配器只有一个参数:一个用户定义的 lambda 谓词函数，用于评估节点并确定是进入还是退出。进入导致评估子节点，而退出导致访问下一个兄弟节点(或可能是该节点的父节点的下一个兄弟节点)，直到叶节点被成功评估或我们通过根节点“退出”。 (您可以将其视为 DFS 模式。)

因此，我们能够根据 RandomAccessIterator(来自派生范围)和 Sentinel(与另一个迭代器相对)定义此范围。

下面是一些显示整体结构的精简代码。 (如果缺少成员数据/结构，我深表歉意):

template<typename Rng, typename Fun>
class quadtree_query_view
  : public ranges::view_adaptor<quadtree_query_view<Rng, Fun>, Rng>
{
    friend ranges::range_access;

    using base_iterator_t = ranges::iterator_t<Rng>;

    ranges::semiregular_t<Fun> fun;
    uint tree_depth;

    struct query_termination_adaptor : public ranges::adaptor_base
    {
        query_termination_adaptor() = default;
        query_termination_adaptor(uint tree_depth) : tree_depth(tree_depth) {};

        uint tree_depth;

        uint end(quadtree_query_view const&) {
            return tree_depth;
        }
    };

    struct query_adaptor : public ranges::adaptor_base
    {
        query_adaptor() = default;
        query_adaptor(ranges::semiregular_t<Fun> const& fun) : fun(fun) {};

        ranges::semiregular_t<Fun> fun;

        bool exited = false;
        uint current_node_depth = 0;

        base_iterator_t begin(quadtree_query_view const& rng) {
            return ranges::begin(rng.base());
        }

        // TODO: implement equal?
        // TODO: implement empty?

        auto read(base_iterator_t const& it) const 
        {
            return *it; // I'm not concerned about the value returned by this range yet.
        }

        CONCEPT_REQUIRES(ranges::RandomAccessIterator<base_iterator_t>())
        void next(base_iterator_t& it ){
            if (fun(*it)) { // Step in
                // Advance base iterator (step in)
                // Increment current_node_depth
            } else {  // Step out
                // Advance base iterator (step out)
                // Set "exited = true" if stepping out past root node.
                // Decrement current_node_depth
            }
        }
    };

public:
    quadtree_query_view() = default;

    quadtree_query_view(Rng&& rng, uint tree_depth, Fun fun)
      : quadtree_query_view::view_adaptor{std::forward<Rng>(rng)}
      , tree_depth(tree_depth)
      , fun(std::move(fun))
    {}

    query_adaptor begin_adaptor() const {
        return {std::move(fun)};
    }

    query_termination_adaptor end_adaptor() const {
        return {tree_depth};
    }
};

我正在尝试找出完成此实现的最后几个步骤:

• 我的范围不满足 Range 概念，因为 WeaklyEqualityComparable 要求没有为我的迭代器/哨兵对实现。继续执行此操作的最佳方法是什么？

• 是否需要为 query_adaptor 实现 equal 成员方法？两个迭代器参数分别对应什么？

• 我假设我需要为 query_adaptor 实现 empty 成员方法。这是查询退出条件逻辑的去向吗？根据文档，段参数需要是与哨兵关联的类型。这是否与 query_termination_adaptor::end() 返回的类型相同，例如 uint？或者这是否需要是另一种类型？

感谢您分享任何见解。看到范围被合并到 C++20 中，我真的很兴奋!

Answer 1

啊。

我能够使用 default_sentinel 解决我的问题。由于 query_adaptor 意味着从根节点开始并在一个方向上迭代，我可以一起删除 end_adaptor 和 query_termination_adaptor。我只需要为适配器实现一个 bool equal(default_sentinel) const { ... } 方法，我就可以确定是否满足查询退出条件。

我仍然不确定为什么尝试实现自定义哨兵类型会给我带来问题。但是，除了拥有 tree_depth 之外，它没有提供任何超过 default_sentinel 的附加功能。