C++ legen Sie fest, wie ein Set nach Wert sortiert und nach Schlüssel

Question

Ich implementiere A* kürzester Weg Algorithmus. Der Openlist-Teil speichert alle Knoten, die besucht werden. Die Liste ist wie eine Prioritätswarteschlange, bei der das erste Element den Mindestkostenwert hat. Daher wird in jeder Iteration nur das erste Element angezeigt und aufgerufen. Aber innerhalb der Iteration müssen wir die Nachbarn dieses Knotens durchlaufen und prüfen, ob der Nachbar in Openlist ist.

Das heißt also, diese Openlist zwei Arten von Operationen unterstützen muss:

1. automatische Sortierung
2. einen Knoten suchen (durch seine ID)

Das hier Problem ist, dass Openlist wird Nach dem Kostenwert sortieren, während das Nachschlagen auf der ID des Nachbarknotens (der benachbarten Knoten) basieren muss. Also überlegte ich, set zu verwenden, wo die Elemente die Knoten sind. Aber ich weiß nicht, wie man ein Element nach seiner ID in diesem Set sucht.

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++ Container, wie std::set, std::map, std::list und std::vector und andere, werden als "Einzweck" oder "primitive" Container. Jeder hat bestimmte, einzigartige Eigenschaften, die sie von anderen Behältern unterscheiden; Sonst gäbe es natürlich keinen Grund, alle diese Container an erster Stelle zu haben.

Der Zweck einer std::set ist es, die Werte im Container nach Wert zu suchen, und nur eindeutige Werte in der Menge zu speichern, das ist es.

Eine std::set ermöglicht Ihnen, wie andere assoziative Container, eine optionale Vergleichsklasse anzugeben, die genau angibt, was der "Wert" für jeden tatsächlichen Wert im Container bedeutet. Und Sie haben das getan, indem Sie in der Tat festgelegt haben, dass nur das f Mitglied Ihrer astar_node Klasse für die Definition des Sets von Bedeutung ist. Alle anderen Werte aller anderen Elemente von astar_node werden ignoriert.

Sobald das erledigt ist, ist es soweit, was die std::set betrifft. Das Set kann von astar_node::f nachgeschlagen werden, und das war's. Nur so kann man etwas im Set finden.

Wie ich am Anfang sagte, sind std::set und andere, "primitive" Container, und manchmal brauchen Sie etwas ein wenig raffinierter, als hier der Fall ist. In diesem Fall können Sie mehrere Container verwenden und sie so kombinieren, dass das gewünschte Ergebnis erzielt wird. Es gibt kein Gesetz gegen die Verwendung von mehr als einem Container, um einen einzelnen Datensatz zu speichern. Es gibt kein Gesetz, das besagt, dass Sie einen einzelnen Container verwenden müssen, um mit einer bestimmten Datensammlung alles zu tun, was Sie tun müssen.

Hier, wie ich es verstehe, müssen Sie auch eine astar_node im Set durch den id Wert finden können.

Fein:

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

openlist_t Openlist; 

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

Nachdem Sie insert() ein neues astar_node in Ihr OpenList, insert() im openlist_t einen Iterator für das neue Element zurückgibt. Sie erhalten den Iterator für die eingefügte astar_node. Nimm diesen Iterator und lege ihn in OpenList_by_id, wobei der Schlüssel der id ist.

Nun, wenn Sie etwas in OpenList mit einem id finden möchten, verwenden Sie die Karte, um den Iterator zu finden, dann dereferenzieren. Problem gelöst.

Zusätzlich:

1. remove() auch ein astar_node vom std::set ing erfordert seinen Iterator aus der OpenList_by_id Lookup Karte zu entfernen.

2. Da ein std::set eindeutige Werte enthalten, müssen Sie die Situation behandeln, wo ein astar_node mit den gleichen f bereits in der Menge vorhanden ist, und diese Situation entsprechend zu behandeln.