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()是以插入花费线性时间为代价的恒定时间。