Set implementation in STL
in [C++]
|
Prev: output?
Next: Shallow copy
From: Vaclav Haisman on 9 Aug 2010 11:59 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! ]
From: Joe Gottman on 9 Aug 2010 13:29 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! ]
From: Michael Doubez on 9 Aug 2010 13:20
On 8 ao�t, 05:05, MC <manan.cho...(a)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! ] |