CODEWITHSUNDEEP
rust
Anonymous
Anonymous

Reputation: 449

How to partition Vec in place in method that doesn't own `self`?

So, there's some struct that looks like this:

struct foo {
    alpha: Vec<T>,
    beta: Vec<T>,
}

And some method should move some values that matches some condition from alpha to beta. The question is: what is the clean way to do it without owning self?

The Vec::partition() method can't be used because any moving of self.alpha causes cannot move out of dereference of &mut-pointer compile error.

PS: T have File inside so it doesn't implement Clone.

Upvotes: 2

Views: 642

Answers (1)

Chris Morgan
Chris Morgan

Reputation: 90812

Do you want to just drop beta? This is the sort of thing that std::mem::replace is for, allowing you to pull it out:

use std::mem;

impl Foo {
    fn munge(&mut self) {
        let alpha = mem::replace(&mut self.alpha, Vec::new());
        let (alpha, beta) = alpha.partition(…);
        self.alpha = alpha;
        self.beta = beta;
    }
}

Note that there is a new Vec created there briefly, but that doesn’t really matter; it doesn’t involve an allocation and is very cheap. (The alternative would be leaving uninitialised memory there and replacing it again, forgetting the uninitialised memory, but that is unsafe if the partition can fail as it will run the destructor on the uninitialised memory.)

Since you want to just shift the elements matching the predicate, it’s worth looking at how partition is implemented:

pub fn partition<F>(self, mut f: F) -> (Vec<T>, Vec<T>) where F: FnMut(&T) -> bool {
    let mut lefts  = Vec::new();
    let mut rights = Vec::new();

    for elt in self.into_iter() {
        if f(&elt) {
            lefts.push(elt);
        } else {
            rights.push(elt);
        }
    }

    (lefts, rights)
}

Knowing that this is how it is implemented makes implementing something like it which doesn’t involve a second vector being created is rather easy; here’s the general idea:

let source = mem::replace(&mut self.alpha, Vec::new());
for element in source.into_iter() {
    if f(&element) { /* for some `f` */
        self.alpha.push(element)
    } else {
        self.beta.push(element)
    }
}

Really, mem::replace is the only thing you need to know about for these sorts of things; the rest then becomes fairly easy.

Upvotes: 3

Related Questions