C++ STL「Association Set/Map」

Question

我正在尋找特定種類的set/map的名稱，希望這些名稱有一些現有的代碼，例如C++ STL。

致電集A。

我想運行下面的命令：

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

然後可以提出下列問題，收到的答覆表明：

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

你知不知道這樣的名字構造/集合？

您是否知道現有的C/C++實現？

Answer 1

編輯：如果你想要走額外的步驟，你應該考慮Disjoint-set Union-Find的有效實施。

不幸的是我看到的唯一明智的方法是制定一個std::map過std::sets - 你需要每次的插入查詢，這兩個元素是否在不同的子集 - 如果是這樣，你將它們合併。

因此，外部集合存儲所有元素並將它們指向它們所屬的集合。

現在，如果你添加一個新的關聯：

1. 檢查這臺做A和B屬於
2. 如果不屬於任何一組，創建一個新的集合和這兩個值映射到該集（端）
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))。

使用unordered_set/unordered_map你可能都減少O(1)攤銷。

Answer 2

一般來說，我認爲這個數據結構是一個圖形：也就是說，在你的情況下使用整數標識的一組節點和一組可能是有向節點的邊。根據您的具體需求，有很多方法來表示和圖形。 Boost有許多典型的圖形數據結構以及一系列對其進行操作的算法。

根據評論中的一些說明：is_associated()操作是無向圖中的路徑搜索。根據圖形的需要，可以添加邊來表示數據結構，使得is_associated()是以插入花費線性時間爲代價的恆定時間。