Container of VecDeque/LinkedList iterators

help
1

This question is follow up on the Vector of iterators. It seems to be quite easy to store vec::IntoIter inside a vector:

    let seq: Vec<Vec<i32>> = vec![vec![0,1], vec![2,3]];
    
    type IT = std::vec::IntoIter<i32>;
    let mut iters: Vec<IT> = Vec::new();
    
    let mut it = seq.into_iter();
    loop {
        match it.next() {
            None => break,
            Some(s) => {
                iters.push( s.into_iter() );
            },
        };
    }

But if the original vector is modified it means that iterators are invalidated (from my C++ background) so I think it makes sense to use LinkedList or VecDeque to be sure that iterators are always valid (please correct me if I'm wrong). The problem is that I don't get how to declare a type alias for VecDeque::Iter and also I found that there is no IntoIter in VecDeque:

    use std::collections::VecDeque;
    let seq: Vec<Vec<i32>> = vec![vec![0,1], vec![2,3]];
    
    type IT = std::collections::VecDeque::Iter; // Error!
    let mut iters: Vec<IT> = Vec::new();
    
    let mut it = seq.iter(); // no into_iter for VecDeque, might be wrong as well
    loop {
        match it.next() {
            None => break,
            Some(s) => {
                iters.push( s.iter() ); // not sure that we can do this way
            },
        };
    }

Background for this post: I'm learning Rust by rewriting some leetcode problems from C++ to Rust. In this case, I'm doing specifically problem "LRU Cache". It might mean that I'm doing something conceptually wrong just due to my C++ background.

2

You don't have to worry about iterator invalidation with the std collections (or any soundly-implemented collection), because Rust's borrow check prevents it at compile time. In this case, because Vec::into_iter consumes the Vec that you call it on, you can't access the Vec at all after you've obtained the vec::IntoIter, so there is no possibility of invalidation.

The consuming iterator for VecDeque<T> (the thing that's returned from VecDeque::into_iter) is called std::collections::vec_deque::IntoIter<T>, alternatively spelled <VecDeque<T> as IntoIterator>::IntoIter. Rust collections usually have an API like this:

mod my_collection {
    // a collection of `T`
    struct MyCollection<T> { ... }
    // an iterator over shared references to the elements of a `MyCollection<T>`
    struct Iter<'a, T> { ... }
    impl<'a, T> Iterator for Iter<'a, T> {
        type Item = &'a T;
        fn next(&mut self) -> Option<Self::Item> { ... }
    }
    // an iterator over exclusive/mutable references to the elements of a `MyCollection<T>`
    struct IterMut<'a, T> { ... }
    impl<'a, T> Iterator for IterMut<'a, T> {
        type Item = &'a mut T;
        fn next(&mut self) -> Option<Self::Item> { ... }
    }
    // an iterator that consumes a `MyCollection<T>` and yields the owned elements
    struct IntoIter<T> { ... }
    impl<T> Iterator for IntoIter<T> {
        type Item = T;
        fn next(&mut self) -> Option<Self::Item> { ... }
    }
    impl<T> MyCollection<T> {
        // create an iterator over `&'a T` from a `&'a MyCollection<T>`
        fn iter(&self) -> Iter<'_, T> { ... }
        // create an iterator over `&'a mut T` from a `&'a mut MyCollection<T>`
        fn iter_mut(&mut self) -> IterMut<'_, T> { ... }
    }
    // this impl allows writing `for x in &my_coll { ... }`, among other uses
    impl<'a, T> IntoIterator for &'a MyCollection<T> {
        type Item = &'a T;
        type IntoIter = Iter<'a, T>;
        fn into_iter(self) -> Self::IntoIter { self.iter() }
    }
    // this impl allows writing `for x in &mut my_coll { ... }`, among other uses
    impl<'a, T> IntoIterator for &'a mut MyCollection<T> {
        type Item = &'a mut T;
        type IntoIter = IterMut<'a, T>;
        fn into_iter(self) -> Self::IntoIter { self.iter_mut() }
    }
    impl<T> IntoIterator for MyCollection<T> {
        type Item = T;
        type IntoIter = IntoIter<T>;
        fn into_iter(self) -> Self::IntoIter { ... }
    }
}

In your second snippet you seem to be mixing up .iter() and Iter with .into_iter() and IntoIter; these are distinct and have different uses.

5 Likes
3

Due to the way iterators interact with Rust lifetimes, this isn't true: Every iterator remains valid for as long as you keep a hold of it, and all non-consuming iterators will prevent any changes to the underlying collection as long as they exist (at least in std).

If you want to allow the underlying collection to change during iteration, you'll need to write that by hand with the indexing operator or similar. Even then, it can sometimes be tricky to make the iteration and modification code play nicely together wrt. lifetimes.

2 Likes
4

In other words, one of the advantages of Rust is that iterator invalidation (of the UB variety) is not possible without unsafe (or unsoundness in someone else's code). If you're building your own iterators or similar from the standard data structures and want to do so without unsafe to take advantage of this, methods like split_at_mut are the main building block -- methods that allow you to segment a uniquely borrowed piece of memory into multiple pieces, one of which you can hold on to, and the other of which you can return.

As for naming -- the primary way to end up with a return value that you cannot name is if the return type was opaque -- something like -> impl Iterator<Item=Foo>. These opaque types are the simplest way to return iterators that involve (unnameable) closures in Rust, so you may see them in library crates or other people's code. As a consumer, these unnameable types can be a little annoying in that you cannot yet put them in your own data structures without either becoming unnameable yourself, or by using some sort of indirection (like Box<dyn Iterator<Item=Foo>>).

However,

  • They cannot be used in traits yet, so you won't see them there
  • The standard library has made a point (so far anyway) to only return named types

So when working with the standard library, you can be pretty sure you can get ahold of something that's easy to put into your own structs. That is, if an IntoIter analogue for VecDeque exists in stdlib, it has a name you could find. You can consult the docs:

Or you can usually just get the compiler to tell you:

    // n.b. this is your code block except...
    let seq: Vec<Vec<i32>> = vec![vec![0,1], vec![2,3]];
    
    // ... I changed this part to be intentionally wrong
    let mut iters: Vec<()> = Vec::new();
    //                 ^^    
    let mut it = seq.iter();
    loop {
        match it.next() {
            None => break,
            Some(s) => {
                iters.push( s.iter() );
            },
        };
    }

12 |                 iters.push( s.iter() );
   |                             ^^^^^^^^ expected `()`, found struct `std::slice::Iter`

But wait, that's slice::Iter, not the vec_deque::IntoIter (or Iter) you were hoping for...

There is not one underlying set of iterator structs or generic iterator structs that the standard library uses. Every collection has it's own set of type-specific iterators. The only [1] way you can get a vec_deque::IntoIter is if you start with a VecDeque; you can't ask for one from a Vec (or slice). If there's some semantic difference between a slice::Iter and a vec_deque::Iter, it's probably due to the underlying type, and not something you could induce just by asking for a different type of iterator.

So, I think you were searching for this vec_deque::IntoIter because you thought you needed to given your history of running into iterator invalidation, and you don't actually need it for your Vec<Vec<_>>. If you did need it, you'd probably also need to be starting with a Vec<VecDeque<_>>.

This particular post is getting a bit long, so I'll just stop here. I might make another post exploring what getting hold of a Vec<vec_deque::IntoIter> might look like though.

  1. never say never, but I think you'll understand my gist here ↩ī¸Ž

2 Likes
5

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.