search

orium / rpds

Rust persistent data structures
Mozilla Public License 2.0
1.24k stars 58 forks source link

Implement .range_index() for RedBlackTreeMap/RedBlackTreeSet #56

Open liangyongrui opened 3 years ago

liangyongrui commented 3 years ago

Is it possible to search RedBlackTreeMap by index?

like this

orium commented 3 years ago

Currently it's not possible. To have that with O(lg(n)) we would need to add some extra information to each node (the number of elements to the left).

I'm not sure if there is enough demand for this to spend and extra usize per node.