'Disjoint Sets'에서 모든 요소의 목록을 얻는 방법

Question

내 문제는 요소 (클래스 요소)가 많습니다. 1000 개 요소가 있다고 가정 해보십시오. 이 요소들은 처음에는 연관성이 없으므로 자체 집합에 포함됩니다.

나중에 내 프로그램 흐름을 기반으로 이러한 집합 중 일부를 병합하려면 통합 작업을 사용해야합니다. 부스트 라이브러리의 disjoint_set (http://www.boost.org/doc/libs/1_57_0/libs/disjoint_sets/disjoint_sets.html)을 사용할 계획입니다.

제 질문은 어떻게 세트를 대표하는 집합에 요소를 나열 할 수 있습니까?

disjoint_set은 그러한 작업을위한 최상의 데이터 구조입니다. 그래서 다른 것을 사용하는 방법을 조사해야합니까?

Answer 1

산문 설명을 통해 세트가 실제로 그래프를 형성한다는 정보를 얻지 못했습니다. 당신이 원하는 모든 세트와 연관 ​​요소 인 경우

, 나는 좋을 것

std::map<ElementId, SetId> 

(당신이 포인터가 유효 체류 알고 있다면 어디 ElementId 단순히 Element* 될 수있다).

당신이 효율적으로

bimap<Element, bimaps::multiset_of<SetId> > 

이 후보가 될 것입니다 역을 조회 할 수있게하려면

. Coliru에 라이브 데모를 참조하십시오 Coliru 아래로 보인다

300 - Element(1) 
300 - Element(2) 
300 - Element(4) 

---

가 ¹

#include <boost/range/iterator_range.hpp> 
#include <boost/bimap/multiset_of.hpp> 
#include <boost/bimap.hpp> 
#include <iostream> 

using namespace boost; 

int main() { 
    using Element = int; // for simplicity :) 
    using SetId = int; 
    using Sets = bimap<Element, bimaps::multiset_of<SetId> >; 

    Sets sets; 
    sets.insert({ Element(1), 300 }); 
    sets.insert({ Element(2), 300 }); 
    sets.insert({ Element(3), 400 }); 
    sets.insert({ Element(4), 300 }); 

    // give us set #300 
    for (auto& e : make_iterator_range(sets.right.equal_range(300))) 
     std::cout << e.first << " - Element(" << e.second << ")\n"; 
} 

인쇄

을 ¹. 나중에 추가 할 것입니다