Step 3 of 6
std::set
A set is a map with keys but no values. std::set<T> holds unique values in sorted order. Inserting something that's already there does nothing, which makes a set the natural tool for "remove duplicates" and "have I seen this before?".
#include <iostream>
#include <set>
#include <vector>
int main() {
std::vector<int> rolls = {4, 2, 6, 2, 4, 4, 1};
std::set<int> seen(rolls.begin(), rolls.end()); // build from a range
seen.insert(6); // already there: no change
seen.insert(3);
for (int x : seen) std::cout << x << " ";
std::cout << "\n" << seen.size() << " distinct, has 5? " << seen.contains(5) << "\n";
std::vector<int> back(seen.begin(), seen.end()); // and back to a vector
std::cout << "smallest " << back.front() << ", largest " << back.back() << "\n";
}
1 2 3 4 6
5 distinct, has 5? 0
smallest 1, largest 6
How it works
- Containers can be built from any range given as two iterators:
std::set<int> s(v.begin(), v.end())inserts every element ofv. The same trick turns a set back into a vector. - Iterating a set always goes in sorted order.
insertreturns a pair whose.secondistrueif the value was new. That lets you detect duplicates as you go:
if (!seen.insert(x).second) { /* x was a duplicate */ }
- Like
map, a set is a balanced tree: insert, erase and lookup are O(log n).
Common mistakes
- Trying to change an element in place. Set elements are
const, because changing one could break the sorted order. Erase it and insert the new value instead. - Using a set when you need to keep duplicates. That's
std::multiset, or just a sorted vector.
Your task
Write std::vector<std::string> unique_sorted(const std::vector<std::string>& v) that returns the distinct strings in sorted order.
Challenge 2
Write std::vector<int> common(const std::vector<int>& a, const std::vector<int>& b) that returns the values found in both vectors, each once, sorted.
Challenge 3
Write int first_repeat(const std::vector<std::string>& v) that returns the index of the first element that already appeared earlier, or -1. {"a", "b", "c", "b", "a"} gives 3. set::insert returns a pair whose .second is false when the value was already there.