Set implementation in STL
MC
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! ]
Zeljko Vrba
>
> 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?
>
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.
Juan Pedro Bolivar Puente
> 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
Mathias Gaunard
> 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.
Daniel T.
> 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.
Vaclav Haisman
> 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?
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
Michael Doubez
> 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
Joe Gottman
> 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