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

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.

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.

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

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.

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

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

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

2 Likes

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

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"))

Might as well generalize to

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

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

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

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.