Check if a string slice is contained in HashSet<Rc<String>> without allocating a new String

Question

I'm caching words coming from the input in a HashSet<Rc<String>>. Can I somehow use &str as a key for this set when checking if it contained in set as I could for HashSet<String>?

Using a HashSet<String>, it works:

use std::rc::Rc;
use std::collections::HashSet;

let input = "";
let string = input.to_string();
let rc_string: Rc<String> = Rc::new(string.clone());

let set: HashSet<String> = [string.clone()].iter().cloned().collect();
assert!(set.contains(&string));
assert!(set.contains(input));

But if I try to use a HashSet<Rc<String>>:

let string_cache: HashSet<Rc<String>> = [rc_string.clone()].iter().cloned().collect();
assert!(string_cache.contains(&rc_string));
assert!(string_cache.contains(&string));
assert!(string_cache.contains(input));

Then I get this error:

error[E0277]: the trait bound `std::rc::Rc<std::string::String>: std::borrow::Borrow<str>` is not satisfied
  --> src/main.rs:16:26
   |
16 |     assert!(string_cache.contains(input));
   |                          ^^^^^^^^ the trait `std::borrow::Borrow<str>` is not implemented for `std::rc::Rc<std::string::String>`
   |
   = help: the following implementations were found:
             <std::rc::Rc<T> as std::borrow::Borrow<T>>

Answer 1

As the error message says, HashSet::contains requires that the type of the item stored in the collection has a Borrow implementation for its argument type. There is no implementation of Borrow<str> for Rc<String>.

You can't add this implementation yourself because neither the types involved nor the trait are from your crate. However, you can create a newtype wrapper for Rc<String> and implement whichever Borrow implementations you might need:

#[derive(Debug, Eq, PartialEq, Hash)]
struct CacheItem(Rc<String>);

impl Borrow<str> for CacheItem {
    fn borrow(&self) -> &str {
        &self.0
    }
}

impl Borrow<String> for CacheItem {
    fn borrow(&self) -> &String {
        &self.0
    }
}

impl Borrow<Rc<String>> for CacheItem {
    fn borrow(&self) -> &Rc<String> {
        &self.0
    }
}

let string_cache: HashSet<CacheItem> = [rc_string.clone()].iter().cloned().map(CacheItem).collect();
assert!(string_cache.contains(&rc_string));
assert!(string_cache.contains(&string));
assert!(string_cache.contains(input));

Newtype wrappers constructed like this should have zero runtime cost. However, you may need to add a number of extra trait implementations in order to use it conveniently.