在密钥之外的其他东西上订购容器

Question

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

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

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

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

编辑：

显然不清楚 "smaller based on int value" 的含义。我的意思是我的对象有一个 public 属性（比方说 score）。对于两个对象 a 和 b，a < b 当且仅当 a.score < b.score.

我希望 a 和 b 放在容器中，按 score 排序。如果我尝试用 c.hash == a.hash 插入 c，我希望插入失败。

Answer 1

您可以使用 stl 类型 priority_queue。如果您的元素是整数，那么您可以这样做：

priority_queue<int> q;

优先级队列在内部是用堆实现的，堆是一棵完全二叉树，其根始终是集合中的最小元素。因此，您可以通过调用 top().

在 O(1) 中进行咨询

但是，随着算法的进步，您将需要提取带有 pop() 的项目。由于是一棵二叉树，因此提取需要 O(log N)，这不是 O(1)，但这是一个非常好的时间并且它是有保证的，与预期时间相比，这是不完美的情况哈希 table 。

我不知道维护集合并在 O(1) 中提取最小值的方法。

Answer 2

使用自定义比较器和 std::set :

#include <set>
#include <string>

struct Object
{
  int value;
  long hash;

  std::string data;

  Object(int value, std::string  data) :
    value(value), data(data)
  {

  }

  bool operator<(const Object& other) const
  {
    return data < other.data;
  }

};

struct ObjComp1
{

  bool operator()(const Object& lhs, const Object& rhs) const
  {
    return lhs.value < rhs.value;
  }

};

struct ObjComp2
{

  bool operator()(const Object& lhs, const Object& rhs) const
  {
    if (lhs.value != rhs.value)
    {
      return lhs.value < rhs.value;
    }

    return lhs < rhs;
  }

};

int main()
{

  Object o1(5, "a");
  Object o2(1, "b");
  Object o3(1, "c");
  Object o4(1, "c");

  std::set<Object, ObjComp1> set;
  set.insert(o1);
  set.insert(o2);
  set.insert(o3);
  set.insert(o4);

  std::set<Object, ObjComp2> set2;
  set2.insert(o1);
  set2.insert(o2);
  set2.insert(o3);
  set2.insert(o4);

    return 0;
}

第一个变体将允许您仅插入 o1 和 o2，第二个变体将允许您插入 o1、o2 和 o3，因为您不太清楚您需要哪个。唯一的缺点是您需要为对象类型编写自己的运算符<。

或者，如果您不想为您的数据类型创建自定义运算符<，您可以包装一个 std::map > 但这不太简单

Answer 3

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

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

在密钥之外的其他东西上订购容器

Ordering a container on something else than the key

c++

containers

c++11