Repository: billyrieger/bimap-rs (language: rust)

Issue:
Generalize query interfaces
It should be possible to generalize some of the interfaces for querying the BiMap to match the APIs in the standard library. ([BTreeMap::get](https://doc.rust-lang.org/stable/std/collections/struct.BTreeMap.html#method.get), [HashMap::get](https://doc.rust-lang.org/stable/std/collections/struct.HashMap.html#method.get).)

I've implemented this for my own copy of BiBTreeMap, so I'm fairly confident it works as expected.

```rust
    pub fn get_by_left<Q>(&self, left: &Q) -> Option<&R> 
        where
            Rc<L>: Borrow<Q>,
            Q: Ord + ?Sized, 
```

I'm not familiar enough with the code to know if it would be an obvious improvement or not, but I'd be happy to submit a PR if it's desirable and I find a good time to write it up.


Discussion / hints:
I agree that using the `Borrow` trait would be desirable. Unfortunately, the method signature you suggested leaks implementation details, namely the use of `Rc` to share keys and values between the interior maps. That's a deal-breaker for me because eventually I'd like to get rid of `Rc` usage entirely and use raw pointers instead, something like this:

```rust
struct BiHashMap<L, R> {
    left_map: HashMap<Box<L>, *const R>,
    right_map: HashMap<Box<R>, *const L>,
}
```

I _think_ such an implementation would be safe, but I'm not completely sure. Regardless, such a change would mean changing the function's type signature, any similar changes in the future would be propagated through the public API. If there's a way to accomplish this without leaking implementation details, I'd be all for it.

Out of curiosity, how did you get that to work at all? I attempted essentially the same thing a while ago but [ran into a roadblock](https://users.rust-lang.org/t/transitive-borrow-trait/27001).
I think you're right. I don't actually have the `Rc<L>: Borrow<Q>` version working in the way I thought I had, due to the same roadblock you mentioned. Bummer... Thanks for taking a look at it anyway.
I think I may have found a way to get this to work, although it requires some `unsafe` usage. [playground link](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=6a0324ddd3ad6f80c9e2f2d66359f33d)

Fix patch:
diff --git a/src/btree.rs b/src/btree.rs
index adad415..1801eaf 100644
--- a/src/btree.rs
+++ b/src/btree.rs
@@ -1,11 +1,15 @@
 //! A bimap backed by two `BTreeMap`s.
 
-use crate::Overwritten;
+use crate::{
+    mem::{Ref, Wrapper},
+    Overwritten,
+};
 use alloc::{
     collections::{btree_map, BTreeMap},
     rc::Rc,
 };
 use core::{
+    borrow::Borrow,
     cmp::Ordering,
     fmt,
     hash::{Hash, Hasher},
@@ -19,8 +23,8 @@ use core::{
 ///
 /// [module-level documentation]: crate
 pub struct BiBTreeMap<L, R> {
-    left2right: BTreeMap<Rc<L>, Rc<R>>,
-    right2left: BTreeMap<Rc<R>, Rc<L>>,
+    left2right: BTreeMap<Ref<L>, Ref<R>>,
+    right2left: BTreeMap<Ref<R>, Ref<L>>,
 }
 
 impl<L, R> BiBTreeMap<L, R>
@@ -177,6 +181,10 @@ where
     /// Returns a reference to the right value corresponding to the given left
     /// value.
     ///
+    /// The input may be any borrowed form of the bimap's left type, but the
+    /// ordering on the borrowed form *must* match the ordering on the left
+    /// type.
+    ///
     /// # Examples
     ///
     /// ```
@@ -187,13 +195,21 @@ where
     /// assert_eq!(bimap.get_by_left(&'a'), Some(&1));
     /// assert_eq!(bimap.get_by_left(&'z'), None);
     /// ```
-    pub fn get_by_left(&self, left: &L) -> Option<&R> {
-        self.left2right.get(left).map(|l| &**l)
+    pub fn get_by_left<Q>(&self, left: &Q) -> Option<&R>
+    where
+        L: Borrow<Q>,
+        Q: Ord + ?Sized,
+    {
+        self.left2right.get(Wrapper::wrap(left)).map(|l| &*l.0)
     }
 
     /// Returns a reference to the left value corresponding to the given right
     /// value.
     ///
+    /// The input may be any borrowed form of the bimap's right type, but the
+    /// ordering on the borrowed form *must* match the ordering on the right
+    /// type.
+    ///
     /// # Examples
     ///
     /// ```
@@ -204,13 +220,21 @@ where
     /// assert_eq!(bimap.get_by_right(&1), Some(&'a'));
     /// assert_eq!(bimap.get_by_right(&2), None);
     /// ```
-    pub fn get_by_right(&self, right: &R) -> Option<&L> {
-        self.right2left.get(right).map(|r| &**r)
+    pub fn get_by_right<Q>(&self, right: &Q) -> Option<&L>
+    where
+        R: Borrow<Q>,
+        Q: Ord + ?Sized,
+    {
+        self.right2left.get(Wrapper::wrap(right)).map(|r| &*r.0)
     }
 
     /// Returns `true` if the bimap contains the given left value and `false`
     /// otherwise.
     ///
+    /// The input may be any borrowed form of the bimap's left type, but the
+    /// ordering on the borrowed form *must* match the ordering on the left
+    /// type.
+    ///
     /// # Examples
     ///
     /// ```
@@ -221,13 +245,21 @@ where
     /// assert!(bimap.contains_left(&'a'));
     /// assert!(!bimap.contains_left(&'b'));
     /// ```
-    pub fn contains_left(&self, left: &L) -> bool {
-        self.left2right.contains_key(left)
+    pub fn contains_left<Q>(&self, left: &Q) -> bool
+    where
+        L: Borrow<Q>,
+        Q: Ord + ?Sized,
+    {
+        self.left2right.contains_key(Wrapper::wrap(left))
     }
 
     /// Returns `true` if the map contains the given right value and `false`
     /// otherwise.
     ///
+    /// The input may be any borrowed form of the bimap's right type, but the
+    /// ordering on the borrowed form *must* match the ordering on the right
+    /// type.
+    ///
     /// # Examples
     ///
     /// ```
@@ -238,8 +270,12 @@ where
     /// assert!(bimap.contains_right(&1));
     /// assert!(!bimap.contains_right(&2));
     /// ```
-    pub fn contains_right(&self, right: &R) -> bool {
-        self.right2left.contains_key(right)
+    pub fn contains_right<Q>(&self, right: &Q) -> bool
+    where
+        R: Borrow<Q>,
+        Q: Ord + ?Sized,
+    {
+        self.right2left.contains_key(Wrapper::wrap(right))
     }
 
     /// Removes the left-right pair corresponding to the given left value.
@@ -247,6 +283,10 @@ where
     /// Returns the previous left-right pair if the map contained the left value
     /// and `None` otherwise.
     ///
+    /// The input may be any borrowed form of the bimap's left type, but the
+    /// ordering on the borrowed form *must* match the ordering on the left
+    /// type.
+    ///
     /// # Examples
     ///
     /// ```
@@ -260,14 +300,18 @@ where
     /// assert_eq!(bimap.remove_by_left(&'b'), Some(('b', 2)));
     /// assert_eq!(bimap.remove_by_left(&'b'), None);
     /// ```
-    pub fn remove_by_left(&mut self, left: &L) -> Option<(L, R)> {
-        self.left2right.remove(left).map(|right_rc| {
+    pub fn remove_by_left<Q>(&mut self, left: &Q) -> Option<(L, R)>
+    where
+        L: Borrow<Q>,
+        Q: Ord + ?Sized,
+    {
+        self.left2right.remove(Wrapper::wrap(left)).map(|right_rc| {
             // unwrap is safe because we know right2left contains the key (it's a bimap)
             let left_rc = self.right2left.remove(&right_rc).unwrap();
             // at this point we can safely unwrap because the other pointers are gone
             (
-                Rc::try_unwrap(left_rc).ok().unwrap(),
-                Rc::try_unwrap(right_rc).ok().unwrap(),
+                Rc::try_unwrap(left_rc.0).ok().unwrap(),
+                Rc::try_unwrap(right_rc.0).ok().unwrap(),
             )
         })
     }
@@ -277,6 +321,10 @@ where
     /// Returns the previous left-right pair if the map contained the right
     /// value and `None` otherwise.
     ///
+    /// The input may be any borrowed form of the bimap's right type, but the
+    /// ordering on the borrowed form *must* match the ordering on the right
+    /// type.
+    ///
     /// # Examples
     ///
     /// ```
@@ -290,14 +338,18 @@ where
     /// assert_eq!(bimap.remove_by_right(&2), Some(('b', 2)));
     /// assert_eq!(bimap.remove_by_right(&2), None);
     /// ```
-    pub fn remove_by_right(&mut self, right: &R) -> Option<(L, R)> {
-        self.right2left.remove(right).map(|left_rc| {
+    pub fn remove_by_right<Q>(&mut self, right: &Q) -> Option<(L, R)>
+    where
+        R: Borrow<Q>,
+        Q: Ord + ?Sized,
+    {
+        self.right2left.remove(Wrapper::wrap(right)).map(|left_rc| {
             // unwrap is safe because we know left2right contains the key (it's a bimap)
             let right_rc = self.left2right.remove(&left_rc).unwrap();
             // at this point we can safely unwrap because the other pointers are gone
             (
-                Rc::try_unwrap(left_rc).ok().unwrap(),
-                Rc::try_unwrap(right_rc).ok().unwrap(),
+                Rc::try_unwrap(left_rc.0).ok().unwrap(),
+                Rc::try_unwrap(right_rc.0).ok().unwrap(),
             )
         })
     }
@@ -400,10 +452,10 @@ where
     /// Inserts the given left-right pair into the bimap without checking if the
     /// pair already exists.
     fn insert_unchecked(&mut self, left: L, right: R) {
-        let left_rc = Rc::new(left);
-        let right_rc = Rc::new(right);
-        self.left2right.insert(left_rc.clone(), right_rc.clone());
-        self.right2left.insert(right_rc, left_rc);
+        let left = Ref(Rc::new(left));
+        let right_rc = Ref(Rc::new(right));
+        self.left2right.insert(left.clone(), right_rc.clone());
+        self.right2left.insert(right_rc, left);
     }
 
     /// Creates an iterator over the left-right pairs lying within a range of
@@ -411,6 +463,10 @@ where
     ///
     /// The iterator element type is `(&L, &R)`.
     ///
+    /// The range bounds may be any borrowed form of the bimap's left type, but
+    /// the ordering on the borrowed form *must* match the ordering on the left
+    /// type.
+    ///
     /// # Examples
     ///
     /// ```
@@ -426,12 +482,16 @@ where
     ///     println!("({}, {})", left, right);
     /// }
     /// ```
-    pub fn left_range<A>(&self, range: A) -> LeftRange<'_, L, R>
+    pub fn left_range<T, A>(&self, range: A) -> LeftRange<'_, L, R>
     where
-        A: RangeBounds<L>,
+        L: Borrow<T>,
+        A: RangeBounds<T>,
+        T: Ord + ?Sized,
     {
+        let start = Wrapper::wrap_bound(range.start_bound());
+        let end = Wrapper::wrap_bound(range.end_bound());
         LeftRange {
-            inner: self.left2right.range(range),
+            inner: self.left2right.range::<Wrapper<_>, _>((start, end)),
         }
     }
 
@@ -440,6 +500,10 @@ where
     ///
     /// The iterator element type is `(&L, &R)`.
     ///
+    /// The range bounds may be any borrowed form of the bimap's right type, but
+    /// the ordering on the borrowed form *must* match the ordering on the right
+    /// type.
+    ///
     /// # Examples
     ///
     /// ```
@@ -455,12 +519,16 @@ where
     ///     println!("({}, {})", left, right);
     /// }
     /// ```
-    pub fn right_range<A>(&self, range: A) -> RightRange<'_, L, R>
+    pub fn right_range<T, A>(&self, range: A) -> RightRange<'_, L, R>
     where
-        A: RangeBounds<R>,
+        R: Borrow<T>,
+        A: RangeBounds<T>,
+        T: Ord + ?Sized,
     {
+        let start = Wrapper::wrap_bound(range.start_bound());
+        let end = Wrapper::wrap_bound(range.end_bound());
         RightRange {
-            inner: self.right2left.range(range),
+            inner: self.right2left.range::<Wrapper<_>, _>((start, end)),
         }
     }
 }
@@ -610,7 +678,7 @@ where
 
 /// An owning iterator over the left-right pairs in a `BiBTreeMap`.
 pub struct IntoIter<L, R> {
-    inner: btree_map::IntoIter<Rc<L>, Rc<R>>,
+    inner: btree_map::IntoIter<Ref<L>, Ref<R>>,
 }
 
 impl<L, R> DoubleEndedIterator for IntoIter<L, R> {
@@ -618,8 +686,8 @@ impl<L, R> DoubleEndedIterator for IntoIter<L, R> {
         // unwraps are safe because right2left is gone
         self.inner.next_back().map(|(l, r)| {
             (
-                Rc::try_unwrap(l).ok().unwrap(),
-                Rc::try_unwrap(r).ok().unwrap(),
+                Rc::try_unwrap(l.0).ok().unwrap(),
+                Rc::try_unwrap(r.0).ok().unwrap(),
             )
         })
     }
@@ -636,8 +704,8 @@ impl<L, R> Iterator for IntoIter<L, R> {
         // unwraps are safe because right2left is gone
         self.inner.next().map(|(l, r)| {
             (
-                Rc::try_unwrap(l).ok().unwrap(),
-                Rc::try_unwrap(r).ok().unwrap(),
+                Rc::try_unwrap(l.0).ok().unwrap(),
+                Rc::try_unwrap(r.0).ok().unwrap(),
             )
         })
     }
@@ -653,12 +721,12 @@ impl<L, R> Iterator for IntoIter<L, R> {
 ///
 /// [`iter`]: BiBTreeMap::iter
 pub struct Iter<'a, L, R> {
-    inner: btree_map::Iter<'a, Rc<L>, Rc<R>>,
+    inner: btree_map::Iter<'a, Ref<L>, Ref<R>>,
 }
 
 impl<'a, L, R> DoubleEndedIterator for Iter<'a, L, R> {
     fn next_back(&mut self) -> Option<Self::Item> {
-        self.inner.next_back().map(|(l, r)| (&**l, &**r))
+        self.inner.next_back().map(|(l, r)| (&*l.0, &*r.0))
     }
 }
 
@@ -670,7 +738,7 @@ impl<'a, L, R> Iterator for Iter<'a, L, R> {
     type Item = (&'a L, &'a R);
 
     fn next(&mut self) -> Option<Self::Item> {
-        self.inner.next().map(|(l, r)| (&**l, &**r))
+        self.inner.next().map(|(l, r)| (&*l.0, &*r.0))
     }
 
     fn size_hint(&self) -> (usize, Option<usize>) {
@@ -684,12 +752,12 @@ impl<'a, L, R> Iterator for Iter<'a, L, R> {
 ///
 /// [`left_values`]: BiBTreeMap::left_values
 pub struct LeftValues<'a, L, R> {
-    inner: btree_map::Iter<'a, Rc<L>, Rc<R>>,
+    inner: btree_map::Iter<'a, Ref<L>, Ref<R>>,
 }
 
 impl<'a, L, R> DoubleEndedIterator for LeftValues<'a, L, R> {
     fn next_back(&mut self) -> Option<Self::Item> {
-        self.inner.next_back().map(|(l, _)| &**l)
+        self.inner.next_back().map(|(l, _)| &*l.0)
     }
 }
 
@@ -701,7 +769,7 @@ impl<'a, L, R> Iterator for LeftValues<'a, L, R> {
     type Item = &'a L;
 
     fn next(&mut self) -> Option<Self::Item> {
-        self.inner.next().map(|(l, _)| &**l)
+        self.inner.next().map(|(l, _)| &*l.0)
     }
 
     fn size_hint(&self) -> (usize, Option<usize>) {
@@ -715,12 +783,12 @@ impl<'a, L, R> Iterator for LeftValues<'a, L, R> {
 ///
 /// [`right_values`]: BiBTreeMap::right_values
 pub struct RightValues<'a, L, R> {
-    inner: btree_map::Iter<'a, Rc<R>, Rc<L>>,
+    inner: btree_map::Iter<'a, Ref<R>, Ref<L>>,
 }
 
 impl<'a, L, R> DoubleEndedIterator for RightValues<'a, L, R> {
     fn next_back(&mut self) -> Option<Self::Item> {
-        self.inner.next_back().map(|(r, _)| &**r)
+        self.inner.next_back().map(|(r, _)| &*r.0)
     }
 }
 
@@ -732,7 +800,7 @@ impl<'a, L, R> Iterator for RightValues<'a, L, R> {
     type Item = &'a R;
 
     fn next(&mut self) -> Option<Self::Item> {
-        self.inner.next().map(|(r, _)| &**r)
+        self.inner.next().map(|(r, _)| &*r.0)
     }
 
     fn size_hint(&self) -> (usize, Option<usize>) {
@@ -747,12 +815,12 @@ impl<'a, L, R> Iterator for RightValues<'a, L, R> {
 /// [`left_range`]: BiBTreeMap::left_range
 #[derive(Debug)]
 pub struct LeftRange<'a, L, R> {
-    inner: btree_map::Range<'a, Rc<L>, Rc<R>>,
+    inner: btree_map::Range<'a, Ref<L>, Ref<R>>,
 }
 
 impl<'a, L, R> DoubleEndedIterator for LeftRange<'a, L, R> {
     fn next_back(&mut self) -> Option<Self::Item> {
-        self.inner.next_back().map(|(l, r)| (&**l, &**r))
+        self.inner.next_back().map(|(l, r)| (&*l.0, &*r.0))
     }
 }
 
@@ -764,7 +832,7 @@ impl<'a, L, R> Iterator for LeftRange<'a, L, R> {
     type Item = (&'a L, &'a R);
 
     fn next(&mut self) -> Option<Self::Item> {
-        self.inner.next().map(|(l, r)| (&**l, &**r))
+        self.inner.next().map(|(l, r)| (&*l.0, &*r.0))
     }
 
     fn size_hint(&self) -> (usize, Option<usize>) {
@@ -779,12 +847,12 @@ impl<'a, L, R> Iterator for LeftRange<'a, L, R> {
 /// [`right_range`]: BiBTreeMap::right_range
 #[derive(Debug)]
 pub struct RightRange<'a, L, R> {
-    inner: btree_map::Range<'a, Rc<R>, Rc<L>>,
+    inner: btree_map::Range<'a, Ref<R>, Ref<L>>,
 }
 
 impl<'a, L, R> DoubleEndedIterator for RightRange<'a, L, R> {
     fn next_back(&mut self) -> Option<Self::Item> {
-        self.inner.next_back().map(|(r, l)| (&**l, &**r))
+        self.inner.next_back().map(|(r, l)| (&*l.0, &*r.0))
     }
 }
 
@@ -796,13 +864,14 @@ impl<'a, L, R> Iterator for RightRange<'a, L, R> {
     type Item = (&'a L, &'a R);
 
     fn next(&mut self) -> Option<Self::Item> {
-        self.inner.next().map(|(r, l)| (&**l, &**r))
+        self.inner.next().map(|(r, l)| (&*l.0, &*r.0))
     }
 
     fn size_hint(&self) -> (usize, Option<usize>) {
         self.inner.size_hint()
     }
 }
+
 // safe because internal Rcs are not exposed by the api and the reference counts
 // only change in methods with &mut self
 unsafe impl<L, R> Send for BiBTreeMap<L, R>
@@ -811,6 +880,7 @@ where
     R: Send,
 {
 }
+
 unsafe impl<L, R> Sync for BiBTreeMap<L, R>
 where
     L: Sync,
diff --git a/src/hash.rs b/src/hash.rs
index 684bbeb..5e761c0 100644
--- a/src/hash.rs
+++ b/src/hash.rs
@@ -1,12 +1,15 @@
 //! A bimap backed by two `HashMap`s.
 
-use crate::Overwritten;
+use crate::{
+    mem::{Ref, Wrapper},
+    Overwritten,
+};
 use std::{
+    borrow::Borrow,
     collections::{hash_map, HashMap},
     fmt,
     hash::{BuildHasher, Hash},
     iter::{Extend, FromIterator, FusedIterator},
-    ops::Deref,
     rc::Rc,
 };
 
@@ -16,8 +19,8 @@ use std::{
 ///
 /// [module-level documentation]: crate
 pub struct BiHashMap<L, R, LS = hash_map::RandomState, RS = hash_map::RandomState> {
-    left2right: HashMap<Rc<L>, Rc<R>, LS>,
-    right2left: HashMap<Rc<R>, Rc<L>, RS>,
+    left2right: HashMap<Ref<L>, Ref<R>, LS>,
+    right2left: HashMap<Ref<R>, Ref<L>, RS>,
 }
 
 impl<L, R> BiHashMap<L, R, hash_map::RandomState, hash_map::RandomState>
@@ -267,6 +270,9 @@ where
     /// Returns a reference to the right value corresponding to the given left
     /// value.
     ///
+    /// The input may be any borrowed form of the bimap's left type, but `Eq`
+    /// and `Hash` on the borrowed form *must* match those for the left type.
+    ///
     /// # Examples
     ///
     /// ```
@@ -277,13 +283,20 @@ where
     /// assert_eq!(bimap.get_by_left(&'a'), Some(&1));
     /// assert_eq!(bimap.get_by_left(&'z'), None);
     /// ```
-    pub fn get_by_left(&self, left: &L) -> Option<&R> {
-        self.left2right.get(left).map(Deref::deref)
+    pub fn get_by_left<Q>(&self, left: &Q) -> Option<&R>
+    where
+        L: Borrow<Q>,
+        Q: Eq + Hash + ?Sized,
+    {
+        self.left2right.get(Wrapper::wrap(left)).map(|r| &*r.0)
     }
 
     /// Returns a reference to the left value corresponding to the given right
     /// value.
     ///
+    /// The input may be any borrowed form of the bimap's right type, but `Eq`
+    /// and `Hash` on the borrowed form *must* match those for the right type.
+    ///
     /// # Examples
     ///
     /// ```
@@ -294,13 +307,20 @@ where
     /// assert_eq!(bimap.get_by_right(&1), Some(&'a'));
     /// assert_eq!(bimap.get_by_right(&2), None);
     /// ```
-    pub fn get_by_right(&self, right: &R) -> Option<&L> {
-        self.right2left.get(right).map(Deref::deref)
+    pub fn get_by_right<Q>(&self, right: &Q) -> Option<&L>
+    where
+        R: Borrow<Q>,
+        Q: Eq + Hash + ?Sized,
+    {
+        self.right2left.get(Wrapper::wrap(right)).map(|l| &*l.0)
     }
 
     /// Returns `true` if the bimap contains the given left value and `false`
     /// otherwise.
     ///
+    /// The input may be any borrowed form of the bimap's left type, but `Eq`
+    /// and `Hash` on the borrowed form *must* match those for the left type.
+    ///
     /// # Examples
     ///
     /// ```
@@ -311,13 +331,20 @@ where
     /// assert!(bimap.contains_left(&'a'));
     /// assert!(!bimap.contains_left(&'b'));
     /// ```
-    pub fn contains_left(&self, left: &L) -> bool {
-        self.left2right.contains_key(left)
+    pub fn contains_left<Q>(&self, left: &Q) -> bool
+    where
+        L: Borrow<Q>,
+        Q: Eq + Hash + ?Sized,
+    {
+        self.left2right.contains_key(Wrapper::wrap(left))
     }
 
     /// Returns `true` if the map contains the given right value and `false`
     /// otherwise.
     ///
+    /// The input may be any borrowed form of the bimap's right type, but `Eq`
+    /// and `Hash` on the borrowed form *must* match those for the right type.
+    ///
     /// # Examples
     ///
     /// ```
@@ -328,8 +355,12 @@ where
     /// assert!(bimap.contains_right(&1));
     /// assert!(!bimap.contains_right(&2));
     /// ```
-    pub fn contains_right(&self, right: &R) -> bool {
-        self.right2left.contains_key(right)
+    pub fn contains_right<Q>(&self, right: &Q) -> bool
+    where
+        R: Borrow<Q>,
+        Q: Eq + Hash + ?Sized,
+    {
+        self.right2left.contains_key(Wrapper::wrap(right))
     }
 
     /// Removes the left-right pair corresponding to the given left value.
@@ -337,6 +368,9 @@ where
     /// Returns the previous left-right pair if the map contained the left value
     /// and `None` otherwise.
     ///
+    /// The input may be any borrowed form of the bimap's left type, but `Eq`
+    /// and `Hash` on the borrowed form *must* match those for the left type.
+    ///
     /// # Examples
     ///
     /// ```
@@ -350,14 +384,18 @@ where
     /// assert_eq!(bimap.remove_by_left(&'b'), Some(('b', 2)));
     /// assert_eq!(bimap.remove_by_left(&'b'), None);
     /// ```
-    pub fn remove_by_left(&mut self, left: &L) -> Option<(L, R)> {
-        self.left2right.remove(left).map(|right_rc| {
+    pub fn remove_by_left<Q>(&mut self, left: &Q) -> Option<(L, R)>
+    where
+        L: Borrow<Q>,
+        Q: Eq + Hash + ?Sized,
+    {
+        self.left2right.remove(Wrapper::wrap(left)).map(|right_rc| {
             // unwrap is safe because we know right2left contains the key (it's a bimap)
             let left_rc = self.right2left.remove(&right_rc).unwrap();
             // at this point we can safely unwrap because the other pointers are gone
             (
-                Rc::try_unwrap(left_rc).ok().unwrap(),
-                Rc::try_unwrap(right_rc).ok().unwrap(),
+                Rc::try_unwrap(left_rc.0).ok().unwrap(),
+                Rc::try_unwrap(right_rc.0).ok().unwrap(),
             )
         })
     }
@@ -367,6 +405,9 @@ where
     /// Returns the previous left-right pair if the map contained the right
     /// value and `None` otherwise.
     ///
+    /// The input may be any borrowed form of the bimap's right type, but `Eq`
+    /// and `Hash` on the borrowed form *must* match those for the right type.
+    ///
     /// # Examples
     ///
     /// ```
@@ -380,14 +421,18 @@ where
     /// assert_eq!(bimap.remove_by_right(&2), Some(('b', 2)));
     /// assert_eq!(bimap.remove_by_right(&2), None);
     /// ```
-    pub fn remove_by_right(&mut self, right: &R) -> Option<(L, R)> {
-        self.right2left.remove(right).map(|left_rc| {
+    pub fn remove_by_right<Q>(&mut self, right: &Q) -> Option<(L, R)>
+    where
+        R: Borrow<Q>,
+        Q: Eq + Hash + ?Sized,
+    {
+        self.right2left.remove(Wrapper::wrap(right)).map(|left_rc| {
             // unwrap is safe because we know left2right contains the key (it's a bimap)
             let right_rc = self.left2right.remove(&left_rc).unwrap();
             // at this point we can safely unwrap because the other pointers are gone
             (
-                Rc::try_unwrap(left_rc).ok().unwrap(),
-                Rc::try_unwrap(right_rc).ok().unwrap(),
+                Rc::try_unwrap(left_rc.0).ok().unwrap(),
+                Rc::try_unwrap(right_rc.0).ok().unwrap(),
             )
         })
     }
@@ -514,7 +559,7 @@ where
         let mut f = f;
         let right2left = &mut self.right2left;
         self.left2right.retain(|l, r| {
-            let to_retain = f(l, r);
+            let to_retain = f(&l.0, &r.0);
             if !to_retain {
                 right2left.remove(r);
             }
@@ -525,10 +570,10 @@ where
     /// Inserts the given left-right pair into the bimap without checking if the
     /// pair already exists.
     fn insert_unchecked(&mut self, left: L, right: R) {
-        let left_rc = Rc::new(left);
-        let right_rc = Rc::new(right);
-        self.left2right.insert(left_rc.clone(), right_rc.clone());
-        self.right2left.insert(right_rc, left_rc);
+        let left = Ref(Rc::new(left));
+        let right = Ref(Rc::new(right));
+        self.left2right.insert(left.clone(), right.clone());
+        self.right2left.insert(right, left);
     }
 }
 
@@ -690,7 +735,7 @@ where
 
 /// An owning iterator over the left-right pairs in a `BiHashMap`.
 pub struct IntoIter<L, R> {
-    inner: hash_map::IntoIter<Rc<L>, Rc<R>>,
+    inner: hash_map::IntoIter<Ref<L>, Ref<R>>,
 }
 
 impl<L, R> ExactSizeIterator for IntoIter<L, R> {}
@@ -703,8 +748,8 @@ impl<L, R> Iterator for IntoIter<L, R> {
     fn next(&mut self) -> Option<Self::Item> {
         self.inner.next().map(|(l, r)| {
             (
-                Rc::try_unwrap(l).ok().unwrap(),
-                Rc::try_unwrap(r).ok().unwrap(),
+                Rc::try_unwrap(l.0).ok().unwrap(),
+                Rc::try_unwrap(r.0).ok().unwrap(),
             )
         })
     }
@@ -720,7 +765,7 @@ impl<L, R> Iterator for IntoIter<L, R> {
 ///
 /// [`iter`]: BiHashMap::iter
 pub struct Iter<'a, L, R> {
-    inner: hash_map::Iter<'a, Rc<L>, Rc<R>>,
+    inner: hash_map::Iter<'a, Ref<L>, Ref<R>>,
 }
 
 impl<'a, L, R> ExactSizeIterator for Iter<'a, L, R> {}
@@ -731,9 +776,7 @@ impl<'a, L, R> Iterator for Iter<'a, L, R> {
     type Item = (&'a L, &'a R);
 
     fn next(&mut self) -> Option<Self::Item> {
-        self.inner
-            .next()
-            .map(|(l, r)| (Deref::deref(l), Deref::deref(r)))
+        self.inner.next().map(|(l, r)| (&*l.0, &*r.0))
     }
 
     fn size_hint(&self) -> (usize, Option<usize>) {
@@ -747,7 +790,7 @@ impl<'a, L, R> Iterator for Iter<'a, L, R> {
 ///
 /// [`left_values`]: BiHashMap::left_values
 pub struct LeftValues<'a, L, R> {
-    inner: hash_map::Iter<'a, Rc<L>, Rc<R>>,
+    inner: hash_map::Iter<'a, Ref<L>, Ref<R>>,
 }
 
 impl<'a, L, R> ExactSizeIterator for LeftValues<'a, L, R> {}
@@ -758,7 +801,7 @@ impl<'a, L, R> Iterator for LeftValues<'a, L, R> {
     type Item = &'a L;
 
     fn next(&mut self) -> Option<Self::Item> {
-        self.inner.next().map(|(l, _)| Deref::deref(l))
+        self.inner.next().map(|(l, _)| &*l.0)
     }
 
     fn size_hint(&self) -> (usize, Option<usize>) {
@@ -772,7 +815,7 @@ impl<'a, L, R> Iterator for LeftValues<'a, L, R> {
 ///
 /// [`right_values`]: BiHashMap::right_values
 pub struct RightValues<'a, L, R> {
-    inner: hash_map::Iter<'a, Rc<R>, Rc<L>>,
+    inner: hash_map::Iter<'a, Ref<R>, Ref<L>>,
 }
 
 impl<'a, L, R> ExactSizeIterator for RightValues<'a, L, R> {}
@@ -783,7 +826,7 @@ impl<'a, L, R> Iterator for RightValues<'a, L, R> {
     type Item = &'a R;
 
     fn next(&mut self) -> Option<Self::Item> {
-        self.inner.next().map(|(r, _)| Deref::deref(r))
+        self.inner.next().map(|(r, _)| &*r.0)
     }
 
     fn size_hint(&self) -> (usize, Option<usize>) {
diff --git a/src/lib.rs b/src/lib.rs
index 721e9d8..88756d5 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -199,6 +199,8 @@
 #[macro_use]
 extern crate alloc;
 
+mod mem;
+
 pub mod btree;
 pub use btree::BiBTreeMap;
 
diff --git a/src/mem.rs b/src/mem.rs
new file mode 100644
index 0000000..1dde42f
--- /dev/null
+++ b/src/mem.rs
@@ -0,0 +1,54 @@
+use alloc::rc::Rc;
+use core::{borrow::Borrow, fmt, ops::Bound};
+
+#[derive(Eq, Hash, Ord, PartialEq, PartialOrd)]
+pub struct Ref<T>(pub Rc<T>);
+
+impl<T> Clone for Ref<T> {
+    fn clone(&self) -> Self {
+        Self(self.0.clone())
+    }
+}
+
+impl<T> fmt::Debug for Ref<T>
+where
+    T: fmt::Debug,
+{
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        self.0.fmt(f)
+    }
+}
+
+#[derive(Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
+#[repr(transparent)]
+pub struct Wrapper<T: ?Sized>(pub T);
+
+impl<T: ?Sized> Wrapper<T> {
+    pub fn wrap(value: &T) -> &Self {
+        // safe because Wrapper<T> is #[repr(transparent)]
+        unsafe { core::mem::transmute(value) }
+    }
+
+    pub fn wrap_bound(bound: Bound<&T>) -> Bound<&Self> {
+        match bound {
+            Bound::Included(t) => Bound::Included(Self::wrap(t)),
+            Bound::Excluded(t) => Bound::Excluded(Self::wrap(t)),
+            Bound::Unbounded => Bound::Unbounded,
+        }
+    }
+}
+
+impl<K, Q> Borrow<Wrapper<Q>> for Ref<K>
+where
+    K: Borrow<Q>,
+    Q: ?Sized,
+{
+    fn borrow(&self) -> &Wrapper<Q> {
+        // Rc<K>: Borrow<K>
+        let k: &K = self.0.borrow();
+        // K: Borrow<Q>
+        let q: &Q = k.borrow();
+
+        Wrapper::wrap(q)
+    }
+}


Test patch: