Adding retain_unsorted or similar

language design
1

Just thought it was odd that there was no retain equivalent that uses swap_remove under the hood. Why not add something like this?

fn retain_unordered<T, F>(vec: &mut Vec<T>, mut keep: F)
where
    F: FnMut(&T) -> bool,
{
    let mut i = 0;

    while i < vec.len() {
        if keep(&vec[i]) {
            i += 1;
        } else {
            vec.swap_remove(i);
        }
    }
}

Thank you for your time.

2

I'd be curious if that has significant performance benefit.. and if so, how much.

Of course the precise results could also depend on the complexity of the predicate's logic, size of the item datatype, proportion (and pattern?) of values to be removed... etc. Nonetheless have you already benchmarked this? (Or if not, could you maybe try that?)

From an asymptotic point of view, the run time is going to be basically linear w. r. t. the number of elements either way (because you ultimately need to visit every single element).[1] Notably retain is much much more efficient already than what a loop with calls to remove would be. (The latter would actually use time quadratic w. r. t. the number rof elements in most cases.)

  1. But who knows it it's still worth it for good constant factor speedup :man_shrugging:t2: ↩︎

1 Like
3

Sorry, I did not perform any benchmaks.

Using this vs. the standard retain implementation would not lead to any useful results either way, since that uses a way more efficent method to achieve the compaction (which I only found out after posting).

The question was ultimately unqualified, I did not know that the low level implementation is as optimized as it is - instead imagining something similar to the same simplistic logic as in my proposed example.

1 Like
4

For cases where you're keeping most elements, I could see the unordered version being significantly faster.