在这些情况下，我们可能会倾向于将对象存储在一个 Vec<T> 中，并通过它们的索引相互引用。不再需要借用检查或所有权问题！通常，这种解决方案已经足够好了。

然而，现在当我们不再需要它们时，无法从那个 Vec<T> 中删除单个项目，因为我们最终会

• 弄乱被删除元素之后每个元素的索引，或者

• 遭受ABA问题。为了进一步阐述，如果我们尝试将 Vec<T> 替换为 Vec<Option<T>>，并通过将其设置为 None 来删除一个元素，那么我们就会产生以下存在缺陷的序列

  • obj1 在索引 i 处引用 obj2

  • 其他人从索引 i 删除了 obj2，将该元素设置为 None

  • 第三件事在索引 i 分配了 obj3，因为该索引处的元素是 None，因此可以用于分配

  • obj1 尝试在索引 i 处获取 obj2，但错误地得到了 obj3，而实际上获取应该失败。

通过在集合中引入单调递增的生成计数器，将每个元素与它被插入时的生成关联起来，并通过索引和元素被插入时的生成时间对获取集合中的元素，然后我们可以解决上述ABA问题。当在集合中索引时，如果索引对的生成与该索引处的元素生成不匹配，则该操作失败。

特性

• 零 unsafe
• 有不同类型的迭代器遍历树
• 经过良好测试

用法

首先，将 vec-tree 添加到您的 Cargo.toml

[dependencies]
vec-tree = "0.1"

然后，导入crate并使用 vec-tree::Tree

extern crate vec_tree;
use vec_tree::VecTree;

let mut tree = VecTree::new();

// Insert some elements into the tree.
let root_node = tree.insert_root(1);
let child_node_1 = tree.insert(10, root_node);
let child_node_2 = tree.insert(11, root_node);
let child_node_3 = tree.insert(12, root_node);
let grandchild = tree.insert(100, child_node_3);

// Inserted elements can be accessed infallibly via indexing (and missing
// entries will panic).
assert_eq!(tree[child_node_1], 10);

// Alternatively, the `get` and `get_mut` methods provide fallible lookup.
if let Some(node_value) = tree.get(child_node_2) {
    println!("The node value is: {}", node_value);
}
if let Some(node_value) = tree.get_mut(grandchild) {
    *node_value = 101;
}

// We can remove elements.
tree.remove(child_node_3);

// Insert a new one.
let child_node_4 = tree.insert(13, root_node);

// The tree does not contain `child_node_3` anymore, but it does contain
// `child_node_4`, even though they are almost certainly at the same index
// within the arena of the tree in practice. Ambiguities are resolved with
// an associated generation tag.
assert!(!tree.contains(child_node_3));
assert!(tree.contains(child_node_4));

// We can also move a node (and its descendants).
tree.append_child(child_node_1, child_node_4);

// Iterate over the children of a node.
for value in tree.children(child_node_1) {
    println!("value: {:?}", value);
}

// Or all the descendants in depth first search order.
let descendants = tree
    .descendants(root_node)
    .map(|node| tree[node])
    .collect::<Vec<i32>>();

assert_eq!(descendants, [1, 10, 13, 11]);