How can I efficiently transfer objects from one java collection to an other according to a predicate?

Question

First of all I hope this question has not been asked before. I've looked a bit and could not find an appropriate answer :s

I'm looking for an efficient way of moving some objects from one collection to an other, when a specific condition is true.

Currently, I would do it in a pretty straightforward way, but I'm afraid this might not be optimal:

Collection<Object> myFirstCollection;  //let's consider it instanciated and populated
Collection<Object> mySecondCollection; //same for this one

myFirstCollection.stream().forEach(o -> { 
    if ( conditionReturningTrue(o) ) {
        mySecondCollection.add(o);
        myFirstCollection.remove(o);
    }
});

Do you know any better way / more efficient of doing that ?

Answer 1

To make it more readable, there are Collection::addAll and Collection::removeAll to use in this situation, your code can be :

// create a new Collection where you use filter to search only the Object you want
Collection<Object> filterdCollection = myFirstCollection.stream()
        .filter(o -> conditionReturningTrue(o))
        .collect(Collectors.toCollection(LinkedHashSet::new));

// use allAll to add all the filtered Object to the second collection
mySecondCollection.addAll(filterdCollection);
// use removeAll to remove all the filtered Object from the first collection
myFirstCollection.removeAll(filterdCollection);

Answer 2

First of all, you should strive for correctness. For most collections, it is forbidden to modify the source collection while iterating over it. You may get a ConcurrentModificationException while trying, but even if it happen to run without an exception, the code still isn’t correct. It’s just that this error is not always detected (it’s a best-effort check, trying to avoid wasting too much performance). This applies to forEach(…), as well as stream().forEach(…), and the for-each loop (for(variable declaration: collection))

The only support for removing elements while iterating is via manual Iterator usage:

for(Iterator<Object> it = myFirstCollection.iterator(); it.hasNext(); ) {
    Object o = it.next();
    if(conditionReturningTrue(o)) {
        it.remove();
        mySecondCollection.add(o);
    }
}

The alternative are bulk methods.

First, like shown in this and that answer, creating a copy of all elements to be transferred first.

Second, you can use

myFirstCollection.removeIf(o -> conditionReturningTrue(o) && mySecondCollection.add(o));

The default implementation of removeIf uses an Iterator in a loop similar to the one above. However, collections like ArrayList provide their own implementation of removeIf, to overcome the quadratic time complexity of the Iterator loop.

Answer 3

You might be able to improve performance by avoiding removeAll (which might require quadratic time for some Collections in which object lookup requires linear search, such as Lists), by using Collectors.partitioningBy to split the original Collection into two Lists:

Collection<Object> myFirstCollection;  //let's consider it instanciated and populated
Collection<Object> mySecondCollection; //same for this one

Map<Boolean,List<Object>> partition = 
    myFirstCollection.stream()
                     .collect(Collectors.partitioningBy(o -> conditionReturningTrue(o)));
myFirstCollection.clear();
myFirstCollections.addAll(partition.get(false));
mySecondCollection.addAll(partition.get(true));

On the other hand, this solution may be less efficient if only few elements should be moved from myFirstCollection to mySecondCollection.

Answer 4

You already got a good answer from YCF_L here: https://stackoverflow.com/a/52295144/9568238

But I would just like to add that if you do go for the forEach method, as you describe in your question, then the stream() is redundant. You can just do myFirstCollection.forEach(...)

Either way, I'd go with the answer mentioned.