自定义数据结构

When you first start programming in Cairo, you'll likely want to use arrays (Array<T>) to store collections of data. However, you will quickly realize that arrays have one big limitation - the data stored in them is immutable. Once you append a value to an array, you can't modify it.

This can be frustrating when you want to use a mutable data structure. For example, say you're making a game where the players have a level, and they can level up. You might try to store the level of the players in an array:

    let mut level_players = array![5, 1, 10];

But then you realize you can't increase the level at a specific index once it's set. If a player dies, you cannot remove it from the array unless he happens to be in the first position.

Fortunately, Cairo provides a handy built-in dictionary type called Felt252Dict<T> that allows us to simulate the behavior of mutable data structures. Let's first explore how to create a struct that contains, among others, a Felt252Dict<T>.

Note: Several concepts used in this chapter were already presented earlier in the book. We recommend checking out the following chapters if you need to revise them: Structs, Methods, Generic types, Traits.

Dictionaries as Struct Members

在Cairo中可将字典定义为结构体成员，但正确地与它们交互可能不是完全无障碍的。让我们尝试实现一个自定义的_user数据库，它将允许我们添加用户并查询他们。我们需要定义一个struct来表示新的类型，并定义一个trait来定义其功能：

struct UserDatabase<T> {
    users_updates: u64,
    balances: Felt252Dict<T>,
}

trait UserDatabaseTrait<T> {
    fn new() -> UserDatabase<T>;
    fn update_user<+Drop<T>>(ref self: UserDatabase<T>, name: felt252, balance: T);
    fn get_balance<+Copy<T>>(ref self: UserDatabase<T>, name: felt252) -> T;
}

我们的新类型UserDatabase<T>表示用户数据库。它用泛型表示用户的余额，给使用我们的数据类型的人提���了很大的灵活性。它的两个成员是：

• users_updates, the number of users updates in the dictionary.
• balances, a mapping of each user to its balance.

数据库核心功能由UserDatabaseTrait定义。定义了以下方法：

• new for easily creating new UserDatabase types.
• update_user to update the balance of users in the database.
• get_balance to find user's balance in the database.

The only remaining step is to implement each of the methods in UserDatabaseTrait, but since we are working with Generic types we also need to correctly establish the requirements of T so it can be a valid Felt252Dict<T> value type:

1. T should implement the Copy<T> since it's required for getting values from a Felt252Dict<T>.
2. All value types of a dictionary implement the Felt252DictValue<T>, our generic type should do as well.
3. To insert values, Felt252DictTrait<T> requires all value types to be droppable (implement the Drop<T> trait).

The implementation, with all restrictions in place, would be as follows:

impl UserDatabaseImpl<T, +Felt252DictValue<T>> of UserDatabaseTrait<T> {
    // Creates a database
    fn new() -> UserDatabase<T> {
        UserDatabase { users_updates: 0, balances: Default::default() }
    }

    // Get the user's balance
    fn get_balance<+Copy<T>>(ref self: UserDatabase<T>, name: felt252) -> T {
        self.balances.get(name)
    }

    // Add a user
    fn update_user<+Drop<T>>(ref self: UserDatabase<T>, name: felt252, balance: T) {
        self.balances.insert(name, balance);
        self.users_updates += 1;
    }
}

Our database implementation is almost complete, except for one thing: the compiler doesn't know how to make a UserDatabase<T> go out of scope, since it doesn't implement the Drop<T> trait, nor the Destruct<T> trait. Since it has a Felt252Dict<T> as a member, it cannot be dropped, so we are forced to implement the Destruct<T> trait manually (refer to the Ownership chapter for more information). Using #[derive(Destruct)] on top of the UserDatabase<T> definition won't work because of the use of Generic types in the struct definition. We need to code the Destruct<T> trait implementation by ourselves:

impl UserDatabaseDestruct<T, +Drop<T>, +Felt252DictValue<T>> of Destruct<UserDatabase<T>> {
    fn destruct(self: UserDatabase<T>) nopanic {
        self.balances.squash();
    }
}

