data-structures - 如何反转单链表并将其转换为向量？

Question

在写A*算法的时候，我尝试将一个单向 Action 链表逆向打包成Vec。

这是我的单链表的结构:

use std::rc::Rc;

struct FrontierElem<A> {
    prev: Option<Rc<FrontierElem<A>>>,
    action: A,
}

我的第一个想法是将操作push 到Vec 然后反转矢量:

fn rev1<A>(fel: &Rc<FrontierElem<A>>) -> Vec<A>
where
    A: Clone,
{
    let mut cur = fel;
    let mut ret = Vec::new();
    while let Some(ref prev) = cur.prev {
        ret.push(cur.action.clone());
        cur = prev;
    } // First action (where cur.prev==None) is ignored by design
    ret.as_mut_slice().reverse();
    ret
}

当时没有找到SliceExt::reverse方法，于是进行了第二种方案:从尾到头填充向量。我没有找到安全的方法。

/// Copies action fields from single-linked list to vector in reverse order.
/// `fel` stands for first element
fn rev2<A>(fel: &Rc<FrontierElem<A>>) -> Vec<A>
where
    A: Clone,
{
    let mut cnt = 0usize;
    // First pass. Let's find a length of list `fel`
    {
        let mut cur = fel;
        while let Some(ref prev) = cur.prev {
            cnt = cnt + 1;
            cur = prev;
        }
    } // Lexical scoping to unborrow `fel`

    // Second pass. Create and fill `ret` vector
    let mut ret = Vec::<A>::with_capacity(cnt);
    {
        let mut idx = cnt - 1;
        let mut cur = fel;
        // I didn't find safe and fast way to populate vector from the end to the beginning.
        unsafe {
            ret.set_len(cnt); //unsafe. vector values aren't initialized
            while let Some(ref prev) = cur.prev {
                ret[idx] = cur.action.clone();
                idx = idx - 1;
                cur = prev;
            }
        }
        assert_eq!(idx, std::usize::MAX);
    } // Lexical scoping to make `fel` usable again
    ret
}

在写这篇文章的时候，我突然想到我也可以为链表实现Iterator，然后使用rev和from_iter创建一个向量。唉，这需要大量开销，因为我必须实现 DoubleEndedIterator 特性才能使 rev 工作。

在这一点上，我的问题似乎微不足道，但我张贴它希望它会有一些用处。

基准:

running 2 tests
test bench_rev1 ... bench:   1537061 ns/iter (+/- 14466)
test bench_rev2 ... bench:   1556088 ns/iter (+/- 17165)

Answer 1

填充向量，然后使用 .as_mut_slice().reverse() 反转它。

fn rev1<A>(fel: &Rc<FrontierElem<A>>) -> Vec<A>
where
    A: Clone,
{
    let mut cur = fel;
    let mut ret = Vec::new();
    while let Some(ref prev) = cur.prev {
        ret.push(cur.action.clone());
        cur = prev;
    } // First action (where cur.prev==None) is ignored by design
    ret.as_mut_slice().reverse();
    ret
}