mozilla/rust — pull request #6360 by alexcrichton (2013-05-09 14:39:07+00:00)
Title: Add a splay tree implementation to libstd

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 `treemap` module, so I extracted out a lot of the iterators and implementations into the `iterator` module.

If this doesn't belong in libstd, it was mostly a proof-of-concept idea anyway. I remember talk about moving the current `std` away 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 than `TreeMap` most 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...