The Cairo Programming Language

字典

Cairo在其核心库中提供了一个类似字典的类型。Felt252Dict<T> 数据类型表示键值对的集合，其中每个键都是唯一的，并与相应的值相关联。这种类型的数据结构在不同的编程语言中有不同的名称，如映射、哈希表、关联数组等。

Felt252Dict<T> 类型在你想以某种方式组织数据而使用Array<T>和索引不能满足要求时非常有用。Cairo字典还允许程序员在内存非可变的情况下轻松地模拟可变内存。

字典的基本用法

在其他语言中, 当创建一个新的字典时, 通常需要定义键和值的数据类型。在Cairo中，键类型被限制为felt252，你只能指定值数据的类型，这在Felt252Dict<T>中用T表示。

Felt252Dict<T>的核心功能在trait Felt252DictTrait中实现，它包括所有的基本操作。在其中我们可以看到：

1. insert(felt252, T) -> ()向字典实例写入值，以及
2. get(felt252) -> T 从字典中读取值。

这些函数允许我们使用其他语言一样的方法来操作字典。在下面的示例中，我们创建一个字典来表示个体及其余额之间的映射：

fn main() {
    let mut balances: Felt252Dict<u64> = Default::default();

    balances.insert('Alex', 100);
    balances.insert('Maria', 200);

    let alex_balance = balances.get('Alex');
    assert(alex_balance == 100, 'Balance is not 100');

    let maria_balance = balances.get('Maria');
    assert(maria_balance == 200, 'Balance is not 200');
}

我们做的第一件事是导入Felt252DictTrait，它将我们需要与字典交互的所有方法导入到作用域。接下来，我们使用Defaulttrait的default方法创建一个新的Felt252Dict<u64>实例，并使用insert方法添加两个个体，每个个体都有自己的余额。最后，我们使用get方法检查了用户的余额。

在整本书中，我们都在说Cairo的内存是不可变的，这意味着你只能向一个内存单元写入一次，但是 Felt252Dict<T> 类型代表了一种克服这一障碍的方法。我们将在后面的深入Cairo的字典中解释如何实现。

在前面示例的基础上，让我们展示一个同一用户的余额产生变化的代码示例：

fn main() {
    let mut balances: Felt252Dict<u64> = Default::default();

    // Insert Alex with 100 balance
    balances.insert('Alex', 100);
    // Check that Alex has indeed 100 associated with him
    let alex_balance = balances.get('Alex');
    assert(alex_balance == 100, 'Alex balance is not 100');

    // Insert Alex again, this time with 200 balance
    balances.insert('Alex', 200);
    // Check the new balance is correct
    let alex_balance_2 = balances.get('Alex');
    assert(alex_balance_2 == 200, 'Alex balance is not 200');
}

注意在这个示例中，我们是添加 Alex 这个个体两次，每次都使用了不同的余额，并且每次我们检查它的余额时，它都显示出了最新的值！Felt252Dict<T>使得我们可以 "重写 "任何给定的键中所存储值。

在继续解释字典是如何实现的之前，值得一提的是，一旦你实例化了一个 Felt252Dict<T>，其所有的键值都将被初始化为0。这意味着，例如，如果你试图获取一个不存在的用户的余额，你将得到0，而不是一个错误或未定义的值。这也意味着无法从字典中删除数据。在代码中使用这歌结构纳时你需要考虑到这一点。

到此为止，我们已经了解了 Felt252Dict<T> 的所有基本特性，以及它是如何在外部表现上模仿其他语言中相应数据结构的。Cairo的核心是一种非确定的图灵完备的编程语言，与其他任何流行的语言都有很大的不同，这意味着字典的实现也有很大的不同！

在下面的章节中，我们将深入介绍 Felt252Dict<T> 的内部机制以及为使其正常工作而做出的妥协。之后，我们将介绍如何将字典与其他数据结构一起使用，以及使用entry方法作为与字典交互的另一种方式。

深入Cairo的字典

