在两个集合中共享一个引用变量

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

- Navid Nabavi

Answer 1

在多个集合中同时存储单个项目的想法并不新鲜...也不简单。

共享元素的常见方法是通过不安全的方式（知道有多少个集合）或使用共享指针。

只是盲目地使用带有共享指针的普通集合存在一些低效性：

基于节点的集合意味着您需要进行双重间接引用。

从一个视图切换到另一个视图需要重新查找元素。

在Boost.MultiIndex（C ++）中，使用的范例是创建一个包装值的内部节点，并将此节点链接到各种视图中。诀窍（和难点）在于以允许获取周围元素的方式来构建内部节点，以便能够在O（1）或O（log N）中“取消链接”它。

这样做相当危险，我不建议尝试，除非您准备花费大量时间。

因此，对于快速解决方案：

type Node = Rc<RefCell<Data>>;

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

只要您不需要通过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() {}

- Matthieu M.

---

RefCell 中的性能问题如何？我知道它为项目提供了 RWLock。在处理大量数据时，这不是一个问题吗？ - Navid Nabavi

@NavidNabavi 从语义上讲，它类似于RWLock，允许多个读取器但只有一个写入器。但与锁不同的是，它不需要跨线程工作，因此获取可变引用实际上是普通的非原子内存访问（接近您稍后访问的数据，因此实际上是免费的）和条件跳转。这很便宜，唯一可能的减速是因为它需要额外的一个字的内存，这可能会影响缓存。但是为什么不进行基准测试并自行查看呢？ - user395760

Answer 2

个人而言，我会使用 Rc 替代 Box。

或者，您可以将索引存储为哈希映射的值类型（即使用 HashMap<String, usize> 而不是 HashMap<String, Box<Data>>）。

根据您的实际需求，只使用列表或映射可能更好，而不是同时使用两者。

- Adrian

---

我需要通过字符串访问值，并通过列表删除值，这就是为什么我必须同时使用它们以获得更好的性能。同时，可变性也是另一个必要的关键。 - Navid Nabavi

如果你需要可变性，你可以使用RefCell，但我不建议这样做。 - Adrian

请注意，如果您需要性能，链表通常不是最佳选择，特别是因为您只使用 {pop,push}_back。您可以存储一个 HashMap<String, *const Data>> 并使用一些 unsafe 块。只要确保列表和映射同步，这将是您特定数据结构的安全包装器。 - mcarton

我需要一个优先队列，其中元素可以从任何地方删除，这就是为什么我需要一个链表的原因。因此，由于我将从我的顺序集合中的任何位置进行删除，链表在我的用例中将表现更好。顺便说一下，我的问题是要在集合中拥有共享引用，而示例没有提供我将来需要的细节。但是我肯定需要它们一起工作。 - Navid Nabavi

@NavidNabavi：不要确定链表在中间删除操作上的性能更好；性能优势只有在大型列表中才会发挥作用，因此您需要测量与Vec相比的性能（特别是如果顺序不重要，则使用Vec::swap_remove，它也是O(1)）。 - Matthieu M.