C++设置如何按值排序集和按键搜索

Question

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

因此，这意味着这Openlist需要支持两种操作：

1. 自动分拣
2. 查找一个节点（通过其ID）

这里的问题是，Openlist会按成本值排序，而查找需要基于邻居节点（相邻节点）的ID。所以我正在考虑使用set，其中的元素是节点。但是我不知道如何通过它在这个集合中的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的目的是按值查找容器中的值，并且只在该集中存储唯一值，就是这样。

A std::set与其他关联容器一样，允许您指定一个可选的比较器类，它实际上指定容器中每个实际值的“值”的含义。而且你已经这样做了，实际上，只是定义你的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，关键是id。

现在，当您想在OpenList中找到id中的内容时，请使用该映射来查找迭代器，然后对其进行解引用。问题解决了。

此外：

1. remove（）荷兰国际集团从std::set一个astar_node也将需要从OpenList_by_id查找图中除去它的迭代器。

2. 由于std::set包含唯一值，因此需要处理集合中已存在具有相同f的astar_node并适当处理这种情况的情况。