C++ STL“关联集/映射”

Question

我正在寻找特定类型的集合/映射的名称，希望有一些现有代码，例如 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

一般来说，我认为这个数据结构是一个图：也就是说，在您的情况下使用整数标识的一组节点，以及一组可能是有向节点对的边。根据您的具体需求，有多种表示方法和图表。 Boost有许多典型的图数据结构以及在它们上运行的算法集合。

基于评论中的一些说明： is_linked() 操作是无向图中的路径搜索。根据图的需要，可以添加边来表示数据结构，使得 is_linked() 是常数时间，但代价是插入线性时间。

Answer 2

编辑：如果您想采取额外的步骤，您应该考虑有效实施不相交集并查。

不幸的是，我看到的唯一明智的方法是在 std::sets 上创建 std::map ——你需要每次插入时检查这两个元素是否在不同的子集——如果是这样，则将它们合并。

因此，外部集合存储所有元素并将它们指向它们所属的集合。

现在，如果您添加一个新关联：

1. 检查 A 和 B 属于哪个集合（
2. 如果两者都不属于任何集合），则创建一个新集合并将两个值映射到该集合（结束）
3. （如果一个属于集合而另一个不属于集合） t，将另一个放入第一个集合并将其映射到那里（结束）
4. 如果两者属于不同的集合，则合并集合并相应地更新元素映射。

现在 is_linked 函数非常快——只需检查两个元素是否属于同一集合即可。

用英语：

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) 摊销。