5 ms·

I have many years of experience writing C++. I still can't iterate and delete from a map without looking it up (if not allowed to use erase_if).

by few 1y ago

OskarS 1y ago
Both of these things are very easy to do in modern C++: // erase map.erase(2); // iterate for (auto &[k,v]: map) { // do stuff } godbolt: https://godbolt.org/z/o8f6zhqxq https://godbolt.org/z/o8f6zhqxq
- maattdd 1y ago
  Obviously you can delete than iterate. He means delete while iterating.
  - incrudible 1y ago
    What is the use case for that? Seems more like a footgun, at least for a generic container interface.
    - gpderetta 1y ago
      It happens surprisingly often.
    - simonask 1y ago
      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.
      - account42 1y ago
        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.
        incrudible 1y ago
        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.
  - OskarS 1y ago
    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.
    - tom_ 1y ago
      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!
      - OskarS 1y ago
        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.
        monkeyelite 1y ago
        > 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.
monkeyelite 1y ago
And if the library just did “python iterators” it would be impossible rather than difficult to remember.

I have many years of experience writing C++. I still can't iterate and delete from a map without looking it up (if not allowed to use erase_if).

by few 1y ago

I have many years of experience writing C++. I still can't iterate and delete from a map without looking it up (if not allowed to use erase_if).

OskarS 1y ago

Both of these things are very easy to do in modern C++: // erase map.erase(2); // iterate for (auto &[k,v]: map) { // do stuff } godbolt: https://godbolt.org/z/o8f6zhqxq https://godbolt.org/z/o8f6zhqxq

maattdd 1y ago
Obviously you can delete than iterate. He means delete while iterating.
- incrudible 1y ago
  What is the use case for that? Seems more like a footgun, at least for a generic container interface.
  - gpderetta 1y ago
    It happens surprisingly often.
  - simonask 1y ago
    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.
    - account42 1y ago
      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.
      - incrudible 1y ago
        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.
- OskarS 1y ago
  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.
  - tom_ 1y ago
    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!
    - OskarS 1y ago
      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.
      - monkeyelite 1y ago
        > 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.

monkeyelite 1y ago

And if the library just did “python iterators” it would be impossible rather than difficult to remember.