Postorder traversal in stl Karte

Question

Ich verwende eine STL-Map auf GCC-Comper, die einen Baum verwendet, um Schlüssel, Wert-Paare zu speichern. Der Iterator schreitet in einer Inorder-Mode fort, so dass die Invers-Traversierung wirklich einfach ist. Eine meiner Ausgabeanforderungen ist jedoch eine Postorder-Traversierung. Ich wurde ausdrücklich gebeten, die Karte zu verwenden. Gibt es einen Weg, um es zu erledigen?

Answer 1

Da Steve Jessop sagte Map ist die abstrakte Datenstruktur von C++ zur Verfügung gestellt, können Sie nicht die Reihenfolge der Elemente in der Map in beliebiger Reihenfolge, wie wir in Tree oder AVL durch Traversieren in pre/post/in Reihenfolge ändern können . Sie können jedoch die Reihenfolge des Speicherns umkehren, indem Sie std::greater als Schlüssel anstelle von std::less verwenden.

z.B.

std::map< std::string, int, std::greater<std::string> > my_map; 

OR Kiste ein Vektor desiredOrder, die die trac der Reihenfolge der Einfügungen in der Karte halten wird, und wenn Sie mit Einsetzen erfolgt nur tun, was Sortiervorgang Sie Pre/Post/um auf der desiredOrder Vector und mit for-Schleife können Sie den Vektor durchqueren und die Kartenelemente Zugriff auf den Vektorwert als Schlüssel für Ihre Karte mit

zB

std::vector<std::string> desiredOrder; 
std::map<std::string, int> myTree; 

myTree["A"] = 0; 
desiredOrder.push_back("A"); 
myTree["B"] = 0; 
desiredOrder.push_back("B"); 
myTree["C"] = 0; 
desiredOrder.push_back("C"); 
myTree["D"] = 0; 
desiredOrder.push_back("D"); 

/* 
Do whatever sorting you want to do here.... 
*/ 

for (int i = 0; i < desiredOrder.size(); ++i) 
{ 
    const std::string &s = desiredOrder[i]; 
    std::cout << s << ' ' << myTree[s] << '\n'; 
} 

Answer 2

Es gibt keine Standardmethode, um auf die "tatsächliche Baumstruktur" einer Instanz von std::map zuzugreifen.

Darüber hinaus weiß (oder kümmert) sich der Standard nicht genau, wie die Elemente eines map in einem internen Baum angeordnet sind, den die Karte verwenden könnte. Rot-Schwarz-Bäume und AVL-Bäume sind beide gültige Implementierungen von std::map, und Sie würden einen anderen Postorder-Traversal erhalten, der tatsächlich verwendet wird. In der Praxis erwarte ich, dass es immer R-B oder sehr ähnlich ist, aber die Implementierungsfreiheit informiert die durch den Standard definierte Schnittstelle.

Kurz gesagt, std::map ist kein Baum, es ist eine abstrakte Datenstruktur, die mithilfe eines Baumes implementiert werden kann (und wird).

Es könnte möglich sein, eine bestimmte Implementierung zu hacken, aber wahrscheinlich am besten nicht. Wenn Sie möchten, dass die Baumstruktur Ihrer Daten Teil des definierten Status Ihres Programms ist, könnten Sie vielleicht Ihren eigenen Baum schreiben.