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

user_3936294 0
Viewed 79

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);
c++
1 Answers

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.

user_3646960
Related