Vec::dedup Removes Consecutive Duplicates, Not Global Duplicates

Vec::dedup removes consecutive repeated elements. It does not search the complete vector for every value seen before. The failing fixture starts with 4, 7, 4, 4, 7. The adjacent 4, 4 run collapses, but the earlier 4 and final 7 remain.

Dedup is a run operation

The Vec::dedup documentation says consecutive repeated elements are removed. This gives an in-place linear pass with no extra set. It also preserves the order of the surviving runs.

I picture the algorithm as reading one run at a time. When the next element equals the last retained element, it is removed. When a different value appears, a new run begins. There is no memory of values from older runs.

The method is therefore ideal after grouping or sorting and useful for compressed event streams. It is not a drop-in implementation of the general statement “make these values unique.”

Global uniqueness needs another invariant

The repaired fixture sorts with sort_unstable before deduplication. Sorting places equal values next to one another, so removing consecutive duplicates becomes global deduplication. The tradeoff is that original order is lost and T needs ordering.

If first-seen order must remain, I retain elements while inserting keys into a HashSet. That needs hashing, equality, and extra memory. If the value space is small, a bit set or boolean table may be simpler. If values arrive already grouped, plain dedup is enough.

The correct algorithm follows the required equivalence and order contract. “Unique” without those details is incomplete.

Equality can be customised

dedup_by lets neighbouring elements be considered equal through a predicate, and dedup_by_key derives a comparison key. Their scope is still consecutive elements. A predicate comparing record IDs does not remember an ID seen ten positions ago.

The dedup_by predicate receives elements in an order that can surprise people, so I follow its documented arguments and avoid predicates with external side effects. Its purpose is to decide whether neighbouring retained candidates belong to one run.

For floating-point or normalised text, I define equality carefully. Case-folding, Unicode normalisation, approximate numbers, and version keys can make “duplicate” a domain operation. Sorting and deduplication must use compatible relations or equal items may not become adjacent.

Mutation and destruction are observable

Deduplication removes values and drops them. For ordinary data this is unremarkable. For guards, temporary files, reference-counted handles, or types with meaningful Drop, removal can release resources during the operation.

If comparison panics, Rust preserves memory safety but the exact partially processed state should not be treated as a transaction. I keep equality pure and move fallible normalisation before the mutation when rollback matters.

The vector retains its allocation. Length decreases, capacity normally remains available for later pushes. This is useful for reusable buffers but should not be confused with returning memory to the allocator.

Tests need separated duplicates

A test containing only [1, 1, 2, 2] makes both consecutive and global algorithms produce the same answer. It cannot detect the misunderstanding. I include [1, 2, 1], already unique input, an empty vector, and one long run.

When order must remain, the expected sequence is important. When order may change, I state that explicitly and compare the chosen canonical form. Property tests can assert that no adjacent pair is equal for dedup, or that every value occurs once for a global algorithm. Those are different properties.

My dedup checklist

• Do I need to remove repeated runs or every repeated value?
• Is original order part of the result contract?
• Can I sort, and does the ordering agree with equality?
• Would a HashSet, bit set, or domain key express uniqueness better?
• Are equality and key functions pure and inexpensive?
• What happens when removed values are dropped?
• Does the test include equal values separated by another value?
• Am I asserting adjacency uniqueness or global uniqueness?

The core principle is that a method's locality matters. dedup remembers the retained neighbour, not the whole history. I use it for runs, combine it with sorting for ordered types, and choose explicit seen-state when stable global uniqueness is the real requirement.