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

#1

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?

8 Likes

#2

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

0 Likes

#3

range() searches over keys, not over indices.

0 Likes

#4

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

1 Like