How are sets generally implemented in STL. I have read they are
implemented as BST, are they some kind of balanced BST like Red Black
trees?


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On 2010-08-08, MC <manan.chopra@gmail.com> wrote:
>
> How are sets generally implemented in STL. I have read they are
> implemented as BST, are they some kind of balanced BST like Red Black
> trees?
>
The standard specifies only complexity requirements: insertion and 
search must
be O(log n) (in the number of elements already in the tree) worst-case. 
  Thus,
e.g., both red-black trees and AVL trees qualify.


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On Aug 8, 4:05 am, MC <manan.cho...@gmail.com> wrote:
> How are sets generally implemented in STL. I have read they are
> implemented as BST, are they some kind of balanced BST like Red Black
> trees?

It's necessarily some kind of self-balancing binary tree since that's
the only way to provide the complexity guarantees that are required.
Implementations typically use a red-black tree or an AVL tree.


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On 08/08/10 05:05, MC wrote:
> How are sets generally implemented in STL. I have read they are
> implemented as BST, are they some kind of balanced BST like Red Black
> trees?
> 

AFAIK, yes, Red Black Trees are one of the most common implementations
for sets, maps and alikes. There are also AVL implementations out there,
that you can google for.

JP


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

MC <manan.chopra@gmail.com> wrote:

> How are sets generally implemented in STL. I have read they are
> implemented as BST, are they some kind of balanced BST like Red Black
> trees?

Yes.

-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

MC wrote, On 8.8.2010 5:05:
> How are sets generally implemented in STL. I have read they are
> implemented as BST, are they some kind of balanced BST like Red Black
> trees?
The C++ ISO standard does not specify such implementation details, only run
time complexitis. For std::set<>, they pretty much imply some kind of search
tree. The standard library shipped with GCC uses Red-Black Tree and os does
the one shipped with VS.NET 2005.


-- 
VH

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On 8 ao�t, 05:05, MC <manan.cho...@gmail.com> wrote:
> How are sets generally implemented in STL.

Well, it depends on ... the implementation :)

> I have read they are
> implemented as BST, are they some kind of balanced BST like Red Black
> trees?

IMO that's the obvious (I dare say intended) implementation. But
nothing prevents the implementer from providing more efficient
structures for specific specialization.

-- 
Michael


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On 8/7/2010 11:05 PM, MC wrote:
> How are sets generally implemented in STL. I have read they are
> implemented as BST, are they some kind of balanced BST like Red Black
> trees?
>
>

    Every implementation I know of uses a red-black tree, although the
standard says nothing about which underlying data type to use.

Joe Gottman

-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]