Set algebra with BTreeSet

Compare two tag lists as sets, then find the first repeated item in a third list. Implement both functions:

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>

Return four sorted sets

compare_tags returns (both, only_a, only_b, either):

Each vector must be sorted in ascending order and contain no duplicates. Ascending order here means the order defined by String's Ord implementation: the UTF-8 bytes are compared lexicographically, which gives the same order as comparing Unicode code points one by one.

For a = ["x", "y", "x"] and b = ["y", "z"], return (["y"], ["x"], ["z"], ["x", "y", "z"]).

Tags are exact strings: preserve case, whitespace and empty strings. Do not normalize Unicode or use locale-specific sorting. For example, "B" sorts before "a" because byte 0x42 is less than byte 0x61, and the empty string sorts before every other string. Duplicate input tags have no effect on the set results.

Empty inputs follow the same rules. If a is empty, both and only_a are empty, while only_b and either contain the distinct tags from b.

Find the earliest repeated occurrence

first_duplicate scans in input order and returns the first item whose value has already appeared. For ["a", "b", "b", "a"], return Some("b"): the second b occurs before the second a. This is not the alphabetically smallest repeated value or the value with the earliest first occurrence.

Return None when no value repeats, including for an empty list. ["", ""] returns Some(""); an empty string is still a value.

Collect owned values from borrowed iterators

Build BTreeSet<String> values from a and b. Their set-operation methods return iterators over references to their stored strings:

sa.intersection(&sb)          // present in both
sa.difference(&sb)            // present only in a
sb.difference(&sa)            // present only in b
sa.union(&sb)                 // present in either

The starter tries to collect &String items into Vec<String>, so each of its four collect calls fails to compile with error E0277 (a required trait is not implemented):

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

The function owns the sets, but these methods borrow their contents; they do not move strings out of the sets.

Add .cloned() before .collect() to produce owned strings. The adapter clones each yielded string when consumed. Calling .cloned() alone does not eagerly copy every value. String cloning and collecting the resulting vector can allocate; copying a Copy element with .copied() is a different operation and does not inherently allocate.

You can also consume a set-operation iterator without collecting a new collection, for example with .count() or .any(...). The iterator does not build an intermediate result set. Finding each result can still require examining input elements, so taking a few outputs does not imply examining only that many inputs.

Keep the direction of difference clear

Intersection and union are symmetric. Difference is directional: sa.difference(&sb) and sb.difference(&sa) can produce different results. symmetric_difference is another operation, containing values found in exactly one set; it is not one of the four return fields requested here.

is_subset, is_superset and is_disjoint answer related yes/no questions. is_disjoint expresses the intent directly. Do not assume it is always faster than checking whether an intersection has a first element; either approach can stop once overlap is found.

Use insert's result to detect repeats

BTreeSet::insert returns true when it adds a new value and false when an equal value is already present. This combines membership checking with insertion:

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

into_iter() yields owned strings, but find passes a reference to each candidate into its predicate. The predicate clones that string for storage in seen; when insertion returns false, find returns the original owned candidate. The source of the cloning requirement here is this particular iterator-and-set design, not a rule that duplicate detection always clones.

An alternative can keep the input alive and store borrowed &str keys. That avoids cloning strings into the set, but the set's nodes can still allocate. Collections own their entries; those entries may themselves be references rather than owners of the referenced text.

Calling contains and then insert also gives the correct answer, but for a new value it searches the set twice. Checking insert's return value needs one call.

Choose a collection for the required behavior

Use BTreeSet to practice ordered set operations. Its iteration order is sorted, so the output vectors need no separate sort. A HashSet solution can produce the same elements, but its unspecified iteration order requires an explicit sorting step to satisfy this contract. Output tests do not enforce the choice of collection.

A vector with repeated contains calls can be reasonable for small inputs, but processing many distinct values can take quadratically many comparisons. There is no universal small-input winner: key sizes, allocation costs and the workload affect performance.

Passing requires compilation, the expected results and Clippy with warnings treated as errors.