How to use a struct's member as its own key when inserting the struct into a map without duplicating it?

Question

Is it possible to insert a struct into a map where the key is owned by the value being inserted?

When using hash-maps in C, this is something which I'm used to doing.

Pseudocode example:

struct MyStruct {
    pub map: BTreeMap<&String, StructThatContainsString>,
    // XXX            ^ Rust wants lifetime specified here!
}

struct StructThatContainsString {
    id: String,
    other_data: u32,
}

fn my_fn() {
    let ms = MyStruct { map: BTreeMap::new() };

    let item = StructThatContainsString {
        id: "Some Key".to_string(),
        other_data: 0,
    }

    ms.insert(&item.id, item);
}

How can this situation be correctly handled?

---

• If this isn't possible, could the reverse be done, where the value holds a reference to the key which would be a String ?

• An alternative could be to use a set instead of a map, then store the entire struct as the key, but only use one of its values when comparing (seems like it would work, but could backfire if you wanted to compare the struct in other contexts).

Answer 1

It's not going to work with plain references:

let item = StructThatContainsString {
    id: "Some Key".to_string(),
    other_data: 0,
}

ms.insert(&item.id, item);

item is moved into the map, so there can't be any pending borrows/references.

Also, methods like get_mut() would become dangerous or impossible, as it would let you modify the item that has an outstanding reference.

Assuming the reason for wanting to do this is to save space, the obvious options are:

• Take the key out of the value struct. If you need it at the same time, you've either got it when looking up a key in the map, or the iterators include both key and value:

  struct OnlyKey {
      id: String,
  }
  
  struct OnlyValue {
      other_data: u32,
  }
  

  This can be cleaned up with appropriate methods to split apart / recombine the various pieces.

• Use something like Rc for the key part of the value. Rc<T> implements Ord (required for BTreeMap) if T does.

  struct StructThatContainsString {
      id: Rc<String>,
      other_data: u32,
  }
  

Answer 2

Using a single member of a struct as a key in a map can be done (in principle) by using a set with a zero-overhead wrapper struct that only serves to override implementations.

• Override Ord, Eq, PartialEq, PartialOrd
  To control it's order in the set.

• Override Borrow so BTreeSet.get(..) can take the type used for ordering, instead of the entire struct.

• One down side with this method is you need to wrap the struct with the container when adding it into the set.

Here is a working example:

use ::std::collections::BTreeSet;

#[derive(Debug)]
pub struct MyItem {
    id: String,
    num: i64,
}

mod my_item_ord {
    use super::MyItem;

    #[derive(Debug)]
    pub struct MyItem_Ord(pub MyItem);

    use ::std::cmp::{
        PartialEq,
        Eq,
        Ord,
        Ordering,
    };
    use ::std::borrow::Borrow;

    impl PartialEq for MyItem_Ord {
        fn eq(&self, other: &Self) -> bool {
            return self.0.id.eq(&other.0.id);
        }

    }
    impl PartialOrd for MyItem_Ord {
        fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
            return self.0.id.partial_cmp(&other.0.id);
        }
    }
    impl Eq for MyItem_Ord {}
    impl Ord for MyItem_Ord {
        fn cmp(&self, other: &Self) -> Ordering {
            return self.0.id.cmp(&other.0.id);
        }
    }
    impl Borrow<str> for MyItem_Ord {
        fn borrow(&self) -> &str {
            return &self.0.id;
        }
    }
}


fn main() {
    use my_item_ord::MyItem_Ord;

    let mut c: BTreeSet<MyItem_Ord> = BTreeSet::new();

    c.insert(MyItem_Ord(MyItem { id: "Zombie".to_string(), num: 21, }));
    c.insert(MyItem_Ord(MyItem { id: "Hello".to_string(), num: 1, }));
    c.insert(MyItem_Ord(MyItem { id: "World".to_string(), num: 22, }));
    c.insert(MyItem_Ord(MyItem { id: "The".to_string(), num: 11,  }));
    c.insert(MyItem_Ord(MyItem { id: "Brown".to_string(), num: 33, }));
    c.insert(MyItem_Ord(MyItem { id: "Fox".to_string(), num: 99, }));

    for i in &c {
        println!("{:?}", i);
    }

    // Typical '.get()', too verbose needs an entire struct.
    println!("lookup: {:?}", c.get(&MyItem_Ord(MyItem { id: "Zombie".to_string(), num: -1, })));
    //                                                                            ^^^^^^^ ignored

    // Fancy '.get()' using only string, allowed because 'Borrow<str>' is implemented.
    println!("lookup: {:?}", c.get("Zombie"));

    println!("done!");
}

To avoid having to define these manually, this can be wrapped up into a macro:

///
/// Macro to create a container type to be used in a 'BTreeSet' or ordered types
/// to behave like a map where a key in the struct is used for the key.
///
/// For example, data in a set may have a unique identifier which
/// can be used in the struct as well as a key for it's use in the set.
///
///
/// ```
/// // Defines 'MyTypeOrd', a container type for existing struct,
/// // using MyType.uuid is used as the key.
/// container_order_by_member_impl(MyTypeOrd, MyType, uuid);
/// ```
///
/// See: http://stackoverflow.com/questions/41035869

#[macro_export]
macro_rules! container_type_order_by_member_struct_impl {
    ($t_ord:ident, $t_base:ty, $t_member:ident) => {
        /// Caller must define the struct, see: container_type_order_by_member_impl
        // pub struct $t_ord(pub $t_base);
        impl PartialEq for $t_ord {
            fn eq(&self, other: &Self) -> bool {
                return (self.0).$t_member.eq(&(other.0).$t_member);
            }
        }
        impl PartialOrd for $t_ord {
            fn partial_cmp(&self, other: &Self) -> Option<::std::cmp::Ordering> {
                return (self.0).$t_member.partial_cmp(&(other.0).$t_member);
            }
        }
        impl Eq for $t_ord {}
        impl Ord for $t_ord {
            fn cmp(&self, other: &Self) -> ::std::cmp::Ordering {
                return (self.0).$t_member.cmp(&(other.0).$t_member);
            }
        }
        impl ::std::borrow::Borrow<str> for $t_ord {
            fn borrow(&self) -> &str {
                return &(self.0).$t_member;
            }
        }
    }
}

/// Macro that also defines structs.
#[macro_export]
macro_rules! container_type_order_by_member_impl {
    (pub $t_ord:ident, $t_base:ty, $t_member:ident) => {
        pub struct $t_ord(pub $t_base);
        container_type_order_by_member_struct_impl!($t_ord, $t_base, $t_member);
    };
    ($t_ord:ident, $t_base:ty, $t_member:ident) => {
        struct $t_ord(pub $t_base);
        container_type_order_by_member_struct_impl!($t_ord, $t_base, $t_member);
    };
}