BTreeMap::lower_bound requiring `str` (key) to be Sized?

help
1

I'm trying to understand this indexset::BTreeMap::lower_bound method. I wrote some test code, but it won't work. I don't see why this bound should be a problem.

let mut m = indexset::BTreeMap::new();
m.insert("apple", "a");
m.insert("banana", "b");
m.insert("blueberry", "b");
let bound = Bound::Included("apple");
let curs = m.lower_bound(bound);

It points at the last line, and complains that the key isn't Sized.

error[E0277]: the size for values of type `str` cannot be known at compilation time
    --> learning/src/data_structures.rs:36:30
     |
36   |     let curs = m.lower_bound(bound);
     |                  ----------- ^^^^^ doesn't have a size known at compile-time
     |                  |
     |                  required by a bound introduced by this call
     |
     = help: the trait `Sized` is not implemented for `str`

I flailed with some other variations, like:

let bound = Bound::Included("apple".to_owned());
let bound = Bound::Included(&"apple".to_owned());

They don't work either.

2

Try:

    let bound = Bound::Included(&"apple");

The method takes a Bound(&Q), so when you pass a Bound(&str), you have Q = str. But the way the method is defined, Q must be Sized. That's the origin of the error.

When you pass a Bound(&&str), you have Q = &str, which is Sized.

Passing a Bound(&String) doesn't work because you can't borrow a String from a &str. Passing a Bound(String) doesn't work because, additionally, a String cannot be a &Q -- you need to pass in a shared reference within the Bound.

Your original code would work if they allowed Q to be not-Sized:

        pub fn lower_bound<Q>(&self, bound: Bound<&Q>) -> CursorMap<'_, K, V>
        where
            K: Borrow<Q> + Ord,
            Q: Ord + ?Sized,
        //           ^^^^^^^

Which I believe is a non-breaking change since this is an inherent method. Consider submitting a feature request or PR.

1 Like