STL and Balanced Trees???

[Peter Tkacz]

Are there any data types within STL that implement a balanced tree?

Peter

 

[Dave]

Are there any data types within STL that implement a balanced tree?

Peter

Well, the performance requirements imposed on maps, multimaps, sets and
multisets cause them to be implemented as balanced trees.

 

[Grzegorz Sakrejda]

Are there any data types within STL that implement a balanced tree?

Peter

map , multimap , set , mutliset

 

[Gianni Mariani]

Are there any data types within STL that implement a balanced tree?

There is no requirement to implement a certain algorithm but STL
templates that might do somthing similar are std::map<...> or
std::multimap<...> .

 

[Dave]

There is no requirement to implement a certain algorithm but STL
templates that might do somthing similar are std::map<...> or
std::multimap<...> .

True, but can anyone think of any known data structures other than balanced
binary trees that would meet the logarithmic time complexity requirements
imposed by the Standard? I'm really seriously asking because, as far as I
know, there are none, but I don't know that I am right on that...

 

[Jerry Coffin]

[ ... ]

Well, the performance requirements imposed on maps, multimaps, sets and
multisets cause them to be implemented as balanced trees.

More or less, partly depending on how tightly you define "tree" -- just
for example, you might be able to do the job with a heap, but it's open
to argument that a heap really IS a tree, just represented differently
than usual.

 

[Dave]

True, but can anyone think of any known data structures other than balanced
binary trees that would meet the logarithmic time complexity requirements
imposed by the Standard? I'm really seriously asking because, as far as I
know, there are none, but I don't know that I am right on that...

In looking around a bit on this, it appears that skip lists might also be a
data structure that could be used to implement the STL associative
containers and meet the logarithmic time complexity requirements.

 

[Jerry Coffin]

[ ... ]

In looking around a bit on this, it appears that skip lists might also be a
data structure that could be used to implement the STL associative
containers and meet the logarithmic time complexity requirements.

IIRC, a skip list provides excellent _expected_ complexity, but at least
the usual ones don't meet the requirements for worst-case complexity.