1

Is there any way or library to have a set in solidity that can be iterated like C++'s std::set?

    library Set {
  // We define a new struct datatype that will be used to
  // hold its data in the calling contract.
  struct Data { mapping(string => bool) flags; }

  // Note that the first parameter is of type "storage
  // reference" and thus only its storage address and not
  // its contents is passed as part of the call.  This is a
  // special feature of library functions.  It is idiomatic
  // to call the first parameter `self`, if the function can
  // be seen as a method of that object.
  function insert(Data storage self, string memory value)
      public
      returns (bool)
  {
      if (self.flags[value])
          return false; // already there
      self.flags[value] = true;
      return true;
  }

  function remove(Data storage self, string memory value)
      public
      returns (bool)
  {
      if (!self.flags[value])
          return false; // not there
      self.flags[value] = false;
      return true;
  }

  function contains(Data storage self, string memory value)
      public
      view
      returns (bool)
  {
      return self.flags[value];
  }
}

This is an implementation I found but this struct can not be iterated

1

The closest thing you can have is using a mapping and an array, a bit like you did.

contract Contract {

    struct Set {
        uint[] values;
        mapping (uint => bool) is_in;
    }

    Set my_set;

    function add(uint a) public {
        if (!my_set.is_in[a]) {
            my_set.values.push(a);
            my_set.is_in[a] = true;
        }
    }
}
  • I agree but it will have terrible cost to iterate when I want to remove an element right? – chatzich Apr 14 at 21:30
  • Yeah, but if you absolutely want a set, you have no other choice. Depending of your application, you could maybe offload some of the computation load off-chain by moving the mapping out on your computer. – Eli Drion Apr 14 at 21:31
  • I shall agree with that – chatzich Apr 14 at 22:08
0

This is very close to what you what you want. It was not modeled after std set but I estimate it could be adapted to match it more precisely.

The iteration concern is addressed by the count and retrieve one by row functions (atIndex). These make it possible and clean to iterate externally, which means all internal ops are O(1) complexity.

https://github.com/rob-Hitchens/UnorderedKeySet

Explainer: https://medium.com/robhitchens/solidity-crud-epilogue-e563e794fde

For background, earlier description of the data organization. https://medium.com/@robhitchens/solidity-crud-part-1-824ffa69509a

Hope it helps.

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.