Set difference on BTreeSet and BTreeMap keys

1

I've got a BTreeMap, and I want to check that all items of a BTreeSet are present in the map. The simplest way would be to check the set difference is empty, but set difference methods only work if both collections are BTreeSets. How do I do it with a BTreeMap and a BTreeSet?

2 Likes
2

One simple solution is:

    set.iter().all(|k| map.contains_key(k))

However, this does a map lookup for each key. It may be faster to iterate through both collections at the same time, comparing keys as you go. The itertools crate has a merge_join_by function that can be useful for this:

    itertools::merge_join_by(set, map, |k1, (k2, _)|
        Ord::cmp(k1, k2)
    ).all(|merged| match merged {
        EitherOrBoth::Left(..) => false, // key was in set but not map
        _ => true
    });
3

(But note, the second solution requires iterating through every key in the map. If the map is large relative to the set, this may be slower than the first solution. If the speed of this comparison is important, compare the real-world performance on realistic work loads.)

1 Like
4

Thanks for the solution!

I still feel like there is an opportunity for this kind of function in the standard library. Maybe it could check lengths and decide which strategy to use?

5

A method to get the keys of a Map as a Set seems like it would be useful for many things, as long as it could be effectively zero-copy. By the time you have to iterate through the Map just to make the set, you might as well do the comparison as you iterate.

Longer term design-wise, I think there's a set-like interface trait here that it seems maps should implement for their keys.

2 Likes
6

A SortedIterator trait (and/or IntoSortedIterator) would be useful for writing generic functions like difference to work with any combination of BTreeSet, BTreeMap, or other sorted sequences.

3 Likes