c++ - 在 key 之外的其他东西上订购容器

Question

我目前正在尝试实现 A* 算法，但遇到了一个问题:

我想保留一组不同的对象，由散列标识(我使用了 boost::hash 和系列，但可以使用其他任何东西)并按公共(public) int 值排序，这些对象的成员。

目标是能够根据 O(1) 中的 int 值检索较小的对象，并以最有效的方式保证唯一性(散列似乎是实现该目标的好方法，但我对替代方案持开放态度)。如果满足这两个条件，我就不需要遍历容器。

是否有满足这些规范的现有实现？我的假设有误吗？我应该只扩展任何现有容器吗？

编辑:

显然不清楚“基于 int 值的更小”是什么意思。我的意思是我的对象有一个公共(public)属性(比方说 score )。对于两个对象 a和 b , a < b当且仅当 a.score < b.score .

我要a和 b装在容器中，由 score 订购.如果我尝试插入 c与 c.hash == a.hash , 我希望插入失败。

Answer 1

虽然std::priority_queue是一个适配器，但是它的Container模板参数必须满足SequenceContainer，所以不能构建一个backed通过 std::set。

看起来你最好的选择是同时维护一个集合和一个优先级队列，并使用前者来控制插入后者。将它封装到一个容器概念类中可能是个好主意，但如果您对它的使用非常本地化，您可能会使用一些方法。