Cairo的非确定性设计的限制之一是它的内存系统是不可变的，因此为了模拟可变性，语言将Felt252Dict<T>实现为一个条目(entry)列表。每个条目代表了字典被读取/更新/写入的时间。一个条目有三个字段：

1.一个 key字段，用于标识字典中键值对的值。 2.一个previous_value字段，表示key所拥有的前一个值。 3.一个new_value字段，用于指明key所拥有的新值。

如果我们尝试使用高级结构来实现 Felt252Dict<T>，我们将在内部把它定义为 Array<Entry<T>> 其中每个 Entry<T> 都有关于它代表的键值对的信息，以及它持有的前一个值和新值。Entry<T> 的定义如下：

struct Entry<T> {
    key: felt252,
    previous_value: T,
    new_value: T,
}

每次我们与Felt252Dict<T>交互时，都会产生一个新的Entry<T>并注册：

• get 将注册一个状态没有发生变化的条目，以前的值和新值以相同的值存储。
• 一个insert将注册一个新的Entry<T>，其中new_value是被插入的元素，previous_value是在此之前插入的最后一个元素。如果这是某个键的第一个条目，那么之前的值将为0。

条目列表的使用展示了这里没有任何值的覆盖，只是在每次Felt252Dict<T>交互中创建新的存储单元。让我们使用上一节中的 balances 字典并插入用户 'Alex' 和 'Maria' 来展示一个例子：

struct Entry<T> {
    key: felt252,
    previous_value: T,
    new_value: T,
}

fn main() {
    let mut balances: Felt252Dict<u64> = Default::default();
    balances.insert('Alex', 100_u64);
    balances.insert('Maria', 50_u64);
    balances.insert('Alex', 200_u64);
    balances.get('Maria');
}

这些指令将产生以下条目列表：

注意，由于'Alex'被插入了两次，所以它出现了两次，并且'previous'和'current'值被正确的设置。从'Maria'中读取的数据也是一个条目，从前值到现值没有发生变化。

这种实现 Felt252Dict<T> 的方法意味着每一次读/写操作，都要扫描整个条目列表，寻找最后一个具有相同 key的条目。一旦条目被找到，它的new_value就会被提取出来，并作为previous_value添加到新的条目中。这意味着与 Felt252Dict<T> 交互的最坏情况下的时间复杂度为 O(n)，其中 n 是列表中的条目数。

如果你花点心思，你肯定会找到其他实现Felt252Dict<T>的方法，其中一些方法甚至可能完全抛弃对previous_value字段的需求，然而，由于Cairo不是普通的编程语言，这是不可行的。 Cairo的目的之一是通过STARK证明系统来生成计算完整性的证明。这意味着你需要验证程序的执行是否正确，是否在Cairo的限制范围内。其中一个边界检查包括 "字典压缩"，这需要每个条目的前值和新值的信息。

字典压缩

为了验证使用Felt252Dict<T>的Cairo程序执行所生成的证明是否正确，我们需要检查字典是否被非法篡改。这是通过一个名为squash_dict的方法来完成的，这个方法会审查条目列表中的每一个条目，并检查字典的访问在整个执行过程中是否保持一致。

压缩过程如下：给定所有具有特定键k的条目，按照它们被插入的相同顺序，验证第i个条目new_value是否等于第i+1个条目previous_value。

例如，给定以下条目列表：

压缩后，条目列表将缩减为：

如果第一张表中的任何值发生变化，则在运行期间压缩将会失败。

字典的析构

如果你运行字典的基本用法中的示例，你会发现那些例子从来没有调用过字典压缩，但程序还是编译成功了。这是因为在背后，squash通过Destruct<T> trait的Felt252Dict<T>实现了被自动调用。这个调用发生在balance字典离开作用域之前。

