Share a reference variable in two collections

Question

I am trying to share a reference in two collections: a map and a list. I want to push to both of the collections and remove from the back of the list and remove from the map too. This code is just a sample to present what I want to do, it doesn't even compile!

What is the right paradigm to implement this? What kind of guarantees are the best practice?

use std::collections::{HashMap, LinkedList};

struct Data {
    url: String,
    access: u64,
}

struct Holder {
    list: LinkedList<Box<Data>>,
    map: HashMap<String, Box<Data>>,
}

impl Holder {
    fn push(&mut self, d: Data) {
        let boxed = Box::new(d);
        self.list.push_back(boxed);
        self.map.insert(d.url.to_owned(), boxed);
    }

    fn remove_last(&mut self) {
        if let Some(v) = self.list.back() {
            self.map.remove(&v.url);
        }
        self.list.pop_back();
    }
}

Answer 1

The idea of storing a single item in multiple collections simultaneously is not new... and is not simple.

The common idea to sharing elements is either doing it unsafely (knowing how many collections there are) or doing it with a shared pointer.

There is a some inefficiency in just blindly using regular collections with a shared pointer:

• Node based collections mean you have a double indirection
• Switching from one view to the other require finding the element all over again

In Boost.MultiIndex (C++), the paradigm used is to create an intrusive node to wrap the value, and then link this node in the various views. The trick (and difficulty) is to craft the intrusive node in a way that allows getting to the surrounding elements to be able to "unlink" it in O(1) or O(log N).

It would be quite unsafe to do so, and I don't recommend attempting it unless you are ready to spend significant time on it.

Thus, for a quick solution:

type Node = Rc<RefCell<Data>>;

struct Holder {
    list: LinkedList<Node>,
    map: HashMap<String, Node>,
}

As long as you do not need to remove by url, this is efficient enough.

---

Complete example:

use std::collections::{HashMap, LinkedList};
use std::cell::RefCell;
use std::rc::Rc;

struct Data {
    url: String,
    access: u64,
}

type Node = Rc<RefCell<Data>>;

struct Holder {
    list: LinkedList<Node>,
    map: HashMap<String, Node>,
}

impl Holder {
    fn push(&mut self, d: Data) {
        let url = d.url.to_owned();
        let node = Rc::new(RefCell::new(d));
        self.list.push_back(Rc::clone(&node));
        self.map.insert(url, node);
    }

    fn remove_last(&mut self) {
        if let Some(node) = self.list.back() {
            self.map.remove(&node.borrow().url);
        }
        self.list.pop_back();
    }
}

fn main() {}

Answer 2

Personally, I would use Rc instead of Box.

Alternatively, you could store indexes into your list as the value type of your hash map (i.e. use HashMap<String, usize> instead of HashMap<String, Box<Data>>.

Depending on what you are trying to do, it might be a better idea to only have either a list or a map, and not both.