Add `VecDeque::extract_if`

[tisonkun]

Proposal

Problem statement

The same as Vec::extract_if but for VecDeque. Refer to rust-lang/rust#43244.

Motivating examples or use cases

I wrote some code that is effectively VecDeque::extract_if: https://github.com/fast/fastpool/blob/7727c520/fastpool/src/retain_spec.rs#L42-L89

If we already have extract_if for Vec and LinkedList, it should be natural to add one for VecDeque.

Solution sketch

Should be almost the same as vec::ExtractIf but for VecDeque:

impl<T, A: Allocator> VecDeque<T, A> {
    pub fn extract_if<F, R>(&mut self, range: R, filter: F) -> ExtractIf<'_, T, F, A>
    where
        F: FnMut(&mut T) -> bool,
        R: RangeBounds<usize>,
    {
        ExtractIf::new(self, filter, range)
    }
}

pub struct ExtractIf<'a, T, F, A: Allocator = Global> {
    vec: &'a mut VecDeque<T, A>,
    idx: usize,
    end: usize,
    del: usize,
    old_len: usize,
    pred: F,
}

Alternatives

Not yet. You can read the code snippet above for how to work around it outside the std.

Links and related work

• Tracking issue for Vec::extract_if and LinkedList::extract_if rust#43244
• Tracking Issue for {BTreeMap,BTreeSet}::extract_if rust#70530

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[programmerjake]

if it's not too hard, can you implement Default for the new iterator? (for making an empty iterator)

[tisonkun]

if it's not too hard, can you implement Default for the new iterator? (for making an empty iterator)

I'll try to figure it out. However, a quick glance shows that:

1. Vec's and BTreeMap's ExtractIf does not implement Default.
2. It may not be intuitive because ExtractIf has an F type param which may not implement Default.

Or you are referring to other "new iterator"?

[kennytm]

@tisonkun "implement Default" is referring to #656.

@programmerjake In #656 the ExtractIf of all 6 existing collection types (Vec, LinkedList, BTreeSet, BTreeMap, HashSet, HashMap) are categorized as "iterator could implement Default but it might make the rest of the iterator slower (e.g. adding a conditional in Drop)". The ExtractIf of VecDeque should have the same property. Because of the performance cost, I think this ACP should not implement Default (unless it is shown to be zero-cost), deferring the decision whether to impl Default on this category in #656.

[tisonkun]

Thanks for your information!

I'll create a tracking issue with feature flag vec_deque_extract_if later this week.

It seems no ACP approved yet, maybe it would be discussed in the next meeting?

[Amanieu]

We discussed this in the @rust-lang/libs-api meeting and are happy to accept this.

Please open a tracking issue and open a PR to rust-lang/rust to add it as an unstable feature. You can close this ACP once the tracking issue has been created.

[tisonkun]

Closed as now tracked by rust-lang/rust#147750.

[tisonkun]

Ready for review - rust-lang/rust#147780