How can I erase elements from a std::set in reverse (from the end until a lower_bounds)

user_16726630 0
Viewed 53

So I need to erase elements from a std::set in a particular order, doing something with the first.

so if I had a set containing {1,2,3,4,5,6} and my I wanted to go until 4, I need to:

doSomething(6);
erase(6);
doSomething(5);
erase(5);
doSomething(4);
erase(4);

I have the following code that does not work:

#include <iostream>
#include <set>

void doSomething(int value) {
    std::cout << value << '\n';
}

int main() {
    std::set<int> s = {1,2,3,4,5,6};

    auto beginIt = s.end();
    auto endIt = s.lower_bound(4);
    auto rbegin = std::make_reverse_iterator(beginIt);
    auto rend = std::make_reverse_iterator(endIt);

    for (auto it = rbegin; it != rend;) {
        doSomething(*it);
        s.erase(std::next(it).base());
    }

    return 0;
}

I think the issue is that it erasing the end iterator then keeps going util it crashes.

How can I get this to work.

godbolt: https://godbolt.org/z/KvaGWhr4G

c++
1 Answers

The correct way of doing what you want is to getting your end iterator each time.

for (auto it = rbegin; it != std::make_reverse_iterator(s.lower_bound(4));) {
        doSomething(*it);
        s.erase(std::next(it).base());
    }

Now let's see why you initial code didn't work.

In set, the iterators are not invalidated after erasing an element, EXCEPT for the iterator that was pointing to the erased element.

Now let's see what happened in the last iteration when you remove 4.

When dereferencing the rend, we will see that it points to 3. However, the base of rend points to 4. And after removal of 4, the base of rend has been invalidated. So your program had Undefined behavior.

To understand why getting end iterator at every iteration works, we have to understand that during the program the base of it is always s.end(). And at the last step, when we call s.lower_bound(4), we get s.end(). Hence, the condition for exiting the loop is satisfied.

user_152624890
Related