Remove and return matching events with extract_if

Remove old events from a log and return them in a separate vector. Leave the remaining events in log, preserving input order in both vectors.

pub struct Event { pub id: u64, pub ts: u64 }

pub fn compact_log(log: &mut Vec<Event>, cutoff: u64) -> Vec<Event>

An event is old when ts < cutoff. An event with ts == cutoff stays. IDs and timestamps can repeat, and the input need not be sorted. Accept the full u64 range for both fields and the cutoff. An empty input produces an empty result and leaves log empty.

Keep the public Event type, its field names and the function signature so the harness can construct events and read your results.

For example, with cutoff 10:

Practice moving matching events out with Vec::extract_if, keeping the survivors in the existing vector. The returned vector still needs storage.

Why the starter does not compile

retain calls its predicate with &Event. The predicate returns true to keep an event or false to drop it. It does not receive ownership of the event. Because the supplied Event is not Copy, removed.push(*e) tries to move a value through a shared reference and fails with E0507.

extract_if instead yields matching elements by value. Its first argument selects a range; .. covers the whole vector. Consume the iterator to inspect every element in that range. Collecting its yielded events gives you the removed vector while leaving the survivors in their original order.

Deriving Clone would allow a different solution that clones events inside retain. For this struct, cloning two u64 fields does not itself allocate heap storage. A struct containing owned strings could have a different cost. Moving events out is useful because it does not require them to be cloneable.

Stopping early: extract_if and drain differ

Dropping an extract_if iterator leaves its unvisited elements in the vector, even if they would match the predicate. Dropping a drain iterator removes the rest of its selected range. Compare these complete examples in one program:

fn main() {
    let mut extracted = vec![1, 2, 3, 4];
    {
        let mut old = extracted.extract_if(.., |n| *n < 3);
        assert_eq!(old.next(), Some(1));
        // Dropping `old` leaves the unvisited 2, 3 and 4 in place.
    }
    assert_eq!(extracted, [2, 3, 4]);

    let mut drained = vec![1, 2, 3, 4];
    {
        let mut first_two = drained.drain(..2);
        assert_eq!(first_two.next(), Some(1));
        // Dropping `first_two` also removes 2 from the selected range.
    }
    assert_eq!(drained, [3, 4]);
}

In this problem, consuming the entire extraction iterator matters: stopping after the first match would leave other old events behind.

Mutating elements while retaining them

If you need to update elements and discard some without returning them, retain_mut supplies &mut T to its predicate. Here the program changes each value before deciding whether to keep it:

fn main() {
    let mut values = vec![1, 2, 3];
    values.retain_mut(|value| {
        *value *= 10;
        *value >= 20
    });
    assert_eq!(values, [20, 30]);
}

The same assignment inside retain fails with E0594 because its predicate receives a shared reference. Check the method's signature to see what access it grants. retain_mut allows mutation but still does not yield removed elements as owned values.

What the allocation budget measures

A large test constructs 500,000 events with id == ts, then removes the first 250,000. During compact_log, the harness counts calls to the global allocator's alloc and realloc methods and allows at most 20 combined. Input construction and output serialization happen outside that measurement. This counts allocation operations, not bytes, peak memory or elapsed time.

Extracting into one result vector avoids rebuilding the survivors in a second buffer. Exact growth counts depend on collection behavior; they are not fixed API guarantees. A rebuild using preallocated buffers can also meet the count budget, so passing it alone does not prove you used in-place extraction.

Repeated remove(i) calls are another possibility, but each removal shifts the remaining tail. Many removals near the front can make the total work quadratic. remove itself needs no new buffer, but storing its returned values in a growing vector can still allocate.

Choose the operation for the ownership and ordering you need, then measure performance on a representative workload. Element types, input size and buffer capacity affect the costs. Submissions must compile, pass the output and allocation tests, and pass the runner's Clippy checks.