引言

本文通过阅读分析table_vec和vec_set实现原理，深入了解它们的构成与使用，为阅读deny_list的实现准备条件

table_vec是对table的进一层封装

结构体

    struct TableVec<phantom Element: store> has store {
        /// The contents of the table vector.
        contents: Table<u64, Element>,
    }

TableVec规定了储存的table键类型必须是u64，而值是拥有store能力的任意一类类型

创建

    /// Create an empty TableVec.
    public fun empty<Element: store>(ctx: &mut TxContext): TableVec<Element> {
        TableVec {
            contents: table::new(ctx)
        }
    }

    /// Return a TableVec of size one containing element `e`.
    public fun singleton<Element: store>(e: Element, ctx: &mut TxContext): TableVec<Element> {
        let t = empty(ctx);
        push_back(&mut t, e);
        t
    }

二者的区别是singleton可以在新建TableVec是插入一个值

插入/删除

    public fun push_back<Element: store>(t: &mut TableVec<Element>, e: Element) {
        let key = length(t);
        table::add(&mut t.contents, key, e);
    }

    public fun pop_back<Element: store>(t: &mut TableVec<Element>): Element {
        let length = length(t);
        assert!(length > 0, EIndexOutOfBound);
        table::remove(&mut t.contents, length - 1)
    }

可以发现TableVec通过数组长度获取索引，作为新插入数据的key
pop_back获取了TableVec的长度作为待删除元素的key，key这就意味着在调用删除元素时需要从数组末尾依次删除

那么我们需要删除中间的元素怎么办呢？
合约提供了这两个函数

    public fun swap<Element: store>(t: &mut TableVec<Element>, i: u64, j: u64) {
        assert!(length(t) > i, EIndexOutOfBound);
        assert!(length(t) > j, EIndexOutOfBound);
        if (i == j) { return };
        let element_i = table::remove(&mut t.contents, i);
        let element_j = table::remove(&mut t.contents, j);
        table::add(&mut t.contents, j, element_i);
        table::add(&mut t.contents, i, element_j);
    }

    /// Swap the `i`th element of the TableVec `t` with the last element and then pop the TableVec.
    /// This is O(1), but does not preserve ordering of elements in the TableVec.
    /// Aborts if `i` is out of bounds.
    public fun swap_remove<Element: store>(t: &mut TableVec<Element>, i: u64): Element {
        assert!(length(t) > i, EIndexOutOfBound);
        let last_idx = length(t) - 1;
        swap(t, i, last_idx);
        pop_back(t)
    }

它可以让TableVec中的两个元素调换位置
swap函数首先检查输入索引i，j是否超出范围,如果i，j不相等，那么就会调用table::remove将对应索引的元素取出,然后调用table::add将两个元素对应的索引交换再次插入，这样实现了两个元素的交换。
swap_remove提供了移除中间值的方法，原理是将待删除的值与最后一个值交换位置，然后再调用pop_back弹出待删除的值

取值

     public fun borrow<Element: store>(t: &TableVec<Element>, i: u64): &Element {
        assert!(length(t) > i, EIndexOutOfBound);
        table::borrow(&t.contents, i)
    }

    /// Add element `e` to the end of the TableVec `t`.
    public fun push_back<Element: store>(t: &mut TableVec<Element>, e: Element) {
        let key = length(t);
        table::add(&mut t.contents, key, e);
    }

删除

    public fun destroy_empty<Element: store>(t: TableVec<Element>) {
        assert!(length(&t) == 0, ETableNonEmpty);
        let TableVec { contents } = t;
        table::destroy_empty(contents);
    }

    public fun drop<Element: drop + store>(t: TableVec<Element>) {
        let TableVec { contents } = t;
        table::drop(contents)
    }

删除TableVec，区别是drop可以删除非空的TableVec

vec_set

vec_set与TableVec有相似之处

结构体

    struct VecSet<K: copy + drop> has copy, drop, store {
        contents: vector<K>,
    }

VecSet可以储存任意一类具有copy drop能力的数据集合

创建

    public fun empty<K: copy + drop>(): VecSet<K> {
        VecSet { contents: vector::empty() }
    }

    public fun singleton<K: copy + drop>(key: K): VecSet<K> {
        VecSet { contents: vector::singleton(key) }
    }

添加/删除

VecSet可以保证集合中不会存在重复的元素
这是因为add在添加元素时会先检查VecSet中是否含有相同的元素

    public fun contains<K: copy + drop>(self: &VecSet<K>, key: &K): bool {
        option::is_some(&get_idx_opt(self, key))
    }

    public fun insert<K: copy + drop>(self: &mut VecSet<K>, key: K) {
        assert!(!contains(self, &key), EKeyAlreadyExists);
        vector::push_back(&mut self.contents, key)
    }

在删除中，会从索引0遍历VecSet数组，直到找到相同的元素返回索引，否则返回none，会报错EKeyDoesNotExist，最后根据索引移除相应元素

    fun get_idx_opt<K: copy + drop>(self: &VecSet<K>, key: &K): Option<u64> {
        let i = 0;
        let n = size(self);
        while (i < n) {
            if (vector::borrow(&self.contents, i) == key) {
                return option::some(i)
            };
            i = i + 1;
        };
        option::none()
    }

    fun get_idx<K: copy + drop>(self: &VecSet<K>, key: &K): u64 {
        let idx_opt = get_idx_opt(self, key);
        assert!(option::is_some(&idx_opt), EKeyDoesNotExist);
        option::destroy_some(idx_opt)
    }

    public fun remove<K: copy + drop>(self: &mut VecSet<K>, key: &K) {
        let idx = get_idx(self, key);
        vector::remove(&mut self.contents, idx);
    }

取值

    public fun keys<K: copy + drop>(self: &VecSet<K>): &vector<K> {
        &self.contents
    }

keys返回其中集合的借用

删除

    public fun into_keys<K: copy + drop>(self: VecSet<K>): vector<K> {
        let VecSet { contents } = self;
        contents
    }

into_keys解包VecSet，返回其中储存的集合

总结

table_vec和vec_set都是对下层结构table和vector的一种使用方式，如果不满足使用需求，可以按需求自行封装使用table，和vector。其中vec_set参与实现了deny_list。希望能对理解如何使用动态集合的有所帮助。 <!--StartFragment-->

Move语言学习交流QQ群: 79489587\ Sui官方中文开发者电报群: <https://t.me/sui_dev_cn>

<!--EndFragment-->