Does the STL have an implementation of a Binary Search Tree or any sort of tree for that matter?
Does the STL have an implementation of a Binary Search Tree or any sort of tree for that matter?
The set/multiset/map/multimap containers are typically (not guaranteed) implemented as a form of tree, i.e. red-black tree. The MSVC compiler versions of the headers for these containers include a header called xtree and if you open that up, you get something like:
So I would guess that means that a red/black tree is definitely implemented for those containers mentioned above.Code:template<class _K, class _Ty, class _Kfn, class _Pr, class _A> class _Tree { protected: enum _Redbl {_Red, _Black}; etc...
Last edited by hk_mp5kpdw; 11-29-2004 at 11:29 AM.
"Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
-Christopher Hitchens
The C++ standard sets speed requirements on the various operations of sets and maps. In practice, only binary search trees meet these requirements.
All the buzzt!
CornedBee
"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law