use warnings;
use strict;

use Data::Dumper;

sub grep_in_place(&@) {
   my ($cb, $array) = @_;
   my $src = -1;
   my $dst = -1;
   while (++$src < @$array) {
      my $keep;
      $keep = $cb->() for $array->[$src];
      $array->[++$dst] = $array->[$src];
   }
   $#$array = $dst;
}

sub grep_and_remove (&\@) {
   my ($cb, $array_ref) = @_;
   my @found;
   my $i = 0;

   GREP:
   while ($i < @{ $array_ref })
   {
       $cb->()
           and push(@found, splice(@{ $array_ref }, $i, 1))
           and next GREP
             for $array_ref->[$i];
       ++$i;
   }

   return @found;
}

my @arr1 = (1,2,3,4,5,6,7,8);
my @arr2 = grep_in_place   { $_ > 4 } @arr1;

my @arr3 = (1,2,3,4,5,6,7,8);
my @arr4 = grep_and_remove { $_ > 4 } @arr3;

print Dumper(\@arr1, \@arr2, \@arr3, \@arr4);

__END__
$VAR1 = [
          1,
          2,
          3,
          4,
          5,
          6,
          7,
          8
        ];
$VAR2 = [
          '-1'
        ];
$VAR3 = [
          1,
          2,
          3,
          4
        ];
$VAR4 = [
          5,
          6,
          7,
          8
        ];
[download]

You used it wrong, but I see I used the wrong prototype, and my "if $keep" disappeared.

use strict;
use warnings;

sub grep_in_place(&\@) {
   my ($cb, $array) = @_;
   my $src = -1;
   my $dst = -1;
   while (++$src < @$array) {
      my $keep;
      $keep = $cb->() for $array->[$src];
      $array->[++$dst] = $array->[$src] if $keep;
   }
   $#$array = $dst;
}

my @a = (1,2,3,4,5,6,7,8);
print("Before: @a\n");
grep_in_place { $_ > 4 } @a;
print("After:  @a\n");
[download]

Before: 1 2 3 4 5 6 7 8
After:  5 6 7 8
[download]

To get your (and probably the OP's) semantics:

sub grep_and_remove(&\@) {
   my ($cb, $array) = @_;
   my $src = -1;
   my $dst = -1;
   my @deleted;
   while (++$src < @$array) {
      my $keep;
      $keep = $cb->() for $array->[$src];
      ($keep
         ? $deleted[@deleted]
         : $array->[++$dst]
      ) = $array->[$src];
   }
   $#$array = $dst;
   return @deleted;
}

my @a = (1,2,3,4,5,6,7,8);
print("Before:   @a\n");
my @b = grep_and_remove { $_ > 4 } @a;
print("After:    @a\n");
print("Returned: @b\n");
[download]

Before:   1 2 3 4 5 6 7 8
After:    1 2 3 4
Returned: 5 6 7 8
[download]

No crazy splice!

Thanks for the clarification and the better way! :)