数据结构

数据结构是用于高效访问数据的数据组织、管理和存储格式。更准确地说，数据结构是一组数据值、它们之间的关系以及可应用于数据的函数或操作的集合。

本页列出了一组在 Tact 中实现的数据结构，可满足您日常需求及更多。

所有在此列出的数据结构都是使用内置的 map<K, V> 类型创建的。有关 map 的描述和基本用法，请参阅书中专门的页面。

数组（Array）

数组是由连续的内存块组成的数据结构，表示同一内存大小的元素集合，每个元素由至少一个数组键或索引标识。

以下示例使用包装在结构体中的 map<Int as uint16, Int> 来模拟数组，其中 V 可以是 map 允许的任何值类型：

import "@stdlib/deploy"; // for Deployable trait
 
struct Array {
    map: map<Int as uint16, Int>; // array of Int values as a map of Ints to Ints,
                                  // with serialization of its keys to uint16 to save space
    length: Int = 0;              // length of the array, defaults to 0
}
 
// Compile-time constant upper bound for our map representing an array.
const MaxArraySize: Int = 5_000; // 5,000 entries max, to stay reasonably far from limits
 
// Extension mutation function for adding new entries to the end of the array
extends mutates fun append(self: Array, item: Int) {
    require(self.length + 1 <= MaxArraySize, "No space in the array left for new items!");
 
    self.map.set(self.length, item); // set the entry (key-value pair)
    self.length += 1;                // increase the length field
}
 
// Extension mutation function for inserting new entries at the given index
extends mutates fun insert(self: Array, item: Int, idx: Int) {
    require(self.length + 1 <= MaxArraySize, "No space in the array left for new items!");
    require(idx >= 0, "Index of the item cannot be negative!");
    require(idx < self.length, "Index is out of array bounds!");
 
    // Move all items from idx to the right
    let i: Int = self.length; // not a typo, as we need to start from the non-existing place
    while (i > idx) {
        // Note, that we use !! operator as we know for sure that the value would be there
        self.map.set(i, self.map.get(i - 1)!!);
        i -= 1;
    }
 
    // And put the new item in
    self.map.set(idx, item); // set the entry (key-value pair)
    self.length += 1;        // increase the length field
}
 
// Extension function for getting the value at the given index
extends fun getIdx(self: Array, idx: Int): Int {
    require(self.length > 0, "No items in the array!");
    require(idx >= 0, "Index of the item cannot be negative!");
    require(idx < self.length, "Index is out of array bounds!");
 
    // Note, that we use !! operator as we know for sure that the value would be there
    return self.map.get(idx)!!;
}
 
// Extension function for returning the last value
extends fun getLast(self: Array): Int {
    require(self.length > 0, "No items in the array!");
 
    // Note, that we use !! operator as we know for sure that the value would be there
    return self.map.get(self.length - 1)!!;
}
 
// Extension mutation function for deleting and entry at the given index and returning its value
extends mutates fun deleteIdx(self: Array, idx: Int): Int {
    require(self.length > 0, "No items in the array to delete!");
    require(idx >= 0, "Index of the item cannot be negative!");
    require(idx < self.length, "Index is out of array bounds!");
 
    // Remember the value, which is going to be deleted
    let memorized: Int = self.map.get(idx)!!;
 
    // Move all items from idx and including to the left
    let i: Int = idx;
    while (i + 1 < self.length) {
        // Note, that we use !! operator as we know for sure that the value would be there
        self.map.set(i, self.map.get(i + 1)!!);
        i += 1;
    }
 
    self.map.set(self.length - 1, null); // delete the last entry
    self.length -= 1;                    // decrease the length field
 
    return memorized;
}
 
// Extension mutation function for deleting the last entry and returning its value
extends fun deleteLast(self: Array): Int {
    require(self.length > 0, "No items in the array!");
 
    // Note, that we use !! operator as we know for sure that the value would be there
    let lastItem: Int = self.map.get(self.length - 1)!!;
    self.map.set(self.length - 1, null); // delete the entry
    self.length -= 1;                    // decrease the length field
 
    return lastItem;
}
 
