Idea: Looking up holes in BTreeMaps

Binary trees are useful for more than just key and range lookups. They are also commonly used to do interval lookups ("is x within a set of non-overlapping intervals?"), or neighborhood lookups ("is a value near x present?"). But this requires the ability to look up values that are "near" some key x, not just the value for key x. Currently, there is no way with a BTreeMap to query for the elements on either side of such a "hole". If you're willing to pay some additional complexity and do two lookups, you can use range:

fn neighbors_of<K, V>(map: &BTreeMap<K, V>, key: &K) -> (Option<(&K, &V)>, Option<(&K, &V)>) {
    let before = map.range(Bound::Unbounded, Bound::Included(x));
    let after = map.range(Bound::Included(x), Bound::Unbounded);
    (before.next_back(), after.next())
}

Arguably, the function above should actually return the full Range for both before and after, but then the caller would need to remember to use next_back() on before. But none of this feels particularly ergonomic.

Instead, I think BTreeMap should provide an implementation of neighbors_of that is analogous to the definition above. By being implemented internally, it could be more efficient than the example above, including not having to construct an iterator. This would enable the use-cases describe above without the indirection through two range queries.

A further enhancement could be a BTreeMap::search(), which returns an unbounded DoubleEndedIterator starting at the largest element <= x (which you can't do with range() today). But without a concrete use-case for this, that should probably be considered a secondary concern?

Start by reviewing the existing BTreeMap::range behavior and the proposed neighbors_of and search APIs in this issue. Compare the interval and neighborhood use cases, then clarify the desired API and semantics with the RFC discussion. Done means an agreed, concrete design suitable for progressing through the RFC process.