2

I'm trying to implement building a singly-linked list from an Iterator, keeping the order of elements.

The structure is defined as:

#[derive(Debug)]
struct List<T> {
    list: Node<T>,
}

type Node<T> = Option<Box<Link<T>>>;

#[derive(Debug)]
struct Link<T> {
    head: T,
    tail: Node<T>,
}

I was thinking of keeping a mutable reference to the end of the list and expanding it while iterating. However, I couldn't figure out how this could be done. The (non-working) idea was:

impl<T> List<T> {
    pub fn from_iterator(i: &mut Iterator<Item = T>) -> Self {
        let mut list = List { list: None };
        {
            let mut last: &mut Node<T> = &mut list.list;
            for x in i {
                let singleton = Box::new(Link {
                    head: x,
                    tail: None,
                });
                *last = Some(singleton);
                // --> I aim for something like the line below. Of course
                // 'singleton' can't be accessed at this point, but even if I
                // match on *last to retrieve it, still I couldn't figure out how
                // to properly reference the new tail.
                // last = &mut singleton.tail;
            }
        }
        list
    }
}

It'd be possible to just build the list in reverse and then reverse it afterwards with the same time complexity, but I was curious if the above approach is ever possible in Rust.

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
Petr
  • 62,528
  • 13
  • 153
  • 317

2 Answers2

2

As described in Cannot obtain a mutable reference when iterating a recursive structure: cannot borrow as mutable more than once at a time, you can explicitly transfer ownership of the mutable reference using {}:

impl<T> List<T> {
    pub fn from_iterator<I>(i: I) -> Self
    where
        I: IntoIterator<Item = T>,
    {
        let mut list = List { list: None };
        {
            let mut last: &mut Node<T> = &mut list.list;

            for x in i {
                let singleton = Box::new(Link {
                    head: x,
                    tail: None,
                });
                *last = Some(singleton);

                last = &mut {last}.as_mut().unwrap().tail;
            }
        }
        list
    }
}

I also removed the trait object (&mut Iterator) in favor of a generic. This allows for more optimized code (although with a linked list it's probably not worth it).

It's unfortunate that the unwrap is needed. Even though the Link is placed on the heap, making the address stable, the compiler does not perform that level of lifetime tracking. One could use unsafe code based on this external knowledge, but I don't know that it's worth it here.

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
  • Could you please also elaborate on the `&mut Iterator` comment and more optimized code? Is my intuition correct that using generics the compiler can specialize the function for different iterators? – Petr Mar 17 '18 at 18:06
  • @PetrPudlák does [What is the difference between Box and &Trait / Box?](https://stackoverflow.com/q/45151770/155423) answer your question? – Shepmaster Mar 17 '18 at 23:01
0

I'm not sure you can do it in a loop. The borrow checker might not be smart enough. You can do it with recursion though.

impl<T> List<T> {
    pub fn from_iterator(i: &mut Iterator<Item = T>) -> Self {
        let mut list = List { list: None };
        Self::append_from_iterator(&mut list.list, i);
        list
    }
    pub fn append_from_iterator(list: &mut Node<T>, i: &mut Iterator<Item = T>) {
        match i.next() {
            Some(x) => {
                let mut singleton = Box::new(Link {
                    head: x,
                    tail: None,
                });
                Self::append_from_iterator(&mut singleton.tail, i);
                *list = Some(singleton);
            }, 
            None => (),
        }

    }
}

playground

NovaDenizen
  • 5,089
  • 14
  • 28