How to avoid multiple borrows when modifying a vector?

help
1

I've been doing some practice programming questions and thought it would be fun to do them in Rust. The task is to merge sorted linked list into a single sorted list. I tried to do it using a Vec as a heap. The whole code can be found at playground, the interesting part is:

pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

impl Solution {
    fn pop_min<'a>(heap: &'a mut Vec<&'a Box<ListNode>>) -> &'a Box<ListNode>{
...
    }

    fn add_heap<'a>(heap: &'a mut Vec<&'a Box<ListNode>>, elem: &'a Option<Box<ListNode>>)
...
    }

    pub fn merge_k_lists(lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
        let mut heap = Vec::new();
        let mut result_rev = None;
        for l in &lists {
            Solution::add_heap(&mut heap, l);
        }
        while !heap.is_empty() {
            let next_node = Solution::pop_min(&mut heap);
            let mut new_node = Box::new(ListNode::new(next_node.val));
            new_node.next = result_rev;
            result_rev = Some(new_node);
            Solution::add_heap(&mut heap, & next_node.next);
        }
        return result_rev;
    }

The problem is obviously that the code uses multiple borrows of heap. But, as I'm completely new to Rust, I don't know how can I avoid them, as the code needs to frequently change the heap while traversing the lists. How should I reorganize my code so that it doesn't have the problem of multiple borrows, but does not sacrifice cpu nor memory by unnecessary copies? I cannot change signature of merge_k_lists, as it is specified in the task. What is the Rust way to cope with situations like this?

2

It seems to me that both pop_min and add_heap should only borrow their argument until they are done, but for some reason, they seem to borrow if for longer. For add_heap that reason may be the explicit lifetime annotations that require heap and elem to have the same lifetime. For pop_min, the reason is that it borrows the returned value from the heap rather than actually popping it -- removing it from the heap. I think pop_min should return a Box<ListNode>, not a borrow of such a box. And I believe the heap should be a Vec<Box<ListNode>> rather than a Vec<&Box<ListNode>>.

1 Like
3

Here's an updated Rust Playground that uses boxes directly rather than references to them. It also uses the Vec::swap_remove and slice::swap methods to make things easier.

4

In general, any type that looks like &'a mut Something<'a> will cause lots of trouble and is probably wrong. It represents something of a Catch-22 in the type system:

  • Because of the 'a in &'a mut, this has exclusive use of the Something<'a> until the end of lifetime 'a.
  • Because of the 'a in Something<'a>, the lifetime 'a must last at least as long as the Something exists.

So, the reference can't give up its exclusivity until the object it points to is destroyed, but that object can't be destroyed as long as the reference has exclusive access1. The only way to make both of these things true is if the object is never destroyed and never released, which is not a very useful combination.

1 Because dropping a value through an &mut reference isn't allowed.

2 Likes
5

If you're developing lists, you should know that linked lists are the worst way to learn Rust:

  • &mut is not just mutable, but most importantly an exclusive lock. It's freezing whatever its target is, along with everything labelled with the same lifetime. You want to use it as little as possible, in a scope as small as possible. Don't extend its restrictions to everything by putting the same lifetime scope on every other reference.

  • & means it's only a temporary view of a value stored elsewhere, and through this reference that value can't be changed, nor moved, nor deleted, nor stored anywhere else. It's only for having a peek at it for a second. If you have an add function, it should be taking ownership of values, unless you specifically want to create a copy and store a copy.

  • It never makes sense to have &Box<T> as a type. Box is a pointer, so this is a needless double indirection. Just use &T if you're borrowing something temporarily, or Box<T> if you're passing or storing T by reference, but not both.

  • Don't try to avoid copying by overusing references. Rust doesn't copy things by accident. Rust passes things by reference even when they don't have & in their type.

2 Likes
6

Is this: Loading... ?

I cheesed that naively (put all values in a vec, sort it, and reconstruct the linked list from the sorted vector) and get:

Runtime: 4 ms, faster than 96.00% of Rust online submissions for Merge k Sorted Lists.
Memory Usage: 3.1 MB, less than 88.00% of Rust online submissions for Merge k Sorted Lists.

Since Rust objects unless pinned do not have a stable place in memory, there's no (easy) way for the grader to know that you reconstructed the linked list rather than used the original boxes.

7

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.