std :: sort를 사용하여 종속성 트리 정렬

Question

여러 가지 플러그인을 종속성별로 정렬하여 충돌없이 선형 적으로로드 할 수있게하려고합니다. 종속성주기는 계약에 의해 제외됩니다 (정의되지 않은 동작이 발생 함).

가장자리가 잎을 향하는 깊이 2의 이진 트리를 상상해보십시오. 이것이 인공적인 의존성 트리라고합시다. 가장자리의 세트는

가 나는 우를 달성하기 위해 좌에 따라 관계를 나타내는 비교와 표준 : 종류를 사용할 수 튜플 (좌, 우)가 R.

에있는 경우 관계 R. 사실 수익률을 비교 표시한다 이?

Answer 1

나는 최근에 같은 요구 사항을 가지고있었습니다. 필자는 코드에서 데이터베이스 엔터티를 모델링하고 종속성을 매핑하여 올바른 순서로 엔터티를 만들고 파괴 할 수있는 방법이 필요했습니다.

boost::graph 라이브러리가있는 솔루션을 발견했습니다. 나는 당신이 올바른 방향으로 시작할 수 있기를 희망하면서 (실제 코드의) 스 니펫을 포함 시켰습니다. 아래의 코드에서

이 함수 create_order들이 작성해야합니다 순서로 개체의 벡터를 산출하고, 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; 
    } 

Answer 2

없음 - I 돈 그렇게 생각하지 않아.

A 
/\ 
B C 
    \ 
     D 

B 및 C가에 의존 D 지금 C.에 의존한다 :

다음 상상

1. B는 C에 의존하지 않기 때문에 B는 C. 이상인
2. C는 B에 의존하지 않으므로 C는 B보다 작지 않습니다.
3. 따라서 B "는 정렬 알고리즘과 관련하여"C "와 같습니다.
4. 마찬가지로, D "가 같은지를"B

첫번째 문제 : B = 많은 정렬 알고리즘을 혼동하기 쉽다 < D C, B = D하지만 C.

둘째, std :: sort가 사용하는 알고리즘은 지정되지 않았지만 많은 구현이 quicksort의 형식을 사용한다는 것을 알고 있습니다. Quicksort 구현은 세 개의 버킷으로 값을 분할 할 수 있습니다. 즉, 피벗보다 작은 값, 피벗보다 큰 값, 및 모두 피벗과 동등하므로 더 정렬 할 필요가 없습니다..

그런 퀵 정렬이 B를 피벗으로 선택한 경우 C와 D는 모두 지정되지 않은 순서로이 "팻 (fat) 파티션"에서 자신을 찾습니다. std :: sort는 그렇지 않습니다. 비교 함수를 사용하여 D에 대해 C를 테스트 할 수도 있습니다.