The `BTreeMap::range`

and `BTreeSet::range`

functions are very handy for a variety of searching tasks; for example, they can be used to find the first element larger than something, or the last element smaller than or equal to something, etc. However, these functions have a common drawback: they require the caller to be able to construct something of a type `Q`

for which `K: Borrow<Q>`

holds. In some cases this might be difficult, for example if your key type is `(i32, SomeLargeType)`

and you want to search for the first key whose first coordinate is at least 5.

One solution would be to add the method `BTreeMap::range_by`

, with the signature

```
fn range_by<F: FnMut(&K) -> Ordering>(&self, f: F) -> impl Iterator<Item=(&K, &V)>
```

(and similarly for `BTreeSet`

) where the function `f`

is supposed to return `Ordering::Equal`

for some consecutive range of values, `Ordering::Less`

for values before that range, and `Ordering::Equal`

for values after that range. The return value would iterate over all values for which `f`

returns `Ordering::Equal`

.

There’s some precedent for this in the `slice`

type, which has `binary_search_by`

in addition to `binary_search`

.

What do you think? Is there a better solution?

EDIT: I forgot to say it, but I want the solution to be as efficient as `BTreeMap::range`

. That is, it should have a one-time cost of O(log n) (where n is the size of the map), and amortized cost of O(1) for each iteration.