为UserDatabase实现Destruct<T>是我们得到一个功能齐全的数据库的最后一步。现在我们可以试试了：

use core::dict::Felt252Dict;

struct UserDatabase<T> {
    users_updates: u64,
    balances: Felt252Dict<T>,
}

trait UserDatabaseTrait<T> {
    fn new() -> UserDatabase<T>;
    fn update_user<+Drop<T>>(ref self: UserDatabase<T>, name: felt252, balance: T);
    fn get_balance<+Copy<T>>(ref self: UserDatabase<T>, name: felt252) -> T;
}

impl UserDatabaseImpl<T, +Felt252DictValue<T>> of UserDatabaseTrait<T> {
    // Creates a database
    fn new() -> UserDatabase<T> {
        UserDatabase { users_updates: 0, balances: Default::default() }
    }

    // Get the user's balance
    fn get_balance<+Copy<T>>(ref self: UserDatabase<T>, name: felt252) -> T {
        self.balances.get(name)
    }

    // Add a user
    fn update_user<+Drop<T>>(ref self: UserDatabase<T>, name: felt252, balance: T) {
        self.balances.insert(name, balance);
        self.users_updates += 1;
    }
}

impl UserDatabaseDestruct<T, +Drop<T>, +Felt252DictValue<T>> of Destruct<UserDatabase<T>> {
    fn destruct(self: UserDatabase<T>) nopanic {
        self.balances.squash();
    }
}

fn main() {
    let mut db = UserDatabaseTrait::<u64>::new();

    db.update_user('Alex', 100);
    db.update_user('Maria', 80);

    db.update_user('Alex', 40);
    db.update_user('Maria', 0);

    let alex_latest_balance = db.get_balance('Alex');
    let maria_latest_balance = db.get_balance('Maria');

    assert!(alex_latest_balance == 40, "Expected 40");
    assert!(maria_latest_balance == 0, "Expected 0");
}

Simulating a Dynamic Array with Dicts

First, let's think about how we want our mutable dynamic array to behave. What operations should it support?

它应该：

• Allow us to append items at the end.
• Let us access any item by index.
• Allow setting the value of an item at a specific index.
• Return the current length.

我们可以在Cairo中定义这个接口，如下所示：

trait MemoryVecTrait<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;
}

This provides a blueprint for the implementation of our dynamic array. We named it MemoryVec as it is similar to the Vec<T> data structure in Rust.

Note: The core library of Cairo already includes a Vec<T> data structure, strictly used as a storage type in smart contracts. To differentiate our data structure from the core library's one, we named our implementation MemoryVec.

Implementing a Dynamic Array in Cairo

To store our data, we'll use a Felt252Dict<T> which maps index numbers (felts) to values. We'll also store a separate len field to track the length.

Here is what our struct looks like. We wrap the type T inside Nullable pointer to allow using any type T in our data structure, as explained in the Dictionaries section:

use core::dict::Felt252Dict;
use core::nullable::NullableTrait;
use core::num::traits::WrappingAdd;

trait MemoryVecTrait<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;
}

struct MemoryVec<T> {
    data: Felt252Dict<Nullable<T>>,
    len: usize,
}

impl DestructMemoryVec<T, +Drop<T>> of Destruct<MemoryVec<T>> {
    fn destruct(self: MemoryVec<T>) nopanic {
        self.data.squash();
    }
}

impl MemoryVecImpl<T, +Drop<T>, +Copy<T>> of MemoryVecTrait<MemoryVec<T>, T> {
    fn new() -> MemoryVec<T> {
        MemoryVec { data: Default::default(), len: 0 }
    }

    fn get(ref self: MemoryVec<T>, index: usize) -> Option<T> {
        if index < self.len() {
            Option::Some(self.data.get(index.into()).deref())
        } else {
            Option::None
        }
    }

    fn at(ref self: MemoryVec<T>, index: usize) -> T {
        assert!(index < self.len(), "Index out of bounds");
        self.data.get(index.into()).deref()
    }

