0
struct Data {
  ...
}

contract Court {
  mapping(address => Data) subcourts;
}

I want to keep track of a small finite set (which can be added or removed) of all keys of this mapping.

What is the better way?

  1. make an array of addresses as a new field of Court;
  2. add a new address field to Data to make a linked list;
  3. add two new address fields to Data to make a doubly linked list.
  • 1
    An array in Solidity is in fact a linked list, in the sense that you can easily add elements dynamically. Very easily to the end of the array, and a little less easily to other places (by swapping with the one at the end). So an array is what you need. BTW, it would be my choice also for a large finite set, and in fact, even if you told me that the set was infinite. It's stored on the blockchain after all. – goodvibration Oct 6 '19 at 16:51
1

Assuming order doesn't matter (implied by "set"), the combination of a mapping and an array can handle set operations in constant time. The trick is to keep track of where in the array each element is and swap elements to the end for deletion. I wrote a blog post about this pattern: https://programtheblockchain.com/posts/2018/06/03/storage-patterns-set/.

Here's the finished code from that post:

pragma solidity ^0.4.24;

contract Set {
    bytes32[] public items;

    // 1-based indexing into the array. 0 represents non-existence.
    mapping(bytes32 => uint256) indexOf;

    function add(bytes32 value) public {
        if (indexOf[value] == 0) {
            items.push(value);
            indexOf[value] = items.length;
        }
    }

    function remove(bytes32 value) public {
        uint256 index = indexOf[value];

        require(index > 0);

        // move the last item into the index being vacated
        bytes32 lastValue = items[items.length - 1];
        items[index - 1] = lastValue;  // adjust for 1-based indexing
        indexOf[lastValue] = index;

        items.length -= 1;
        indexOf[value] = 0;
    }

    function contains(bytes32 value) public view returns (bool) {
        return indexOf[value] > 0;
    }

    function count() public view returns (uint256) {
        return items.length;
    }
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.