MySpace interview question

WHich datastructure STL map is based on.

Interview Answer

Anonymous

17 Oct 2010

I said linked lists and trying to convey if it's right. He said Binary Tree. Then I discussed that it should be Binary Search Tree and why so. He seemed to be satisfied.