    fn push(ref self: MemoryVec<T>, value: T) -> () {
        self.data.insert(self.len.into(), NullableTrait::new(value));
        self.len.wrapping_add(1_usize);
    }
    fn set(ref self: MemoryVec<T>, index: usize, value: T) {
        assert!(index < self.len(), "Index out of bounds");
        self.data.insert(index.into(), NullableTrait::new(value));
    }
    fn len(self: @MemoryVec<T>) -> usize {
        *self.len
    }
}

Since we again have Felt252Dict<T> as a struct member, we need to implement the Destruct<T> trait to tell the compiler how to make MemoryVec<T> go out of scope.

use core::dict::Felt252Dict;
use core::nullable::NullableTrait;
use core::num::traits::WrappingAdd;

trait MemoryVecTrait<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;
}

struct MemoryVec<T> {
    data: Felt252Dict<Nullable<T>>,
    len: usize,
}

impl DestructMemoryVec<T, +Drop<T>> of Destruct<MemoryVec<T>> {
    fn destruct(self: MemoryVec<T>) nopanic {
        self.data.squash();
    }
}

impl MemoryVecImpl<T, +Drop<T>, +Copy<T>> of MemoryVecTrait<MemoryVec<T>, T> {
    fn new() -> MemoryVec<T> {
        MemoryVec { data: Default::default(), len: 0 }
    }

    fn get(ref self: MemoryVec<T>, index: usize) -> Option<T> {
        if index < self.len() {
            Option::Some(self.data.get(index.into()).deref())
        } else {
            Option::None
        }
    }

    fn at(ref self: MemoryVec<T>, index: usize) -> T {
        assert!(index < self.len(), "Index out of bounds");
        self.data.get(index.into()).deref()
    }

    fn push(ref self: MemoryVec<T>, value: T) -> () {
        self.data.insert(self.len.into(), NullableTrait::new(value));
        self.len.wrapping_add(1_usize);
    }
    fn set(ref self: MemoryVec<T>, index: usize, value: T) {
        assert!(index < self.len(), "Index out of bounds");
        self.data.insert(index.into(), NullableTrait::new(value));
    }
    fn len(self: @MemoryVec<T>) -> usize {
        *self.len
    }
}

The key thing that makes this vector mutable is that we can insert values into the dictionary to set or update values in our data structure. For example, to update a value at a specific index, we do:

use core::dict::Felt252Dict;
use core::nullable::NullableTrait;
use core::num::traits::WrappingAdd;

trait MemoryVecTrait<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;
}

struct MemoryVec<T> {
    data: Felt252Dict<Nullable<T>>,
    len: usize,
}

impl DestructMemoryVec<T, +Drop<T>> of Destruct<MemoryVec<T>> {
    fn destruct(self: MemoryVec<T>) nopanic {
        self.data.squash();
    }
}

impl MemoryVecImpl<T, +Drop<T>, +Copy<T>> of MemoryVecTrait<MemoryVec<T>, T> {
    fn new() -> MemoryVec<T> {
        MemoryVec { data: Default::default(), len: 0 }
    }

    fn get(ref self: MemoryVec<T>, index: usize) -> Option<T> {
        if index < self.len() {
            Option::Some(self.data.get(index.into()).deref())
        } else {
            Option::None
        }
    }

    fn at(ref self: MemoryVec<T>, index: usize) -> T {
        assert!(index < self.len(), "Index out of bounds");
        self.data.get(index.into()).deref()
    }

    fn push(ref self: MemoryVec<T>, value: T) -> () {
        self.data.insert(self.len.into(), NullableTrait::new(value));
        self.len.wrapping_add(1_usize);
    }
    fn set(ref self: MemoryVec<T>, index: usize, value: T) {
        assert!(index < self.len(), "Index out of bounds");
        self.data.insert(index.into(), NullableTrait::new(value));
    }
    fn len(self: @MemoryVec<T>) -> usize {
        *self.len
    }
}

这将覆盖字典中该索引处先前存在的值。

While arrays are immutable, dictionaries provide the flexibility we need for modifiable data structures like vectors.

The implementation of the rest of the interface is straightforward. The implementation of all the methods defined in our interface can be done as follow :

