如何在 BTreeMap/BTreeSet 中找到下一个较小的键？

Question

如果我正确理解 b 树，那么在对数时间内搜索键应该很容易并且可能。如果key不存在，可以返回下一个越来越小的key；给定键的邻居（如果它被插入）。

这个功能已经存在了吗？

使用当前 API 执行此操作的一种可能但复杂的方法是插入键，然后获取该键的迭代器，以便我们可以调用next此迭代器。虽然，它也不清楚如何获得一个迭代器到一个新插入的元素（见这个问题）

为什么缺少这些方法或者我缺少什么？

Answer 1

您可以在返回的对象上使用range方法和迭代器方法Range：

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;
println!("maximum in map less than {}: {:?}",
         key, map.range(..key).next_back().unwrap());
println!("minimum in map greater than {}: {:?}",
         key, map.range(key..).next().unwrap());

next_back()并且next()两者都执行树遍历，因此它们相当有效。