How to take all elements of a vec without shrinking capacity?

Background

I have a vec, and my algorithms requires that in each round, I will iterate the vec and do a filter on each elements, and the round will finish when the vec's length is stable.

To implement this algorithm, it is nature to have two vecs: ori and tmp. The pseudocode looks like

let mut tmp = Vec::with_capacity(ori.len());
loop {
    let prev_round_length = ori.len();
    for ele in ori /* Here needs help! */ {
        if filter(&ele) {
            tmp.push(ele);
        }
    }
    std::mem::swap(&mut tmp, &mut ori);
    let cur_round_length = ori.len();
    if cur_round_length == prev_round_length {
        break;
    }
}

Problem

The for ele in ori is where I need help. In this pseudocode, this for-loop needs to meet several requirements:

  • The ownership of ori should not be taken
    Since ori needs to be swapped with tmp later.
  • The ownership of all elements of ori should be taken
    Since they would be pushed into tmp later.
  • The capacity of ori should not be shrunk
    We shall make sure tmp and ori does not require additional resize in the loop, since it is unnecessary (The maximum length is already known before the loop).

For now, I can only use while let Some(ele) = ori.pop() to work around, since the documentation of pop does not mention the resize, so I could assume pop does not lead to ori's capacity shrinking.

However, I don't think it is a graceful pattern. Is there any better ways to achieve this?

Use Vec::drain?

2 Likes

As already mentioned, if you want to keep your exact approach, then you can work with

for ele in ori.drain(..)

which keeps ori's ownership and capacity intact.

That being said, the thing you're doing here, filtering a vec down with some predicate, is probably much more fittingly handled by instead using the Vec::retain method; which works fully in-place (no need for the extra tmp; also preserving ownership & capacity of ori).

3 Likes

Thank you for pointing this out. I suddenly realize that, is it true that all "filtering" functions for vec (such as pop, drain, retain) are guaranteed to not shrink the capacity?

Yes, looks like it is:

Vec will never automatically shrink itself, even if completely empty. This ensures no unnecessary allocations or deallocations occur. Emptying a Vec and then filling it back up to the same len should incur no calls to the allocator. If you wish to free up unused memory, use shrink_to_fit or shrink_to.

(from within this section)

5 Likes