C++ STL "Association Set/Map"

Question

나는 C++ STL과 같은 기존 코드가있는 특정 종류의 set/map의 이름을 찾고 있습니다.

A으로 전화하십시오.

나는 다음과 같은 명령을 실행하려는

:

A.is_associated(3,5) -> True 
A.is_associated(5,10) -> True 
A.is_associated(10,3) -> True 
A.is_associated(4,10) -> False 

당신은 이런 종류의 이름을 알고 있나요 : 답변이 표시된 수신

A.associate(3,5) 
A.associate(3,6) 
A.associate(6,8) 
A.associate(8,10) 
A.associate(4,9) 

을 그리고 다음과 같은 질문을 할 수 구성/집합?

기존 C/C++ 구현이 있는지 알고 계십니까?

Answer 1

편집 : 추가 단계로 이동하려면 Disjoint-set Union-Find의 효율적인 구현에 대해 고려해야합니다.

불행히도 내가 볼 수있는 유일한 정상적인 방법은 을 std::sets 이상으로 만드는 것입니다. 삽입 할 때마다 두 요소가 다른 하위 집합에 있는지 여부를 확인해야합니다. 그렇다면 병합합니다.

그래서 바깥 쪽 집합은 모든 요소를 ​​저장하고 속한 집합을 가리 킵니다.

1. 검사에 대한 집합에 속하는하지 둘, 새로운 세트를 만들고 해당 세트에 두 값을 매핑 할 경우 (A와 B는
2. 에 속하는 할 설정 : 새 연결을 추가 할 경우 지금

   end)

3. 두 세트가 다른 세트에 속해 있으면 세트를 병합하고 요소를 업데이트 할 때 하나가 세트에 속하고 다른 세트가 없으면 다른 세트를 첫 세트에 넣고 거기에 매핑하십시오 (끝)
4. 그에 따라 매핑.

이제 is_associated 함수는 매우 빠릅니다. 두 요소가 같은 세트에 속하는지 확인하십시오. 영어

: 어쩌면이 같은

typedef std::map< int, std::set<int>& > assoc_set; // note that you need to 
       // store the sets somewhere else, maybe in another set 

뭔가 :

class assoc_set 
{ 
    typedef std::set<int> int_set; 
    typedef std::set<int_set> int_set_set; 
    typedef std::map< int, int_set_set::iterator > set_map; 
public: 
    void associate(int a, int b) 
    { 
     set_set_map::iterator ia = iss.find(a); 
     set_set_map::iterator ib = iss.find(b); 
     if (ia == set_set_map::end()) 
     { 
      if (ib == set_set_map::end()) 
      { 
       // create new 
       int_set ab; 
       ab.insert(a); 
       ab.insert(b); 
       int_set_set::iterator r = iss.insert(ab).second; 
       smap[a] = r; 
       smap[b] = r; 
      } 
      else 
      { 
       // add to a 
       smap[a] = ib; 
       ib->insert(a); 
      } 
     } 
     else 
     { 
      if (ib == set_set_map::end()) 
      { 
       // add to b 
       smap[b] = ia; 
       ia->insert(b); 
      } 
      else 
      { 
       // merge 
       ia->insert(ib->begin(), ib->end()); 
       // this could be done better 
       for (int_set::iterator i = it->begin(); i != it->end(); ++i) 
       { 
        smap[*i] = ia; 
       } 

      } 

     } 


    } 

    bool is_associated(int a, int b) 
    { 
     set_set_map::iterator ia = iss.find(a); 
     set_set_map::iterator ib = iss.find(b); 

     return ia != set_set_map::end() && ia = ib; 
    } 

private: 
    int_set_set iss; 
    set_map smap; 
} 

오류 및 버그가있을 것입니다, 난 그냥 메모장 가능한 (그리고 어쨌든이에 너무 많은 시간을 보냈다).추가

는) O(n)이다 (그러나 간접 계층을 사용하여 (그리고 바보지도 루프를 제거하기로 O(log(n))로 감소 될 수 있습니다. 쿼리 O(log(n))입니다. 당신은 상각 O(1)에 모두 줄일 수 unordered_set/unordered_map를 사용

.

Answer 2

일반적으로이 데이터 구조는 그래프입니다. 즉, 정수를 사용하여 식별되는 노드 세트와 가능하면 노드 쌍을 지향하는 가장자리 세트입니다. 특정 요구에 따라 그래프를 표현하고 표현할 수있는 많은 방법이 있습니다. 부스트는 다수의 일반적인 그래프 데이터 구조와 함께 작동하는 알고리즘 모음을 가지고 있습니다.

설명에있는 설명에 따라 : is_associated() 작업은 무향 그래프의 경로 검색입니다. 그래프의 필요성에 따라, is_associated()이 삽입 시간의 선형 시간을 소비하는 비용으로 일정한 시간이되도록 데이터 구조를 나타 내기 위해 가장자리를 추가 할 수 있습니다.