On Monday 29 January 2007 15:48, Steve wrote: > By my reading of the STL container class deffinitions, I thought > std::map and std::multimap were rtrees. Am I wrong in this? std::map is implemented as a red-black tree. Not the same as an r-tree. Red-black trees are a balanced-tree structure.