Set implementation in STL
in [C++]
|
Prev: output?
Next: Shallow copy
From: MC on 7 Aug 2010 12: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? -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Zeljko Vrba on 8 Aug 2010 23:30 On 2010-08-08, MC <manan.chopra(a)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! ]
From: Juan Pedro Bolivar Puente on 8 Aug 2010 23:55 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! ]
From: Mathias Gaunard on 8 Aug 2010 23:53 On Aug 8, 4:05 am, MC <manan.cho...(a)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! ]
From: Daniel T. on 9 Aug 2010 11:28
MC <manan.chopra(a)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! ] |