自定义数据结构
当你第一次在开罗开始编程时，你可能想要使用数组（'Array
当您想要使用可变数据结构时，这可能会令人沮丧。 例如，假设你正在制作一个游戏，玩家有一个等级属性，他们可以升级。 您可以尝试将玩家的等级存储在数组中：
let mut level_players = Array::new();
level_players.append(5);
level_players.append(1);
level_players.append(10);但是接下来你会发觉，一旦给某个特定的索引中玩家设置了等级，它的等级就无法再次提升。 如果玩家死亡，你也无法将它移出数组，除非他碰巧排在第一位。
幸运的是，Cairo 提供了一个方便的内置 [字典类型]（./ch03-02-dictionaries.md） 称为 Felt252Dict<T>，
允许我们模拟可变数据结构的行为。我们先来探讨一下如何使用它来创建一个动态数组实现。
注意：本章中使用的几个概念将在后面几个章节里详细解释。 我们建议您先查看以下章节： [结构体]（./ch05-00-using-structs-to-structure-related-data）， [方法]（./ch05-03-method-syntax.md）、 [泛型]（./ch08-00-generic-types-and-traits.md）， [Traits]（./ch08-02-traits-in-cairo.md）
使用字典模拟动态数组
首先，让我们考虑一下我们希望可变动态数组的行为方式。它需要支持哪些操作？
它应该：
- 允许我们在末尾附加项
- 让我们按索引访问任何项
- 允许在特定索引处设置项的值
- 返回当前长度
我们可以在Cairo中定义这个接口，如下所示：
#![allow(unused)] fn main() { trait VecTrait<V, T> { fn new() -> V; fn get(ref self: V, index: usize) -> Option<T>; fn at(ref self: V, index: usize) -> T; fn push(ref self: V, value: T) -> (); fn set(ref self: V, index: usize, value: T); fn len(self: @V) -> usize; } }
这为我们的动态数组的实现提供了蓝图。
我们命名它为Vec，因为它类似于 Rust 中的Vec<T> 数据结构。
在Cairo中实现���态数组
为了存储我们的数据，我们将使用Felt252Dict<T> 来映射索引号（felt）到值。
我们还将存储一个单独的len字段来跟踪长度。
下面是我们的结构体的样子。我们将类型T包装在Nullable指针中，这使得在我们的数据结构中可以使用任何类型的 T ，
如词典 ：
#![allow(unused)] fn main() { struct NullableVec<T> { data: Felt252Dict<Nullable<T>>, len: usize } }
使这个向量可变的关键是我们可以将值插入到用于在数据结构中设置或更新值的字典。 例如，要更新特定索引处的值，我们执行以下操作：
fn set(ref self: NullableVec<T>, index: usize, value: T) {
assert(index < self.len(), 'Index out of bounds');
self.data.insert(index.into(), nullable_from_box(BoxTrait::new(value)));
}这将覆盖字典中该索引处先前存在的值。
虽然数组是不可变的，但字典提供了我们的可修改的数据结构（如向量）所需要的灵活性。
接口其余部分的实现非常简单。 在我们的接口中定义的所有方法的实现可以按如下方式完成:
#![allow(unused)] fn main() { impl NullableVecImpl<T, +Drop<T>, +Copy<T>> of VecTrait<NullableVec<T>, T> { fn new() -> NullableVec<T> { NullableVec { data: Default::default(), len: 0 } } fn get(ref self: NullableVec<T>, index: usize) -> Option<T> { if index < self.len() { Option::Some(self.data.get(index.into()).deref()) } else { Option::None } } fn at(ref self: NullableVec<T>, index: usize) -> T { assert(index < self.len(), 'Index out of bounds'); self.data.get(index.into()).deref() } fn push(ref self: NullableVec<T>, value: T) -> () { self.data.insert(self.len.into(), nullable_from_box(BoxTrait::new(value))); self.len = integer::u32_wrapping_add(self.len, 1_usize); } fn set(ref self: NullableVec<T>, index: usize, value: T) { assert(index < self.len(), 'Index out of bounds'); self.data.insert(index.into(), nullable_from_box(BoxTrait::new(value))); } fn len(self: @NullableVec<T>) -> usize { *self.len } } }
“Vec”结构的完整实现可以在社区维护的库 Alexandria里找到。
使用字典模拟堆栈
现在，我们将查看第二个示例及其实现细节：堆栈。
堆栈是 LIFO（后进先出）集合。插入新的元素和现有元素的删除发生在同一端， 表示为堆栈的顶部。
让我们定义创建堆栈所需的操作：
- 将项推到堆栈的顶部
- 从堆栈顶部弹出一个项
- 检查堆栈中是否还有元素。
根据这些规则我们可以定义以下接口：
#![allow(unused)] fn main() { trait StackTrait<S, T> { fn push(ref self: S, value: T); fn pop(ref self: S) -> Option<T>; fn is_empty(self: @S) -> bool; } }
在Cairo实现可变堆栈
要在Cairo创建堆栈数据结构，我们可以再次使用Felt252Dict<T>
将堆栈的值与usize字段一起存储，以跟踪堆栈的长度来迭代它。
堆栈结构定义如下：
#![allow(unused)] fn main() { struct NullableStack<T> { data: Felt252Dict<Nullable<T>>, len: usize, } }
接下来，让我们看看我们的主要功能push和pop 是如何实现的。
#![allow(unused)] fn main() { impl NullableStackImpl<T, +Drop<T>, +Copy<T>> of StackTrait<NullableStack<T>, T> { fn push(ref self: NullableStack<T>, value: T) { self.data.insert(self.len.into(), nullable_from_box(BoxTrait::new(value))); self.len += 1; } fn pop(ref self: NullableStack<T>) -> Option<T> { if self.is_empty() { return Option::None; } self.len -= 1; Option::Some(self.data.get(self.len.into()).deref()) } fn is_empty(self: @NullableStack<T>) -> bool { *self.len == 0 } } }
该代码使用 insert和 get方法访问Felt252Dict<T>。
要将元素推送到堆栈顶部，使用push函数将元素插入字典中的索引 'len' - 并增加
堆栈的 'len' 字段来跟踪堆栈顶部的位置。
要删除一个值，使用pop函数检索位置len-1处的最后一个值
然后减小 'len' 的值以更新堆栈顶部的位置。
堆栈的完整实现，以及您拥有的更多数据结构
可以在你的代码中使用，可以在社区维护中的
Alexandria
库中的data_structures crate中找到。
总结
虽然 Cairo 的内存模型是不可变的，使其难以实现可变的数据结构，
但幸运的是，我们可以使用 'Felt252Dict