Interleaving iterator code review | Rust Programming Language Community | Page 1

candid imp Oct 11, 2022, 7:12 PM

#

I wrote immutable and mutable variants of an iterator that interleaves N iterators until one of them runs out. I had to avoid using allocations since this is used in DSP code, so I used an array of MaybeUninit objects for storing the iterators. Can anyone spot anything funny here?

Here's the gist as it was too long for Discord: https://gist.github.com/ilmai/bd2c92920a4b3304a5040a61723c1fc5

snow cradle Oct 11, 2022, 7:17 PM

#

Do you have to take them as an iterator of iterators? If you take it as an array, you can use a const generic for the array length

candid imp Oct 11, 2022, 7:21 PM

#

Nope, the number of sub-iterators isn't known at compile time

snow cradle Oct 11, 2022, 7:24 PM

#

Then there's the arrayvec crate, which lets you avoid MaybeUninit.

#

And I don't think you need a mut variant.

candid imp Oct 11, 2022, 7:27 PM

#

Ah you're correct, that was a leftover from earlier before I made this generic...

snow cradle Oct 11, 2022, 7:30 PM

#

I think you can replace this

if self.next_iterator_index >= self.iterators.len() {
    return None
}
```with 
```rs
if self.iterator_count == 0 {
    return None
}

candid imp Oct 11, 2022, 7:32 PM

#

Ah yes, good catch

amber mortar Oct 11, 2022, 7:36 PM

#

you can use option rather than maybeuninit, and use no unsafe

#

also, this is a big problem:

#

fn main() {
    let v = vec![1_u8, 2, 3].into_iter();
    let w = vec![4, 5, 6].into_iter();
    InterleaveIterator::new([v, w]);
}```

#

|| it leaks memory ||

candid imp Oct 11, 2022, 7:43 PM

#

amber mortar you can use option rather than maybeuninit, and use no unsafe

That requires the contained type to be Copy to construct the array

#

Ah right, objects inside MaybeUninit are implicitly ManuallyDrop?

amber mortar Oct 11, 2022, 7:45 PM

#

?play ```rust
pub fn foo<T, const N: usize>() -> [Option<T>; N] {
[0; N].map(|_| None)
}

loud dirgeBOT Oct 11, 2022, 7:45 PM

#

     Running `target/debug/playground`

candid imp Oct 11, 2022, 7:45 PM

#

Ah wait I can use Default

amber mortar Oct 11, 2022, 7:46 PM

#

candid imp Ah right, objects inside MaybeUninit are implicitly ManuallyDrop?

yeah, if you do this with maybeuninit you have to drop any remaining items yourself

candid imp Oct 11, 2022, 7:47 PM

#

Yep good catch.

snow cradle Oct 11, 2022, 7:47 PM

#

Here's what I figure:

use arrayvec::ArrayVec;

const MAX_ITERATORS: usize = 4;

pub struct InterleaveIterator<T, I: Iterator<Item = T>> {
    iterators: ArrayVec<I, MAX_ITERATORS>,
    next_index: usize,
}

impl<T, I> InterleaveIterator<T, I>
where
    I: Iterator<Item = T>
{
    pub fn new<II: IntoIterator<Item = I>>(iterators: II) -> InterleaveIterator<T, I> {
        let iterators = iterators.into_iter().collect();
        InterleaveIterator {
            iterators,
            next_index: 0
        }
    }
}

impl<T, I: Iterator<Item = T>> Iterator for InterleaveIterator<T, I> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.iterators.is_empty() {
            return None
        }
        
        let result = self.iterators[self.next_index].next();
        
        self.next_index += 1;
        self.next_index %= self.iterators.len();

        result
    }
}

amber mortar Oct 11, 2022, 7:47 PM

#

of course the danger with that is that you might end up dropping things twice which would be incredibly bad

#

(if you mess up)

snow cradle Oct 11, 2022, 7:52 PM

#

And then of course you can reimplement stuff like skip and nth (or advance_by on nightly) so that it stays efficient when the underlying iterators have efficient implementations.

#Interleaving iterator code review