Assert vectors equal in any order?

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

You can sort them and then compare them.

2 Likes

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

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.

2 Likes

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

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

1 Like

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

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

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=fbf86bfb5503a28b86840bc15d955e65

Also hash sets don't properly handle duplicated elements.

2 Likes

d'oh!

so I need to convert them both into HashSets?

Ah I see there are some answers here and it does exactly that (where duplicates don't matter): https://stackoverflow.com/questions/42748277/how-do-i-test-for-the-equality-of-two-unordered-lists

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.

3 Likes

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

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

1 Like

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