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_associated()操作是无向图中的路径搜索.根据图形的需要,可以使用添加边来表示数据结构,这is_associated()是以插入成本计算线性时间为代价的恒定时间.