Is it possible to range(&str..&str) on a BtreeSet<String>?

1

For example:

    let mut map : BTreeSet<i32> = BTreeSet::new();
    map.insert(1);
    map.insert(2);
    map.range(&1..&10) // use reference here
    .for_each(|i| { 
        println!("{}", i);
    });


    let mut map : BTreeSet<String> = BTreeSet::new();
    map.insert("aaaaa".to_string());
    map.insert("aaaab".to_string());
    map.insert("abbbb".to_string());
    map.insert("zzzzz".to_string());
    println!("{:?}", map);
    map.range("aaaab".."zzzzz"); // do not compile, don't know how to code.

In this case, I must use map.range_mut("aaaab".to_string().."zzzzz".to_string()), but to_string is expensive.

2

No, because the BTree will break if the relative order of the strings changes while they are in the set. You'll need to remove them and then re-add the modified ones.

3

Then why map.range(&1..&10) works?

4

You (usually) can't use & references to change the ordering, so there's no problem giving them out while the items are still in the set.

5

Wait a second, range_mut is a typo, I want to use range. Sorry for that. Does the answer still valid? :rofl: I'm not intent to change orders in the set, just want to iterator on a range. :sweat_smile:

1 Like
6

The issue here is that String implements Borrow<str> but not Borrow<&str>. It looks like it's supposed to work, but the ?Sized bound has been left off of the relevant RangeBounds implementation. Looking through the list of other implementations, this should work:

use std::ops::Bound::{Included, Excluded};
map.range::<str,_>((Included("aaaab"), Excluded("zzzzz")))
5 Likes
7

Looks like it’s the correct workaround, judging e.g. by this comment on GitHub.

2 Likes
8

It works, but checked the code and didn't find out how it works... What's the magic here?

9

If you're doing this a lot, you can define a helper function:

use std::ops::RangeBounds;
fn str_range<'a>(r:impl RangeBounds<&'a str>)->impl 'a + RangeBounds<str> {
    (r.start_bound().cloned(), r.end_bound().cloned())
}

// ....

map.range(str_range("aaaab".."zzzzz"))
10

Might as well generalize to

fn ref_range<'a, T: ?Sized + 'a>(r: impl RangeBounds<&'a T>) -> impl 'a + RangeBounds<T>
2 Likes
11

The method wants

pub fn range<T, R>(&self, range: R) -> Range<'_, K, V>
where
    T: Ord + ?Sized,
    K: Borrow<T> + Ord,
    R: RangeBounds<T>,

K = String and the Borrow relationship you want to use here is String: Borrow<str>, so you have T = str.

Then for the the actual range argument with type R, you need R: RangeBounds<str>. For "a".."z", the resulting type is R = Range<&str>, for example.

The first implementation in this list allows T: ?Sized, but the others (except for ..) don't. So this is fulfilled:

(Bound<&str>, Bound<&str>): RangeBounds<str>

But due to str being unsized, this is not fulfilled:

Range<&str>: RangeBounds<str>
2 Likes
12

Here's a more ergonomic work-around IMO.

struct R<'a>(Range<&'a str>);
impl RangeBounds<str> for R<'_> { /* ... */ }

map.range(R("aaaab".."zzzzz"));

Could be generalized to R<'a, T>, implement for T = [the various Range* types].

3 Likes