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

Question

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

这意味着这个 Openlist 需要支持两种类型的操作:

1. 自动排序
2. 查找节点(通过其 ID)

这里的问题是Openlist会按照cost值排序，而查找需要根据邻居节点(相邻节点)的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等是“单一用途”或“原始”容器。每一种容器都具有一定的、独特的属性，将它们与其他容器区分开来；否则，当然就没有理由首先拥有所有这些容器。

std::set 的目的就是按值查找容器中的值，并且只存储集合中唯一的值，就是这样。

一个std::set与其他关联容器一样，允许您指定一个可选的比较器类，该类实际上指定容器中每个实际值的“值”的含义。实际上，您已经通过定义仅 f 来做到这一点。您的成员(member)astar_node类对于定义集合包含的内容很重要。 astar_node 的所有其他成员的所有其他值被忽略。

完成后，就是这样，直到 std::set被关注到。该集合可以通过astar_node::f查找，就是这样。这是在集合中查找某些内容的唯一方法。

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

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

很好:

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()返回 openlist_t 中新元素的迭代器。您将获得插入的 astar_node 的迭代器。获取这个迭代器，并将其放入 OpenList_by_id ， key 是 id .

现在，当您想在 OpenList 中查找某些内容时给出 id ，使用映射查找迭代器，然后取消引用它。问题解决了。

另外:

1. remove ()ing astar_node来自std::set还需要从 OpenList_by_id 中删除其迭代器查找 map 。

2. 自 std::set包含唯一值，您需要处理 astar_node 的情况与相同的f集合中已存在，并适当处理这种情况。