otherwise I'll have to write my own and I dont wanna
otherwise I'll have to write my own and I dont wanna
C Code. C Code Run. Run Code Run... Please!
"Love is like a blackhole, you fall into it... then you get ripped apart"
>is there an AVLTree STL class
Not as such, but a lot of times the associative containers are suitable replacements for a proper tree. You also have the option of acquiring a third party tree container, which is to be preferred over writing your own since it's already debugged and working.
-Prelude
My best code is written with the delete key.
hmmm, Im unaware of any that could guarantee log(n) search and deletion as an AVL tree would.
Also, I had better write my own since Im probably gonna need to be able to do an in-order iteration from an arbitrary position in the tree. No big deal though, I had to write a BST with this capability for class last semester so I guess it wouldnt be too tough to add rotations for the AVL
Perhaps I should write a Skiplist instead lol.
C Code. C Code Run. Run Code Run... Please!
"Love is like a blackhole, you fall into it... then you get ripped apart"
>hmmm, Im unaware of any that could guarantee log(n) search and deletion as an AVL tree would.
All of the associative containers require insertions, deletions, and searches to be logarithmic.
>Perhaps I should write a Skiplist instead lol.
A tree would be better, skip lists are generally more annoying than even balanced trees in my experience and the lack of familiarity with them for most programmers effects maintenance. You also have to consider speed, while still logarithmic, skip lists are still slower than trees. I would only consider using them when memory is at a premium.
-Prelude
My best code is written with the delete key.
>All of the associative containers require insertions, deletions, and searches to be logarithmic.
Isnt it the case that they could degenerate into nearly linear running times?
C Code. C Code Run. Run Code Run... Please!
"Love is like a blackhole, you fall into it... then you get ripped apart"
>Isnt it the case that they could degenerate into nearly linear running times?
Perhaps in a particularly non-conforming and dumb implementation. Here's what the standard says:
-PreludeCode:a.insert(p,t) logarithmic in general, but amortized constant if t is inserted right after p. a.erase(q) amortized constant a.find(k) logarithmic
My best code is written with the delete key.
Really? Wow, I never knew that, I always thought it degenerated to linear if it was filled aasymmetrically.
>I always thought it degenerated to linear if it was filled aasymmetrically.
The associative containers are most easily implemented with a balanced binary tree, no one in their right mind would allow the worst case tree scenario to occur with a generic library. Besides, to meet the minimum requirements for the standard the implementation has to guarantee logarithmic performance. A basic tree cannot do this (barring a quantum space/time flux, but they're rare in C++).
-Prelude
My best code is written with the delete key.
> (barring a quantum space/time flux, but they're rare in C++).
Perhaps for you, Ms. "I never invoke undefined behavior". Try flushing an input stream whilst modifying an object several times in one sequence point in a program whose main() fincttion is declared as returning void on a decently powerful chip. BAM, instant temporal anomaly.
whatever that means lol
C Code. C Code Run. Run Code Run... Please!
"Love is like a blackhole, you fall into it... then you get ripped apart"
Well I just mean that rending the fabric of time itself is as likely an outcome of running the program I described as any other.
>BAM, instant temporal anomaly.
-PreludeCode:/* If you run this you'll be thrown into Sliders episode 12 */ float *main(double argc, int **argv) { char *p; fflush ( printf ( "%s%lf", argv[*(int *)&argc], p += 5 - *p++ / 2 ) ); return "Wait for me professor!"; }
My best code is written with the delete key.