motoko-base
motoko-base copied to clipboard
dfinity
Possible improvements for `RBTree`
Possible improvements for RBTree:
- Reduce garbage creation, especially during reading functions, such as
get()and iteration. - More efficient
size()function.
Another long-standing issue with RBTree is that it does not fully support delete.
Separately but also related, RBTree is purely functional. So maybe some users would consider an additional imperative version to be another dimension of improvement?
We should probably round out the functional one before adding an imperative one. Ie implement purely functional delete. Is it hard? Genuine question.
(Sorry, didn't mean to reference this issue from irrelevant PR #500 - meant #499)
Reduce garbage creation, especially during reading functions, such as get() and iteration
General question: How can get() produce garbage? It's only reading. Recursion builds up the stack but that isn't garbage. What am I missing?
Separately but also related, RBTree is purely functional. So maybe some users would consider an additional imperative version to be another dimension of improvement?
I wonder what kind of improvement we can expect from an imperative one. Wouldn't it end up looking very similar and have the same representation? What would get improved?