在两个集合中共享一个参考变量

Question

我正在尝试在两个集合中共享一个参考：一个地图和一个列表。我想推送到这两个集合，并从列表的后面删除，也从地图中删除。这段代码只是展示我想要做的一个示例，它甚至没有编译！

实现此目标的正确范例是什么？最佳实践是什么样的保证？

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

同时将单个项目存储在多个集合中的想法并不新鲜……而且并不简单。

共享元素的常见想法是不安全地执行（知道有多少集合）或使用共享指针执行此操作。

盲目地使用带有共享指针的常规集合会有些低效：

• 基于节点的集合意味着你有一个双重间接
• 从一个视图切换到另一个视图需要重新查找元素

在 Boost.MultiIndex (C++) 中，使用的范式是创建一个侵入节点来包装值，然后将这个节点链接到各个视图中。技巧（和困难）是以一种允许到达周围元素的方式制作侵入节点，以便能够在 O(1) 或 O(log N) 中“取消链接”它。

这样unsafe做会很好，我不建议尝试它，除非您准备好花大量时间在上面。

因此，为了快速解决方案：

type Node = Rc<RefCell<Data>>;

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

只要您不需要删除 by url，这就足够有效了。

完整示例：

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() {}