Iterator invalidation

Why this matters

A loop that goes through a list and removes some of its items is one of the most common things a program does. Filter out empty names. Remove expired sessions. Delete finished jobs from a queue. The loop looks simple, and it often works on the first test. Then it fails on a longer list, or on a list where the first or last item matches, and the failure is hard to explain.

The reason is usually the same. The loop holds a position in the list, and the removal moved the list under that position. This lesson shows what that looks like in Java and in C++, and how to write the removal so the loop keeps working.

Words you need

A collection is a container that holds many values. In this lesson the collections are a Java List and a C++ std::vector.

An iterator is an object that remembers one position in a collection. It can read the item at that position and move to the next one. In Java, a for loop written with : (called a for-each loop) uses an iterator behind the scenes. In C++, an iterator works like a pointer. The function begin() returns an iterator to the first item, and end() returns an iterator to the spot just after the last item. That spot is not an item, so it must never be read.

An iterator is invalidated when the collection changes in a way that the iterator no longer points at a correct position. Using an invalid iterator is a bug. In Java, the library checks for this and throws an exception. In C++, the library usually does not check, so the result is undefined behaviour. The program may crash, print a random number, or seem to work. The same code can behave differently on another compiler or after a change in the optimisation setting.

Java: the list checks itself

The idea

Java's ArrayList keeps a counter. Every time the list is changed in size, the counter goes up by one. The counter is called modCount, which means "modification count". An iterator remembers the counter when it is created. Each time the iterator moves to the next item, it compares the remembered value with the current one. If they differ, someone changed the list in a way the iterator did not expect, and the iterator throws ConcurrentModificationException.

The name is long, but the meaning is simple. The list was changed while someone else was still walking through it.

Worked example 1: removing inside a for-each loop

This program tries to remove every name that starts with B from a list. It uses a for-each loop and calls remove inside it.

import java.util.ArrayList;
import java.util.List;
 
public class Main {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>(List.of("Ana", "Ben", "Cara", "Dev"));
        for (String name : names) {
            if (name.startsWith("B")) {
                names.remove(name);
            }
        }
        System.out.println(names);
    }
}

Trace it by hand. The loop starts with the list [Ana, Ben, Cara, Dev]. The first item is Ana, which does not start with B, so nothing happens. The loop moves on and gets Ben. The if is true, so remove takes Ben out. The list is now [Ana, Cara, Dev], and the list's counter has gone up by one. The loop then asks the iterator for the next item. The iterator sees that the counter changed, and it throws.

Compile and run it. This is the real output from Java 25 on this machine:

Exception in thread "main" java.util.ConcurrentModificationException
	at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1096)
	at java.base/java.util.ArrayList$Itr.next(ArrayList.java:1050)
	at Main.main(Main.java:7)

Read the last line first. It names the file Main.java and the line number 7, which is the for line. The exception is thrown inside next(), the method that moves the loop forward. The line numbers inside java.base may change between Java versions, but the class name ConcurrentModificationException does not.

Worked example 2: the case that does not throw

Now change the list to [Ana, Ben, Cara] and remove Ben. Ben is the second item from the end. This version prints without an error:

import java.util.ArrayList;
import java.util.List;
 
public class Main {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>(List.of("Ana", "Ben", "Cara"));
        for (String name : names) {
            if (name.equals("Ben")) {
                names.remove(name);
            }
        }
        System.out.println(names);
    }
}

[Ana, Cara]

The output looks right, but the program was lucky. After Ben is removed, the list has two items. The loop asks whether there is a next item. The iterator's position is now 2, and the list size is also 2, so the answer is no. The loop ends without calling next(), so the check never runs.

This case is a trap. A program can pass its tests and still fail when the removed item is in a different place. The rule is simple: never change a list inside a for-each loop over that same list, even when the program seems to work.

Worked example 3: remove with the iterator

Java gives two safe ways to remove items while walking a list. The first is to use the iterator directly and call its remove method. The iterator knows about its own removal, so it updates its position and its remembered counter.

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
 
