How to find next smaller key in BTreeMap/BTreeSet?

Question

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?

The second half of your question already exists: [How to insert a value into a BTreeSet in Rust and then get an iterator beginning at its location?](https://stackoverflow.com/q/39121982/155423). Please [edit] your question to remove it as questions should focus on one specific topic. — Shepmaster, Apr 01 '18 at 16:16
Thanks for your help, I edited the question to only concern the extended api of finding the next smaller and larger element (optimally without inserting) — blacktemplar, Apr 01 '18 at 16:22

score 24 · Accepted Answer · edited Jun 10 '22 at 05:35

24

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.

edited Jun 10 '22 at 05:35

Abhijit Sarkar

21,927
20
110
219

answered Apr 01 '18 at 16:23

Florian Weimer

32,022
3
48
92

1

`map.range(..key).rev().next().unwrap()` or `map.range(..key).next_back().unwrap()` – Shepmaster Apr 01 '18 at 16:27
Why wouldn't it be? Do you believe that the Rust standard library would implement `DoubleEndedIterator` on a type if it wasn't efficient to do so? – Shepmaster Apr 01 '18 at 16:32
Well, it lacks an efficient implementation of `last()`, so I was worried. But the code looks okay. – Florian Weimer Apr 01 '18 at 16:35
You could submit a PR that adds a specialization of `Iterator::last` to the `Range` and `RangeMut` iterators, in that case. – Shepmaster Apr 01 '18 at 16:39
Wow thanks for the fast help, didn't realize you can have open ranges. Is all this still in O(log(n))? – blacktemplar Apr 01 '18 at 16:45
1

Yes, these functions use the tree structure and should be fairly efficient. – Florian Weimer Apr 01 '18 at 16:59

How to find next smaller key in BTreeMap/BTreeSet?

1 Answers1