Which custom data structures do you use in Solidity?

Hi everyone!

In this thread we want to assess the need for data structure libraries in OpenZeppelin, and to gather ideas for what those libraries could look like.

After seeing many many simple implementation errors that translate to catastrophic failures, we think it may be worth it to pursue this feature, even if language support for it is not where we want it to be yet. We have some ideas regarding which patterns are useful in a blockchain-context, but would like for developers to share their ideas, use-cases, and experience working with these.

As an example, a pattern we’ve successfully used is the swap-and-pop for deletion of array elements (where array order is mutable and unimportant, e.g. unsorted arrays). See the following pseudo implementation:

uint256[] private _array;

function delete(uint256 index) public {
  uint256 _array[index] = _array[_array.length.sub(1)];
  _array.length--;
}

OpenZeppelin’s ERC721Enumerable's code uses this pattern in a more involved way, since a mapping of indexes is also updated, and while the code is somewhat complex, it is very gas efficient. We’d like to make this sort of thing reusable so that everyone can also have correct, inexpensive algorithms in their contracts.

Looking forward to hear everyone’s thoughts!

5 Likes

I’d love to see iterable mappings! In other words, a data structure backed by both a mapping and an array, in that provides immediate access via the mapping, but also enumeration of the keys and values via the array.

6 Likes

Solidity in a nutshell is just a laguage. Developers need pretty much all data structures to address problems in the efficient way. Solidity has only a few data structures built in and does miss a lot of them. In computer science we use Big O notation to estimates time and space complexity of data structure operations. It would epic if someone would make a such table for Solidity data structures with canonical implementations but for the Big O notation of gas usage. Which would give developers clear idea of how expensive certain data structures. Maybe it already exists?

Speaking data structures which we definitely need, I think queue is a good example. It is widely used and I think I even have seen it implemented as a linked list on a blockchain.

3 Likes

@Dennison said:

My 2 cents: stacks, queues, linked lists, balancing trees. :slight_smile:

3 Likes

Some previous discussion around this topic in the repository:

Note that they used a linked list to avoid moving arrays around.

2 Likes