c++ - deleteMin 和按键操作搜索的有效数据结构

Question

我有100组A对象，每组对应一个查询点Qi，1 <= i <= 100 .

class A {
    int id;
    int distance;
    float x;
    float y;
}

在我的算法的每次迭代中，我选择一个查询点 Qi 并从相应的集合中提取具有最小距离值的对象。然后，我必须在所有 100 个集合中找到这个特定对象，使用它的 ID 进行搜索，然后删除所有这些对象。

如果我为每组对象使用一个堆，那么用 MIN(distance) 提取对象的成本很低。 .但是，我将无法在使用 id 搜索的其他堆中找到相同的对象，因为堆是用距离值组织的。此外，更新堆的成本很高。

我考虑过的另一个选择是使用 map<id, (distance, x, y)>对于每组。这种通过 id 搜索(查找操作)的方式很便宜。然而，提取具有最小值的元素需要线性时间(它必须检查 map 中的每个元素)。

是否有任何我可以使用的数据结构对我需要的两种操作都有效？

• extract_min(距离)
• 查找(id)

提前致谢!

Answer 1

std::map 或 boost::multi_index