implement a persistent self-balancing binary search tree

[thestinger]

This will need to be a different implementation than TreeMap - an efficient persistent tree is a different beast.

[graydon]

nominating for backwards-compatible milestone

[pcwalton]

This is part of extra and so I don't think this is backwards incompatible.

[graydon]

I would like treemap to be in std, it's a completely normal container type, in many standard libraries and specs.

[graydon]

accepted for backwards-compatible milestone

[sfackler]

What's the intended use case for fun_treemap? Should it be fully functional? I don't see why that's particularly useful since it cant be shared over task boundaries as @thestinger mentioned in #7212. Purely functional implementations also (I think) require O(log(n)) space overhead per copy, which is a bummer if the use case is to keep tons of generations around. If it's not going to be purely functional, should it be partially consistent or fully consistent? Traditional persistent maps appear to be useful in some computational geometry problems, but I'm not sure if that's really a common enough application to support in extra.

[thestinger]

It could be written with extra::arc::Arc instead of managed pointers. The high-fanout persistent data structures can't be implemented efficiently with reference counting, but it's fine for a binary tree.

[catamorphism]

This won't break backwards-compatibility. Clearing milestone.

[steveklabnik]

I'm pulling a massive triage effort to get us ready for 1.0. As part of this, I'm moving stuff that's wishlist-like to the RFCs repo, as that's where major new things should get discussed/prioritized.

This issue has been moved to the RFCs repo: rust-lang/rfcs#649