Is there any problem using a reference to a std::set key to erase itself?

Question

Consider the following code

std::set<int> int_set = {1, 2, 3, 4};

for(const auto& key : int_set)
{
    if(key == 2)
    {
        int_set.erase(key);
        break;
    }
}

The code runs as expected, but is it safe?

It feels wrong to be using a reference to a key to erase itself from a set, as presumably once the erase has happened the reference is no longer valid.

Another code snippet with the same potential problem would be

std::set<int> int_set = {1, 2, 3, 4};
const auto& key  = *int_set.find(2);
int_set.erase(k);

I think my question is different to the similar question as I am interested in using a reference to erase from a set rather than an iterator. https://stackoverflow.com/questions/2874441/deleting-elements-from-stdset-while-iterating — KyleL, Jun 15 '22 at 13:30
Is the presence of the `break;` statement an important part of your question? Without that, the iterator used (implicitly) in the `for` loop will become invalid after the call to `erase`. — Adrian Mole, Jun 15 '22 at 13:32
How you have written it is fine. Like others have said though, after removing the `element` you've invalidated your `iterator`, but since you're breaking out of the loop you're fine. So yes, your code, as written, is safe. Just hope that no one comes along and removes that `break` statement at some point in the future. — WBuck, Jun 15 '22 at 13:34
So the reference to `key` will become invalid after the erase, but the erase itself using `key` is safe? — KyleL, Jun 15 '22 at 13:40
I agree with OP that this is not a duplicate of either target. The code could equally well have been written as: `const auto& k = *int_set.find(2); int_set.erase(k);` and the question (now 'answered' in the comments) is still meaningful and valid. — Adrian Mole, Jun 15 '22 at 13:52
Yes, my query is related to the reference to the key being used, not the fact it is in a for loop — KyleL, Jun 15 '22 at 13:55

ShadowRanger · Accepted Answer · 2022-06-15T14:21:08.827

This is safe in the code provided since you break out of the loop without attempting to use the reference (key) again (nor implicitly advance the underlying iterator that for-each loops are implemented in terms of, which would happen if you did not break/return/throw/exit()/crash, when you looped back to the top of the loop) after the call to erase. key itself is only needed to find the element to remove; until that element is removed, it's valid, once it's removed, it's not used again by erase (it already found the element to erase, there's no possible use for it after that point).

If you tried to use key after the erase, you'd be using a dangling reference, invoking undefined behavior. Similarly, even allowing the loop to continue (implicitly advancing the underlying iterator) would be illegal; the iterator is invalid, and the implicit advancing of the iterator when you returned to the top of the loop would be equally invalid. The safe way to erase more than one element as you iterate would be to switch from for-each loops (that are convenient, but inflexible) to using iterators directly, so you can update them with the return value of erase, e.g.:

for(auto it = int_set.begin(); it != int_set.end(); /* Don't increment here */)
{
    if (predicate(*it)) {
        it = int_set.erase(it);  // In C++11 and higher, erase returns an iterator to the
                                 // element following the erased element so we can
                                 // seamlessly continue processing
                                                       
    } else {
        ++it;                    // Increment if we didn't erase anything
    }
}

Of course, as noted in the comments, if you only need to remove one element with a known value, the whole loop is pointless, being a slow (O(n) loop + O(log n) erase) way to spell:

int_set.erase(2);  // Returns 1 if 2 was in the set, 0 otherwise

which is a single O(log n) operation.

OP made it clear that the question is about using a *reference*, not an iterator. Your answer, while good, answers a different question. (Not my downvote though.) — DevSolar, Jun 15 '22 at 14:14
@DevSolar: Well, the reference is a result of an implicit iterator in the for-each loop, which is why I mention it (alongside the reference). Without the `break`, you'd try to use that implicit iterator again. I'll clarify. — ShadowRanger, Jun 15 '22 at 14:17
@DevSolar: Clarified. My goal was to make it clear that iterators are involved under the covers at all times, so it's not just that you can't use `key` again after the `erase`, the loop can't continue at all (because it involves an implicit `++hidden_iterator` where the hidden iterator is invalid as soon as `erase` occurs, and can't even be used to generate new iterators). — ShadowRanger, Jun 15 '22 at 14:22

Is there any problem using a reference to a std::set key to erase itself?

1 Answers1