如何将 Vec 部分折叠到位？

Question

我想遍历 Vec 并组合其中的一些元素。我如何在 idiomatic Rust 中做到这一点？

示例：

#[derive(PartialEq, Debug)]
enum Thing { A, B, AandB }
fn combine(v: Vec<Thing>) -> Vec<Thing> {
    // idiomatic code here
}

fn main() {
     let v = vec![Thing::A, Thing::B];
     assert_eq!(vec![Thing::AandB], combine(v));
}

我会怎么做：

用Iterator::scan遍历Vec，如果Thing::A是之前的元素，用Thing::AandB替换所有出现的Thing::B。然后我会再次遍历它并删除 Thing::AandB.

之前的所有 Thing::As

这看起来超级复杂和不优雅。

Answer 1

不确定这是否算作惯用，但是 itertools 库具有适用于所有迭代器的 batching() 函数。结合标准库中的 peek()，您只需一次迭代即可获得结果，而不是两次。

extern crate itertools;

use itertools::Itertools;
use Thing::*;

#[derive(PartialEq, Debug)]
enum Thing { A, B, AandB }
fn combine(v: Vec<Thing>) -> Vec<Thing> {
    v.into_iter().peekable().batching(|mut it| {
        match it.next() {
            Some(A) => {
                if Some(&B) == it.peek() {
                    it.next();
                    Some(AandB)
                } else {
                    Some(A)
                }
            }
            x => x,
        }
    }).collect()
}

fn main() {
    let v = vec![A, B, A, A, A, B, B, A];
    assert_eq!(
        vec![AandB, A, A, AandB, B, A],
        combine(v)
    );
}

显然 collect() will allocate a new buffer.

Answer 2

我怀疑没有简单的方法可以用迭代器做到这一点，但没有人对普通的旧 c 风格设置禁运：

#[derive(PartialEq, Debug, Copy)]
enum Thing { A, B, AandB }
fn combine(mut v: Vec<Thing>) -> Vec<Thing> {
    let mut prev: Option<Thing> = None;
    let mut end = 0;
    for i in 0 .. v.len() {
        let el = v[i];
        match (el, prev) {
            (Thing::B, Some(Thing::A)) => {
                end = end - 1;
                v[end] = Thing::AandB
            },
            _ => 
                v[end] = el
        };
        prev = Some(el);
        end = end + 1;
    }

    v.truncate(end);
    v
}

fn main() {
     let v = vec![Thing::A, Thing::A, Thing::B, Thing::AandB, Thing::B, Thing::A];
     assert_eq!(vec![Thing::A, Thing::AandB, Thing::AandB, Thing::B, Thing::A], combine(v));
}

这是一个直接转换的过程。

Answer 3

这是一个使用递归和模式匹配的解决方案。我很确定递归是尾递归，因此可以变成迭代。

use Thing::*;

#[derive(Copy,Clone,PartialEq,Debug)]
enum Thing { A, B, AandB }

fn combine(v: Vec<Thing>) -> Vec<Thing> {
    fn inner(mut res: Vec<Thing>, s: &[Thing]) -> Vec<Thing> {
        match s {
            [A, B, tail..] => {
                res.push(AandB);
                inner(res, tail)
            },
            [a, tail..] => {
                res.push(a);
                inner(res, tail)
            },
            [] => res,
        }
    };

    inner(Vec::new(), &v)
}

fn main() {
    let v = vec![A, A, B, AandB, B, A];
    assert_eq!(vec![A, AandB, AandB, B, A], combine(v));

    let v = vec![A, A, B, AandB, B, A, B, A, B];
    assert_eq!(vec![A, AandB, AandB, B, AandB, AandB], combine(v));

    let v = vec![A, A, B, AandB, B, A, B, A, A];
    assert_eq!(vec![A, AandB, AandB, B, AandB, A, A], combine(v));
}

Answer 4

我合并了 swizard 的答案和 Shepmaster 的答案，最终得到了一个就地解决方案，该解决方案递归地运行向量，只有向量是可变的，并且从不移动任何东西两次。不保证运行时或惯用性 ;)

use Thing::*;
use std::cmp::min;

#[derive(Copy,Clone,PartialEq,Debug)]
enum Thing { A, B, AandB}

fn combine(mut v: Vec<Thing>) -> Vec<Thing> {
    fn inner(res: &mut Vec<Thing>, i: usize, backshift: usize) {
        match &res[i..min(i+2, res.len())] {
            [A, B] => {
                res[i - backshift] = AandB;
                inner(res, i + 2, backshift + 1);
            },
            [a, ..] => {
                res[i - backshift] = a;
                inner(res, i + 1, backshift);
            },
            [] => res.truncate(i - backshift),
        }
    };

    inner(&mut v, 0, 0);
    v
}

fn main() {
     let v = vec![A, A, B, AandB, B, A, B, A, B];
     assert_eq!(vec![A, AandB, AandB, B, AandB, AandB], combine(v));
     let v = vec![A, A, B, AandB, B, A, B, A, A];
     assert_eq!(vec![A, AandB, AandB, B, AandB, A, A], combine(v));
}

Answer 5

好的，这是一个没有显式 for 循环和递归的惯用版本:)

#[derive(PartialEq, Debug, Copy)]
enum Thing { A, B, AandB }
fn combine(mut v: Vec<Thing>) -> Vec<Thing> {
    let (_, total) = (0 .. v.len()).fold((None, 0), |&mut: (prev, end), i| {
        let el = v[i];
        let (next, item) = match (el, prev) {
            (Thing::B, Some(Thing::A)) => (end, Thing::AandB),
            _ => (end + 1, el),
        };
        v[next - 1] = item;
        (Some(el), next)
    });

    v.truncate(total);
    v
}

fn main() {
     let v = vec![Thing::A, Thing::A, Thing::B, Thing::AandB, Thing::B, Thing::A];
     assert_eq!(vec![Thing::A, Thing::AandB, Thing::AandB, Thing::B, Thing::A], combine(v));
}

如何将 Vec 部分折叠到位？

How do I partially fold a Vec in place?

coding-style

rust

示例：

我会怎么做：