Why is there no repeat for String and Vec?

libs
1

Only str and slice have a repeat method, for owned String and Vec this means one unnecessary copy.

3 Likes
2

Even on an owned String or Vec it would likely require a copy. If the output length exceeds the capacity of the input the String or Vec will reallocate it's internal storage, which copies all elements over.

1 Like
3

The reallocation is not guaranteed (depends on the capacity), and can be avoided if you allocate the vec using Vec::with_capacity beforehand.

4 Likes
4

You can make your own using just Vec::reserve and Vec::extend_from_within. Here is my attempt, though I haven't tested it very thoroughly.

Unfortunately I can't encourage rustc to optimize out the redundant reserve calls. I tried adding assertions such as assert!(v.len() <= v.capacity()) or assert!(len_new <= v.capacity()) to no avail.

5

can you not subtract the len itself with wrapping?

6

Notice that, the signature for &[T] is

pub fn repeat(&self, n: usize) -> Vec<T>

Thus this is the one you should use for Vec<T>

In case you want to visit vec for many times, maybe (0..times).flat_map(|_|vec.iter()).// do your stuff is better for you.

7

You can use it, but you may throw away unused allocations.

Is this not a cycle().take(n*len) or iter::repeat().take(n).flatten()?

8

Is it more about repeating a Vec a small number of times efficiently, like 10 times.

9

Actually that yields the same results as (0..times).flat_map(|_|vec.iter())

In case you want a real vector, the allocation is not avoidable. And in case you just want to create a read-only iterator over the repeated vector, (0..times).flat_map(|_|vec.iter()) is enough.

10

In some cases try_reserve() can optimize better. It has some extra hints for the optimizer, and without panic branch may be easier to optimize. But in this case I suspect LLVM just can't prove the reserved length matches later uses.

3 Likes
11

Yes, I suspect part of the issue is that Vec::extend_from_within unconditionally calls Vec::reserve, so we can't eliminate every reserve call unfortunately.

I am also noticing that rustc struggles to reason that even basic Vec invariants such as v.capacity() >= v.len() are preserved across [try_]reserve[_exact] calls (godbolt example)

3 Likes
13

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.