除 Drop<T> 之外，Destruct<T> trait代表了另一种将实例移出作用域的方法。这两者之间的主要区别在于 Drop<T> 被视为一个 no-op 操作，这意味着它不会产生新的 CASM，而 Destruct<T> 没有这个限制。唯一主动使用Destruct<T>特性的类型是Felt252Dict<T>，对于其他类型Destruct<T>和Drop<T>是同义词。你可以在[Drop and Destruct](/appendix-03-derivable-traits.md#drop and-destruct)中阅读更多关于这些trait的信息。

在 Dictionaries as Struct Members后面，我们将有一个实践示例，我们将为自定义类型实现 Destruct<T> trait。

更多字典范例

到此为止，我们已经全面地介绍了Felt252Dict<T>的功能，以及它是如何和为什么以某种方式实现的。如果您还没有完全理解，请不要担心，因为在本节中我们将提供更多使用字典的示例。

我们将首先解释entry方法，它是Felt252DictTrait<T>中包含的字典基本功能的一部分，我们在开始时没有提到。很快，我们将看到Felt252Dict<T>如何与其他复杂类型如Array<T>交互的例子，以及如何实现一个以字典为成员的结构体。

条目(Entry)和最终确定(Finalize)

在 Dictionaries Underneath 部分，我们解释了 Felt252Dict<T> 内部是如何工作的。它是每次以任何方式访问字典时的条目列表。它会首先找到给定key的最后一个条目，然后根据执行的操作更新它。Cairo语言通过entry和finalize方法为我们提供了复制这种方式的工具。

entry 方法作为Felt252DictTrait<T> 的一部分，目的是在给定键的情况下创建一个新的条目。一旦被调用，该方法将获得字典的所有权并返回要更新的条目。方法签名如下:

fn entry(self: Felt252Dict<T>, key: felt252) -> (Felt252DictEntry<T>, T) nopanic

第一个输入参数获得字典的所有权，第二个参数用于创建相应的条目。它返回一个元组，包含一个Felt252DictEntry<T>，这是Cairo用来表示字典条目的类型，和一个T，代表之前持有的值。

接下来要做的是用新值更新条目。为此，我们使用finalize方法插入条目并返回字典的所有权：

fn finalize(self: Felt252DictEntry<T>, new_value: T) -> Felt252Dict<T> {

该方法接收条目和新值作为参数，并返回更新后的字典。

让我们看一个使用entry和finalize的例子。想象一下，我们想从字典中实现我们自己版本的get方法。我们应该这样做：

1.使用entry方法创建要添加的新条目 2.插入new_value等于previous_value的条目。 3.返回值。

实现我们的自定义get将如下所示：

use dict::Felt252DictEntryTrait;

fn custom_get<T, +Felt252DictValue<T>, +Drop<T>, +Copy<T>>(
    ref dict: Felt252Dict<T>, key: felt252
) -> T {
    // Get the new entry and the previous value held at `key`
    let (entry, prev_value) = dict.entry(key);

    // Store the value to return
    let return_value = prev_value;

    // Update the entry with `prev_value` and get back ownership of the dictionary
    dict = entry.finalize(prev_value);

    // Return the read value
    return_value
}

实现insert方法将遵循类似的工作流程，除了在最终确定时插入一个新值。如果我们要实现它，它将看起来像下面这样：

use dict::Felt252DictEntryTrait;

fn custom_insert<T, +Felt252DictValue<T>, +Destruct<T>, +PrintTrait<T>, +Drop<T>>(
    ref dict: Felt252Dict<T>, key: felt252, value: T
) {
    // Get the last entry associated with `key`
    // Notice that if `key` does not exists, _prev_value will
    // be the default value of T.
    let (entry, _prev_value) = dict.entry(key);

    // Insert `entry` back in the dictionary with the updated value,
    // and receive ownership of the dictionary
    dict = entry.finalize(value);
}

最后要说明的是，这两个方法的实现方式类似于Felt252Dict<T>的insert和get的实现方式。这段代码展示了一些使用示例：

use dict::Felt252DictEntryTrait;

use debug::PrintTrait;

fn custom_get<T, +Felt252DictValue<T>, +Drop<T>, +Copy<T>>(
    ref dict: Felt252Dict<T>, key: felt252
) -> T {
    // Get the new entry and the previous value held at `key`
    let (entry, prev_value) = dict.entry(key);

    // Store the value to return
    let return_value = prev_value;

    // Update the entry with `prev_value` and get back ownership of the dictionary
    dict = entry.finalize(prev_value);

    // Return the read value
    return_value
}

fn custom_insert<T, +Felt252DictValue<T>, +Destruct<T>, +PrintTrait<T>, +Drop<T>>(
    ref dict: Felt252Dict<T>, key: felt252, value: T
) {
    // Get the last entry associated with `key`
    // Notice that if `key` does not exists, _prev_value will
    // be the default value of T.
    let (entry, _prev_value) = dict.entry(key);

    // Insert `entry` back in the dictionary with the updated value,
    // and receive ownership of the dictionary
    dict = entry.finalize(value);
}

fn main() {
    let mut dict: Felt252Dict<u64> = Default::default();

    custom_insert(ref dict, '0', 100);

    let val = custom_get(ref dict, '0');

    assert(val == 100, 'Expecting 100');
}

非远胜支持类型的字典

Felt252Dict<T>的一个限制我们还没有讨论过，那就是 Felt252DictValue<T> trait。 该trait定义了 zero_default 方法，当字典中不存在某个值时，就会调用该方法。 一些常见的数据类型（如大多数无符号整数、bool 和 felt252）实现了该方法，但更复杂的数据类型，如数组、结构体（包括 u256）和核心库中的其他类型，则没有实现该方法。 这就意味着，将不受原生支持的类型封装成字典并不是一件简单的事情，因为您需要编写一些trait的实现，才能使这些数据类型成为有效的字典值类型。 为了弥补这一不足，您可以将您的类型封装在 Nullable<T>中。

Nullable<T> 是一种智能指针类型，既可以指向一个值，也可以在没有值的情况下为 null。当引用不指向任何地方时，它通常用于面向对象编程语言。与 Option 不同的是，封装的值存储在 Box<T> 数据类型中。受 Rust 的启发，Box<T> 类型允许我们为我们的类型分配一个新的内存段，并使用一个指针访问该内存段，该指针一次只能在一个地方操作。

让我们来举例说明。我们将尝试在字典中存储一个Span<felt252>。为此，我们将使用 Nullable<T> 和 Box<T>。另外，我们要存储的是一个 Span<T> 而不是一个 Array<T> ，因为后者没有实现 Copy<T> 特性，而从字典中读取数据是需要这个特性的。

use dict::Felt252DictTrait;
use nullable::{nullable_from_box, match_nullable, FromNullableResult};

fn main() {
    // Create the dictionary
    let mut d: Felt252Dict<Nullable<Span<felt252>>> = Default::default();

    // Crate the array to insert
    let mut a = ArrayTrait::new();
    a.append(8);
    a.append(9);
    a.append(10);

    // Insert it as a `Span`
    d.insert(0, nullable_from_box(BoxTrait::new(a.span())));

//...

在这段代码中，我们首先创建了一个新的字典d。我们希望它保存一个Nullable<Span>。然后，我们创建了一个数组，并在其中填入值。

最后一步是在字典中插入数组。请注意，我们并没有直接这样做，而是在中间采取了一些步骤：

1.我们使用BoxTrait中的new方法将数组封装在Box中。 2.我们使用nullable_from_box函数将Box封装在nullable中。 3.最后，我们插入了上面的结果。

一旦元素存在字典中，并且我们想获取它，我们将遵循相同的步骤，但顺序相反。下面的代码展示了如何实现这一点：

//...

    // Get value back
    let val = d.get(0);

    // Search the value and assert it is not null
    let span = match match_nullable(val) {
        FromNullableResult::Null(()) => panic_with_felt252('No value found'),
        FromNullableResult::NotNull(val) => val.unbox(),
    };

    // Verify we are having the right values
    assert(*span.at(0) == 8, 'Expecting 8');
    assert(*span.at(1) == 9, 'Expecting 9');
    assert(*span.at(2) == 10, 'Expecting 10');
}

我们在这里：

1.使用get读取值。 2.使用match_nullable函数验证其为非空值。 3.解压缩Box内的值，并断言它是正确的。

完整的脚本如下：

use dict::Felt252DictTrait;
use nullable::{nullable_from_box, match_nullable, FromNullableResult};

fn main() {
    // Create the dictionary
    let mut d: Felt252Dict<Nullable<Span<felt252>>> = Default::default();

    // Crate the array to insert
    let mut a = ArrayTrait::new();
    a.append(8);
    a.append(9);
    a.append(10);

    // Insert it as a `Span`
    d.insert(0, nullable_from_box(BoxTrait::new(a.span())));

    // Get value back
    let val = d.get(0);

    // Search the value and assert it is not null
    let span = match match_nullable(val) {
        FromNullableResult::Null(()) => panic_with_felt252('No value found'),
        FromNullableResult::NotNull(val) => val.unbox(),
    };

    // Verify we are having the right values
    assert(*span.at(0) == 8, 'Expecting 8');
    assert(*span.at(1) == 9, 'Expecting 9');
    assert(*span.at(2) == 10, 'Expecting 10');
}

作为结构体成员的字典

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

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

trait UserDatabaseTrait<T> {
    fn new() -> UserDatabase<T>;
    fn add_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_amount，当前插入的用户数量。
• balances，每个用户与其余额的映射。

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

• new用于方便创建新的UserDatabase类型。
• add_user用于在数据库中插入用户。
• get_balance用于在数据库中查找用户的余额。

剩下的步骤就是实现UserDatabaseTrait中的每一个方法，但是由于我们使用的是泛型，我们还需要正确地建立T的要求，这样它才能成为一个有效的Felt252Dict<T>值类型：

1.T 应该实现 Copy<T>，因为从 Felt252Dict<T> 获取值需要它。 2.所有字典的值类型都实现了 Felt252DictValue<T>，我们的泛型也应该实现。 3.为了插入值，Felt252DictTrait<T>要求所有的值类型都是可析构的。

在所有限制条件均已实现的情况下，执行情况如下：

impl UserDatabaseImpl<T, +Felt252DictValue<T>> of UserDatabaseTrait<T> {
    // Creates a database
    fn new() -> UserDatabase<T> {
        UserDatabase { users_amount: 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 add_user<+Drop<T>>(ref self: UserDatabase<T>, name: felt252, balance: T) {
        self.balances.insert(name, balance);
        self.users_amount += 1;
    }
}

我们的数据库实现几乎已经完成，除了一点：编译器不知道如何让 UserDatabase<T> 脱离作用域，因为它没有实现 Drop<T> 特性，也没有实现 Destruct<T> 特性。 由于它有一个 Felt252Dict<T> 作为成员，它不能被丢弃，所以我们不得不手动实现 Destruct<T> 特性（更多信息请参阅 所有权 章节）。 在 UserDatabase<T> 定义之上使用 #[derive(Destruct)]是行不通的，因为在 struct 定义中使用了 泛型 。我们需要自己编写实现 Destruct<T> trait的代码：

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

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

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

trait UserDatabaseTrait<T> {
    fn new() -> UserDatabase<T>;
    fn add_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_amount: 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 add_user<+Drop<T>>(ref self: UserDatabase<T>, name: felt252, balance: T) {
        self.balances.insert(name, balance);
        self.users_amount += 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::new();

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

    db.add_user('Alex', 40);
    db.add_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');
}

总结

干得好！你已经完成了Cairo中关于数组和字典的章节。要掌握这些数据结构可能有点难度，但它们确实非常有用。

当你准备好继续前进时，我们将讨论一个Cairo与Rust共有，而在其他编程语言中通常 不存在 的概念：所有权。