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

Question

如果我正确理解B树，那么在对键进行搜索时，可以很容易地在对数时间内找到并返回该键。如果该键不存在，则可以返回下一个较小和较大的键; 如果将其插入，则返回给定键的相邻键。

这种功能是否已经存在？

通过当前的API实现这个功能的一种可能但复杂的方式是插入该键，然后获取到这个键的迭代器，以便我们可以在此迭代器上调用next。虽然如何获取新插入元素的迭代器也不是很清楚（参见这个问题）。

为什么这些方法缺失或者我漏掉了什么？

- blacktemplar

---

你的问题的后半部分已经存在：如何在Rust中将值插入BTreeSet，然后获得以其位置开头的迭代器？。请[编辑]您的问题以删除它，因为问题应专注于一个特定主题。 - Shepmaster

谢谢您的帮助，我编辑了问题，只关注查找下一个更小和更大元素的扩展API（最好不要插入）。 - blacktemplar

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;
// 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()和next()都执行树的遍历操作，因此它们具有相当高的效率。

- Florian Weimer

---

map.range(..key).rev().next().unwrap() or map.range(..key).next_back().unwrap() - Shepmaster

为什么不呢？如果Rust标准库没有足够的效率，你认为它会在一个类型上实现DoubleEndedIterator吗？ - Shepmaster

好吧，它缺乏一个高效的 last() 实现，所以我有些担心。但是代码看起来还不错。 - Florian Weimer

你可以提交一个PR，将Range和RangeMut迭代器的Iterator::last添加为专门化。 - Shepmaster

哇，谢谢你的快速帮助，我没意识到你可以有开放范围。这些操作仍然是O(log(n))吗？ - blacktemplar

是的，这些函数使用树形结构，应该相当高效。 - Florian Weimer