stl map中的Postorder遍历

Question

我在gcc计算机上使用了一个stl映射，它使用一个树来存储键、值对。迭代器以有序的方式前进，因此有序遍历非常容易。但是，我的输出需求之一是后序遍历。我特别熟悉使用map。有没有办法把这件事做完？

Answer 1

正如Steve Jessop所说，Map是由c++提供的抽象数据结构，您不能以任何顺序更改存储在map中的元素的顺序，就像我们在树或AVL中通过按顺序遍历pre/post/in order所做的那样。但是，您可以通过使用std::greater而不是std::less作为键来颠倒存储顺序。

例如：

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

或者创建一个矢量desiredOrder，这将保持地图中插入顺序的跟踪，完成插入后，只需在desiredOrder矢量上按之前/之后/顺序执行任何排序操作，并使用for循环，您可以遍历矢量并使用矢量值作为地图的键来访问地图元素

e.g

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

此外，该标准并不确切知道(或关心) map的元素在映射可能使用的任何内部树中是如何排列的。红黑树和AVL树都是std::map的有效实现，根据实际使用的情况，你会得到不同的后序遍历。在实践中，我希望它总是R-B或非常类似，但实现的自由度通知由标准定义的接口。

简而言之，std::map不是一棵树，它是一种抽象的数据结构，可以(并且正在)使用树实现。

破解一个特定的实现是可能的，但最好不要这么做。如果您希望数据的树结构成为程序定义状态的一部分，您可以编写自己的树。