Walk and erase safely
Understand iterators, extremes, references, and deletion loops.
An iterator is a position in traversal
A set iterator can move one step forward or backward. It cannot be added to an integer, subtracted from another set iterator, or used like vector indexing. std::next(s.begin(), k) walks k steps and costs O(k). A sorted collection does not automatically provide fast indexing.
For a nonempty ascending set, *begin() is the smallest key and *rbegin() is the largest. For an empty set, begin() equals end(). Never dereference end() or decrement begin(). A set key is read-only because changing it in place would break the ordering. To replace a key, erase it and insert the new key.
Keys and iterators select different erase contracts
s.erase(x) safely removes the key if present and returns how many entries were removed. s.erase(it) requires a valid element iterator; passing end() is invalid. Therefore s.erase(s.find(x)) needs a successful-lookup guard when x may be absent.
Insertion into a standard ordered set, multiset, or map preserves existing element iterators. Erasing an element invalidates iterators and references to that element, while surviving entries remain valid. Never use an iterator after its element was erased.
Let erase return the next candidate
In an erase loop, assign the returned iterator after removal; otherwise increment once. Doing both can skip an element. The same standard-container pattern works for maps and multisets. GNU PBDS has its own interface, so do not assume it returns an identical iterator result.
Finding by key costs logarithmic work. Erasing an already-known valid iterator in these standard ordered containers has amortized constant cost. The pass below is O(d) amortized after construction; construction costs O(n log(n + 1)).
// Complete C++23 program. Input: n, followed by n integers.
#include <iostream>
#include <set>
int main() {
int n;
std::cin >> n;
std::set<int> values;
for (int i = 0; i < n; ++i) {
int x;
std::cin >> x;
values.insert(x);
}
for (auto it = values.begin(); it != values.end();) {
if (*it < 0) it = values.erase(it);
else ++it;
}
if (values.empty()) std::cout << "EMPTY\n";
else std::cout << *values.begin() << ' '
<< *values.rbegin() << '\n';
}A set contains {-3, -2, 4}. After erasing the iterator to -3, what should the removal loop do next?
Turn the idea into code
Remove every even key from {-2, 0, 3, 4, 7} using an iterator loop. Explain what to print if no keys remain.
Give me a hint
Use the same two-branch loop, replacing the condition with *it % 2 == 0.
Show the explained solution
Erase -2, 0, and 4; the survivors are 3 and 7. After the loop, check empty() before accessing either extreme. If the container is empty, print the task’s explicit empty result instead of dereferencing an iterator.
Your notes
Mark complete when you can explain it yourself.