Tracking issue for Vec::extract_if and LinkedList::extract_if

[Gankra]

Feature gate: #![feature(extract_if)] (previously drain_filter)

This is a tracking issue for Vec::extract_if and LinkedList::extract_if, which can be used for random deletes using iterators.

Public API

pub mod alloc {
    pub mod vec {
        impl<T, A> Vec<T, A>
        where
            A: Allocator,
        {
            pub fn extract_if<F>(&mut self, filter: F) -> ExtractIf<'_, T, F, A>
            where
                F: FnMut(&mut T) -> bool;
        }

        pub struct ExtractIf<'a, T, F, #[unstable(feature = "allocator_api", issue = "32838")] A = Global>
        where
            F: FnMut(&mut T) -> bool,
            A: Allocator;

        impl<T, F, A> Iterator for ExtractIf<'_, T, F, A>
        where
            F: FnMut(&mut T) -> bool,
            A: Allocator;

        impl<T, F, A> Drop for ExtractIf<'_, T, F, A>
        where
            A: Allocator;

        impl<T, F, A> Debug for ExtractIf<'_, T, F, A>
        where
            T: Debug,
            F: Debug,
            A: Debug + Allocator;
    }

    pub mod collections {
        pub mod linked_list {
            impl<T, A> LinkedList<T, A>
            where
                A: Allocator,
            {
                pub fn extract_if<F>(&mut self, filter: F) -> ExtractIf<'_, T, F, A>
                where
                    F: FnMut(&mut T) -> bool;
            }

            pub struct ExtractIf<'a, T, F, #[unstable(feature = "allocator_api", issue = "32838")] A = Global>
            where
                T: 'a,
                F: 'a + FnMut(&mut T) -> bool,
                A: Allocator;

            impl<T, F, A> Iterator for ExtractIf<'_, T, F, A>
            where
                F: FnMut(&mut T) -> bool,
                A: Allocator;

            impl<T, F> Debug for ExtractIf<'_, T, F, Global>
            where
                T: Debug;
        }
    }
}

Steps / History

• Implementation: Add Vec::drain_filter #43245
• removed drain-on-drop behavior, renamed to extract_if
  • Don't drain-on-drop in DrainFilter impls of various collections. #104455
  • Remove drain-on-drop behavior from various DrainFilter iterators libs-team#136
• Stabilization PR

Unresolved Questions

• What should the method be named?
• Should extract_if accept a Range argument?
• Missing Send+Sync impls on linked list's ExtractIf, see comment

See #43244 (comment) for a more detailed summary of open issues.

[RalfJung]

Related issues:
#25477
#34265

[bluss]

Maybe this doesn't need to include the kitchen sink, but it could have a range parameter, so that it's like a superset of drain. Any drawbacks to that? I guess adding bounds checking for the range is a drawback, it's another thing that can panic. But drain_filter(.., f) can not.

[rustonaut]

Is there any chance this will stabilize in some form in the not to far future?

[rustonaut]

If the compiler is clever enough to eliminate the bounds checks
in the drain_filter(.., f) case I would opt for doing this.

( And I'm pretty sure you can implement it in a way
which makes the compiler clever eneugh, in the worst
case you could have a "in function specialization",
basically something like if Type::of::<R>() == Type::of::<RangeFull>() { dont;do;type;checks; return } )

[jonhoo]

I know this is bikeshedding to some extent, but what was the reasoning behind naming this drain_filter rather than drain_where? To me, the former implies that the whole Vec will be drained, but that we also run a filter over the results (when I first saw it, I thought: "how is this not just .drain(..).filter()?"). The former on the other hand indicates that we only drain elements where some condition holds.

[rustonaut]

No idea, but drain_where sounds much better and is much more intuitive.
Is there still a chance to change it?

[bluss]

.remove_if has been a prior suggestion too

[rustonaut]

I think drain_where does explains it the best. Like drain it returns values, but it does not drain/remove all values but just such where a given condition is true.

remove_if sounds a lot like a conditional version of remove which just removes a single item by index if a condition is true e.g. letters.remove_if(3, |n| n < 10); removes the letter at index 3 if it's < 10.

drain_filter on the other hand is slightly ambiguous, does it drain then filter in a more optimized way (like filter_map) or does if drain so that a iterator is returned comparble to the iterator filter would return,
and if so shouldn't it be called filtered_drain as the filter get logically used before...

[Gankra]

There is no precedent for using _where or _if anywhere in the standard library.

[jonhoo]

@gankro is there a precedent for using _filter anywhere? I also don't know that that is that a reason for not using the less ambiguous terminology? Other places in the standard library already use a variety of suffixes such as _until and _while.