CODEWITHSUNDEEP
rustb-tree
blacktemplar
blacktemplar

Reputation: 709

How to find next smaller key in BTreeMap/BTreeSet?

If I understand b-trees correctly, it should be easy and possible in logarithmic time to search for a key. If the key is not existent, it can return the next smaller and larger key; the neighbors of the given key if it would get inserted.

Does this functionality already exist?

One possible but complicated way to do it with the current API is to insert the key and then get an iterator to that key so that we can call next on this iterator. Although, its also not clear how to get an iterator to a newly inserted element (see this question)

Why are those methods missing or am I missing something?

Upvotes: 20

Views: 4475

Answers (1)

Florian Weimer
Florian Weimer

Reputation: 33719

You can use the range method and the iterator methods on the returned Range object:

use std::collections::BTreeMap;
let mut map = BTreeMap::new();
map.insert(2, 0);
map.insert(3, 1);
map.insert(5, 2);
map.insert(7, 3);
map.insert(11, 4);
let key = 6;
// maximum in map less than 6: (5, 2)
println!("maximum in map less than {}: {:?}",
         key, map.range(..key).next_back().unwrap());
// minimum in map greater than or equal to 6: (7, 3)
println!("minimum in map greater than or equal to {}: {:?}",
         key, map.range(key..).next().unwrap());

next_back() and next() both perform tree traversals, so they are reasonably efficient.

Upvotes: 26

Related Questions