Why does std :: for_each with element deletion not interrupt the iteration?

Question

As far as I know, erasing elements during iteration of the collection should interrupt the iteration or you should skip elements. Why doesn't calling std :: for_each with a predicate that erases cause this? (He works).

Snip code:

#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

int main() {
    map<int,long long> m;
    m[1] = 5000;
    m[2] = 1;
    m[3] = 2;
    m[4] = 5000;
    m[5] = 5000;
    m[6] = 3;

    // Erase all elements > 1000
    std::for_each(m.begin(), m.end(), [&](const decltype(m)::value_type& v){
        if (v.second > 1000) {
            m.erase(v.first);
        }
    });

    for (const auto& a: m) {
      cout << a.second << endl;
    }
    return 0;
}

displays

1
2
3

EDIT: now I see that if it actually increments the iterator before calling the function, then it can work. But does this count as the specific behavior of the / undefined compiler?

Answer 1

This behavior is undefined and will not work reliably. After adding a line to print the keys and values ​​inside your erasing lambda function, I see:

1=5000
2=1
3=2
4=5000
2=1          // AGAIN!!!
3=2          // AGAIN!!!
5=5000
6=3

map 4 node 2! node 3. (v.second > 1000) - , .

: " , ( node) ?"

, .

node delete , node, , delete, :

• ( , left-child, right-child parent-point),

• , .

" ", , ( ).

, node, , , - .

, erase map, , - , . // , .

, , , , // , , operator++() "" , , , map.

, N3 node 3:

                           N5
                          /  \
                        N3    N7
                       / \    /
                      N1  N4 N6

, , :

• , N1; map , , , begin() O (1)

• node , {Nfrom = , , nullptr right!= Nfrom break} (, N1- > N3, N4- > N3- > N5, N6- > N7- > N5- > nullptr)

• node , (, N3- > N4, N5- > N7- > N6)

, , N4 ( N3->right = nullptr;) , NFrom = N4, N3, N3- > right!= Nfrom, , N3 N5.

, erase, , " ".

, erase - it undefined . , , .

Answer 2

std::for_each ++ (25.2.4) . , , , .

, . , .

Answer 3

, - undefined.

, , std::for_each . , libc++ std::for_each :

template<typename _InputIterator, typename _Function>
_Function 
for_each(_InputIterator __first, _InputIterator __last, _Function __f) {
   // concept requirements
   __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
     __glibcxx_requires_valid_range(__first, __last);
   for (; __first != __last; ++__first)
     __f(*__first);
   return _GLIBCXX_MOVE(__f);
 }

__f , , __first . undefined.

Answer 4

, , undefined, , .

void remove_erase_if( Container&&, Test&& );

for handling both associative and non-containers, sending a tag tag to a custom property class is_associative_containeris an associative transition to the manual during the cycle, while the rest go to the remove_if- version erase.

In my case, I just hardcode the 4 associative containers in the dash - you can print a duck, bit, this is a higher-level concept, so you would still have to match the patterns.