c++ - 使用 std::sort 对依赖树进行排序

Question

我想根据插件之间的依赖关系对一堆插件进行排序，这样我就可以线性加载它们而不会发生任何冲突。契约(Contract)排除了依赖循环(导致未定义的行为)。

想象一棵深度为 2 的二叉树，它的边指向叶子。让它成为一个人工依赖树。边集表示关系 R。如果元组 (lhs, rhs) 在 R 中，比较返回真。

我能否将 std::sort 与表示关系 rhs 取决于 lhs 的比较一起使用来实现此目的？

Answer 1

我最近也有同样的需求。我在代码中对数据库实体进行建模，需要一种映射依赖关系的方法，以便可以按正确的顺序创建和销毁实体。

我找到了一个使用 boost::graph 库的解决方案。我包含了一个(真实代码的)片段，希望它能帮助您朝着正确的方向开始。

在下面的代码中，函数 create_order 按照必须创建的顺序生成实体 vector ，而 drop_order 则相反(最依赖的实体最先出现):

    using edge = std::pair<std::size_t, std::size_t>;
    using edge_vector = std::vector<edge>;

    using graph_properties = boost::property<
    boost::vertex_color_t,
    boost::default_color_type
    >;

    typedef boost::adjacency_list<boost::vecS, boost::vecS,
    boost::bidirectionalS,
    graph_properties
    > Graph;
    typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;

    struct cycle_detector : public boost::dfs_visitor<>
    {
        cycle_detector( edge_vector& back_edges)
        : _back_edges(back_edges)
        { }

        void back_edge(const boost::graph_traits<Graph>::edge_descriptor& e, const Graph&) const {
            _back_edges.emplace_back(e.m_source, e.m_target);
        }
    protected:
        edge_vector& _back_edges;
    };


    auto generate_graph() const {
        Graph g(std::begin(_edges), std::end(_edges), _entities.size());
        return g;
    }

    void check_cycles(const Graph& g) const
    {
        edge_vector back_edges;
        cycle_detector vis(back_edges);
        boost::depth_first_search(g, visitor(vis));

        if (back_edges.size())
        {
            std::ostringstream ss;
            ss << "cyclic dependency detected. Back edges are:\n";
            for (auto& p : back_edges)
            {
                ss << value::debug::demangle(typeid(_entities[p.first].get()))
                << " <<==>> "
                << value::debug::demangle(typeid(_entities[p.second].get()))
                << std::endl;
            }
            throw std::logic_error(ss.str());
        }
    }

    auto create_order() const {
        using namespace boost;

        auto g = generate_graph();
        check_cycles(g);

        std::vector<std::size_t> result_order;
        vector_type result;

        boost::topological_sort(g, std::back_inserter(result_order));
        std::transform(std::begin(result_order), std::end(result_order),
                       std::back_inserter(result), [this](auto i) {
                           return _entities[i];
                       });

        return result;
    }

    auto drop_order() const {
        auto result = create_order();
        std::reverse(std::begin(result), std::end(result));
        return result;
    }