// Extension function for deleting all items in the Array
extends mutates fun deleteAll(self: Array) {
    self.map = emptyMap();
    self.length = 0;
}
 
// Global static function for creating an empty Array
fun emptyArray(): Array {
    return Array{map: emptyMap()}; // length defaults to 0
}
 
// Contract, with emulating an Array using the map
contract MapAsArray with Deployable {
    // Persistent state variables
    array: Array;
 
    // Constructor (initialization) function of the contract
    init() {
        self.array = emptyArray();
    }
 
    // Internal message receiver, which responds to a String message "append"
    receive("append") {
        // Add a new item
        self.array.append(42);
    }
 
    // Internal message receiver, which responds to a String message "delete_5h"
    receive("delete_5th") {
        // Remove the 5th item if it exists and reply back with its value, or raise an error
        self.reply(self.array.deleteIdx(4).toCoinsString().asComment()); // index offset 0 + 4 gives the 5th item
    }
 
    // Internal message receiver, which responds to a String message "del_last"
    receive("del_last") {
        // Remove the last item and reply back with its value, or raise an error
        self.reply(self.array.deleteLast().toCoinsString().asComment());
    }
 
    // Internal message receiver, which responds to a String message "get_last"
    receive("get_last") {
        // Reply back with the latest item in the array if it exists, or raise an error
        self.reply(self.array.getLast().toCoinsString().asComment());
    }
 
    // Internal message receiver, which responds to a String message "delete_all"
    receive("delete_all") {
        self.array.deleteAll();
    }
}

栈（Stack）

栈是由元素组成的数据结构，具有两个主要操作：

• push：将元素添加到集合的末尾
• pop：移除最近添加的元素

以下示例使用包装在结构体中的 map<Int as uint16, Int> 来模拟栈，其中 V 可以是 map 允许的任何值类型：

import "@stdlib/deploy"; // for Deployable trait
 
struct Stack {
    map: map<Int as uint16, Int>; // stack of Int values as a map of Ints to Ints,
                                  // with serialization of its keys to uint16 to save space
    length: Int = 0;              // length of the stack, defaults to 0
}
 
// Compile-time constant upper bound for our map representing an stack.
const MaxStackSize: Int = 5_000; // 5,000 entries max, to stay reasonably far from limits
 
// Extension mutation function for adding new entries to the end of the stack
extends mutates fun push(self: Stack, item: Int) {
    require(self.length + 1 <= MaxStackSize, "No space in the stack left for new items!");
 
    self.map.set(self.length, item); // set the entry (key-value pair)
    self.length += 1;                // increase the length field
}
 
// Extension mutation function for deleting the last entry and returning its value
extends mutates fun pop(self: Stack): Int {
    require(self.length > 0, "No items in the stack to delete!");
 
    // Note, that we use !! operator as we know for sure that the value would be there
    let lastItem: Int = self.map.get(self.length - 1)!!;
    self.map.set(self.length - 1, null); // delete the entry
    self.length -= 1;                    // decrease the length field
 
    return lastItem;
}
 
// Extension function for returning the last value
extends fun peek(self: Stack): Int {
    require(self.length > 0, "No items in the stack!");
 
    // Note, that we use !! operator as we know for sure that the value would be there
    return self.map.get(self.length - 1)!!;
}
 
// Extension function for deleting all items in the Stack
extends mutates fun deleteAll(self: Stack) {
    self.map = emptyMap();
    self.length = 0;
}
 
// Global static function for creating an empty Stack
fun emptyStack(): Stack {
    return Stack{map: emptyMap()}; // length defaults to 0
}
 
contract MapAsStack with Deployable {
    // Persistent state variables
    stack: Stack; // our stack, which uses the map
 
    // Constructor (initialization) function of the contract
    init() {
        self.stack = emptyStack();
    }
 
    // Internal message receiver, which responds to a String message "push"
    receive("push") {
        // Add a new item
        self.stack.push(42);
    }
 
    // Internal message receiver, which responds to a String message "pop"
    receive("pop") {
        // Remove the last item and reply with it
        self.reply(self.stack.pop().toCoinsString().asComment());
    }
 
    // Internal message receiver, which responds to a String message "peek"
    receive("peek") {
        // Reply back with the latest item in the map if it exists, or raise an error
        self.reply(self.stack.peek().toCoinsString().asComment());
    }
 
    // Internal message receiver, which responds to a String message "delete_all"
    receive("delete_all") {
        self.stack.deleteAll();
    }
 
    // Getter function for obtaining the stack
    get fun map(): map<Int, Int> {
        return self.stack.map;
    }
 
    // Getter function for obtaining the current length of the stack
    get fun length(): Int {
        return self.stack.length;
    }
}

