How to remove empty/nil elements from Array?

Question

How can I remove empty elements or elements with nil pointers from an Array? A generic solution would be welcome.

Answer 1

You could write it like this:

type
  TArrayHelper = class
    class function RemoveAll<T>(var Values: TArray<T>; const Value: T); static;
  end;

....

function TArrayHelper.RemoveAll<T>(var Values: TArray<T>; const Value: T);
var
  Index, Count: Integer;
  DefaultComparer: IEqualityComparer<T>;
begin
  // obtain an equality comparer for our type T
  DefaultComparer := TEqualityComparer<T>.Default;

  // loop over the the array, only retaining non-matching values
  Count := 0;
  for Index := 0 to high(Values) do begin
    if not DefaultComparer.Equals(Values[Index], Value) then begin
      Values[Count] := Values[Index];
      inc(Count);
    end;
  end;

  // re-size the array
  SetLength(Values, Count);
end;

Suppose that you had an array of pointers:

var
  arr: TArray<Pointer>;

Then you would remove the nil elements like this:

TArrayHelper.RemoveAll<Pointer>(arr, nil);

This code takes the easy way out and always uses the default comparer. For more complex types that is no good. For instance some records need custom comparers. You would need to supply a comparer to support that.

---

The above implementation is as simple as possible. In terms of performance, it may well be wasteful in the likely common scenario where no matching values, or very few, are found. That's because the version above unconditionally assigns, even if the two indices are the same.

Instead, if there was an issue with performance, you might optimize the code by stepping through the array as far as the first match. And only then start moving values.

function TArrayHelper.RemoveAll<T>(var Values: TArray<T>; const Value: T);
var
  Index, Count: Integer;
  DefaultComparer: IEqualityComparer<T>;
begin
  // obtain an equality comparer for our type T
  DefaultComparer := TEqualityComparer<T>.Default;

  // step through the array until we find a match, or reach the end
  Count := 0;
  while (Count<=high(Values)) 
  and not DefaultComparer.Equals(Values[Count], Value) do begin
    inc(Count);
  end;
  // Count is either the index of the first match or one off the end

  // loop over the rest of the array copying non-matching values to the next slot
  for Index := Count to high(Values) do begin
    if not DefaultComparer.Equals(Values[Index], Value) then begin
      Values[Count] := Values[Index];
      inc(Count);
    end;
  end;

  // re-size the array
  SetLength(Values, Count);
end;

As you can see this is a lot more difficult to analyse. You would only contemplate doing this if the original version was a bottleneck.