Using range on a BTreeSet<Box<dyn Trait>>

playground link leads to the following code:

use std::cmp::Ordering;
use std::collections::BTreeSet;

trait KeyTrait {}

impl KeyTrait for u64 {}
impl KeyTrait for &str {}

// Traits Ord depend on are also implemented
impl Ord for dyn KeyTrait + '_ { /* ... */ }


fn main() {
    let trait_objects: Vec<Box<dyn KeyTrait>> = vec![
        Box::new(1),
        Box::new("two")
    ];
    let other_object: Box<dyn KeyTrait> = Box::new("three");
    
    let set: BTreeSet<Box<dyn KeyTrait>> = BTreeSet::from_iter(trait_objects.into_iter());
    let a = set.get(&other_object); // OK
    set.get(other_object.as_ref()); // OK
    
    set.range::<Box<dyn KeyTrait>, _>((a.unwrap())..); // OK, we get &Box<dyn KeyTrait> after unwrapping a
    set.range::<Box<dyn KeyTrait>, _>((&other_object)..); // OK, but usually &dyn Trait is passed rather than &Box<dyn Trait>
    set.range(other_object..); // OK, but this takes ownership of the Box
    
    // set.range((other_object.as_ref())..); // bad, trait Borrow<&dyn KeyTrait> is not implemented for Box<dyn KeyTrait>
}

Ideally I would want the last commented version to work, but it doesn't work as Box<T, A> implements Borrow<T>, but T = dyn KeyTrait is unsized, and RangeFrom<Idx> requires Idx = dyn KeyTrait to be sized.

Currently I can seem to get around this by using the key value BTreeSet gives me to put into range:

    let a = set.get(other_object.as_ref());
    set.range::<Box<dyn KeyTrait>, _>((a.unwrap())..);

Are there other ways of getting a range out of BTreeSet<Box<dyn KeyTrait>> when given only &dyn KeyTrait?

It think the underlying issue/restriction is the one discussed (and not lifted for a variety of reasons) in

The workaround is to use (Bound<&T>, Bound<&T>) which does support T: ?Sized

set.range::<dyn KeyTrait, _>((Included(other_object.as_ref()), Unbounded));

Rust Playground

2 Likes