如何测试两个无序列表的相等性？

Question

我有两个结构向量。知道那些列表的长度相同并且所有元素都在两个列表中的最佳方法是什么？

[foo, bar, baz, beh]等于，[beh, foo, baz, bar]但[beh, foo, baz, bar]不等于[beh, foo, baz, baz]。

Answer 1

如果您知道永远不会有重复项，则可以使用一组（HashSet或BTreeSet，取决于您的类型）：

use std::{collections::HashSet, hash::Hash};

fn my_eq<T>(a: &[T], b: &[T]) -> bool
where
    T: Eq + Hash,
{
    let a: HashSet<_> = a.iter().collect();
    let b: HashSet<_> = b.iter().collect();

    a == b
}

fn main() {
    assert!(my_eq(
        &["foo", "bar", "baz", "beh"],
        &["beh", "foo", "baz", "bar"]
    ));
    assert!(!my_eq(
        &["beh", "foo", "baz", "bar"],
        &["beh", "foo", "baz", "baz"]
    ));
}

如果您需要处理重复项，则也要计算值的数量：

use std::{collections::HashMap, hash::Hash};

fn my_eq<T>(a: &[T], b: &[T]) -> bool
where
    T: Eq + Hash,
{
    fn count<T>(items: &[T]) -> HashMap<&T, usize>
    where
        T: Eq + Hash,
    {
        let mut cnt = HashMap::new();
        for i in items {
            *cnt.entry(i).or_insert(0) += 1
        }
        cnt
    }

    count(a) == count(b)
}

fn main() {
    assert!(my_eq(
        &["foo", "foo", "baz", "beh"],
        &["beh", "foo", "baz", "foo"]
    ));
    assert!(!my_eq(
        &["foo", "foo", "baz", "beh"],
        &["beh", "foo", "baz"]
    ));
}

如果你想成为超级花哨，你可以创建一个NEWTYPE直接增加了这种类型的平等：

use std::{collections::HashMap, hash::Hash};

#[derive(Debug, Copy, Clone)]
struct CustomEq<'a, T: 'a>(&'a [T]);

impl<'a, T> CustomEq<'a, T>
where
    T: Eq + Hash,
{
    fn count(&self) -> HashMap<&T, usize> {
        let mut cnt = HashMap::new();
        for i in self.0 {
            *cnt.entry(i).or_insert(0) += 1
        }
        cnt
    }
}

impl<'a, T> PartialEq for CustomEq<'a, T>
where
    T: Eq + Hash,
{
    fn eq(&self, other: &Self) -> bool {
        self.count() == other.count()
    }
}

fn main() {
    assert_eq!(
        CustomEq(&["foo", "bar", "baz", "beh"]),
        CustomEq(&["beh", "foo", "baz", "bar"])
    );
    assert_ne!(
        CustomEq(&["beh", "foo", "baz", "bar"]),
        CustomEq(&["beh", "foo", "baz", "baz"])
    );
}