aptos-labs / aptos-core

Aptos is a layer 1 blockchain built to support the widespread use of blockchain through better technology and user experience.
https://aptosfoundation.org
Other
6.15k stars 3.62k forks source link

[Feature Request][Move] Add set (collection) implementation #10145

Open alnoki opened 1 year ago

alnoki commented 1 year ago

@BriungRi @davidiw @movekevin @vgao1996 @wrwg

Presently, the Aptos Framework and Move/Aptos Standard libraries include assorted vector and map collections, but no set implementations. The following implementations are suggested:

For collection size fits in a single storage slot:

For collection size does not fit in a single storage slot:

AVL trees are suggested to optimize for lookup speed, though a red-black tree could be used for optimize insertion/removal time

wrwg commented 1 year ago

For this, we need ordering of arbitrary values T. We have discussed to implement this on native level (a hack), but we are also looking at actually adding traits (compiler v2). Probably we are moving forward with the hack (@lightmark FYI).