use core::dict::Felt252Dict;
use core::nullable::NullableTrait;
use core::num::traits::WrappingAdd;

trait MemoryVecTrait<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;
}

struct MemoryVec<T> {
    data: Felt252Dict<Nullable<T>>,
    len: usize,
}

impl DestructMemoryVec<T, +Drop<T>> of Destruct<MemoryVec<T>> {
    fn destruct(self: MemoryVec<T>) nopanic {
        self.data.squash();
    }
}

impl MemoryVecImpl<T, +Drop<T>, +Copy<T>> of MemoryVecTrait<MemoryVec<T>, T> {
    fn new() -> MemoryVec<T> {
        MemoryVec { data: Default::default(), len: 0 }
    }

    fn get(ref self: MemoryVec<T>, index: usize) -> Option<T> {
        if index < self.len() {
            Option::Some(self.data.get(index.into()).deref())
        } else {
            Option::None
        }
    }

    fn at(ref self: MemoryVec<T>, index: usize) -> T {
        assert!(index < self.len(), "Index out of bounds");
        self.data.get(index.into()).deref()
    }

    fn push(ref self: MemoryVec<T>, value: T) -> () {
        self.data.insert(self.len.into(), NullableTrait::new(value));
        self.len.wrapping_add(1_usize);
    }
    fn set(ref self: MemoryVec<T>, index: usize, value: T) {
        assert!(index < self.len(), "Index out of bounds");
        self.data.insert(index.into(), NullableTrait::new(value));
    }
    fn len(self: @MemoryVec<T>) -> usize {
        *self.len
    }
}

The full implementation of the MemoryVec structure can be found in the community-maintained library Alexandria.

Simulating a Stack with Dicts

现在，我们将查看第二个示例及其实现细节：堆栈。

A Stack is a LIFO (Last-In, First-Out) collection. The insertion of a new element and removal of an existing element takes place at the same end, represented as the top of the stack.

Let us define what operations we need to create a stack:

• Push an item to the top of the stack.
• Pop an item from the top of the stack.
• Check whether there are still any elements in the stack.

根据这些规则我们可以定义以下接口：

trait StackTrait<S, T> {
    fn push(ref self: S, value: T);
    fn pop(ref self: S) -> Option<T>;
    fn is_empty(self: @S) -> bool;
}

Implementing a Mutable Stack in Cairo

To create a stack data structure in Cairo, we can again use a Felt252Dict<T> to store the values of the stack along with a usize field to keep track of the length of the stack to iterate over it.

堆栈结构定义如下：

struct NullableStack<T> {
    data: Felt252Dict<Nullable<T>>,
    len: usize,
}

接下来，让我们看看我们的主要功能push和pop 是如何实现的。

use core::dict::Felt252Dict;
use core::nullable::{match_nullable, FromNullableResult, NullableTrait};

trait StackTrait<S, T> {
    fn push(ref self: S, value: T);
    fn pop(ref self: S) -> Option<T>;
    fn is_empty(self: @S) -> bool;
}

struct NullableStack<T> {
    data: Felt252Dict<Nullable<T>>,
    len: usize,
}

impl DestructNullableStack<T, +Drop<T>> of Destruct<NullableStack<T>> {
    fn destruct(self: NullableStack<T>) nopanic {
        self.data.squash();
    }
}


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(), NullableTrait::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
    }
}

The code uses the insert and get methods to access the values in the Felt252Dict<T>. To push an element to the top of the stack, the push function inserts the element in the dict at index len and increases the len field of the stack to keep track of the position of the stack top. To remove a value, the pop function decreases the value of len to update the position of the stack top and then retrieves the last value at position len.

The full implementation of the Stack, along with more data structures that you can use in your code, can be found in the community-maintained Alexandria library, in the "data_structures" crate.

Summary

Well done! Now you have knowledge of arrays, dictionaries and even custom data structures. While Cairo's memory model is immutable and can make it difficult to implement mutable data structures, we can fortunately use the Felt252Dict<T> type to simulate mutable data structures. This allows us to implement a wide range of data structures that are useful for many applications, effectively hiding the complexity of the underlying memory model.