public class Main {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>(List.of("Ana", "Ben", "Cara", "Dev"));
        Iterator<String> it = names.iterator();
        while (it.hasNext()) {
            if (it.next().startsWith("B")) {
                it.remove();
            }
        }
        System.out.println(names);
        names.removeIf(n -> n.startsWith("C"));
        System.out.println(names);
    }
}

[Ana, Cara, Dev]
[Ana, Dev]

The loop calls it.next() to get the item, and it.remove() to take out the item that next() just returned. The first print shows only Ben is gone. The second line uses removeIf, which takes a test function and removes every item that makes the test return true. Since Java 8, removeIf is the shortest way to remove items from a list by a rule. It does the same walk internally and keeps the removal safe.

Use it.remove() when you need to run other code in the loop. Use removeIf when the only job is to remove items that match a rule.

C++: the iterator is a position, not a check

The idea

A std::vector stores its items next to each other in one block of memory. An iterator holds the address of one item in that block. When you erase an item, the items after it move one place to the left to fill the gap. The last place in the block is then free.

Now think about an iterator that pointed at the erased item. It still holds the same address. That address now holds the item that moved in from the right, or it is past the end of the items. The iterator has no check to tell it that anything changed. If you move it forward and read through it, you may read a neighbouring item, skip one, or read memory that is no longer part of the vector.

C++ does not throw an error in this case by default. The standard says the result is undefined. In practice, a program often crashes or prints a number nobody put there.

Worked example 4: erasing inside a loop

This program tries to remove every even number from a vector. It is the C++ version of the mistake from the Java example.

#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> nums{1, 2, 3, 4, 5, 6};
    for (auto it = nums.begin(); it != nums.end(); ++it) {
        if (*it % 2 == 0) {
            nums.erase(it);
        }
    }
    for (int n : nums) std::cout << n << " ";
    std::cout << "\n";
}

Trace it by hand. When it points at 2, the erase call takes it out. The items 3 to 6 move one place left, so it now points at 3. The loop then runs ++it, which moves to 4, and 4 is removed next. This looks correct for a while. The trouble comes at the end. After 6 is removed, the vector has three items, and the iterator still holds the old position, which is now the spot where end() is. The loop runs ++it on that old position and then compares it with end(). The iterator never equals end() again, so the loop keeps reading memory that is not part of the vector.

Compile and run the program. Here the process ends with a segmentation fault, which means the program tried to read memory it does not own. The shell reports exit code 139 and the program prints nothing.

exit=139

The exact result can differ on another machine. The lesson is the same: the program is wrong, even if the first run looks like a crash for an unknown reason.

To see the real cause, compile with the flag -D_GLIBCXX_DEBUG. This flag is specific to GCC's standard library. It makes the library check every iterator use and report a clear message. It slows the program down, so use it while you learn and test, not in a release build.

Error: attempt to increment a singular iterator.

A singular iterator is one that no longer points at a valid position.

Worked example 5: the correct erase

The function erase returns a new iterator. It points at the item that came after the erased one, or at end() if the erased item was last. Store that return value and move forward only when you did not erase.

#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> nums{1, 2, 3, 4, 5, 6};
    for (auto it = nums.begin(); it != nums.end();) {
        if (*it % 2 == 0) {
            it = nums.erase(it);
        } else {
            ++it;
        }
    }
    for (int n : nums) std::cout << n << " ";
    std::cout << "\n";
}

1 3 5 

The loop now has two branches. If the item is even, erase removes it and gives back the position of the next item, so the loop does not move forward. If the item is odd, the loop moves forward with ++it. Each item is looked at once, and nothing is skipped.

Notice that the for line has no third part. The move forward is inside the else branch. Writing ++it in the for line as well would skip items. This is the most common mistake with this pattern.

Worked example 6: the C++20 way

Since C++20, the standard library has a function that does the same job in one line. std::erase_if takes a container and a test, and removes every item that makes the test true.

#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> nums{1, 2, 3, 4, 5, 6};
    std::erase_if(nums, [](int n) { return n % 2 == 0; });
    for (int n : nums) std::cout << n << " ";
    std::cout << "\n";
}

