18

Suppose I have a Collection, and a Predicate that matches elements I'd like to remove from the Collection. But I don't just want to discard them, I want to move the matched elements into a new collection. I'd do something like this in Java 7:

List<E> removed = new LinkedList<>(); for (Iterator<E> i = data.iterator(); i.hasNext();) { E e = i.next(); if (predicate.test(e)) { removed.add(e); i.remove(); } }

I'm curious if there's a streams / Java 8 way to do it. Collections.removeIf() unfortunately simply returns a boolean (not even a count of the number of removed elements? Too bad.) I envision something like this (though of course .removeAndYield(Predicate) doesn't exist):

List<E> removed = data.removeAndYield(predicate).collect(Collectors.toList());

Note: this question was inspired by a similar question; this question is about the more general case of getting a stream over the items removed from a collection. As pointed out in the linked question, the imperative solution may be more readable, but I'm curious if this is even possible with streams.

Edit: Clearly we can split the task into two separate steps, and assuming the appropriate data structures it will be efficient. The question is can this be done on arbitrary collections (which may not have efficient .contains() etc.).

Improve this question
4
  • The difficulty is that you can't remove elements from a Set while iterating over it without getting a ConcurrentModificationException, so any Java 8 way would require at least two iterations as in Misha's answer. AFAIK the only way to do this with a single iteration of set is to use an explicit Iterator. Commented May 5, 2015 at 0:49
  • You can with an Iterator over the Collection, which suggests it's conceptually possible with a Stream. Obviously that doesn't mean it's available out of the box, but maybe it's not complicated to do. Or maybe there's a good reason it's not available in the JDK. Commented May 5, 2015 at 0:51
  • The "Java 7" example in my question demonstrates removing elements mid-iteration. If we can do it in one pass imperatively, can it be done functionally? Commented May 5, 2015 at 0:52
  • 1
    @dimo414 If performance is your concern, keep in mind that the most commonly used collection (ArrayList) will scale very badly under iterative solution -- it is expensive to remove elements from the middle of the array via iterator one at a time. Commented May 5, 2015 at 3:10

4 Answers 4

Reset to default
21

If you don't mind, let me bend your requirements a little bit. :-)

One characteristic of the desired result is that the matching elements should end up in one collection, and the non-matching elements should end up in a different collection. In the pre-Java-8 mutative world, the easiest way to think about getting a collection of non-matching elements is to remove the matching elements from the original collection.

But is removal -- modification of the original list -- an intrinsic part of the requirement?

If it isn't, then the result can be achieved via a simple partitioning operation:

Map<Boolean, List<E>> map = data.stream().collect(partitioningBy(predicate));

The result map is essentially two lists, which contain the matching (key = true) and non-matching (key = false) elements.

The advantage is that this technique can be done in one pass and in parallel if necessary. Of course, this creates a duplicate list of non-matching elements compared to removing the matches from the original, but this is the price to pay for immutability. The tradeoffs might be worth it.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Good suggestion. Mutable collections are often more trouble than they're worth, so it's nice to see there's an easy way to do this with immutable collections.
@dimo414 Thanks, and oh yes, thanks for fixing groupingBy to partitioningBy. Oops!
15

I'd keep it simple:

Set<E> removed = set.stream() .filter(predicate) .collect(Collectors.toSet()); set.removeAll(removed);
Improve this answer

3 Comments

I like this (+1) although the last 2 of your 3 options are better than the first as these only iterate over removed rather than all of set.
I agree in the case where the original structure is a set. However, if the source structure is not a set, remove.forEach will only take out the first occurrence of the matching element from the collection, while removeIf and removeAll will remove them all. Overall, I think removeAll is the best choice.
@pbabcdefp I modified the answer to remove the unnecessary options.
4

If you want a functional way to do this, you could write your own method.

static <E> Set<E> removeIf(Collection<? extends E> collection, Predicate<? super E> predicate) { Set<E> removed = new HashSet<>(); for (Iterator<? extends E> i = collection.iterator(); i.hasNext();) { E e = i.next(); if (predicate.test(e)) { removed.add(e); i.remove(); } } return removed; }

This could be used to remove all odd numbers from a List.

Set<Integer> set = new HashSet<>(Arrays.asList(1, 2, 3, 4, 5, 6)); Set<Integer> removed = removeIf(set, i -> i % 2 != 0); System.out.println(set); System.out.println(removed);
Improve this answer

Comments

0

Just write yourself a reusable function like this:

/** * Removes all matching element from iterator * * @param it * @param predicate */ public static <E> void removeMatching(final Iterator<E> it, final Predicate<E> predicate) { while (it.hasNext()) { final E e = it.next(); if (predicate.test(e)) { it.remove(); } } }

I have also not found a pre-existing solution for Streams. Using iterator.remove() requires less memory than a temporary set.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.