scala Remove (in place) all elements of a ListBuffer that meet a condition

Question

I have a ListBuffer. I want to remove all elements that meet a certain condition.

I could iterate over it and remove each element. But what doe Scala say about mutating a list that you are iterating over? Will it work, or will it delete the wrong elements/not return all elements? (A quick attempt with the REPL suggests that yes, it will mess up)

I could repeatedly call find and then remove the found element until I don't find any more, but that sounds inefficient.

.filter will return me a new ListBuffer without the elements, but I want to do it in place.

This

def --= (xs: TraversableOnce[A]) : ListBuffer.this.type
Removes all elements produced by an iterator from this list buffer.

looks promising but I can't quite see how to use it here

How should I do this?

Monteith

See also #2803585 – Pub

Scala 2.13 brings filterInPlace method to ListBuffer – Bitters

Answer 1

You can't do this efficiently, unfortunately. The implementation of --=(xs: TraversableOnce[A]) is (in expanded form; the actual code is more compact)

xs foreach (x => this -= x) ; this

which is just as inefficient as doing it one at a time (i.e. it's O(n*m) where n is the length of the original list and m is the number of items to remove).

In general, the mutable collections don't have as full and powerful a set of methods as the immutable ones. (That is, they have all the wonderful methods used on immutable collections, but relatively few of their own.)

So unless you're removing very few objects, you're probably better off filtering the list to create a new one.

Earthly

"the mutable collections don't have as full and powerful a set of methods as the immutable ones.". Yes. This is a pity. Functional programming may be great, but sometimes a mutable data structure is really what I want and the relatively meagre support for multable-only ops is a bit disappointing – Monteith

Answer 2

You could combine the two and do the following:

val lb = ListBuffer(1,2,3,4,5,6)
lb --= lb.filter(_ % 2 == 0)

println(lb)
// outputs: ListBuffer(1, 3, 5)

Stepparent

Perfect. Probably being dumb, but how come that works? Does filter return an iterator rather than a list? Or does the TraversableOnce mean a list is good enough as an iterator to --=? – Monteith

TraversableOnce is more general than an iterator. It is a common superclass of both Traversable (on which all collections are based) and Iterator. – Pub

Thanks. The scaladoc is confusing with the description saying it takes an iterator... – Monteith

It's worth noting that's not super efficient - you're producing a new listbuffer from filter, and then you're traversing the original collection AGAIN to remove the values. – Roswald