Think in keys, not positions
Choose a representation, build a set, and ask whether a key exists.
What must survive?
A vector remembers every arrival in order. A set remembers each distinct key once. A multiset remembers every copy in sorted order. A map attaches information to each unique key. The choice follows the question: attendance needs distinct IDs, ticket stock needs repeated copies, and a score table needs names with associated scores.
For arrivals 42, 7, 42, 18, a set contains 7, 18, 42. It has forgotten the second 42 and the arrival order. Keep a separate sequence when those facts matter. A map from value to frequency also has three entries, but its mapped counts add up to four.
Insert and learn whether a key was new
Include <set> for std::set and std::multiset. The default set ordering is ascending. Every insertion keeps the container ordered; duplicates do not create extra entries, and there is no push_back or separate sorting step.
Ordinary set.insert(x) returns a pair: an iterator to the stored key and a boolean indicating whether a new entry was created. This lets one operation both record x and identify its first occurrence. With d distinct fixed-size keys, ordinary insertion takes O(log(d + 1)) work; n arrivals take O(n log(n + 1)) as an upper bound.
// Complete C++23 program. Input: n, followed by n integers.
#include <iostream>
#include <set>
int main() {
int n;
std::cin >> n;
std::set<int> seen;
for (int i = 0; i < n; ++i) {
int x;
std::cin >> x;
auto result = seen.insert(x);
std::cout << (result.second ? "NEW" : "OLD")
<< ' ' << seen.size() << '\n';
}
}Membership does not create keys
contains(x) returns true or false. find(x) returns an iterator, or end() when absent. count(x) returns 0 or 1 for a set. None inserts a missing key. Use contains for existence; use find when you also need the actual element.
end() is a past-the-end marker, not a last element or a numeric sentinel. A key equal to -1 is perfectly valid; failed lookup is detected by comparing the iterator with end(). Check that comparison before dereferencing.
Set & multiset
Both containers keep values sorted. Erase one removes a single occurrence, like erase(iterator).
3 stored items · 3 distinct values
Guided simulation · Change the inputs to test your understanding.
Insert 5, 2, 5, 2, 9 into an empty set. What are its size and traversal order?
Turn the idea into code
For arrivals 7, 2, 7, 7, 4, write every NEW/OLD result and distinct count. Then explain why a set cannot report the total number of 7s.
Give me a hint
After each insertion, write only the distinct keys. The insertion flag changes only for a previously absent key.
Show the explained solution
The lines are NEW 1, NEW 2, OLD 2, OLD 2, NEW 3. The set state ends as {2, 4, 7}; repeated insertions have discarded multiplicity. Use a frequency map or multiset to preserve that information.
Your notes
Mark complete when you can explain it yourself.