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

libs
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?

10 Likes
2

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

3

range() searches over keys, not over indices.

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
5

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.