C ++设置如何按值对集合进行排序并按键搜索

Question

我正在实施 A* 最短路径算法。 Openlist 部分存储所有将要访问的节点。该列表就像一个优先级队列，第一个元素具有最小成本值，因此在每次迭代中，我们只弹出第一个元素并访问它。但是在迭代内部，我们需要遍历该节点的邻居并检查邻居是否在 Openlist 中。

也就是说这个Openlist需要支持两种类型的操作：

自动排序
查找节点（通过其 ID）

这里的问题是Openlist会按照cost value排序，而look up需要根据邻居节点（adjacent nodes）的ID。所以我正在考虑使用集合，其中元素是节点。但是我不知道如何在这个集合中通过它的ID来查找一个元素。

struct astar_node
{
    string id;
    double f;  //estimated cost;
    double g;  //distance from source to this node;
    double h;  //heuristic cost from this node to target;
};  

struct openlist_compare
{
    bool operator()(const astar_node &node1, const astar_node &node2 ){
           return node1.f < node2.f ;
    }
};

std::set<astar_node, openlist_compare> Openlist;

Answer 1

C++ 容器，如 std::set、std::map、std::list 和 std::vector 等，是 "single purpose" 或 "primitive"容器。每个容器都有某些独特的属性，可以将它们与其他容器区分开来；否则当然没有理由首先拥有所有这些容器。

a std::set 的目的是按值查找容器中的值，并仅存储集合中的唯一值，仅此而已。

A std::set，与其他关联容器一样，允许您指定一个可选的比较器 class，它实际上指定 "value" 的含义，对于每个实际值容器。你已经做到了，实际上，定义只有 astar_node class 的 f 成员对于定义集合包含的内容很重要。 astar_node 的所有其他成员的所有其他值都将被忽略。

一旦完成，就 std::set 而言就是这样。该集合可以通过astar_node::f查找，仅此而已。这是在集合中找到东西的唯一方法。

正如我在开头所说，std::set 和其他容器是 "primitive" 容器，有时您需要一些更复杂的东西，就像这里的情况一样。在这种情况下，您可以使用多个容器，并以达到预期效果的方式组合它们。没有法律禁止使用多个容器来存储一组数据。没有法律规定您必须使用一个容器来完成您需要做的所有事情，以及特定的数据集合。

这里，据我了解，你还需要能够在id值的集合中找到一个astar_node。

很好：

typedef std::set<astar_node, openlist_compare> openlist_t;

openlist_t Openlist;

std::map<std::string, openlist_t::iterator> OpenList_by_id;

在你 insert() 一个新的 astar_node 到你的 OpenList 之后，insert() returns openlist_t 中的新元素的迭代器.您将获得插入的 astar_node 的迭代器。拿这个迭代器，把它放到 OpenList_by_id 中，键是 id.

现在，如果您想在给定 id 的 OpenList 中查找内容，请使用映射来查找迭代器，然后取消引用它。问题已解决。

此外：

remove() 从 std::set 中获取 astar_node 也需要从 OpenList_by_id 查找映射中删除它的迭代器。
由于std::set包含唯一值，需要处理集合中已经存在具有相同f的astar_node的情况，并处理这种情况恰到好处。

C ++设置如何按值对集合进行排序并按键搜索

C++ set how to sort a set by value and search by key

c++

a-star

set