Suggestion: BTreeMap/BTreeSet O(log(n)) n-th element access

[Palladinium]

BTrees are able to perform O(log(n)) lookups for the n-th largest/smallest element (a, b), but currently I believe that BTreeMap/BTreeSet don’t provide an API to leverage that, instead having to rely on in-order traversal via .iter().nth(n), which will be O(n).

I propose adding a new O(log(n)) API along the lines of .nth() to BTreeMap/BTreeSet, or specializing .nth() for the relevant iterators (or both).

Any thoughts?

[kornel]

There’s range(n..) that does it.

[Palladinium]

range() searches over keys, not over indices.

[sfackler]

A tree that stores the sizes of its child subtrees can perform this operation, but Rust’s BTreeMap does not do that.