1

If I construct, my own binary tree, then I can find the depth of each node. The sample code is as follows

template<class datatype>
void binary_node<datatype>::printNodeWithDepth(int currentNodeDepth)
{
    if ( left )
        left->printNodeWithDepth(currentNodeDepth+1);
    std::cout << value << " and the depth is " << currentNodeDepth << std::endl;
    if ( right)
        right->printNodeWithDepth(currentNodeDepth+1);
}

But wondering, since map is a b-tree, is it possible to write something similar to this for a std::map?

Deduplicator
  • 44,692
  • 7
  • 66
  • 118
nsivakr
  • 1,565
  • 2
  • 25
  • 46

1 Answers1

7

std::map is not guaranteed to be a b-tree, it is just guaranteed to have at least as good runtime complexity. To open the door for other potential implementations, the interface does not include functions for inspecting this kind of implementation details. :)

Magnus Hoff
  • 21,529
  • 9
  • 63
  • 82
  • Thanks. Wondering, like how people jail breakiPhone, if any of you have done some tweaking to std::map? – nsivakr Aug 23 '10 at 15:55
  • @nsivakr: You might want to inspect an `std::map` in runtime by using a (visual) debugger. – Magnus Hoff Aug 23 '10 at 15:59
  • 2
    @nsivakr: You are not asking how a particular STL implementation can be broken, but rather in general how all implementations can be broken. The simile would be not breaking the iPhone, but rather all mobiles from all manufacturers. The STL is implemented in headers... if you really want to achieve this, just read how your particular implementation is done. – David Rodríguez - dribeas Aug 23 '10 at 16:00
  • Thanks David. Makes a lot of sense now. – nsivakr Aug 23 '10 at 16:02
  • 1
    I have looked through gcc's implementation of std::map and I can tell you that at the time (3.4 maybe?) they were using red-black trees. – Niki Yoshiuchi Aug 23 '10 at 16:06
  • Thanks Mr.Niki. Appreciate your response. – nsivakr Aug 23 '10 at 16:14