std :: map:返回由具有相同值的键组成的向量

Question

我有一个std::map对象.键是实体ID(整数)并且它们的2D位置(向量)的值.目的是确定哪些实体处于相同的位置.

ID  Position
1   {2,3}
5   {6,2}
12  {2,3}
54  {4,4}
92  {6,2}

我需要得到一个由键组成的向量矢量,它们具有相同的值.

以上示例输入数据的输出:{1,12},{5,92}

我知道我可以将2D位置复制到向量矢量并循环第一级向量以找到相等的第二级向量的索引.然后通过索引选择向量并再次循环查找相应的键来返回查找键.

请为此建议更清洁的方法.

Answer 1

要点std::map是为值映射提供有效的关键.您需要的是键映射的附加值 - 可以通过多种方式实现:

• 有一个额外的std::map,从去Position到std::vector<ID>.

• 使用某种空间分区数据结构(例如,四叉树,空间散列,网格),可以根据位置有效地查找实体.

• 使用双向多图类似boost::bimap.这将允许您在值集合上进行双向映射,而无需使用多个数据结构.

"我该如何选择？"

这取决于你的优先事项.如果你想要最大的性能,你应该尝试所有的方法(可能使用某种模板化的包装)和配置文件.如果你想要优雅/清洁,boost::bimap似乎是最合适的解决方案.