3

I have read set and maps provided in c++ STL are implemented using tree, so can i traverse them as tree ? can i get pre-order and post-order traversal of a set or map? i know i can get in-order traversal by simply iterating over all the elements. 

set<int> tree;
tree.insert(1);
tree.insert(2);
tree.insert(3);

inorder traveral for this tree should be 1,2,3 and preorder 2,1,3 and post-order 1,3,2. How can i get letter two if i have tree as set?

Thanks!!

Naveen Mittal
  • 95
  • 1
  • 8
  • 4
    "A tree", yes, but not any specific tree. Maps and sets provide you ordered iteration over the values in key order. The details of the tree are not exposed or observable. – Kerrek SB Jul 02 '16 at 12:27
  • @KerrekSB *"not exposed or observable"* pretty exposed given how many people defacto consider `std::map` as a red-black tree. https://stackoverflow.com/questions/205945/why-does-the-c-stl-not-provide-any-tree-containers – Sergey Kolesnik Mar 08 '23 at 23:14

1 Answers1

2

Stl set and map are balanced trees (like red-black trees). They do not just insert elements and keep it in one order, they can balance their elements to keep trees h O(logn). So your elements are not necessarily in tree that look as you think and there are no functions that would allow you to see how they are.

misztsu
  • 129
  • 5