Assert vectors equal in any order?

help
1

How do you assert that say vec![a,b,c] and vec![b,c,a] are equal in a test?

2 Likes
2

You can sort them and then compare them.

3 Likes
3

My gut reaction is to sort and compare, but you could probably do it O(N^2) without needing clone/move/etc or so by just iterating one list and testing if each element exists in the other list (which would possible be slower than sort and compare to be honest, benchmark if it matters, but I doubt it, just sort and compare).

1 Like
4

Sort and compare is O(N log(N)). You can do it in O(N) by turning one of them into a hashmap and doing lookups from the other.

3 Likes
5

True, a hashset would be quite fast, especially if it was compile-time defined, simple iteration and test then.

6

sort and compare also has implications for clone or mut... anyway, thanks y'all, great solutions here :slight_smile:

2 Likes
7

Thoughts?

fn iters_equal_anyorder<T: Eq + Hash>(mut i1:impl Iterator<Item = T>, i2: impl Iterator<Item = T>) -> bool {
    let set:HashSet<T> = i2.collect();
    i1.all(|x| set.contains(&x))
}
8

That's a subset operation:

fn main() {
    let a = vec![1];
    let b = vec![1, 2];
    
    println!("{:?}", iters_equal_anyorder(a.into_iter(), b.into_iter()));
}

Also hash sets don't properly handle duplicated elements.

2 Likes
9

d'oh!

so I need to convert them both into HashSets?

10

Ah I see there are some answers here and it does exactly that (where duplicates don't matter): rust - How do I test for the equality of two unordered lists? - Stack Overflow

11

If you care about duplicates, you can use a hash map from item to count and then assert that the hash maps are equal.

That said, I would probably just go for the sort and compare.

5 Likes
12

just for the sake of honing my chops, here's take 2 with that approach in mind... thoughts/code-review appreciated (e.g. is there a way to avoid the duplicate generic definition?). Thanks again!

Playground

fn iters_equal_anyorder<T: Eq + Hash>(i1:impl Iterator<Item = T>, i2: impl Iterator<Item = T>) -> bool {
    fn get_lookup<T: Eq + Hash>(iter:impl Iterator<Item = T>) -> HashMap<T, usize> {
        let mut lookup = HashMap::<T, usize>::new();
        for value in iter {
            match lookup.entry(value) {
                Entry::Occupied(entry) => { *entry.into_mut() += 1; },
                Entry::Vacant(entry) => { entry.insert(0); }
            }
        }
        lookup
    }
    get_lookup(i1) == get_lookup(i2)
}
13

Looks reasonable to me. I would probably use IntoIterator instead, to allow passing e.g. a vector directly.

1 Like
14

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.