小编Ste*_*ein的帖子

我的算法需要通过删除元素来迭代地收缩集合,并在每次迭代中删除元素并使用收缩集做一些事情.和:

• 我需要一个快速查找的真实集合,而不仅仅是包含唯一元素的向量.
• 元素的选择是任意的:算法的结果不依赖于访问的顺序.性能可能与该选择有很大不同,但是假设我想要最简单的代码并将其留给集合本身以选择它可以有效移除的元素.
• 顺便说一下,我的算法是Bron-Kerbosch算法的基本形式.该算法的更智能版本工作得更快(大部分),因为他们不会选择任意元素,我想知道这种努力能带来多少回报.

Python集合的pop成员几乎就是这样做的.在Scala和Go中,选择和删除哈希集的"第一个"元素似乎工作正常(其中"first"对应于迭代器).在Rust中,这类似于:

// split off an arbitrary element from a (non-empty) set
pub fn pop<T>(set: &mut HashSet<T>) -> T
where
    T: Eq + Clone + std::hash::Hash,
{
    let elt = set.iter().next().cloned().unwrap();
    set.remove(&elt);
    elt
}

与其他语言相比,这似乎是一个性能瓶颈.我在操场上对一些类似pop的函数的一些实现进行了基准测试,但没有一个表现良好.显然删除一个元素并不昂贵,但选择一个元素是:iter().next()花费一大笔钱.可以retain理解地避免这种情况并没有帮助:它总是迭代整个集合.还有其他选择吗？

我有不可变的向量a，b其中元素的复制成本很低，我想创建一个向量来形成这些现有向量的串联而不改变它们 (*)。

如果其中一个向量是可变的，则较早的问题解决了这个问题，因此一个明显的答案是首先克隆向量a，例如

let mut r = a.clone();
r.extend(&b);

但这似乎既不优雅也不高效（扩展很容易导致不必要的重新分配，对吧？）。我（作为 Rust 菜鸟）提出的（修正后的）最佳选择是：

fn cat(a: &Vec<i32>, b: &Vec<i32>) -> Vec<i32> {
    let mut r = Vec::<i32>::with_capacity(a.len() + b.len());
    r.extend(a);
    r.extend(b);
    r
}

由于元素复制起来很便宜，因此对于字符串向量的更通用问题的答案应该适用于这里，但vec![a, b].concat()只有当您通过将向量移动到向量中来构造向量向量时，这似乎才有效，因为会vec![&a, &b].concat()产生“未concat找到命名的方法”。

对于这项看似简单的工作，即使它不是最佳的，是否有一种单行方式？

(*) 原来“不改变”有两种含义：

• 只是不可变的，这在 Rust 中意味着如果代码编译，它不会看到具有更改值的变量；但变量可能会被移出，进一步或未来的代码不能再使用它
• 实际上是只读的，保留变量不变以供进一步或将来的代码使用