c++ - stl map中的后序遍历

Question

我在 gcc comper 上使用 stl 映射，它使用树来存储键值对。迭代器以中序方式前进，因此中序遍历非常容易。然而，我的输出要求之一是后序遍历。我被特别要求使用地图。有什么办法可以完成吗？

Answer 1

没有标准方法可以访问std::map.

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

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

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

Answer 2

正如 Steve Jessop 所说，Map 是 c++ 提供的抽象数据结构，您不能以任何顺序更改存储在 map 中的元素的顺序，就像我们在 Tree 或 AVL 中可以通过 pre/post/in 顺序遍历一样。但您可以使用std::greateras your key 而不是std::less.

例如

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

或创建一个 VectordesiredOrder，它将在 map 中保留插入顺序的轨迹，一旦完成插入，只需在所需的Order Vector上按顺序执行您想要的前/后/任何排序操作，并使用 for 循环，您可以遍历向量并使用向量值作为 Map 的键来访问 Map 元素

例如

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';
}