Filter_take function pre-RFC


#1

I’ve had an idea for a function that might be useful to collection types in the std library. Before making the RFC I want to see if anyone here knows if any similar ideas have already been proposed, and I’d like to gather feedback on how useful this might be.

filter_take is a function that would be added to all collection types in the std library, it would work much like iter().filter() however this function removes the filtered values from the collection and returns them in an iterator. Additionally this function operates on the collection itself, not an Iterator, as Iterators cannot conditionally remove data from their underlying collection.

To start things off I’d like to provide an example implementation for the Vec type.

pub struct FilterTake<F, T>
where F: FnMut(&mut T) -> bool {
    v: &mut Vec<T>,
    f: F,
    i: isize,
    del: isize,
}

impl<F, T> Iterator for FilterTake<F, T>
where F: FnMut(&mut T) -> bool {
    type Item = T;

    fn next(&mut self) -> Option<T> {
        use std::ptr::{copy_nonoverlapping, read};
        while self.i < self.v.len {
            unsafe {
                if f(*self.v.as_mut_ptr().offset(self.i)) {
                   self.del += 1;
                   self.i += 1;
                   return Some(read(self.v.as_ptr().offset(i-1)));
                } else if self.del > 0 {
                   copy_nonoverlapping(self.v.as_ptr().offset(self.i), self.v.as_mut_ptr().offset(self.i - self.del), 1);
                }
                self.i += 1;
            }
        }
        return None;
    }
}

impl<F, T> Drop for FilterTake<F, T>
where F: FnMut(&mut T) -> bool {
    fn drop(self) {
        self.v.len -= self.del;
    }
}

impl<T> Vec<T> {

    pub fn filter_take<F>(&mut self, f: F) -> FilterTake<F, T>
    where F: FnMut(&mut T) -> bool {
        FilterTake {
            v: self,
            f,
            i: 0,
            del: 0,
        }
    }
}

#2

Great minds think alike :slight_smile: For Vec, this was added recently under the name drain_filter.

I’m not aware of concrete plans for other collections, but it’s certainly possible. The implementation and API design (e.g., for maps: should the closure have access to the value?) may be a tad more complicated than for Vec, though.


#3

This was recently added to Vec with the name drain_filter. It’s currently unstable. I don’t think it’s been implemented for other standard collection types, yet. See also this previous thread.