Postorder traversal in stl map

Question

I am using a stl map on gcc comper which uses a tree to store key,value pairs. The iterator advances in an inorder fashion so inorder traversal is really easy. However one of my output requirements is a postorder traversal. I have been specifically aksed to use map. Is there any way to get it done?

Answer 1

There is no standard way to access the "actual tree structure" of an instance of std::map.

Furthermore, the standard doesn't know (or care) exactly how the elements of a map are arranged in any internal tree that the map might use. Red-Black trees and AVL trees are both valid implementations of std::map, and you'd get a different postorder traversal according to which is in fact used. In practice I expect its always R-B or very similar, but the implementation freedom informs the interface defined by the standard.

In short, std::map is not a tree, it's an abstract data structure that can be (and is) implemented using a tree.

It might be possible to hack a particular implementation, but probably best not to. If you want the tree structure of your data to be part of the defined state of your program, you could perhaps write your own tree.