Erasing while you walk

An iterator identifies a position in a container. Some changes invalidate iterators, so a position saved before the change may no longer be usable. The rules depend on both the container and the operation.

For std::vector:

• Reallocation invalidates all pointers, references and iterators to elements. Appending can cause this when the new size exceeds capacity.
• Appending without reallocation preserves references and iterators to existing elements, but invalidates the old past-the-end iterator.
• Erasing invalidates iterators and references at and after the erased position, including the old past-the-end iterator.

// Assume values is non-empty.
int* p = &values[0];
values.push_back(x);
// p is still valid only if this append did not reallocate.

Reserving capacity can prevent reallocation during planned appends. It does not prevent the invalidation caused by erasing an element.

Why the starter skips elements

The starter erases an element by index, then increments the index:

for (std::size_t i = 0; i < values.size(); ++i) {
    if (unwanted(values[i])) {
        values.erase(values.begin() + static_cast<std::ptrdiff_t>(i));
    }
}

Erasing shifts later elements one position to the left. For [2, 4, 3], erasing index zero produces [4, 3]. Incrementing i to one then visits 3 and skips 4. Recomputing an index avoids retaining an invalid iterator, but it does not fix this logic error.

An iterator loop can use the fresh iterator returned by erase:

for (auto it = values.begin(); it != values.end(); ) {
    if (unwanted(*it)) {
        it = values.erase(it);
    } else {
        ++it;
    }
}

Do not increment it after assigning the result of erase: it already points to the next element, or the new end. This loop is correct, but repeated vector erases can take O(n²) work because each erase shifts the remaining tail.

Compact once with erase_if

C++20 provides std::erase_if in <vector>:

auto removed = std::erase_if(values, unwanted);

It preserves the order of retained elements and returns the number removed. It evaluates the predicate for each element, compacts retained elements toward the front and erases the unused tail. The total work is linear in the original size, rather than shifting the whole tail after every match.

Before C++20, use the erase-remove idiom (std::remove_if needs <algorithm>):

auto new_end = std::remove_if(values.begin(), values.end(), unwanted);
values.erase(new_end, values.end());

remove_if rearranges the range without changing the vector's size. The range before new_end contains the retained elements in order. Elements after it remain valid but have unspecified values until the final erase removes them.

Your task

int purge(std::vector<int>& values, int divisor);

Remove every integer exactly divisible by divisor, preserve the order of the rest, and return the number removed. Input lengths fit in int. For [1, 2, 4, 3, 6] and divisor 2, leave [1, 3] and return 3.

A zero divisor must leave the vector unchanged and return zero. With any nonzero divisor, zero is a multiple and must be removed. Negative values and divisors are allowed.

Handle divisor -1 without evaluating the remainder: every integer is a multiple of -1, but INT_MIN % -1 is undefined because its corresponding quotient cannot be represented as an int. Here INT_MIN means the smallest value of int. This edge case is separate from the starter's skipping bug.