Linear time remove all Option::None from Vec<Option<T>>

1

Here is what I have so far:

                let mut n = clients.len() as i32 - 1;
                while n >= 0 {
                    if clients[n as usize].is_none() {
                        clients.swap_remove(n as usize);
                    }
                    n = n - 1;
                }

clients is a Vec<Option>

I want to remove all Option::None, while keeping the Option::Some.

I don't care about the order of the items.

I want this to work in linear time.

The above code seems very hacky. Is there a better way to do this?

2

Does it have to be the same vector ?
Otherwise you can just use filter like this:

3

retain will do the trick: clients.retain(|c| c.is_some());

4 Likes
4

@willi_kappler : Does your solution avoid clone() because into_iter() takes over ownership of the elements and the original vec is no loner valid?

5

The into_iter + filter + collect approach won't clone the items (they are simply moved to the new vector), but collect will allocate a new buffer for the output vector, and the old vector's buffer will be deallocated. retain won't allocate.

3 Likes
6

@Riateche : Thanks for the detailed analysis. Everything is clear now. Thanks!

1 Like
7

Is the filter + collect method actually linear time? Because Filter does not implement ExactSizeIterator so I guess that collect cannot preallocate the necessary amount of memory which in turn means that the whole operation would be in O(n log n), no?

8

If allocation doubles in size, then for a vec of length n, we are going to do

1 + 2 + 4 + ... + 2^k
where k = ceil(log_2 n)

this ends up being `< 2 * 2^k < 2 * 2n < 4n``

3 Likes
9

So we do log n steps, but each step is not constant * n -- the earlier steps are much smaller.

10

Nice analysis, thanks, you are right!

11

I suppose it would work with a pre-allocated vector of at least the same size as the original, as a slightly different angle to the iterator solution. Then you should be able to use empty_vec.extend(filtered_iterator);. Rust Playground

But you might as well use retain, as suggested above, and spare yourself that extra allocation, if you don't need to or want to also change the type of the content.

1 Like