Thread: STL and Binary Search Trees

  1. #1
    Registered User
    Join Date
    Sep 2004
    Posts
    28

    STL and Binary Search Trees

    Does the STL have an implementation of a Binary Search Tree or any sort of tree for that matter?

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    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:

    Code:
    template<class _K, class _Ty, class _Kfn, class _Pr, class _A>
            class _Tree {
    protected:
            enum _Redbl {_Red, _Black};
    etc...
    So I would guess that means that a red/black tree is definitely implemented for those containers mentioned above.
    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

  3. #3
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. best STL method to implement a binary tree
    By MatthewDoucette in forum C++ Programming
    Replies: 8
    Last Post: 06-16-2006, 07:08 AM
  2. stl - searching for elements in containers
    By Raven Arkadon in forum C++ Programming
    Replies: 4
    Last Post: 03-24-2005, 11:10 AM
  3. vector and binary predicates
    By dalek in forum C++ Programming
    Replies: 3
    Last Post: 08-17-2004, 06:30 AM
  4. Traversing a binary tree with pointers
    By supaben34 in forum C++ Programming
    Replies: 8
    Last Post: 12-07-2003, 01:04 PM
  5. When it comes to the STL, i'm an idiot.
    By Eibro in forum C++ Programming
    Replies: 2
    Last Post: 10-25-2002, 08:05 AM