1 3 5 

This is the same idea as Java's removeIf. Use it when the only job is to remove items that match a rule. Use the manual loop with the return value of erase when the loop must do more than remove, such as writing a log line for each removed item.

Worked example 7: a push_back can move everything

Erasing is not the only change that invalidates an iterator. Adding an item can do it too. A vector has a capacity, which is the number of items the block of memory can hold without getting a bigger block. When a push_back needs more room than the capacity allows, the vector gets a new, bigger block, copies every item into it, and frees the old block. Any iterator that pointed into the old block now points at memory that has been freed.

#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> v{1, 2, 3};
    auto first = v.begin();
    v.push_back(4);
    std::cout << *first << "\n";
}

This vector was made with three items, so its capacity is three. The push_back needs a fourth place and has to move the vector to a new block. The iterator first still points at the old block. When the library checks this with -D_GLIBCXX_DEBUG, it reports:

Error: attempt to dereference a singular iterator.

Without the debug flag, the same line printed a number that was not 1 in three separate runs of the program. The runs printed -2124200266, -617629056 and -884918825. The number changes from run to run because the program reads freed memory.

You can avoid this with reserve. The function reserve sets the capacity ahead of time. As long as the vector stays within that capacity, push_back does not move anything, and an iterator to an early item stays valid.

#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> v{1, 2, 3};
    v.reserve(10);
    auto first = v.begin();
    for (int i = 4; i <= 10; ++i) v.push_back(i);
    std::cout << "first element still " << *first << "\n";
    std::cout << "capacity " << v.capacity() << "\n";
}

first element still 1
capacity 10

The reserve call only helps when you know the final size in advance. When you do not, the safe rule is to get a new iterator after each push_back, and never keep an old one across the call.

Worked example 8: a list keeps its other iterators

A std::list stores each item in its own separate node in memory. The nodes are linked together with pointers. Erasing one node does not move the others, so an iterator to any other item stays valid.

#include <iostream>
#include <iterator>
#include <list>
 
int main() {
    std::list<int> items{10, 20, 30};
    auto a = items.begin();
    auto b = std::next(a);
    auto c = std::next(b);
    items.erase(b);
    std::cout << *a << " " << *c << "\n";
}

Here a points at 10 and c points at 30. The erase call removes the node that holds 20. The a and c iterators are not touched, so they still work. The output is:

10 30

Only the iterator to the erased item becomes invalid. This is a useful property, but it does not mean std::list is always the right choice. A vector is faster to walk through and uses less memory per item. Choose the container for the job, and learn the invalidation rule for the one you use.

The rule for each container is part of the standard. A vector can invalidate every iterator on a reallocation. A list invalidates only the iterators to the erased items. When you are not sure, look up the container in a C++ reference and read its section on iterator invalidation.

Common mistakes

Mistake 1: calling remove inside a Java for-each loop

This is the mistake from worked example 1. The message to look for is:

Exception in thread "main" java.util.ConcurrentModificationException

The fix is to use removeIf or to use the iterator's own remove method.

Mistake 2: the Java loop that works by luck

Removing the second-to-last item does not throw, as worked example 2 shows. The test passes, and the bug shows up later with another list. Do not treat a clean run as proof. Use the safe method every time.

Mistake 3: using the old iterator after erase

it = nums.erase(it);
++it;

When this is inside a loop, the ++it skips the item that moved into the erased place. Move forward only in the branch where nothing was erased.

Mistake 4: keeping an iterator across a push_back

Worked example 7 shows the result. The program may print a random number, crash, or appear correct. The message from the debug flag is:

Error: attempt to dereference a singular iterator.

The fix is to get a new iterator after each change, or to call reserve first when the final size is known.

Mistake 5: erasing in a range-based for loop

This C++ program compiles with -Wall and gives the wrong answer:

#include <algorithm>
#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> nums{1, 2, 3, 4, 5, 6};
    for (int n : nums) {
        if (n % 2 == 0) {
            nums.erase(std::find(nums.begin(), nums.end(), n));
        }
    }
    std::cout << nums.size() << "\n";
}