循环缓冲区（Circular Buffer）

循环缓冲区（也称为循环队列或环形缓冲区）是一种数据结构，它使用单个固定大小的缓冲区，就像它们端对端连接一样。

以下示例使用包装在结构体中的 map<Int as uint8, Int> 来模拟循环缓冲区，其中 V 可以是 map 允许的任何值类型：

import "@stdlib/deploy"; // for Deployable trait
 
struct CircularBuffer {
    map: map<Int as uint8, Int>; // circular buffer of Int values as a map of Ints to Ints,
                                 // with serialization of its keys to uint8 to save space
    length: Int = 0;             // length of the circular buffer, defaults to 0
    start: Int = 0;              // current index into the circular buffer, defaults to 0
}
 
// Compile-time constant upper bound for our map representing a circular buffer.
const MaxCircularBufferSize: Int = 5;
 
// Extension mutation function for putting new items to the circular buffer
extends mutates fun put(self: CircularBuffer, item: Int) {
    if (self.length < MaxCircularBufferSize) {
        self.map.set(self.length, item); // store the item
        self.length += 1;                // increase the length field
    } else {
        self.map.set(self.start, item);                        // store the item, overriding previous entry
        self.start = (self.start + 1) % MaxCircularBufferSize; // update starting position
    }
}
 
// Extension mutation function for getting an item from the circular buffer
extends mutates fun getIdx(self: CircularBuffer, idx: Int): Int {
    require(self.length > 0, "No items in the circular buffer!");
    require(idx >= 0, "Index of the item cannot be negative!");
 
    if (self.length < MaxCircularBufferSize) {
        // Note, that we use !! operator as we know for sure that the value would be there
        return self.map.get(idx % self.length)!!;
    }
 
    // Return the value rotating around the circular buffer, also guaranteed to be there
    return self.map.get((self.start + idx) % MaxCircularBufferSize)!!;
}
 
// Extension function for iterating over all items in the circular buffer and dumping them to the console
extends fun printAll(self: CircularBuffer) {
    let i: Int = self.start;
    repeat (self.length) {
        dump(self.map.get(i)!!); // !! tells the compiler this can't be null
        i = (i + 1) % MaxCircularBufferSize;
    }
}
 
// Extension function for deleting all items in the CircularBuffer
extends mutates fun deleteAll(self: CircularBuffer) {
    self.map = emptyMap();
    self.length = 0;
    self.start = 0;
}
 
// Global static function for creating an empty CircularBuffer
fun emptyCircularBuffer(): CircularBuffer {
    return CircularBuffer{map: emptyMap()}; // length and start default to 0
}
 
// This contract records the last 5 timestamps of when "timer" message was received
contract MapAsCircularBuffer with Deployable {
    // Persistent state variables
    cBuf: CircularBuffer; // our circular buffer, which uses a map
 
    // Constructor (initialization) function of the contract
    init() {
        self.cBuf = emptyCircularBuffer();
    }
 
    // Internal message receiver, which responds to a String message "timer"
    // and records the timestamp when it receives such message
    receive("timer") {
        let timestamp: Int = now();
        self.cBuf.put(timestamp);
    }
 
    // Internal message receiver, which responds to a String message "get_first"
    // and replies with the first item of the circular buffer
    receive("get_first") {
        self.reply(self.cBuf.getIdx(0).toCoinsString().asComment());
    }
 
    // Internal message receiver, which responds to a String message "print_all"
    receive("print_all") {
        self.cBuf.printAll();
    }
 
    // Internal message receiver, which responds to a String message "delete_all"
    receive("delete_all") {
        self.cBuf.deleteAll();
    }
}

这个示例是从 Tact-By-Example 中的数组页面调整而来。