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
There’s some precedent for this in the
slice type, which has
binary_search_by in addition to
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.