Hacker News Reader

Comment by maattdd | Hacker News Reader

Obviously you can delete than iterate. He means delete while iterating.

Ah, ok. But then: you kinda can't do that at all. You certainly shouldn't.

For unordered_map (and every hash table in the known universe) erasing anything invalidates all iterators, so you can't iterate while erasing. For std::map, you can if you're very, very careful (erasing invalidates the iterator you're currently on, but if you cache the next iterator, THEN erase the current one, it'll probably work, but be very fiddly). Most languages forbid this entirely: e.g. Rust's ownership model doesn't allow it, Python throws an exception, etc. It's just a very bad idea in general.

Iterator-based std::unordered_map::erase and std::map::erase return a new iterator, one past the range erased, specifically so that you can erase while iterating. Along these untested lines:

    for(decltype(cont)::const_iterator it=cont.begin();it!=cont.end();++it){
        if(Keep(it.first)){
            ++it;
        }else{
            it=cont.erase(it);
        }
    }

There's an argument to be made that maybe you should do something else, but if you want to do the above, you can!

Huh, TIL! I didn't realize that, I just always avoid this pattern because it's such a common source of bugs (and if I really need to, I just use the erase_if).

EDIT: just saw your example and checked cppreference, it says the return value "Iterator following the last removed element" for std::unordered_map. So i think you need to add an `it--` after your erase, otherwise it will "skip over" the next element. Right?

Also just read this little nugget on cppreference for unordered_map::erase:

> Removes specified elements from the container.The order of the remaining elements is preserved. (This makes it possible to erase individual elements while iterating through the container.)

This seems like a crazy guarantee to put in the standard, it must really limit the kinds of hash tables you can make that matches the unordered_map interface.

The return value refers to the same element that you'd reach by skipping over the elemnent(s) rather than deleting them. So if doing 1 elemnt at a time, you can ++it (and now it is the next element), or you can it=erase(it) (and now the current item is gone, and it is the next element).

(In the map/unordered_map/set/etc. case, you can get away with storing std::advance(it) and then erasing, but when forward-iterating vectors the iterator invalidation rules are quite different and the API is designed to cover this.)

> This seems like a crazy guarantee to put in the standard

It’s a great and useful guarantee.

> it must really limit the kinds of hash tables you can make that matches the unordered_map interface.

Many libraries treat containers as “abstract” with many possible implementations. STL explicitly does not. It’s a specific data structure from a computer science class.

What is the use case for that? Seems more like a footgun, at least for a generic container interface.

Surely you must be kidding? Inserting/removing in a container while iterating through it is one of the all time greatest and most iconic bugs. People do it because they want to do it.

In reality, very few real-life containers can support this pattern, which is why this is a headline case for Rust, because it statically prevents this bug.

But yes, for removal the correct thing is always to use `std::erase_if` (C++) or `retain()` (Rust). For insertions, the only real solution is to build up a separate collection while iterating and then merging it into the original container when done. Yucky, but won't crash.

All containers can (at least theoretically) support modifying the container while iterating. You just have to adjust the iterator to take account for the changed container. C++'s std::map::erase(iterator) returns a new iterator for exactly this purpose - the iterator pointing to the next element before the operation but one that is still valid after the operation. Unfortunately you can't use it with range-based for loops even though they still use iterators under the hood but c'est la vie.

Sure they can, but if you define an interface that allows this, every container type implementing it must support it, and it is probably gonna be rather slow operation for the effort. That's why the question is not "can you do this?" but "why would you want to do this?". I can't think of a good reason for generic containers, if you need something like that, it should be a purpose-built data structure that efficiently supports it.

The STL containers are full of "features" that containers in other languages just do not support, yet it's worse to use in my opinion.

It happens surprisingly often.

Reply on news.ycombinator.com