stl地圖中的後序遍歷

Question

我在gcc comper上使用stl map，它使用樹來存儲鍵值對。 迭代器以無序方式前進，所以遍歷非常簡單。 但是我的輸出要求之一是後序遍歷。 我一直專門使用地圖。 有什麼辦法可以完成它嗎？

Answer 1

正如Steve Jessop所說的Map是由C++提供的抽象數據結構，你不能以任何順序改變存儲在map中的元素的順序，就像我們在Tree或AVL中通過前/後/按順序遍歷一樣。 但您可以使用std::greater作爲您的密鑰而不是std::less來反轉存儲順序。

例如

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

或 箱子一個矢量desiredOrder，這將保持插入在地圖的順序Trac的，一旦你與插入做只是做任何你想要的排序操作前/後/爲了在desiredOrder矢量並使用循環，你可以遍歷矢量，採用矢量值作爲你的地圖

如

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

沒有標準的方式來訪問std::map實例的「實際樹結構」。

此外，標準不知道（或護理）究竟是如何一map的元素被佈置在地圖上可以使用任何內部樹。紅黑樹和AVL樹都是std::map的有效實現，並且您將得到不同的事後使用的後序遍歷。在實踐中，我期望它總是R-B或非常相似，但實現自由通知標準定義的接口。

總之，std::map不是一棵樹，它是一個抽象的數據結構，可以（並且）使用樹來實現。

它可能會破解一個特定的實現，但可能最好不要。如果您希望數據的樹狀結構成爲程序定義狀態的一部分，則可以編寫自己的樹。