Logo

Programming-Idioms

  • Go
  • Elixir
  • C++

Idiom #247 Filter list in-place

Remove all the elements from list x that don't satisfy the predicate p, without allocating a new list.
Keep all the elements that do satisfy p.

For languages that don't have mutable lists, refer to idiom #57 instead.

#include <list>
#include <functional>
std::list<Foo> x;
x.remove_if(std::not_fn(p));

C++17 or later
Also works if x is an std::forward_list
#include <functional>
std::erase_if(x, std::not_fn(p));

C++20

Compatible with most STL containers (Exceptions: x cannot be an std::array, std::stack, or std::queue)

std::erase_if also returns the number of elements removed
j := 0
for i, v := range x {
	if p(v) {
		x[j] = x[i]
		j++
	}
}
for k := j; k < len(x); k++ {
	x[k] = nil
}
x = x[:j]

When elements of x have pointer type, it is necessary to set discarded slice elements to nil, to avoid a memory leak.
import "slices"
del := func(t *T) bool { return !p(t) }

x = slices.DeleteFunc(x, del)

Elements have type T.
del (discard) is the opposite of the function p (keep)
func Filter[S ~[]T, T any](x *S, p func(T) bool) {
	j := 0
	for i, v := range *x {
		if p(v) {
			(*x)[j] = (*x)[i]
			j++
		}
	}
	var zero T
	for k := j; k < len(*x); k++ {
		(*x)[k] = zero
	}
	*x = (*x)[:j]
}

S, T are type parameters.
In case T contains pointers, zeroing discarded elements helps garbage collection.
j := 0
for i, v := range x {
	if p(v) {
		x[j] = x[i]
		j++
	}
}
x = x[:j]

Discarded elements are overwritten.
x is resliced to its new length.
If the elements of x have a pointer type, then you should take care of a potential memory leak by setting all x[j:] elements to nil.
x.RemoveAll(item => !p(item));

x is List<T> (not the more general IList<T>)
New implementation...
< > ⌨
programming-idioms.org 
std::list<Foo> x;
x.remove_if(std::not_fn(p));
std::erase_if(x, std::not_fn(p));
j := 0
for i, v := range x {
	if p(v) {
		x[j] = x[i]
		j++
	}
}
for k := j; k < len(x); k++ {
	x[k] = nil
}
x = x[:j]
del := func(t *T) bool { return !p(t) }

x = slices.DeleteFunc(x, del)
func Filter[S ~[]T, T any](x *S, p func(T) bool) {
	j := 0
	for i, v := range *x {
		if p(v) {
			(*x)[j] = (*x)[i]
			j++
		}
	}
	var zero T
	for k := j; k < len(*x); k++ {
		(*x)[k] = zero
	}
	*x = (*x)[:j]
}
j := 0
for i, v := range x {
	if p(v) {
		x[j] = x[i]
		j++
	}
}
x = x[:j]
x.RemoveAll(item => !p(item));
x.retainWhere((e) => p);
x = pack(x,.not.p())
for (const [key, value] of x.entries()) {
	if (!p(value)) x.splice(key, 1);
}
x = x.filter((e) => p(e));
x.removeIf(p.negate());
for i := x.count-1 downto 0 do
  if not p(x.items[i]) then x.delete(i);
@x = grep { p($_) } @x;
del_count = 0
for i in range(len(x)):
    if not p(x[i - del_count]):
        del x[i - del_count]
        del_count += 1
i, n = 0, len(x)
while i != n:
    if not p(x[i]):
        del x[i]
        n = n - 1
    else:
        i = i + 1
x.select!(&:p)
x.retain(p);
let mut j = 0;
for i in 0..x.len() {
    if p(x[i]) {
        x[j] = x[i];
        j += 1;
    }
}
x.truncate(j);