Set algebra with BTreeSet

Compare two tag lists four ways, and find the first repeat in a third.

pub fn compare_tags(a: Vec<String>, b: Vec<String>)
    -> (Vec<String>, Vec<String>, Vec<String>, Vec<String>)

pub fn first_duplicate(items: Vec<String>) -> Option<String>

compare_tags returns (both, only_a, only_b, either) — intersection, a-minus-b, b-minus-a, union — each sorted ascending and free of duplicates. Duplicates inside an input list are just duplicates; ["m","m"] is the same set as ["m"].

first_duplicate returns the first item that has appeared before, or None.

Set operations return iterators, not sets

This is the design decision worth internalising, and it is why the starter does not compile:

error[E0277]: a value of type `Vec<String>` cannot be built from an iterator
              over elements of type `&String`

sa.intersection(&sb) does not build a set. It returns a lazy iterator that borrows both sets and yields &String as you consume it. Nothing is allocated until you ask for something concrete.

Two consequences follow:

1. sa.intersection(&sb).count() never allocates at all. Neither does .any(|t| t.starts_with("x")), or .take(3). You pay only for what you take. If the operation returned a BTreeSet, every one of those would build and throw away a whole collection.
2. Because the items are borrowed from sets you do not own, you cannot collect() them into Vec<String>. .cloned() (or .copied() for Copy types) inserts the allocation exactly where it belongs — visible, at the point where you decided you wanted ownership.

That second point is the same borrowed-versus-owned distinction from the ownership track, and it will keep arriving as E0277 for the rest of your Rust life. The message even tells you the shape of the fix: it has an iterator of &String and needs an iterator of String.

The four operations, and the one that is not symmetric

sa.intersection(&sb)          // in both
sa.union(&sb)                 // in either
sa.difference(&sb)            // in a, not in b
sa.symmetric_difference(&sb)  // in exactly one

difference is directional. sa.difference(&sb) and sb.difference(&sa) are different answers, and one of the test cases has both non-empty specifically so that swapping them is caught. intersection and union are symmetric; symmetric_difference is the union of the two differences, which is what its name is telling you.

There are also three predicates that answer a question without building anything: is_subset, is_superset, is_disjoint. a.is_disjoint(&b) is clearer and faster than a.intersection(&b).next().is_none(), because it can stop at the first hit and it says what you meant.

insert returns a bool, and it is the cleanest dedup idiom in the language

pub fn insert(&mut self, value: T) -> bool   // true if the value was NEW

So “have I seen this before?” and “remember that I have seen it” are the same operation, one lookup, no contains beforehand:

let mut seen = BTreeSet::new();
items.into_iter().find(|item| !seen.insert(item.clone()))

Read it as: keep inserting until an insert reports “not new”, and that item is the first duplicate. The contains-then-insert version does two lookups and has a race-shaped gap in it if the set is ever shared. HashMap::insert has the same idea with more information — it returns Option<V>, the value that was displaced.

::: question Why does first_duplicate need item.clone()? Because find‘s closure receives &String — it is only looking at the item, since it might have to hand it back to you as the return value — while insert needs an owned String to store. Exactly the same asymmetry as HashMap::get versus HashMap::entry, for exactly the same reason: a collection can only store what it owns.

You could avoid the clone by storing &str keys borrowed from a slice you keep alive — first_duplicate(items: &[String]) -> Option<&str> needs no allocation at all. The signature is the thing that decided this, not the algorithm. That is a theme worth watching for. :::

Why BTreeSet and not HashSet here

Both would answer the question. BTreeSet is specified here because the output must be sorted, and a BTreeSet is already in order — iterating it gives you the sorted answer with no sort step. With a HashSet you get the right elements in a random order (see the HashMap-order problem in this track) and have to sort anyway.

The rule of thumb: HashSet when you only ask “is it in there?”, BTreeSet when order, ranges, or reproducible output matter. And for very small collections, do not be too proud to use a Vec and contains — it beats both for a handful of elements, because there is no hashing and no pointer chasing. Just know that it goes quadratic when the collection grows, which is a later item in this track with a measurement attached.

Remember the grade is compile + tests + clippy -D warnings.