C++ STL "Association Set/Map"

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_associated() 操作是无向图中的路径搜索。根据图形的需要，可以添加边来表示数据结构，这样 is_associated() 是常数时间，但插入成本是线性时间。