The three odd numbers should remain, so the correct output is 3. In the test run the program printed 1. A range-based for loop is written with : and uses the same iterators as the manual loop. The erase call makes those iterators invalid, so the loop reads the wrong items. With -D_GLIBCXX_DEBUG, the library reports:

Error: attempt to increment a singular iterator.

The fix is std::erase_if, or the manual loop from worked example 5.

Practice

Exercise 1: predict the Java output

This program has a for-each loop over [a, b, c, d]. It removes the item c. Predict whether it throws an exception. If it does not, predict the output.

import java.util.ArrayList;
import java.util.List;
 
public class Main {
    public static void main(String[] args) {
        List<String> letters = new ArrayList<>(List.of("a", "b", "c", "d"));
        for (String s : letters) {
            if (s.equals("c")) {
                letters.remove(s);
            }
        }
        System.out.println(letters);
    }
}

Show the answer

The item c is at index 2, and the list has four items. Removing it leaves three items, so the iterator's position is 3 and the size is also 3. The loop ends without calling next(), so there is no exception. The output is:

[a, b, d]

The removed item was second from the end, so the program was lucky, as in worked example 2.

Exercise 2: remove the negative numbers in C++

Write a C++ program that removes every negative number from the vector {3, -1, 4, -5, 9, -2} and prints the rest. Do not use std::erase_if. Use a manual loop that is safe.

Show the answer

Use the loop from worked example 5, with the test *it < 0. The erase branch takes the return value of erase, and the else branch moves forward with ++it:

#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> v{3, -1, 4, -5, 9, -2};
    for (auto it = v.begin(); it != v.end();) {
        if (*it < 0) {
            it = v.erase(it);
        } else {
            ++it;
        }
    }
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";
}

Compiled with g++ -std=c++20 -Wall, the output is:

3 4 9 

Exercise 3: remove the empty strings in Java

Write a Java program that removes every empty string from the list ["go", "", "run", "", "", "stop"]. Use removeIf, and print the list.

Show the answer

The method reference String::isEmpty returns true for an empty string, so removeIf takes out each one:

import java.util.ArrayList;
import java.util.List;
 
public class Main {
    public static void main(String[] args) {
        List<String> words = new ArrayList<>(List.of("go", "", "run", "", "", "stop"));
        words.removeIf(String::isEmpty);
        System.out.println(words);
    }
}

[go, run, stop]

Exercise 4: explain the garbage number

This C++ program prints a number that is not 1. Explain why, and say what the fix is.

#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> v{1, 2, 3};
    auto first = v.begin();
    v.push_back(4);
    std::cout << *first << "\n";
}

Show the answer

The vector was made with three items, so its capacity is three. The push_back needs room for a fourth item, so the vector moves to a new, bigger block of memory and frees the old one. The iterator first still points into the old block. Reading *first reads freed memory, so the number is not defined. The fix is to get a new iterator after the push_back, for example auto first = v.begin(); after the call, or to call v.reserve(10) before taking the iterator when the final size is known.

Exercise 5: which iterator stays valid

A std::list holds 1, 2, 3, 4. The program takes an iterator p to the item 2 and an iterator q to the item 4. Then it calls erase on the item 3. Which iterators are still valid, and why?

Show the answer

Both p and q are still valid. A list stores each item in its own node, and erasing one node does not move the others. Only the iterator to the erased item, 3, becomes invalid. A vector would behave differently: erasing 3 moves 4 one place to the left, and the iterator q would be invalid, since the standard invalidates iterators at or after the erased position.

Summary

• A loop that holds a position in a collection breaks when the collection changes under it.
• In Java, ArrayList checks for changes and throws ConcurrentModificationException, but the check does not run when the removed item was second from the end.
• Use removeIf in Java to remove by a rule, or the iterator's own remove when the loop must do more.
• In C++, store the return value of erase and move forward only when nothing was erased, or use std::erase_if.
• A push_back can give a vector a new block of memory, so get a new iterator after adding items, or call reserve first.
• A std::list keeps other iterators valid after an erase, but the choice of container also depends on speed and memory.