First, mistakes

1.1 Background

Here’s a recent requirement with a similar background:

I have obtained the test score data of a batch of students through a series of operations, and now I need to filter the list of students with a score greater than 95.

Good at writing bugs, I completed the writing of the code:

@Test
public void shouldCompile(a) {
    for (int i = 0; i < studentDomains.size(); i++) {
        if (studentDomains.get(i).getScore() < 95.0) {
            studentDomains.remove(studentDomains.get(i));
        }
    }
    System.out.println(studentDomains);
}
Copy the code

Among the four students in the test data, two students with more than 95 points were successfully screened out. The test was successful and they clocked out.

StudentDomain{id=1, name=' score ', subject=' classNum ', score=95.0, classNum=' class '}, StudentDomain{id=1, name=' wang6 ', subject=' science ', Score =100.0, classNum=' classNum '}]Copy the code

1.2 Looks like, can’t get off work!

After X years in the business, my gut tells me it’s not that simple.

But self-test obviously no problem, is there a problem writing? So let me write it this way (enhanced for loop) :

@Test
public void commonError(a) {
    for (StudentDomain student : studentDomains) {
        if (student.getScore() < 95.0) {
            studentDomains.remove(student);
        }
    }
    System.out.println(studentDomains);
}
Copy the code

Boy, this a try and direct error: ConcurrentModificationException.

  • ordinaryforLoop “no problem”, enhancedforThere is a problem with circulation, is it [enhancement]forCycle 】 problem?

1.3 Is the normal for loop really ok?

To determine if there is a problem with the normal for loop, I printed the original code with the number of executions:

@Test
public void shouldCompile(a) {
    System.out.println("studentDomains.size():" + studentDomains.size());
    int index = 0;
    for (int i = 0; i < studentDomains.size(); i++) {
        index ++;
        if (studentDomains.get(i).getScore() < 95.0) {
            studentDomains.remove(studentDomains.get(i));
        }
    }
    System.out.println(studentDomains);
    System.out.println("Number of executions:" + index);
}
Copy the code

Studentdomains.size () = 4.

Even more coincidentally, the data from the two loops that were executed happened to meet my filtering criteria, which led me to believe that [the requirement was complete].

Second, problem analysis

One by one, let’s look at why a normal for loop executes less often than we would expect.

2.1 The number of common for loops is reduced

The reason for this is that anyone with a bit of development experience should know that the index of the List changes automatically after the element is deleted in the loop, and the length of the List obtained by list.size () is updated in real time, so that the element of the index after the deleted element is omitted.

For example, if you delete the first element in the loop, the second loop should have accessed the second element, but it actually accessed the third element in the original List. Because the first element was deleted, the third element became the second element, which caused the element to be missing.

2.2 Enhanced for loop throw errors

  • We see firstJDKIn the sourceArrayList 的 remove()How to implement the source code:
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true; }}else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true; }}return false;
}
Copy the code

As long as it is not empty, the program’s execution path will go to the else path, and eventually the fastRemove() method will be called:

private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null;
}
Copy the code

In the fastRemove() method, you see line 2 [increment the modCount variable by 1].

  • To enhanceforLoop actual execution

By compiling the code, you can see that the enhanced for loop actually executes using Iterator, using the core methods hasNext () and next().

The next() method calls checkForComodification() :

final void checkForComodification(a) {
	if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
 	}
Copy the code

See throw new ConcurrentModificationException () that can be solved:

Because the topremove()The method has changedmodCountValue of, so there must be an exception thrown here.

Three, the correct way

Now that we know why neither the normal for loop nor the enhanced for loop works, let’s start with those two areas.

3.1 Optimize the ordinary for loop

We know that using a normal for loop is problematic because the array coordinates have changed and we’re still operating with the same coordinates.

  • Change coordinates while removing elements.
@Test
public void forModifyIndex(a) {
    for (int i = 0; i < studentDomains.size(); i++) {
        StudentDomain item = studentDomains.get(i);
        if (item.getScore() < 95.0) {
            studentDomains.remove(i);
            // The key is here: remove the element and change the coordinates
            i = i - 1;
        }
    }
    System.out.println(studentDomains);
}
Copy the code
  • Reverse traversal

Using the reverse order method does not need to change the coordinates, because: when the latter element is removed, the coordinates of the previous element are not affected and will not cause an element to be skipped.

@Test
public void forOptimization(a) {
    List<StudentDomain> studentDomains = genData();
    for (int i = studentDomains.size() - 1; i >= 0; i--) {
        StudentDomain item = studentDomains.get(i);
        if (item.getScore() < 95.0) {
            studentDomains.remove(i);
        }
    }
    System.out.println(studentDomains);
}
Copy the code

3.2 Using Iterator remove()

@Test
public void iteratorRemove(a) {
    Iterator<StudentDomain> iterator = studentDomains.iterator();
    while (iterator.hasNext()) {
        StudentDomain student = iterator.next();
        if (student.getScore() < 95.0) {
            iterator.remove();
        }
    }
    System.out.println(studentDomains);
}
Copy the code

You may be wondering why the remove() method of the iterator works. Again, let’s look at the source code:

public void remove(a) {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();
    try {
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw newConcurrentModificationException(); }}Copy the code

You can see that each time the remove() method is executed, the modCount value is assigned to the expectedModCount so that the two variables are equal.

3.3 the Stream of the filter ()

Anyone who knows Stream should know this method, so I won’t go into details here.

@Test
public void streamFilter(a) {
    List<StudentDomain> studentDomains = genData();
    studentDomains = studentDomains.stream().filter(student -> student.getScore() >= 95.0).collect(Collectors.toList());
    System.out.println(studentDomains);
}
Copy the code

3.4 Collection.removeIf()

In JDK1.8, the removeIf() method was added to Collection and its subclasses, which filters the elements of the Collection according to certain rules.

@Test
public void removeIf(a) {
    List<StudentDomain> studentDomains = genData();
    studentDomains.removeIf(student -> student.getScore() < 95.0);
    System.out.println(studentDomains);
}
Copy the code

Iterator removeIf() : Iterator removeIf() : Iterator removeIf() : Iterator removeIf() : Iterator removeIf() : Iterator removeIf() : Iterator removeIf() : Iterator removeIf()

default boolean removeIf(Predicate<? super E> filter) {
    Objects.requireNonNull(filter);
    boolean removed = false;
    final Iterator<E> each = iterator();
    while (each.hasNext()) {
        if (filter.test(each.next())) {
            each.remove();
            removed = true; }}return removed;
}
Copy the code

Four,

Detailed carefully read the words of this article, the greatest feeling should be: or source reliable!

4.1 Long sentences

In fact, this problem bothered me in the early days of Java development. I just wanted to solve the problem, so I took a stupid approach:

Create a new List, iterate over the old List, and put the elements that meet the criteria into the new element, and then you’re done.

Now think about it, a few years ago, if just like now, take time to think about why can’t directly remove(), ask several why, estimate oneself will be much better than now.

Of course, as long as you realize this, it’s never too late.

4.2 Code examples in this paper

Github/vanDusty