0

How to implement a Set in solidity that fulfills the following criteria?

  • Add and remove items
  • Check if an item is present
  • Iterate the Set

2 Answers 2

1

Have a look here and scroll down to Mapped Structs with Delete-enabled Index.

Are there well-solved and simple storage patterns for Solidity?

There are links to explainers and proven, in some-cases audited code.

Hope it helps.

0

Note: Code hasn't yet been tested.

This implementation allows you to iterate the set in arbitrary order (not the order in which the elements were inserted).

The code sample below stores addresses in the set, but some other data types could be stored instead.

contract Set {
  address immutable controller;
  address[] items;
  mapping (address => uint) presence;

  constructor(address controller_) {
    controller = controller_ == address(0) ? msg.sender : controller_;
  }

  function size() public view returns (uint) {
    return items.length;
  }

  function has(address item) public view returns (bool) {
    return presence[item] > 0;
  }

  function indexOf(address item) public view returns (uint) {
    return presence[item] - 1;
  }

  function get(uint index) public view returns (address) {
    return items[index];
  }

  function add(address item) public {
    require(msg.sender == controller, "Sender does not own this set.");
    
    if (presence[item] == 0) {
      items.push(item);
      presence[item] = items.length; // index plus one
    }
  }

  function remove(address item) public {
    require(msg.sender == controller, "Sender does not own this set.");

    if (presence[item] > 0) {
      uint index = presence[item] - 1;
      presence[item] = 0;
      presence[items[items.length - 1]] = index + 1;
      items[index] = items[items.length - 1];
      items.pop();
    }
  }

  function clear() public {
    require(msg.sender == controller, "Sender does not own this set.");

    for (uint i = 0; i < items.length; i++) {
      presence[items[i]] = 0;
    }

    delete items;
  }

  function destroy() public {
    require(msg.sender == controller, "Sender does not own this set.");
    selfdestruct(msg.sender);
  }
}

Iteration of a set:

Set mySet = new Set(this);
// ... add elements to set

for (uint i = 0; i < mySet.size(); i++) {
  address item = mySet.get(i);
  emit Log(item);
}

Removing elements during iteration is not a good idea. Although it shouldn't cause any errors, doing so will result in skipped items. Instead, store an array to mark elements for deletion. Then iterate this array to remove elements afterwards.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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