Modifying a container within std::for_each

Question

Does the Standard explicitly forbid modifying a container within std::for_each?

More specifically, in case of std::list iterators are not invalidated when the list is modified. Thus, the following code works:

std::list<int> list;

list.push_front(5);
list.push_front(10);
auto it = list.end();
it--; // point to 5

std::for_each(list.begin(), list.end(), [&](int i){
    /* the line below will remove the last element in the list;
     * list will have only one element (the currently processed one);
     * list.end() is not invalidated and we exit for_each() */
    list.erase(it);
});

This is definitely a bad code. But is it legal?

Answer 1

Does the Standard explicitly forbid modifying a container within std::for_each?

The only thing I can think of that would make this code not standard compliant is that in [alg.foreach] we have

Complexity: Applies f exactly last - first times.

^{f being the function for_each applies.}

Since the list is modified and an element is removed we no longer satisfy that complexity. I do not know if that make it non conforming but it is the only thing I could see that would not allow you to remove elements from the container while using for_each

Answer 2

Does the Standard explicitly forbid modifying a container within std::for_each?

No, not explicitly. At least for any sensible definition of "explicitly". The section on std::for_each (§25.2.4) does not say anything at all about iterator invalidation or side effects that cause modification of the iterated range.

There are, however, plenty of implicit reasons for why your code cannot work. Consider how std::for_each must be implemented. It's completely generic and therefore does not know anything about the std::list it operates on; you gave it two iterators to form a range, which means that last can be reached from first. How should std::for_each know that your function object has invalidated the local iterator object with which it goes from first to last?

And even if the function knew that invalidation has occurred, what should it do? In a hand-written loop, you'd take the result of erase and continue iteration with it, but std::for_each cannot do that, by definition.

Here's an old but still valid reference article: http://www.drdobbs.com/effective-standard-c-library-foreach-vs/184403769

It says:

For instance, invalidating the iterators or the sequences that the algorithm works with is disastrous in any case. Even the function object supplied to for_each must obey this common-sense rule, even if the Standard does not say so.

---

Paraphrasing some wise words I once read:

The C++ standard is written by human beings; it's not always as perfect as we wish it to be.

Answer 3

Your code is borderline legal.

With the posted code, it is legal by coincidence. If you add one more item to the list, your program will crash.

Try the following to see the problem:

int main()
{
   std::list<int> list;

   list.push_front(5);
   list.push_front(10);
   list.push_front(12);
   auto it = list.end();
   it--; // point to 5

   std::for_each(list.begin(), list.end(), [&](int i){
                 /* the line below will remove the last element in the list;
                  * list will have only one element (the currently processed one);
                  * list.end() is not invalidated and we exit for_each() */
                 list.erase(it);
                 });
}

Answer 4

25.2.4/2:

Effects: Applies f to the result of dereferencing every iterator in the range [first,last), starting from first and proceeding to last - 1.

Then 25.2.4/4:

Complexity: Applies f exactly last - first times.

I'm prepared to argue that these two points explicitly prohibit mutating the container in a way that changes the number of elements.

That said, even it doesn't your example fails if the list has even one more item, OR if your standard library implementation increments the iterator before calling your function (and I can't see anything in the standard that prohibits such an implementation).

Answer 5

Yes, it's legal. There's const iters if you need something that is guaranteed not to modify the underlying container.