Add a splay tree implementation to libstd#6360
Add a splay tree implementation to libstd#6360alexcrichton wants to merge 3 commits intorust-lang:incomingfrom
Conversation
|
This is really well written. Thank you! I'm not sure how many trees we want in std (soon to be |
|
In hopes of keeping the queue smaller, I'm going to close this. I'll keep an eye on the new |
|
@alexcrichton: Did this ever get updated to HEAD? |
|
The conclusion was that this was just "one more thing" in libextra which just added more maintenance burden, so it wasn't added. I've got a fork at https://github.com/alexcrichton/rs-splay which I'm trying to update as the compiler evolves though. I hope to revisit this again once the fate of libextra has been finalized |
Trigger modulo_one lint also on -1. Fixes rust-lang#6321. changelog: trigger `modulo_one` lint also on `-1`
I was curious if something like this was possible, and it indeed is!
I didn't want to duplicate a lot of functionality between splay trees and the existing
treemapmodule, so I extracted out a lot of the iterators and implementations into theiteratormodule.If this doesn't belong in libstd, it was mostly a proof-of-concept idea anyway. I remember talk about moving the current
stdaway from this repo and into their own repos, so this may just belong elsewhere.Benchmark-wise, it performs about as well as expected. It's real bad on random input (when compared to
TreeMap), and it's better on sequential input thanTreeMapmost of the time. Although that's not quite representative because splay trees are meant to be used on inputs with mild patterns anyway.Method naming would love to have #5898 as well...