如何确保Rust向量仅包含交替类型？

Question

我有一组在A和B之间交替的数据。这些都是有效的选择：

• A -> B -> A
• A -> B -> A -> B
• B -> A -> B
• B -> A -> B -> A

我想利用类型系统来确保交替属性在编译时被检查，同时保持良好的性能。

解决方案1：链表

struct A {
    // data
    next: Option<B>,
}

struct B {
    // data
    next: Option<Box<A>>,
}

问题在于此数据结构的性能充其量是最差的。链接列表频繁发生高速缓存未命中，并且对于迭代数据结构而言，这是非常糟糕的。

解决方案2：Vec +枚举

enum Types {
    A(DataA),
    B(DataB),
}

type Data = Vec<Types>;

使用此解决方案，缓存局部性要好得多，因此可以提高性能。但是，这并不能阻止2 As并排放置。还有一个事实是，每次迭代都需要检查类型，而由于非正式的定义，因此不需要。

解决方案3：组合

struct A {
    // data, default in first link = empty
    b: Option<B>,
}

struct B {
    // data
}

type Data = Vec<A>;

这结合了Vec链表的类型验证和的缓存位置。这很丑陋，需要检查第一个值以验证它是否确实是an A，或者是否是下一个的空容器B。

问题

是否有一种数据结构可允许进行编译时类型验证，同时保持缓存局部性并避免额外分配？

Answer 1

要以类型系统强制且具有合理效率的方式存储交替类型，可以使用元组：Vec<(X, Y)>。

您的情况还需要

• Option从中存储额外的领先价值以开始Y
• 在中存储一个额外的尾随值Option以处理结尾为X

use either::Either; // 1.5.2
use std::iter;

#[derive(Debug, Default)]
struct Data<X, Y> {
    head: Option<Y>,
    pairs: Vec<(X, Y)>,
    tail: Option<X>,
}

impl<X, Y> Data<X, Y> {
    fn iter(&self) -> impl Iterator<Item = Either<&X, &Y>> {
        let head = self.head.iter().map(Either::Right);

        let pairs = self.pairs.iter().flat_map(|(a, b)| {
            let a = iter::once(Either::Left(a));
            let b = iter::once(Either::Right(b));
            a.chain(b)
        });

        let tail = self.tail.iter().map(Either::Left);

        head.chain(pairs).chain(tail)
    }
}

话虽如此，您将在某处遇到人体工程学问题。例如，你不能只是push一个Either<X, Y>因为以前压值可能是同一类型的。一次创建整个结构可能是最简单的方向：

#[derive(Debug)]
struct A;
#[derive(Debug)]
struct B;

fn main() {
    let data = Data {
        head: Some(B),
        pairs: vec![(A, B)],
        tail: None,
    };

    println!("{:?}", data.iter().collect::<Vec<_>>());
}