Why does std::unique on a C++ vector of log messages leave duplicates behind, and what must you do before calling it?
answer
- consecutive runs only
- compares each element to its predecessor
- sort to make equals adjacent
- erase the returned tail
basics
~20 sstd::unique collapses only consecutive equal elements, keeping the first of each run, so duplicates separated by other values survive. Sort the range first so equal values are adjacent, then erase from the returned iterator to end().
solid answer
~40 s`std::unique(first, last)` compares each element with the one before it and eliminates it when they are equal, so it removes runs of **consecutive** duplicates and keeps the first of each run. In `{"disk full", "disk full", "retry", "disk full"}` only the second element goes; the last `"disk full"` survives because `"retry"` separates it. Like `std::remove`, it cannot change the container's size: it returns the new logical end, and you erase the tail with `v.erase(std::unique(v.begin(), v.end()), v.end())`. To remove all duplicates, `std::sort` first so equal values become adjacent; that costs `O(N log N)` and loses the original order. If the original order must survive, track seen values in a `std::unordered_set` and use `std::erase_if` or `remove_if` instead. A custom predicate must be an equivalence relation, matching the key you sorted by.
code
cpp · 18 lines#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
int main() {
std::vector<std::string> msgs{"disk full", "disk full", "retry", "disk full", "retry"};
std::vector<std::string> a = msgs;
a.erase(std::unique(a.begin(), a.end()), a.end()); // only adjacent runs collapse
std::cout << "unique only: " << a.size() << '\n'; // 4
std::vector<std::string> b = msgs;
std::sort(b.begin(), b.end()); // equal values become adjacent
b.erase(std::unique(b.begin(), b.end()), b.end());
std::cout << "sort + unique: " << b.size() << '\n'; // 2
for (const auto& m : b) std::cout << m << '\n';
}go deeper
Remember the pattern: sort, then erase the range returned by std::unique, because unique only removes consecutive repeats.
Explain the neighbour-by-neighbour comparison, why the container keeps its size, and why the sort key and the unique predicate must match.
Choose between sort plus unique, an order-preserving hash-set filter and plain unique for bursts, based on order requirements and memory.
For large log volumes, decide whether deduplication belongs in the producer, the pipeline or the store, rather than repeated in-memory passes.
## What std::unique actually compares The standard defines `std::unique` by comparing each element **with the element just before it**: an element at position `i` is eliminated when `pred(*(i - 1), *i)` is true (with `pred` defaulting to `==`). The first element is never eliminated. The consequences: - only **consecutive runs** of equal elements are collapsed, each to its first element; - equal elements that are not adjacent are compared with different neighbours and are kept; - the survivors keep their relative order; - for a nonempty range it applies the predicate exactly `(last - first) - 1` times, a single linear pass. That makes `std::unique` the right tool for **run-length style** cleanup - collapsing a burst of identical consecutive log lines - and the wrong tool, on its own, for "remove all duplicates". ## It also does not shrink the container Like `std::remove`, `std::unique` works on iterators and returns the new logical end. The elements after it are in a valid but unspecified state and `size()` is unchanged, so it is paired with `erase`: ```cpp msgs.erase(std::unique(msgs.begin(), msgs.end()), msgs.end()); ``` There is no C++20 `std::erase`-style shortcut for `unique`; the member `std::list::unique` exists for lists and removes consecutive duplicates by relinking nodes. ## Removing every duplicate | Goal | Approach | Cost | Order | |---|---|---|---| | Collapse consecutive repeats | `unique` + `erase` | `O(N)` | preserved | | Remove all duplicates | `sort`, then `unique` + `erase` | `O(N log N)` | sorted | | Remove all duplicates, keep first-seen order | `std::unordered_set` + a filtering loop | `O(N)` expected, extra memory | preserved | | Count distinct values only | `sort` + `unique`, then distance | `O(N log N)` | n/a | The usual interview answer is the sort-then-unique combination: 1. `std::sort(msgs.begin(), msgs.end());` makes equal messages adjacent. 2. `msgs.erase(std::unique(msgs.begin(), msgs.end()), msgs.end());` keeps one of each. ## Deduplicating by a key Log records are rarely equal in every field; you dedupe by a key such as the message text. Sort and unique must agree on that key: ```cpp std::sort(log.begin(), log.end(), [](const LogRecord& a, const LogRecord& b) { return a.message < b.message; }); log.erase(std::unique(log.begin(), log.end(), [](const LogRecord& a, const LogRecord& b) { return a.message == b.message; }), log.end()); ``` Two rules apply: - The predicate passed to `std::unique` must be an **equivalence relation**. A "close enough" timestamp comparison, for example, is not transitive, and the result then depends on which neighbour each element happens to be compared with. - The sort comparator and the unique predicate must describe the same key. Sorting by message but deduplicating by message and level leaves records with equal messages but different levels interleaved, so some duplicates by message survive and some do not. If you need the earliest record for each message, sort with `std::stable_sort` (so earlier records stay first among equals) before `std::unique`, which keeps the first element of each run. ## Counting distinct values Sometimes the vector must stay intact and you only need to know how many distinct messages arrived. Two options: - copy, sort the copy, and compute `std::distance(copy.begin(), std::unique(copy.begin(), copy.end()))` - no `erase` needed, because only the returned position matters; - insert every message into a `std::unordered_set` and read its `size()`. `std::unique_copy` is a third: it writes one element per run into an output iterator, leaving the source untouched, so `std::unique_copy(sorted.begin(), sorted.end(), std::back_inserter(distinct))` builds the deduplicated list directly. Like `std::unique`, it only collapses consecutive runs, so the input still has to be sorted for a full dedupe. ## Mistakes interviewers look for - **Calling `std::unique` on unsorted data** and expecting all duplicates gone. - **Forgetting `erase`**, leaving unspecified tail elements in the vector. - **Sorting by one key and comparing by another.** - **Expecting the last of each run to survive**: the first one is kept.
- How do you remove duplicate log messages while keeping the order in which each first appeared?Track seen messages in a `std::unordered_set<std::string>` and, in a range-for loop, copy a record into a new vector only when `seen.insert(r.message).second` is true. That keeps each message's first occurrence in original order at expected linear cost, paying memory for the set. Doing it with a stateful `remove_if` predicate is common, but the standard does not state its visiting order. `std::unique` cannot help: it only compares neighbours.
- Which element of a run of equal values does std::unique keep, and how do you control which record survives?It keeps the first element of each run and eliminates the rest. To keep a particular record - the earliest - arrange that it comes first in its run: sort with `std::stable_sort` by the key, so records with equal keys keep their original order, and then call `std::unique` with a predicate comparing the same key.
- Saying std::unique removes all duplicates from any vector
- Expecting the vector to shrink after std::unique
- Sorting by one field but deduplicating by another
- Passing an approximate comparison as unique's predicate
- Thinking std::unique keeps the last element of each run