Minimum/maximum elements search in BTreeMap/BTreeSet

[abbradar]

It would be nice to have something like (pseudo-code):

fn BTreeMap<K, V>::find{Min,Max}(&self) -> Option<(&K, &V)>;
fn BTreeSet<K, V>::find{Min,Max}(&self) -> Option<&K>;

This should be fast for trees (just walk the tree to the left-most or right-most element) and is very useful. For example Haskell has these functions in its excellent library containers, along with other potentially interesting functions (see the whole "Min/Max" section).

[apasel422]

A dedicated method would improve discoverability, but you can do:

let map: BTreeMap<K, V> = ...;
let min = map.iter().next();
let max = map.iter().next_back();

and the same for BTreeSet.

[abbradar]

Hm, I haven't known about next_back. What I'm interested however is algorithmic complexity of these -- would this be O(log_2 n) (with all the caveats of using B-tree) or something different?

[abbradar]

BTW, I don't see a mention in the documentation that iter() walks items in proper order. It would be nice to add it there, I think.

[abbradar]

Some thoughts on the matter: if iter() does walk items in order, then we should get min with proper complexity automatically if I understand correctly. So this leaves a question of whether next_back() does the right thing there.

[sfackler]

It does do the right thing.

[abbradar]

Thanks! I guess this is purely a documentation issue then. What about changing iter() documentation to something like:

Gets an iterator over the BTreeMap's contents, ordered ascending by its keys. Complexity of first call to next() or next_back() of the resulting iterator is the same as for elements lookup.

(Sorry for possibly bad language, I'm bad at writing documentation)

[apasel422]

Closing this in favor of a new range RFC.